[OS/운영체제] CPU 스케줄링 (CPU Scheduling) - (3)

Priority Scheduling

각 프로세스에 우선도 값을 부여하여, 우선도 값이 높은 프로세스를 CPU에 우선 할당하는 알고리즘이다.

(즉, SJF도 Burst Time이 짧은 프로세스가 높은 우선도를 갖는 Priority Scheduling의 한 경우로 볼 수 있다.)

동일한 우선도에 대해서는 FCFS 알고리즘을 적용한다.

 

우선도는 정의하기 나름이다. 1이라는 우선도가 3이라는 우선도에 비해 낮을 수도 있고, 높을 수도 있다.

(참고한 교재 『Operating System Concepts』 에서는 낮은 숫자를 높은 우선도로 두었다.)

Priority Scheduling이 적용된 모습 (선점)

 

우선도는 내부적 또는 외부적으로 정의될 수 있다.

내부적으로 정의된 우선도는 프로세스의 우선도를 계산하기 위해 측정 가능한 양을 사용한다. 시간 제한이나, 메모리 요구량 등이 이에 해당한다.

외부적으로 정의된 우선도는 운영체제의 외적인 요소를 사용한다. 해당 프로세스의 중요도, 들어간 금전적 비용 등이 이에 해당한다.

 

Priority Scheduling 또한 선점 비선점 모두 가능하다. SJF에서와 같이 더 높은 우선순위를 가진 프로세스가 도착했을 때 어떻게 동작하느냐에 따라 선점 또는 비선점이 된다.

 

Priority Scheduling의 가장 큰 문제점은 Infinate Blocking(Starvation)이다.

실행될 준비는 되었지만 CPU에 할당되기를 기다리는 프로세스를 Block 되었다고 한다. 우선도에 의해 낮은 우선순위를 가진 프로세스들은 CPU에 높은 우선순위를 갖는 프로세스들이 계속 들어온다면 장시간 대기하는 것을 넘어 아예 CPU에 올라갈 수 없게 될 수 있다.

이러한 Starvation 문제를 해결하는 방법으로는 Aging이 있다. Aging은 시간이 지날수록 우선도 값을 변화시켜 우선순위를 증가시키는 것으로, 낮은 우선순위의 프로세스도 기다리다 보면 증가된 우선순위를 통해 언젠간 CPU에 할당되도록 해 준다.

 

RR (Round-Robin)

RR 스케줄링 알고리즘은 시분할 시스템을 위해 설계되었다. FCFS와 유사하지만, 선점이 가능하도록 하여 프로세스의 교체가 가능하다.

Time Quantum (또는 Time Slice) 이라는 시간 단위를 두어, 이 시간 단위마다 돌아가면서 프로세스를 진행시킨다. 만약 프로세스의 Burst Time이 Time Quantum보다 짧을 경우에는, 프로세스의 길이만큼만 실행하고 다음 프로세스를 CPU에 할당한다.

Round-Robin 알고리즘을 적용 (Time Quantum = 4)

위 그림처럼, P1 - P2 - P3 의 순서로 Time Quantum 만큼씩 실행되며 동작한다.

 

RR 알고리즘의 성능에는 Time Quantum의 길이가 크게 작용한다.

Time Quantum이 매우 크다면 RR 알고리즘은 FCFS와 유사하게 동작할 것이고, Time Quantum이 매우 작다면 Processor Sharing 의 형태가 되어 모든 프로세스가 1/n 배 속도로 동작하게 된다.

또한 Time Quantum이 작아질수록 프로세스의 Context Switch가 그만큼 더 많이 발생되므로, 오버헤드가 증가한다.

Time Quantum에 따른 평균 Turnaround Time

일반적으로는 CPU Burst의 80%에 해당하는 값이 Time Quantum보단 짧도록 한다. 

 

Multilevel Queue

프로세스들이 다른 그룹으로 분리되어 다루어져야 할 경우에 사용하는 알고리즘이다.

예를 들어, foreground/background로 구분되는 프로세스들은 분류에 따라 각자 다른 응답 시간이 요구되며, 각자 다른 스케줄링 기준을 가져야 할 것이다.

 

다중 큐 알고리즘은 준비 큐를 유형에 따라 나누어 기준에 따라 분류된 프로세스들을 할당한다.

나누어진 각 큐는 각자 자신의 스케줄링 알고리즘을 가질 수 있다.

Multilevel Queue 알고리즘

 

프로세스들은 메모리 크기, 프로세스 우선도 값, 프로세스 유형 등에 의해 분류될 수 있다.

 

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.