[OS]CPU 스케줄링 알고리즘에 대하여

1. CPU 스케줄링

운영체제의 단기 스케줄러는 스케줄링 알고리즘을 이용해 어떤 프로세스에게 CPU를 할당할 지(디스패치) 결정한다.

프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. CPU 버스트로 시작되어 I/O 버스트가 발생하고 다시 CPU 버스트가 발생, I/O 버스트 발생.. 마지막 CPU 버스트는 또 다른 I/O 버스트가 뒤따르며, 실행을 종료하기 위한 시스템 콜과 함께 끝난다.

CPU를 많이 쓰는 프로세스(CPU bound job)와 I/O를 많이 쓰는 프로세스(I/O bound job)가 섞여 있기 때문에 CPU 스케줄링이 필요하다.

CPU 스케줄링 알고리즘의 선택 기준은 다음과 같다.

• CPU 이용률 : CPU가 얼마나 바쁘게 일을 하는가
• 처리량 : 단위 시간 당 완료된 프로세스의 개수
• 총 처리 시간 : 준비 큐에서 대기한 시간 + CPU에서 실행한 시간 + I/O 실행 시간
• 대기 시간 : 프로세스가 준비 큐에서 보낸 시간의 합
• 응답 시간 : 하나의 요청 후 첫 응답까지의 시간

---

CPU 스케줄링이 일어나는 상황은 다음과 같다.

1. Running → Blocked(Wait) : 프로세스가 실행 상태에서 대기 상태로 전환될 때 ( I/O 요청 혹은 자식 프로세스가 종료되기를 기다리기 위해 wait() 호출할 때)
2. Running → Ready : 프로세스가 실행 상태에서 준비 상태로 전환될 때 (인터럽트 발생)
3. Blocked(Wait) → Ready : 프로세스가 대기 상태에서 준비 상태로 전환될 때 (I/O 종료)
4. Terminate : 프로세스가 종료할 때

1번쨰, 4번째 상황에서만 스케줄링이 발생하면 비선점 스케줄링이라고 한다. 모든 상황에서 스케줄링이 일어나는 경우 선점 스케줄링이라고 하며, Window, macOS, Linux 및 대부분의 현대 운영체제는 선점 스케줄링을 사용한다.

공룡책 p222 - 223 쪽 참고

2. 스케줄링 알고리즘

2.1 FCFS(First Come, First Served)

선착순으로 처리하는 스케줄링 알고리즘이다. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다.

• 비선점형 스케줄링 방식
• 구현이 매우 간단하다.
• 먼저 도착한 프로세스의 버스트 시간이 긴 경우 이후의 프로세스들이 버스트 시간이 짧음에도 기다려야 하는 convoy effect(호위 효과)가 발생한다.
• 각 프로세스가 규칙적인 간격으로 CPU를 사용하는 것이 중요한 대화형 시스템에서는 큰 문제가 된다.

2.2 SJF(Shortest Job First)

프로세스의 CPU 버스트 시간이 가장 짧은 프로세스에 CPU를 먼저 할당한다.

• 비선점 스케줄링 방식과 선점 스케줄링 방식 모두 사용가능하다.
• 평균 대기 시간이 가장 짧기 때문에 최적의 알고리즘이다. 하지만 다음 CPU 버스트의 길이를 알 수 있는 방벙이 없다.
• CPU 버스트 시간을 예측하기 위해 가장 최근의 CPU 버스트 시간을 많이 반영하는 지수 평균을 이용한다.
  • Τn+1 = αΤn + (1 - α)Τn-1
• CPU 버스트의 시간이 긴 프로세스는 CPU의 제어를 얻지 못하는 starvation(기아 상태) 문제가 발생한다.

프로세스가 실행 중에 새로운 프로세스가 도착한 경우, 새로운 프로세스의 CPU 버스트 시간이 실행 중인 프로세스의 남은 시간보다 더 짧은 경우가 있을 것이다.

비선점형 SJF 방식에서는 현재 실행하고 있는 프로세스가 끝나기 전까지 기다릴 것이고, 선점형 방식에서는 새롭게 들어온 프로세스에게 CPU를 내어줄 것이다. 선점형 SJF 방식은 SRF(Shortest Remaining Time First)방식이라고도 불린다.

2.3 RR(Round-Robin)

타임 슬라이스라고 하는 작은 단위의 시간을 정하고 프로세스들이 번갈아가며 할당된 시간 동안 CPU를 사용한다. FCFS와 마찬가지로 선입선출 큐로 구현할 수 있다.

• 선점형 스케줄링 방식
• CPU 스케줄러는 타이머를 이용해 할당 시간이 지나면 인터럽트를 발생시킨다.
• 프로세스의 CPU 버스트가 할당된 시간보다 작은 경우 프로세스가 CPU를 자발적으로 방출한다.
• 프로세스의 CPU 버스트가 할당된 시간보다 길다면, 다시 준비 큐의 꼬리로 들어간다.
• 시간 할당량이 짧으면 잦은 context switching이 발생하게 되어 오버헤드가 발생한다.

2.4 Priority Scheduling

앞에서 다룬 SJF는 일종의 우선순위 스케줄링 알고리즘이다.

• 비선점 스케줄링 방식과 선점 스케줄링 방식 모두 사용가능하다.
• 낮은 우선순위를 가진 프로세스들이 CPU를 무한히 대기하는 starvation(기아 상태) 문제가 발생한다.
  • 이를 해결하기 위해 오랫동안 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 aging 기법을 사용할 수 있다.

2.5 Multilevel Queue

• 프로세스 유형에 따라 프로세스들을 여러 개의 개별 큐로 분할하여 스케줄링한다.
• 각 큐들은 서로 다른 스케줄링 알고리즘을 가질 수 있다.
• 큐와 큐 사이에 스케줄링도 필요하여 일반적으로 선점형으로 구현된다.

2.6 Multilevel Feedback Queue

다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 하나의 큐에 영구적으로 할당된다.

• 다단계 피드백 큐 스케줄링에서는 프로세스가 큐들 사이를 이동할 수 있다.
• 어떤 프로세스가 CPU를 많이 사용하면 낮은 우선순위의 큐로 이동된다.
• 마찬가지로 낮은 우선순위의 큐에서 오래 대기하는 프로세스들은 높은 우선순위의 큐로 이동할 수 있다 (aging). 이러한 방식으로 starvation(기아 상태)를 방지할 수 있다.

3. 멀티 코어 스케줄링

멀티 코어 스케줄링에서는 고려해야 할 요소들이 복잡하다.

• 준비 큐를 어떻게 운영할 것인가? 한 개의 global queue? 코어 당 하나의 queue?
• 각 코어에 프로세스들을 어떻게 부하 분산할 것인가?
• 경쟁 상태를 어떻게 해결할 것인가?

Cache Coherence 캐시 일관성

• 동일한 메모리를 공유하는 CPU 간에 데이터 불일치를 방지하기 위해 동기화가 필요하다.
• Bus Snooping을 통해 버스를 지속적으로 관찰하며 자신이 캐시에 보관중인 데이터에 변화가 발생하면 이를 막거나(invalidate) 갱신한다(update).

Cache Affinity 캐시 친화성

• 하나의 프로세스가 돌아가며 사용한 메모리는 캐시에 적재되어 있다. 문맥 교환 이후에 다른 프로세스가 코어에 적재되면 캐시 미스가 발생한다.
• 이를 방지하기 위해 하나의 프로세스는 가능한 하나의 CPU에서만 처리하도록 스케줄링하는 것이 효율적이다.

1. SQMS 알고리즘

• Single Queue Multiprocessor Scheduling
• 가장 단순하게, gloabal queue를 1개 사용한다.
• 각 코어들은 queue에서 pop한 프로세스를 실행시킨다.
• cache affinity를 고려하지 않음
• 경쟁 상태(동기화)에 대한 고려하지 않음

2. MQMS 알고리즘

• Multi Queue Multiprocessor Scheduling
• 하나의 코어는 한 개의 큐만 사용하다록 한다 → cache affinity를 고려함
• 각 코어들이 분리된 큐를 사용하게 되면 경쟁 상태를 어느 정도 해결할 수 있음
• 각 큐마다 별도의 알고리즘을 적용할 수 있다.
• 부하 분산이 불가능한 문제가 있으며, CPU 효율이 좋지 않다.
  • 이를 해결하기 위해 idle한 CPU에 작업을 이동시키는 방법을 도입한다.
  • 큐의 길이를 일정 시간마다 검사하며, 상대적으로 작은 쪽에서 프로세스를 가져간다. (Work stealing)