CPU 스케줄링 기법

우선순위 스케줄링

CPU 자원을 분배하는 방식으로는 우선순위(priority) 스케줄링이 있다. 모든 프로세스들에게 우선순위를 매기고 높은 우선순위 순으로 CPU를 할당해주는 것이다. 만약 같은 우선순위를 가진 프로세스가 여럿 존재한다면 그 사이에서도 순서를 가릴 보조적인 룰을 따르는데, 일반적으로는 선입선출(first come, first served) 방식을 따른다. 우선순위 스케줄링은 선점형 또는 비선점형으로 구현할 수 있다.

 

선점형 스케줄링

선점형(preemptive) 스케줄링은 현재 CPU를 할당 받아서 쓰고 있는 프로세스가 있어도 다른 프로세스가 필요로 하면 CPU 자원을 더 급한 프로세스가 빼앗아 사용할 수 있도록 하는 스케줄링이다. 따라서 한 프로세스가 CPU를 독점할 수 없도록 설계되어 있다.

 

선점형 스케줄링은 CPU를 사용하고 있는 프로세스가 있을 때 인터럽트 등 프로세스를 교체하는 이벤트가 발생하면 기존 프로세스가 실행 상태에서 준비 상태로 돌입하는 식으로 동작한다. CPU 자원을 더욱 골고루 배분할 수 있다는 장점을 가지지만 그만큼 문맥 교환이 발생해 오버헤드가 있을 수 있다는 단점도 있다. 선점형 스케줄링 기반 알고리즘으로는 라운드 로빈, SRTF 등이 있다.

 

· 라운드 로빈

라운드 로빈(round-robin)은 CPU 자원을 사용할 프로세스들이 나열된 큐의 순서대로 CPU를 할당하되, 제한된 이용 시간을 두는 스케줄링 방식이다. 각 프로세스가 CPU를 사용할 수 있는 시간을 타임 슬라이스(time slice)라고 하며, 타임 슬라이스만큼의 시간이 경과되면 다음 프로세스에게 CPU가 할당된다. 타임 슬라이스 내에 작업이 완료되지 않은 경우에는 문맥 교환이 발생하고, 아직 작업이 끝나지 않은 해당 프로세스는 큐의 맨 뒤로 다시 추가된다.

 

· 최소 잔류 시간 우선

최소 잔류 시간 우선(shortest remaining time first, SRTF) 스케줄링은 선점형으로 구현한 SJF다. 작업 시간이 짧은 순서대로 CPU를 이용하지만, 도중에 큐에 작업 시간이 더 적은 프로세스가 새로 들어온다면 해당 프로세스가 CPU 자원을 선점해 사용할 수 있게 되는 방식이다.

 

작업 시간이 짧은 프로세스가 끊임없이 들어오는 경우 오래 걸리는 프로세스의 실행 순서는 계속 뒤로 밀려 기아 상태가 발생할 수 있다.

새로 도착하는 작업의 버스트 시간이 더 낮을 경우 중간에 CPU 자원을 가로채게 되어, 결국 p5는 0ms에 이미 도착해있었음에도 불구하고 중간중간에 CPU를 빼앗겨 제일 마지막으로 작업이 완료된다

비선점형 스케줄링

비선점형(non-preemptive) 스케줄링은 선점형 스케줄링과 달리 CPU를 사용 중인 프로세스의 작업이 완료될 때까지 CPU 자원을 독점할 수 있는 스케줄링이다. 현재 CPU를 사용하고 있는 프로세스가 종료나 대기 상태로 돌입하고 자원을 반납하기 전까지 다른 프로세스는 해당 CPU를 사용할 수 없다.

 

비선점형 스케줄링은 문맥 교환이 덜 발생해서 그로 인한 오버헤드가 적은 반면에 CPU 자원을 프로세스들이 골고루 이용하기 어렵다는 단점이 있다. 비선점형 스케줄링 기반의 알고리즘은 FCFS, SJF 등이 있다.

 

· 선입선출

선입선출(first come first served, FCFS) 스케줄링은 큐에 먼저 도착한 순서대로 프로세스를 실행시키는 스케줄링 알고리즘이다. 비선점형 스케줄링이기 때문에 앞선 프로세스의 작업이 끝날 때까지 대기해야 하는데, 만약 먼저 실행된 프로세스의 작업 시간이 길면 대기하는 프로세스들이 기다리는 시간이 길어지는 호위 효과(convoy effect)를 야기할 수 있다.

 

· 최단 작업 우선

최단 작업 우선(shortest job first, SJF) 스케줄링은 실행 시간이 짧은 프로세스를 먼저 실행시키는 방식이다. 평균 대기 시간이 가장 짧다는 장점을 가지며, 최단 작업 우선을 선점형으로 구현한 알고리즘이 최소 잔류 시간 우선 스케줄링(SRTF)이다.

 

멀티레벨 큐 스케줄링

프로세스뿐만 아니라 프로세스가 대기하는 큐에도 우선순위를 부여해 큐를 여럿 두는 스케줄링 방식이 멀티레벨 큐(multi-level queue) 스케줄링이다. 우선순위가 가장 높은 큐에 들어있는 프로세스를 먼저 처리하고, 해당 큐가 비어있으면 다음 우선순위의 큐로 넘어가는 방식이다.

 

각 큐는 별개의 스케줄링 알고리즘을 적용할 수 있다는 점이 멀티레벨 큐의 특징이다. 다만 프로세스가 큐 간에 이동할 수 없다는 것이 단점이며, 이로 인해 기아 상태가 발생할 수 있다. 이런 단점은 멀티레벨 큐 피드백 알고리즘으로 보완했다.

 

멀티레벨 큐 피드백 스케줄링

가장 일반적으로 쓰이는 멀티레벨 큐 피드백(multi-level queue feedback) 스케줄링은 멀티레벨 큐 스케줄링의 개선된 버전으로, 큐 간의 이동이 가능하다. 높은 우선순위에 있던 프로세스가 CPU 사용 시간 완료 이후에도 끝나지 않을 경우 점차 낮은 우선순위 큐로 이동하게 되며, 기아 상태에 대응하기 위해 에이징 기법을 적용할 수도 있다.

 

멀티레벨 큐 피드백 스테줄링 알고리즘에서는 CPU를 집중적으로 쓰는 프로세스의 우선순위는 자연스럽게 낮아지고, 입출력을 집중적으로 쓰는 프로세스의 우선순위는 상대적으로 높아진다.

 

기아 상태

일부 스케줄링 알고리즘은 기아 상태(starvation)를 유발하기도 한다. 기아 상태는 프로세스의 우선순위가 낮아서 자원을 계속 할당받지 못하는 상태를 말하며, 우선순위를 부여하는 과정에서 조건을 만족하지 못해 계속 낮은 우선순위를 갖게 되는 경우 발생할 수 있다.

 

오랫동안 자원을 할당 받지 못한 프로세스의 우선순위를 점차 높이도록 알고리즘을 개선해 기아 상태를 해소할 수 있으며, 이런 방식을 에이징(aging) 기법이라고 한다.