[OS - 6] CPU 스케줄링

CPU 스케줄링

멀티 프로그래밍, 멀티 태스킹의 목적은 여러 프로세스를 동시에 실행해 CPU의 유휴 시간을 최대한 줄이는 것이다. 다중 코어 시스템에서는 모든 CPU 코어의 사용량이 최대가 되도록 유지하는 것으로 확장된다. 멀티 프로그래밍 환경에서 핵심은 CPU 자원의 스케줄링이다. CPU 스케줄링은 CPU(또는 CPU 코어) 할당을 기다리는 여러 프로세스 중에서 어떤 프로세스에게 CPU를 할당할지 선택하는 것을 말한다. 그리고 CPU 스케줄링을 수행하는 모듈을 스케줄러라고 한다. 그러면 어떻게 CPU 스케줄링을 해야 효율적일까? 이번 장에서는 여러 CPU 스케줄링 알고리즘을 알아본다.

CPU - I/O 버스트 사이클

프로세스의 실행은 CPU 버스트와 I/O 버스트의 사이클로 구성된다. CPU 버스트는 프로세스가 CPU를 점유하여 실행되는 시간을 말하며 I/O 버스트는 I/O 작업이 발생해 대기하는 시간을 말한다. 프로세스 실행은 CPU 버스트로 시작한다. 뒤이어 CPU 버스트와 I/O 버스트가 교차로 발생하고 마지막으로 CPU 버스트에서 프로세스 종료 요청과 함께 끝난다.

CPU 버스트와 I/O 버스트의 교차

프로세스, 시스템마다 다르지만 CPU 버스트를 광범위하게 측정한 결과 아래의 곡선을 갖는 경향이 있다. 짧은 CPU 버스트가 많이 있으며 긴 CPU 버스트는 적다. I/O 중심의 프로그램은 짧은 CPU 버스트가 많을 것이며 CPU 중심의 프로그램은 긴 CPU 버스트가 많을 것이다. 프로세스마다 다른 버스트 분포는 CPU 스케줄링 시 중요한 고려사항이 된다.

CPU 버스트 지속시간 히스토그램

선점, 비선점 스케줄링

스케줄링 알고리즘은 선점 스케줄링(Preemptive Scheduling)와 비선점 스케줄링(Non-preemptive Scheduling) 방식으로 구분된다. 대부분의 최신 OS는 선점 스케줄링 알고리즘을 사용한다.

 

선점 스케줄링 : 실행 상태의 프로세스를 강제로 중단시키고 다른 프로세스에게 CPU를 할당할 수 있는 방식. 대표적인 알고리즘으로 라운드 로빈 알고리즘이 있다.

• 장점 : 우선 순위가 높은 프로세스에게 빠르게 CPU를 할당할 수 있음, 한 프로세스가 계속 CPU를 점유하는 걸 방지
• 단점 : 자원의 경쟁 발생, A 자원을 사용하다가 다른 프로세스가 CPU를 선점해 강제로 중단되고 뒤이어 실행된 프로세스가 A 자원을 사용할 수 있음 → 경쟁을 방지하기 위해 mutex 락과 같은 기법 필요

비선점 스케줄링 : 실행 상태의 프로세스가 자발적으로 CPU를 반납하기 전까지 계속 CPU를 점유하는 방식. 즉 실행 상태 프로세스는 대기 상태가 되거나 종료되었을 때만 CPU를 반납한다. 대표적인 알고리즘으로 FIFO 스케줄링 알고리즘이 있다.

• 장점 : 단순함
• 단점 : 호위 효과(convoy effect, CPU 버스트가 긴 프로세스가 CPU를 양도해주지 않아 다른 프로세스들이 CPU를 양도받기를 계속 기다리는 현상)

스케줄링 기준

여러 스케줄링 알고리즘을 비교하려면 비교 기준이 필요하다. 비교 기준에 따라서 최선의 스케줄링 알고리즘이 바뀔 수 있다. 아래는 주로 사용되는 기준들이다.

• CPU 이용률 (utilization) : CPU가 일하는 시간의 비율을 CPU 이용률이라 한다.
• 처리량(throughput) : 단위 시간당 완료된 프로세스의 개수
• 총처리 시간(turnaround time) : 프로세스가 생성되어 종료될 때까지의 시간, 즉 준비 큐에서 대기한 시간 + CPU 실행 시간 + I/O 대기 시간을 합한 시간이다.
• 대기 시간(waiting time) : 프로세스가 준비 큐에서 대기하는 시간, 스케줄링 알고리즘은 CPU 실행 시간과 I/O 대기 시간에는 영향을 주지 못하며 오직 준비 큐에서 대기하는 시간에만 영향을 준다.
• 응답 시간(response time) : 사용자가 작업을 요청한 후, 첫 번째 응답이 시작될 때 까지의 시간. 실시간 시스템 또는 대화형 시스템에서는 응답 시간도 중요하다.

CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다. 대부분의 경우 평균 측정 시간을 최적화하려고 한다.

스케줄링 알고리즘

1. FCFS (First-Come, First-Served Scheduling)

초창기에 쓴 간단한 스케줄링 알고리즘이다. CPU를 먼저 요청하는 프로세스에게 CPU를 할당해 준다. FIFO 방식의 큐로 쉽게 구현할 수 있다. 비선점형이다.

 

장점 : 간단하게 구현 가능

단점 : 평균 대기 시간이 길어질 수 있음 (CPU 버스트가 긴 프로세스부터 실행할 경우 모든 프로세스의 평균 대기 시간은 길어짐), 호위 효과

 

2. SJF (Shortest-Job-First Scheduling)

SJF는 CPU를 할당할 프로세스 선택 시 다음 CPU 버스트 시간이 제일 작은 프로세스를 선택한다. 때문에 SJF는 Shortest-next-CPU-burst라고도 불리며 이론적으로 평균 대기 시간이 최소가 된다. SJF를 구현하려면 다음 CPU 버스트를 계산해야 한다. 하지만 정확히 계산할 수 있는 방법은 없으며 과거의 CPU 버스트를 토대로 다음 CPU 버스트를 예측할 수는 있다. SJF는 선점형 또는 비선점형으로 구현 가능하다. 실행되고 있는 프로세스의 잔여 CPU 버스트보다 더 짧은 잔여 CPU 버스트를 가진 프로세스가 준비 큐에 들어왔을 때 새 프로세스가 CPU를 선점하도록 한다면 선점형이고 실행되고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다면 비선점형이다. 때문에 선점형 SJF 알고리즘은 Shortest remaining time first 스케줄링이라고도 불린다. 선점형 SJF 알고리즘이 비선점형보다 평균 대기 시간이 최소이다.

 

장점 : 이론적으로 평균 대기 시간이 최소임

단점 : 현실적으로 CPU 버스트 계산이 쉽지 않아 잘 사용되지 않음(정확히 계산할 수 없으며 예측 시 오버헤드가 발생)

 

3. RR (Round-Robin Scheduling)

선점형 FCFS이다. 스케줄러는 준비 큐를 돌면서 한 번의 타임 슬라이스(time slice) 동안 각 프로세스에게 CPU를 할당한다. 준비 큐는 원형큐로 동작하며 타임 슬라이스는 일반적으로 10~1000ms 범위이다.

 

만약 프로세스의 CPU 버스트가 한번의 타임 슬라이스보다 짧을 경우, 프로세스는 자발적으로 CPU를 반납하고 스케줄러는 다음 프로세스에게 CPU를 할당한다. 반대로 프로세스의 CPU 버스트가 한번의 타임슬라이스보다 긴 경우, 타이머가 OS에게 인터럽트를 걸어주고 컨텍스트 스위칭이 발생한다. 실행 중인 프로세스는 준비 큐의 꼬리에 추가된다.

 

RR 알고리즘의 성능은 타임 슬라이스 크기에 많은 영향을 받는다. 타임 슬라이스가 너무 짧으면 컨텍스트 그 만큼 스위칭 횟수는 증가하기에 성능이 저하된다. (예를 들어 컨텍스트 스위칭에 5ms가 걸린다고 가정하면 10번만 발생해도 50ms가 낭비된다.) 반대로 타임 슬라이스가 너무 길면 FCFS 알고리즘과 다를게 없다.

 

장점 : 모든 프로세스들이 공평하게 CPU를 사용할 수 있음

단점 : 컨텍스트 스위칭이 자주 발생

 

4. 우선순위 스케줄링 (Priority Scheduling)

우선순위가 각 프로세스에 연관되고, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다. 만약 우선순위가 같다면 FCFS 방식으로 먼저 레디큐에 온 프로세스에게 CPU를 할당한다. SJF 알고리즘은 우선순위 알고리즘의 특별한 케이스다. SJF의 경우 우선순위는 다음 CPU 버스트이다. 우선순위 알고리즘은 SJF에서 보았듯 선점형 또는 비선점형으로 구현 가능하다. 실행 중인 프로세스보다 우선순위가 높은 프로세스가 준비 큐에 들어왔을 때 새 프로세스가 CPU를 선점하도록 한다면 선점형이고 실행 중인 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다면 비선점형이다.

 

우선순위 알고리즘은 기아(starvation) 문제가 발생할 수 있다. 기아 문제란 준비 큐에서 대기하고 있는데 계속 우선 순위가 높은 프로세스가 들어와 준비큐에서 무기한 대기하는 문제를 말한다. 이 문제에 대한 해결책으로 aging을 사용한다. aging은 오랜 시간 준비 큐에서 대기하고 있는 프로세스의 우선 순위를 점진적으로 높인다.

 

우선순위 알고리즘에 라운드 로빈 알고리즘을 결합시키기도 한다. 높은 우선순위의 프로세스를 실행하되 같은 우선순위를 가진 프로세스들을 라운드 로빈 방식으로 실행한다.  

 

장점 : 우선순위가 높은 프로세스가 빠르게 CPU를 선점할 수 있음

단점 : 기아 문제가 발생할 수 있음

 

5. 멀티 레벨 큐 스케줄링 (MLQ Scheduling)

N개의 우선순위를 배정하고 각각의 우선순위마다 준비 큐를 따로 두는 방식이다. 우선순위가 높은 준비 큐부터 먼저 스케줄링 되며 우선순위가 높은 준비 큐가 비면 다음 우선순위의 준비 큐를 스케줄링한다.

우선순위마다 별도의 준비 큐 유지

MLQ 알고리즘은 우선순위 별로 다른 CPU 스케줄링 알고리즘을 적용할 때 사용한다. 예를 들어 프로세스 중 실시간 프로세스는 높은 우선순위를 가져 높은 우선순위의 준비 큐에 들어가도록 하며 배치 프로세스는 낮은 우선순위를 가져 낮은 우선순위의 준비 큐에 들어간다. 그리고 각 준비 큐는 큐에 대기하는 프로세스의 특징에 맞춰 서로 다른 스케줄링 알고리즘으로 스케줄링된다.

프로세스 유형 별로 우선순위 구분

MLQ 알고리즘도 우선순위 기반이기 때문에 기아 문제가 발생할 수 있다. MLQ 알고리즘에서 준비 큐에 있는 프로세스는 다른 준비 큐로 이동하지 않는다. 따라서 우선 순위가 낮은 준비 큐에 있는 프로세스들이 무기한 대기하는 기아 문제가 발생할 수 있다. 기아 문제를 해결하기 위해 다단계 피드백 큐 스케줄링(MFQS) 알고리즘을 사용한다. MFQS 알고리즘은 준비 큐에 있는 프로세스가 다른 준비 큐로 이동하는 것을 허용한다. 따라서 준비 큐에 오래 대기하고 있는 프로세스를 높은 우선순위의 준비 큐로 이동시켜 기아 문제를 해결할 수 있다.

 

장점 : 우선순위가 높은 프로세스가 빠르게 CPU를 선점할 수 있음, 준비 큐별로 다른 스케줄링 알고리즘 적용 가능

단점 : 기아 문제가 발생할 수 있음

스레드 스케줄링

현대의 OS는 프로세스가 아닌 스레드(정확히는 커널 스레드) 단위로 스케줄링 한다. 스레드 스케줄링 알고리즘은 더 복잡하기 때문에 이 글에서 다루지 않는다.