CPU 스케줄링에 대하여 알아보자

CPU 스케줄링은 항상 실행중인 프로세스를 가지게 함으로써 중앙처리장치 이용률을 최대화 하는 것에 목적을 두고 있다. 이번 포스팅에서는 CPU 스케줄링의 개념과 스케줄링 알고리즘에 대하여 자세히 알아보겠다.

스케줄링이란 

프로세스와 쓰레드 포스팅에서 배운거처럼, 한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 한다. 따라서 OS는 실행 대기중인 프로세스들에게 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있다.

선점 스케줄링(Preemptive Scheduling)

OS가 나서서 CPU사용권을 '선점'하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식이다. 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있다. 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다. 

비선점 스케줄링(Non-Preemptive Scheduling)

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있으며 선점방식보다 스케쥴러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적다. 일괄처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있다. 

스케줄링 알고리즘 종류

First-Come First-Served

먼저 도착한 순서대로 스케쥴링하는 방법이며, 이름이 너무 길어 흔히 FCFS로 불립니다. 구현은 매우 쉽지만, 버스트가 큰 작업이 먼저 들어오면 후행 작업들의 대기시간이 매우 길어지는 단점을 가지고 있습니다. 이것을 호위효과(Convoy Effect)라고 합니다.

Shortest Job First

직역하면 최단 작업 우선, SJF 알고리즘 입니다. 남은 시간이 가장 짧은 작업을 선택합니다. 검사 시점에 따라 선점형, 비선점형으로 나뉩니다.

비선점형

선점을 사용할 수 없으므로 작업이 끝난 시점에서 검사합니다.

 

P0가 끝난 시점에서 P1, P2, P3 모두 요청이 도착한 상태이므로 셋 중에서 가장 Burst Time이 짧은 P1를 선택합니다. 만약 P1의 Arrival Time이 5보다 컸다면 P0이 끝난 시점에서 P1은 요청되지 않았으므로 고려되지 않았을 것 입니다.

시간이 흘러 P1이 끝난 시점에서, P2가 먼저 요청되었지만 P3의 버스트 시간이 더 짧기 때문에 스케쥴러는 P3을 선택합니다.

 

위의 타임라인을 보면 총처리시간과 대기시간을 쉽게 구할 수 있겠죠. FCFS보다 평균 총처리시간과 평균 대기시간이 줄어든 것을 확인할 수 있습니다.

선점형

이번에는 선점을 사용할 수 있으므로 새로운 작업이 도착한 시점에서도 검사할 수 있습니다.

 

P0 도중에 P1이 도착했습니다. 현재 진행중인 작업을 끝내려면 4초가 더 필요하지만, P1을 끝내려면 3초면 되므로 더 짧은 P1로 교체합니다. 이후에 P1이 처리되고 있는 도중에 P2, P3가 도착하지만 P1이 더 짧으므로 교체되지 않습니다. P1이 완료되면 남은 시간이 가장 짧은(4초가 남은) P0가 선택됩니다.

 

총처리시간은 지금까지와 마찬가지지만 대기시간은 약간 달라집니다. 중간로 선점되어 대기큐로 되돌아갔으므로 다시 대기한 시간을 포함해야 하기 때문입니다. 즉 N 번째 대기시간이 생겨났습니다.

Shortest Job First의 단점

SJF은 고질적인 문제를 가지고 있습니다.

 

첫 번째는 Burst Time이 큰 작업이 뒤로 계속 밀린다는 것이죠. 짧은 작업들이 계속 요청되면, 버스트가 큰 작업의 순서는 영원히 오지 않을 것입니다. 이것을 기아현상(Starvation)라고 합니다.

 

두 번째는 요청된 작업의 Burst Time을 계산할 수 없다는 것 입니다. 예전에 실행했던 경험이 있는 작업이라면 과거의 기록에서 추정할 순 있지만, 정확하게 계산하는 것은 어렵습니다.

우선순위 스케줄링(Priority)

우선순위 스케줄링은 준비 큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당하는 방식이다. 그럼 만약 우선순위가 동일한 프로세스가 준비 큐로 들어오게 되면 FIFO 의 순서로 스케줄링을 하게 된다.

 

또한 우선순위 스케줄링은 선점 또는 비선점이 존재하기 때문에 이 둘을 나눠서 생각해야 한다. 선점과 비선점의 방식도 동일하게 도착한 프로세스의 우선순위를 보고 구분을 하는데 기존 프로세스보다 우선순위가 높으면 할당한다.

우선순위 결정법

우선순위는 내부적, 외부적으로 정의할 수 있다.

내부적 우선순위 결정

>제한 시간, 기억장소 요청량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율

외부적 우선순위 결정

>프로세스의 중요성, 사용료를 많이 낸 사용자, 작업을 지원하는 부서, 정책적 요인

우선순위 스케줄링 장단점

우선순위 스케줄링은 각 프로세스의 상대적 중요성을 정확히 정의할 수 있으며 다양한 반응으로 실시간 시스템에 사용 가능한 장점이 있으나 높은 우선수위 프로세스가 프로세서를 많이 사용하면 우선순위가 낮은 프로세스는 무한정 연기되는 기아가 발생하는 단점이 있다.

라운드 로빈 스케줄링

라운드 로빈의 기본 원칙은 모든 요소를 돌아가면서 순회하는 것 입니다.

 

기본적인 동작은 FCFS와 같으나 특정 시간(Quantum)만큼만 실행하고, 퀀텀을 사용했는데도 미처 작업을 완료하지 못했다면 선점되어 대기큐의 마지막으로 돌아가고 다음 작업을 다시 특정 시간만큼 실행시킵니다. 이러한 특징으로 인해 시분할 알고리즘이라고 불리며 특정 작업이 CPU를 독점하지 못하게 하는 것과 같습니다.

 

라운드 로빈은 퀀텀의 크기에 따라 성능이 좌우됩니다. 퀀텀이 크면 FCFS와 같아지므로 성능이 떨어지고, 퀀텀이 작으면 빈번하게 일어나는 문맥교환때문에 성능이 떨어집니다.

 

얼핏보면 SJF보다 성능이 떨어지는 것 처럼 보이지만, 두 알고리즘의 목표는 서로 다릅니다. SJF는 시스템의 처리량을 최대한 높이는 것을 목적으로 하고, RR은 모든 작업을 최대한 공평하게 다루는 것을 목적으로 합니다. 따라서 RR은 많은 사용자들이 동시에 사용하는 시스템에 적합합니다.

 

연관정보 : 멀티 쓰레드의 장점과 문제점

멀티 쓰레드(Thread)의 장점과 문제점