『OSC Ch 5. Process Scheduling』

• 어떤 프로세스를 프로세서에 할당할 것인가 정하는 프로세스 스케줄링(Process scheduling)에 대해 다룬다.
• FCFS, SJF, RR 등 다양한 프로세스 스케줄링에 대해 소개한다.

Scheduling Criteria

• 디스패치(Dispatch):
  • 운영체제가 프로세스를 프로세서에 할당하는 것.
  • 이때 프로세스 상태가 ready에서 running으로 바뀐다.
• 프로세스 스케줄링(Process scheduling):
  • 운영체제가 레디 큐(Ready queue)에 있는 프로세스들 중에서 어떤 프로세스를 디스패치할 것인가 정하는 것.
• 알고리즘을 평가할 때 기준:
  • Burst time: 수행 시간
  • CPU utilization: CPU 사용량
  • Throughput: 단위 시간 당 끝마친 프로세스의 수
  • Turnaround time: 하나의 프로세스가 레디 큐에서 대기한 시간부터 작업을 마칠 때까지 걸리는 시간
  • Waiting time: 프로세스가 레디 큐에서 대기한 시간
  • Response time: 프로세스가 처음으로 CPU를 할당받기까지 걸린 시간
• 선점(Preemptive) 방식과 비선점(Non-Preemptive) 방식으로 나뉜다:
  • 선점 스케줄링:
    • 운영체제가 강제로 프로세스의 사용권을 통제하는 방식.
    • CPU에 프로세스가 할당되어 있을 때도 운영체제가 개입해 다른 프로세스에게 CPU를 할당할 수 있다.
  • 비선점 스케줄링: 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식.

FCFS (First-Come, First-Served)

• 먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식이다.
• Queue의 FIFO(First-In First-Out)와 동일하다.
• 구현이 쉬워서 간단한 시스템에 자주 사용된다.
• 프로세스 처리 순서에 따라 성능이 크게 달라질 수 있다.
• 수행 시간이 큰 프로세스가 먼저 들어오면 그 뒤에 들어온 프로세스들이 불필요하게 오랜 시간을 기다리게 되는 콘보이 효과(Convoy effect)가 발생한다.
• 먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

+----+----+----+----+----+----+----+----+----+----+----+
|                     P1                     | P2 | P3 |
+----+----+----+----+----+----+----+----+----+----+----+
0                                            9    10   11

SJF (Shortest Job First)

• 프로세스의 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
• FCFS에서 발생하는 콘보이 효과를 해결할 수 있다.
• 최적 알고리즘이지만 수행 시간을 정확히 알 수 없다:
  • 앞서 처리한 프로세스들의 기록을 보고 추측한다.
• 버스트 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(Starvation)가 발생한다.
• 버스트 시간이 짧은 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점 스케줄링 방식이다.

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P4      |              P1             |                P3                |                   P2                  |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3                             9                                  16                                      24

SRF (Shortest Remaining Time First)

• 프로세스의 남은 수행 시간이 짧은 순서에 따라 프로세서에 할당한다.
• SJF에서 발생하는 기아 문제를 해결할 수 있다.
• 수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꾸는 선점 스케줄링 방식이다.

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| P1 |         P2        |           P4           |                P1                |                     P3                     |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1                   5                        10                                 17                                           26

RR (Round Robin)

• 일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
• 시스템의 time-sharing과 같은 방식이다.
• 반응성이 좋다.
• 주로 우선순위 스케줄링(Priority scheduling)과 결합해 프로세스의 시간 할당량을 조절하는 방식으로 활용한다.
• 시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.

Time quantum = 3ms

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|      P1      |    P2   |    P3   |      P1      |      P1      |      P1      |      P1      |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0              3         5         7              10             13             16             19

Priority Scheduling

• 특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.
• 프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다.
• SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.
• 다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.

+----+----+----+----+----+----+----+----+----+----+----+----+
| P2 |      P5      |           P1           |    P3   | P4 |
+----+----+----+----+----+----+----+----+----+----+----+----+
0    1              4                        9         11   12

이 문서를 인용한 문서

• 『Operating System Concepts(OSC)』

  • Chapter 5. Process Scheduling