5. CPU Scheduling

이전까지 프로세스와 쓰레드에 대해 공부해 보았고 시간이 지남에 따라 단일 프로세스 / 쓰레드 환경 → 다중 프로세스/쓰레드 환경으로 변화해왔다는 사실까지 알 수 있었다.

이러한 다중 프로세스 환경에서는 자연스럽게 어느 프로세스가 CPU를 점유할 것인지에 대한 고민이 생겨났으며 보다 효율적으로 CPU에 프로세스를 스케쥴링할 수 있는 방법에 대한 고민이 늘어갔다. 이번 정리에서는 효율적으로 CPU에 프로세스를 할당할 수 있는 여러 CPU Scheduling 방법에 대해 정리해 보았다.

1. 기본 개념

1.1 CPU scheduling

• Multi-Programming(memory에 여러 프로세스를 올려놓고 시분할하여 cpu를 점유하는 것) OS의 기본이라고 할 수 있다.
• 따라서 OS 설계의 핵심이라고 볼 수 있다.

1.2. CPU & I/O burst cycle

• 프로세스의 실행은 CPU 실행 + I/O 대기의 사이클로 구성되며 프로세스는 이 두 상태 중 하나의 상태이다.

• 프로세스 실행의 모식도

  • CPU burst 시의 process 상태는 running으로 볼 수 있다.

  • I/O burst 시의 process는 waiting으로 변했다가 I/O 작업이 끝나면 ready로 변한다.

  • Process 상태 천이도 참고

1.3. CPU Scheduler

• CPU가 idle 상태가 될 때마다, OS는 ready Queue에 있는 프로세스 중에서 하나를 선택해 실행하게 되는데 이러한 선택 절차를 CPU Scheduler가 수행한다.
• 이 때, ready Queue는 반드시 FIFO 방식의 큐가 아니더라도 priority queue, tree, 혹은 일반 linked list로 구현할 수 있다.
• 이러한 ready Queue에 들어가는 레코드는 일반적으로 프로세스들의 PCB(프로세스 제어 블록)이다.

1.4. 선점(Preemptive) / 비선점(Nonpreemptive) 스케쥴링

• CPU 스케쥴링은 크게 다음과 같은 4 가지 상황에서 발생할 수 있다.
  1. 프로세스가 running → waiting 상태로 전환될 때 (ex. I/O 요청이나 wait() 호출 시)
  2. 프로세스가 running → ready 상태로 전환될 때 (ex. 인터럽트 발생)
  3. 프로세스가 waiting → ready 상태로 전환될 때 (ex. I/O 종료 시)
  4. 프로세스가 terminate 될 때
• Preemptive
  • 상황 2, 3의 경우에는 선점 스케쥴링으로 프로세스를 스케쥴링할 여지가 있다.
  • 선점 스케쥴링은 어느 프로세스가 종료되지 않았음에도 CPU를 강제로 점유하는 방식이기 때문에 race condition을 초래할 수 있다.
    —> race condition: 한 프로세스가 자료를 갱신하는 동안 다른 두 번째 프로세스가 선점하여 데이터를 읽을 때, 데이터의 일관성이 깨지는 현상
  • 커널 설계 시, 선점형은 이러한 race condition을 피하기 위해 mutex 락과 같은 기법이 필요하다.
• Nonpreemptive
  • 상황 1, 4의 경우에는 한 프로세스가 종료 혹은 대기 상태로 전환될 때까지는 CPU를 점유하기 때문에 비선점, 협조적(cooperative) 방식이라고 할 수 있다.
  • 커널 설계 시, 비선점형은 context switching 이전에 시스템 콜 완료 혹은 I/O 완료를 기다리고 프로세스의 blocking을 기다린다.

1.5. Dispatcher

• 디스패처는 CPU 코어의 제어를 CPU 스케쥴러가 선택한 프로세스에 할당하는 모듈이며, CPU Scheduler는 다음 실행될 Process의 선택, Dispatcher는 선택된 Process로의 실제 switching을 실행하는 주체라고 생각할 수 있다.
• 디스패처는 다음과 같은 작업들을 포함할 수 있다.
  • 프로세스간 Context Switching
  • User mode로 전환
  • 프로그램을 다시 실행하기 위해 user program의 적절한 위치로 이동
• 위의 설명과 같이 디스패처는 context switching시 호출되기 때문에 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작할 때 까지 시간이 소요되게 되는데 이를 Dispatch Latency라고 한다.

2. 스케쥴링 기준

• 앞에서는 CPU 스케쥴링을 수행하는 스케쥴러와 디스패처, 스케쥴링의 유형을 알아보았다.
• 여러 스케쥴링 알고리즘을 살펴보기 전에 CPU 스케쥴링 알고리즘을 비교할 수 있는 여러 기준들에 대해 먼저 정리해 보았다.
  • CPU utilization(이용률)
    → 가능한 CPU의 이용률을 낮지 않게 유지하는 것을 기준으로 할 수 있다.
    → 일반적으로 부하가 적은 시스템은 40%, 부하가 큰 시스템의 경우 90%의 CPU 이용률을 보인다.
  • Throughput(처리량)
    → 단위 시간당 완료된 프로세스의 개수
    → 긴 프로세스의 경우, 몇 초 동안 1일 수 있고, 짧은 경우 초당 수십개의 프로세스가 완료될 수 있다.
  • Turnaround time(총 처리 시간)
    → 프로세스가 ready queue에서 대기한 시간 + CPU 실행 시간 + I/O 실행 시간을 합한 값
  • Waiting time(대기 시간)
    → 프로세스가 ready queue에서 대기한 시간
    → CPU 스케쥴링 알고리즘은 프로세스의 실행이나 I/O의 시간에 영향을 주지 않고 단시 프로세스가 ready queue에 대기하는 시간의 양에만 영향을 주므로 스케쥴링 알고리즘 비교의 적절한 척도가 될 수 있다.
  • Reponse time(응답 시간)

3. 스케쥴링 알고리즘

3.1. FCFS(선입 선처리 스케쥴링 - First come first served) - 비선점형

• 가장 일반적인 선입 선처리(FIFO) 큐로 관리할 수 있는 스케쥴링 알고리즘

• ready 큐에 들어온 프로세스 순서대로 CPU를 할당받는 기법

• 예시

  • 아래 사진과 같은 CPU 버스트 타임을 갖는 프로세스들이 순서대로 ready 큐에 들어왔다고 가정한다.

• 프로세스의 대기, 실행 시간을 간트차트로 나타내면 아래와 같으며, 평균 대기 시간은 (0+24+27)/3 = 17 밀리초이다.

• 여기서 P2, P3 프로세스가 실행시간이 긴 P1 프로세스를 기다리는데 이를 Convoy effect라고 한다.
• 위 예제에서 프로세스가 ready 큐에 들어가는 순서를 P2, P3, P1 순서로 조금만 바꾸더라도 평균 대기 시간은 (6+0+3)/3 = 3 밀리초로 크게 변하므로 FCFS 알고리즘은 최적의 알고리즘은 아님을 알 수 있다.

3.2. SJF(최단 작업 우선 스케쥴링 - Shortest job first) - 선점, 비선점형

• CPU에 프로세스를 할당할 때 CPU 버스트 길이가 가장 짧은 프로세스를 할당하는 알고리즘이다.

• 이론적으로 평균 대기 시간에 대해 최적의 알고리즘이지만, 다음 프로세스의 CPU 버스트 길이를 알 수 없기 때문에 실제로 완벽히 구현하기에는 무리가 있다.

• 예시

  • 아래와 같은 버스트 시간을 같은 프로세스들이 ready 큐에 있다고 가정한다.

• 각 프로세스의 실행 순는 버스트 시간이 짧은 순서로 결정되기 때문에 프로세스의 실행을 간트차트로 나타내면 아래와 같다.

• 평균 대기 시간은 (3+16+9+0)/4 = 7 밀리초이다.

• 다음 프로세스의 CPU 길이를 알 수는 없지만 예측할 수는 있으며, 그에 대한 예측 방법으로는 이전 프로세스들의 CPU 버스트 길이를 지수 평균하여 예측한다.

• 또한 일반적으로 SJF라고 하면 비선점형을 말하며 기존 프로세스가 실행되는 동안 더 짧은 실행시간의 새로운 프로세스가 들어오게 되면 해당 프로세스가 CPU를 선점할 수 있게하는 선점형인 SRTF(shortest remaining time first) 알고리즘도 SJF 알고리즘의 일부라고 할 수 있다.

• SRTF 예시

  • 아래와 같은 CPU 버스트 시간을 갖는 프로세스들이 ready 큐에 도착한다고 가정한다.

• SRTF는 선점형이기 때문에 현재 실행되는 프로세스보다 더 짧은 실행시간의 프로세스가 ready 큐에 존재하면 해당 프로세스에 CPU를 내준다.

• 따라서 SRTF(선점형 SJF) 알고리즘의 평균 대기 시간은 [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 6.5 밀리초이다.

3.3. RR(라운드 로빈 스케쥴링 - Round Robin) - 선점형

• FCFS 알고리즘과 유사하지만 시분할을 통해 여러 프로세스가 CPU를 선점할 수 있게 하는 알고리즘이다.

• 이 때, 프로세스가 CPU를 점유하는 시간을 time quantum또는 time slice라고 하며 보통 10~100 밀리초로 설정한다.

• 예시

  • 아래와 같은 CPU 버스트 시간을 갖는 프로세스들이 ready 큐에 존재한다고 가정한다.

• 시간 할당량(quantum)을 4 밀리초로 설정한다면 간트 차트는 아래와 같이 표현될 수 있다.

• 여기서 평균 대기 시간을 계산하면 [(10-4)+4+7]/3 = 5.66 밀리초이다.

• 라운드 로빈의 문제점

  • 라운드 로빈 방식의 가장 큰 특징은 quantum을 설정한다는 점인데, 이 수치에 따라 성능이 크게 변화할 수 있다.
  • 아래 그림과 같이 quantum을 1로 작게 설정한다면 context switch 횟수가 증가하여 dispatch latency가 발생할 것이고 이로 인해 총처리 시간(turnaround time)이 길어지게 된다.

• 맨 위의 경우와 같이 quantum을 큰 값으로 설정하면 context switch가 덜 일어나겠지만 이를 너무 크게 설정한다면 FCFS와 크게 다를 바가 없어지게 된다.
• 따라서 quantum의 크기를 설정하는 것이 OS의 성능에 큰 영향을 끼치며 일반적으로는 CPU 버스트의 80%가 quantum보다 짧게 설정하는 것이 좋다고 한다.

3.4. Priority Scheduling(우선순위 스케쥴링) - 선점형, 비선점형

• CPU를 할당할 때 우선순위가 가장 높은 프로세스에 할당하며, 우선순위가 같은 프로세스에 대해서는 FCFS를 적용하는 방식이다.
• 선점형, 비선점형 모두의 방식으로 구현할 수 있으며 모든 경우에 Starvation이 발생할 수 있다.
• Starvation
  • 우선순위가 낮은 프로세스의 경우, 계속해서 자신보다 높은 우선순위의 프로세스가 ready 큐에 들어오게 되면 실행되지 못하고 ready 큐에만 머무르고 있는 현상
  • 하나의 해결 방안으로 Aging이 있다.
    • ready 큐에 대기중인 프로세스의 우선순위를 주기적으로 증가시키는 방법이다.
    • 예를 들어 0~127의 우선순위가 존재한다고 가정하면 1초마다 우선순위를 1씩 높일 수 있으며, 가장 낮은 우선순위의 프로세스라고 하더라도 약 2분정도 안에는 실행되게 할 수 있다.

3.5. 다단계 큐 스케쥴링(MultiLevel queue Scheduling)

• 앞에서는 프로세스 자체에 우선순위를 부여하는 방식이었다면, 다단계 큐 방식은 여러 큐마다 우선순위를 부여하는 방식이다.
• 예를 들어 안드로이드 휴대폰에서 게임을 하더라도 전화가 오면 화면에 표시되어야 하므로 전화 관련 작업은 더 우선순위가 높은 큐에 배정하는 방식이다.
• 모식도로 나타내면 아래와 같다.

3.6. 다단계 피드백 큐 스케쥴링(Multilevel Feedback Queue Scheduling)

• 위의 다단계 큐 스케쥴링의 경우 아무리 우선순위가 낮은 프로세스라고 하더라도 실행되어야 하는 경우가 있을 수 있는데 계속해서 선순위 프로세스가 진입한다면 실행되지 못하는 경우가 생긴다.
• 따라서 다단계 피드백 큐 스케쥴링에서는 프로세스가 서로 다른 우선순위를 갖는 큐 사이를 이동할 수 있도록 한다.
• 프로세스들은 CPU 버스트에 따라 구분하며, CPU 시간을 오래 사용하면 낮은 우선순위의 큐로 이동시키고, 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동시킨다.
• 각 큐는 우선순위가 낮을 수록 긴 quantum을 설정받는다.