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

스케줄링 알고리즘

CPU 스케줄링 알고리즘은 준비 큐에 있는 프로세스들에 대해 어떤 프로세스를 CPU에 할당할지 결정한다.

각 알고리즘들을 살펴보자.

 

FCFS (First-Come, First-Served)

가장 단순한 알고리즘으로, CPU의 사용을 먼저 요청한 프로세스가 먼저 할당되도록 동작하는 비선점 알고리즘이다.

FIFO(First-In, First-Out) 자료구조인 큐(Queue)를 통하여 쉽게 구현할 수 있다는 장점을 갖는다.

하지만, 다음과 같은 상황에서 FCFS의 단점이 드러난다.

시간 단위 : millisecond

위의 예시에서 Burst Time은 프로세스가 CPU를 사용하는 시간이라 생각하면 된다.

이 상황에서 FCFS를 적용한다면, CPU는 P1, P2, P3 순서로 CPU를 할당하게 된다.

FCFS에 의해 할당된 프로세스들 (Gantt Chart)

하지만 P1의 Burst Time이 24로 다른 프로세스들에 비해 매우 긴 탓에, P2는 24, P3는 27의 시간을 기다려야만 자신의 짧은 작업을 수행할 수 있다.

P1 ~ P3의 평균 대기시간은 (0 + 24 + 27) / 3 = 17이 된다.

 

만약 P2, P3을 P1보다 먼저 수행했다면,

수행시간이 짧은 프로세스를 먼저 배치했다면?

P1 ~ P3의 평균 대기시간은 (0 + 3 + 6) / 3 = 3이 된다. 현저하게 줄어든 것을 볼 수 있다.

이를 통해 우리는 FCFS의 평균 대기시간이 일반적으로 최소가 되지 않는다는 것과, 프로세스의 Burst Time에 따라 그 값이 극명하게 변함을 알 수 있다.

 

또한, 하나의 CPU-bound 프로세스와 다수의 I/O-bound 프로세스가 존재하는 상황을 생각해보자.

CPU-bound 프로세스가 CPU를 오랫동안 차지할 동안, 다른 모든 I/O-bound 프로세스들은 자신의 입출력을 완료하고 준비 큐로 옮겨져 CPU의 사용을 기다릴 것이다.

마침내 CPU-bound의 CPU 사용이 끝나고, CPU-bound 프로세스는 입출력을 위해 내려간다. 이 때, 짧은 CPU burst를 갖는 다른 I/O-bound 프로세스들은 빠르게 CPU를 모두 사용한 뒤 다시 I/O 큐로 돌아간다. 하지만 또다시 CPU-bound 프로세스가 입출력을 마칠 때까지 기다려야 한다.

(이 과정에서 CPU는 Idle 상태가 되므로, CPU Utilization이 감소한다.)

즉, 하나의 무거운(Burst time이 큰) 프로세스를 기다리느라 Burst time이 짧은 다른 프로세스들이 자신의 기능을 수행하지 못하게 되어 CPU가 노는 시간이 발생하게 된다. 이를 Convey Effect라 한다.

 

SJF (Shortest Job First)

SJF 알고리즘은 Burst time이 짧은 프로세스를 앞서 배치하는 알고리즘이다.

따라서 다음과 같은 프로세스와 Burst time에서, SJF 알고리즘의 스케줄링을 간트 차트로 나타내면 다음과 같다.

SJF 알고리즘을 적용한 모습

평균 대기시간은 (0 + 3 + 9 + 16) / 4 = 7 이다.

이처럼 SJF 알고리즘은 최소의 평균 대기시간을 내는 최적의 알고리즘이다.

하지만, SJF 알고리즘의 문제는 프로세스의 Burst Time 길이를 알고 있어야 한다는 점에서 발생한다.

long-term 스케줄링에서는 프로세스의 시간 제한이 사용자에 의해 정의될 수 있으므로, 특정 값의 비교를 통해 SJF를 적용할 수 있지만 short-term 스케줄링에는 적용할 수 없다. 아직 실행하지 않은 프로세스의 CPU burst의 길이를 알 방법이 없기 때문이다.

 

따라서 CPU burst의 길이를 알 수는 없지만, 예측하는 기법을 통해 근사 SJF의 형태로 사용한다.

다음 CPU burst는 일반적으로 이전 CPU burst 길이들의 지수 평균(Exponential Average)을 통해 예측된다.

(이 게시물에서는 자세히 서술하진 않는다.)

CPU burst의 길이를 예측

 

SJF 알고리즘은 선점, 비선점 모두 가능하다. 

이전의 프로세스가 아직 실행 중일 때, 준비 큐에 새로 도착한 프로세스의 burst 길이가 더 짧은 경우 이를 다루는 방식에 따라 선점, 비선점이 구분된다.

선점 SJF는 이 경우 원래 실행 중이던 프로세스를 내리고 더 짧은 프로세스를 CPU에 올린다.

따라서 위의 상황을 간트 차트로 나타낸 결과는 다음과 같다.

선점 SJF 알고리즘을 적용

(이를 Shortest-Remaining-Time-First Scheduling이라고도 한다.)

 

 

 

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