[MicroC/OS-II] CPU Scheduling with Non-Preemptive

  [MicroC/OS-II] Task에 관련된 함수들에서 Task에 관한 함수들을 살펴볼 때 CPU Scheduling을 멈춘다, 시작한다 라는 언급을 했었습니다. 이번엔 그 CPU Scheduling에 대해서 알아보겠습니다.

CPU Scheduling

  CPU Scheduling은 말 그대로 Process를 실행하는데 있어 Scheduling을 하는 것입니다. 다음의 그림을 보겠습니다.

  Process가 여러개 있을때 CPU는 어느 Process를 Running 해야 할까요?? 이런 문제의 답을 CPU Scheduling 이라합니다. CPU Scheduling의 형태에는 2가지의 형태가 있습니다. 그 중 하나인 Non-Preemptive에 대해서 살펴보겠습니다.

1. Non-Preemptive (비 선점방식)

Non-Preemption은 한 Process를 실행 중일때 다른 Process가 CPU를 사용할 수 없습니다. 여러가지 예가 있지만 2가지를 보겠습니다.

ㄱ) FCFS(Frist Come First Serve)

  FCFS방식은 순서대로 실행이 되는것입니다. 예를들어 Process와 그 Process를 실행할 시간이 다음과 같습니다.

  FCFS는 Process의 순서인 1,2,3에 따라서 실행이 되어 집니다. 따라서 다음과 같은 결과를 얻을 수 있습니다.

  이러한 결과를 가지고 평균 응답 시간을 구해보겠습니다. (24 + 27 + 30)/3 = 27가 됩니다. 아주 긴 시간이죠 따라서 FCFS는 짧은 응답시간을 가진 Process에게는 이득이 없습니다. 다음으로 SJF에 대해서 살펴보겠습니다.

ㄴ) SJF(Shortest Job First)

  SJF방식은 짧은 Process부터 실행시키는 방식입니다. 위와 마찬가지로 Process와 각 실행시간이 주어졌다고 보면 다음과 같은 결과를 얻을 수 있습니다.

  이 때 짧은 것부터 실행시키므로 P2와 P3는 시간이 같으므로 서로 바뀌어도 됩니다. 이제 평균 응답 시간을 구해보겠습니다. (3 + 6 + 30)/3 = 13 이 됩니다. 바로 위에서 했던 FCFS 보다 절반 정도 시간이 단축된 것을 보실 수 있습니다. 이 SJF는 Non-Preemptive 방식에서는 최선의 방식이라고 할 수 있습니다. 하지만 단점도 존재하기 마련입니다. 무기한의 Starvation(굶주림)에 들어갈 수 있다는 것입니다. Non-Preemption 방식은 CPU를 뺏을 수 없기 때문에 앞선 CPU가 엄청 많거나 엄청 긴 시간을 요구하면 뒤의 CPU는 자기 시간이 올 때 까지 대기만 하고 있어야하는 indefinite starvation 상태에 도달할 수 있습니다. 이러한 문제를 해결하기 위해서 Preemption을 이용한 방식이 나오게 되었습니다.

2. Preemptive (선점방식)

[MicroC/OS-II] CPU Scheduling with Preemptive에서 더 자세히 보실 수 있습니다.