[운영체제] CPU 스케줄링(Scheduling)은 어떻게 이뤄질까?

CPU 스케줄링의 경우 메모리에 동시에 여러 프로세스를 올리는 다중 프로그램 운영체제의 기본이다. 운영체제를 통해 CPU를 프로세스 간에 교환하면서 컴퓨터를 보다 응답성이 높고 생산성이 높게 사용하게 된다. 

 

일단 기본적으로 어떤 프로세스가 특정 요청이 완료되기를 대기해야 하는 경우 운영체제는 CPU를 해당 프로세스로부터 회수하여 다른 프로세스에 할당하게 된다. 이런 Context Switch는 계속해서 반복되며 이런 컴퓨터 자원들은 사용되기 전 스케줄링이 되어야 한다. 

 

따라서 CPU 스케줄링이 운영체제 설계에서 핵심적인 부분이 되는 것이다. 

 

프로세스 실행의 경우 CPU 실행과 I/O 대기의 사이클로 구성되어 있다. CPU Burst를 통해 running 상태가 되었다가 I/O Burst를 통해 Waiting을 거쳐 Ready상태로 오게 된다. 이런 사이클이 반복되면서 프로세스가 실행되며, 마지막 CPU Burst 이후 I/O Burst를 거쳐 실행을 종료하기 위한 시스템 요청과 함께 프로세스가 종료된다. 

 

CPU가 유휴 상태가 될 때마다 운영체제는 Ready Queue에 있는 프로세스 중 하나를 선택하여 실행해야 한다. 이는 CPU 스케줄러를 통해 이뤄지게 된다. Ready Queue의 경우 반드시 선입 선출로 이뤄질 필요는 없으며, 우선순위 큐 / 트리 / 순서가 없는 링크드 리스트 등으로 구현될 수 있다. 

 

CPU 스케줄링의 상황

• 한 프로세스가 실행(running) 상태에서 대기(waiting) 상태로 전환될 때 -> 자발적으로 전환되기 때문에 비선점(Nonpreemptive)
• 프로세스가 실행(running) 상태에서 준비 완료(ready)상태로 전환될 때 [인터럽트 발생] -> 강제 전환되기 때문에 선점(preemptive)
• 프로세스가 대기(waiting) 상태에서 준비 완료(ready)상태로 전환될 때 (I/O 종료시) -> 강제 전환되서 선점 
• 프로세스가 종료될 때 -> 자발적으로 전환되기 때문에 비선점(Nonpreemptive)

비선점 스케줄링의 경우 CPU에 프로세스가 할당되면 프로세스가 종료되거나, 대기상태로 전환해 CPU를 방출할 때까지 점유를 하게 되기 때문에 비효율적이다. 따라서 대부분의 최신 운영체제들은 전부 선점 스케줄링 알고리즘을 사용한다. 

 

하지만 선점 스케줄링을 하는 경우 자발적으로 Context Switch가 발생하기 때문에 데이터가 다수의 프로세스에 의해 공유될 수 있고 이에 따라 Race Condition이 발생할 수 있다. 

 

디스패처

스케줄러에 포함된 요소로 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이다. 

• 한 프로세스에서 다른 프로세스로 Context를 Switch하는 역할
• 사용자 모드로 전환
• 프로그램을 다시 시작하기 위해 프로그램을 적절한 위치로 이동하는 역할

디스패처의 경우 모든 프로세스의 Context Switch를 할 때마다 호출되기 때문에 가능한 빠르게 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간을 Dispatch Latency라고 한다. 만약 Dispatch Latency보다 Context Switch가 빠르게 이뤄지면 프로세스가 제대로 동작하지 않게 된다. 

 

스케줄링 알고리즘을 판단하기 위한 기준

어떤 CPU스케줄링이 효과적인지 판단하기 위한 기준들은 다음과 같다. 

• CPU 이용률 : CPU가 최대한 바쁘게 움직이도록 유지하길 원한다. 보통 40~90% 범위를 가져야 한다. 
• 처리량 : 단위 시간당 완료된 프로세스의 개수를 의미한다. 
• 총처리 시간 : 프로세스를 실행하는데 걸린 총 소요 시간이다. 
• 대기시간 : Ready Queue에서 프로세스가 대기하며 보낸 시간의 합이다. 
• 응답시간 : 응답이 시작되는데까지 소요된 시간 

 

스케줄링 알고리즘

선입 선처리 스케줄링 (First-Come, First-Served Scheduling, FCFS)

가장 간단한 스케줄링 알고리즘이다. 단순히 CPU를 먼저 요청한 프로세스에게 CPU를 할당해주는 방식이다. 

 

평균 대기 시간 : P1 = 0 / P2 = 24 / P3 = 27, (0 + 24 + 27) / 3 = 17

총 처리시간 : P1 = 24 / P2 = 27 / P3 = 30, (24 + 27 + 30) / 3 = 27

-> P1, P2, P3의 순서가 바뀌게 되면 평균 대기시간과 총 처리시간도 변경된다. 

 

처리가 전부 완료될 때까지 기다리는 방식이기 때문에 비선점 스케줄링 방식이다. 

 

단점

• 평균 대기 시간의 경우 일반적으로 최소가 아니며 CPU 버스트 시간에 따라 평균 대기시간의 편차가 매우 크다. 
• 만약 버스트 시간이 긴 프로세스가 먼저 실행되면 모든 다른 프로세스가 이 프로세스가 CPU를 양도하길 기다리는 Convoy Effect(호위효과)이 발생한다. 

 

최단작업 우선 스케줄링 (Shortest-Job-First Scheduling, SJF)

다음 CPU 버스트 시간이 가장 짧은 작업 먼저 CPU를 할당해주는 방식이다. 주어진 프로세스에서 가장 최소의 평균 대기시간을 가지게 되어 최적의 알고리즘이나 다음 CPU 버스트에 걸리는 시간을 알 수 있는 방법이 없기 때문에 이론적인 알고리즘이다. 

일반적으로 측정된 이전의 CPU버스트들의 길이를 지수 평균하여 산출하게 된다. 

이는 선점형 / 비선점형 둘 다 가능하다. 

 

단점

• 이론적인 방법이다. 
• 가장 짧은 프로세스를 먼저 할당하기 때문에 버스트 시간이 긴 프로세스의 경우 거의 영원히 CPU를 할당받을 수 없는 Starvation이 발생할 수 있다. 

 

최소 잔여시간 우선 스케줄링 (Shortest Remaining Time First, SRTF)

SJF를 선점형으로 스케줄링하는 경우 최소 잔여기간 우선 스케줄링을 할 수 있다. 만약 프로세스가 실행되는 동안 새로운 프로세스가 Ready Queue에 온다면 새로운 프로세스의 CPU 버스트 시간이 이미 실행되고 있는 프로세스의 남은 CPU 버스트시간보다 적을 수 있다. 이 경우 실행하고 있던 프로세스를 Ready Queue로 보내고 CPU 버스트 시간이 짧은 새로운 프로세스에게 CPU를 할당하는 방식으로 동작한다. 

 

단점

• 가장 짧은 프로세스를 먼저 할당하기 때문에 버스트 시간이 긴 프로세스의 경우 거의 영원히 CPU를 할당받을 수 없는 Starvation이 발생할 수 있다. 

 

라운드 로빈 스케줄링 (Round-Robin Scheduling, RR)

선입 선처리 알고리즘과 유사하지만 이는 선점형으로 프로세스를 시분할하여 Context Switch하게 된다. 시간 할당량은 대부분 10에서 100밀리초로 주어지며 이 시간동안 프로세스를 끝내면 Ready Queue에 있는 다른 프로세스에 CPU를 할당한다. 여기서는 유일하게 남은 실행가능한 프로세스가 아닌 경우 연속해서 두 번 이상의 시간 할당을 받는 프로세스는 존재하지 않는다. 

 

라운드 로빈 스케줄링의 경우 시간 할당량에 따라 성능이 매우 많은 영향을 받게 된다. 만약 시간 할당량이 너무 길게 되면 거의 선입 선처리 방식과 동일한 결과를 낳게 된다. 하지만 또 시간 할당량이 지나치게 작은 경우 매우 많은 Context Switch가 발생하게 되며 Dispatcher Latency보다 짧을 경우 Context Switch만 발생하고 제대로 프로세스를 처리할 수 없게 된다. 

 

일반적으로 전체 CPU 버스트의 80%가 시간할당량보다 짧아야 한다. 

 

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

SJF 알고리즘은 우선순위 스케줄링에 포함되는 개념이다. (우선순위를 가장 짧은 CPU 버스트 시간을 갖는 프로세스로 잡고 있기 때문)

선점형으로 할 경우 더 높은 우선순위의 프로세스가 도착하면 실행 중인 프로세스를 멈추고 Ready Queue로 보낸 뒤 CPU를 선점하는 방식이다. 만약 비선점형으로 하게 된다면 더 높은 우선순위의 프로세스가 ReadyQueue에 들어오게 되면 가장 먼저 Queue에서 나갈 수 있도록 Head로 설정하게 된다. 

 

단점

• 가장 짧은 프로세스를 먼저 할당하기 때문에 버스트 시간이 긴 프로세스의 경우 거의 영원히 CPU를 할당받을 수 없는 Starvation이 발생할 수 있다. 

 

이런 단점을 해결하기 위한 방법으로 aging이 있다. 만약 오랫동안 Ready Queue에서 대기하게 되는 경우 점진적으로 우선순위를 올려주는 것이다. 이를 통해 버스트 시간이 긴 프로세스도 결국 실행될 수 있도록 하는 방식으로 이를 해결할 수 있다. 

 

참고자료

• http://www.yes24.com/Product/Goods/89496122

운영체제 - YES24