FCFS

First Come, First Served의 약어 이다.
먼저 온것을 먼저 대접한다는 뜻으로, 처음 CPU 를 요구한 프로세스가 CPU를 처음으로 사용한다는 의미를 가진 스케줄링 알고리즘 이다.

이에대한 설명을 보니, 자연스레 FIFO가 생각난다. FIFO하면 떠오르는것이 또 있지 않은가? 먼저 들어온것이 먼저 나가는 Queue이다. 맞다. FCFS를 구현할 때 Queue자료구조를 이용해서 구현을 한다.

이 FCFS는 스케줄링 특성상 비선점 스케줄링 알고리즘을 사용하며, CPU를 사용하고 있는 프로세스 자기 자신이 CPU를 놓아줄 때까지 CPU를 다른 프로세스에게 양보하지 않는다.이를 보고 콘보이 효과라고 한다.

자, 이를 토대로 보면 FCFS 는 비선점 스케줄링으로, 평균 대기시간이 정말 형편이 없는 수준이다. 하지만, 다른 관점에서 보면 이는 모든 프로세스를 공평한 조건으로 CPU를 사용할 수 있으며, 대기시간을 예측할 수 있다.

SJF

Shortest Job First의 약어 이다.

시간이 가장 짧은 작업을 먼저 작업한다는 뜻으로, 가장 실행시간이 짧은 프로세스가 먼저 CPU를 사용한다는 의미를 가진 스케줄링이다.

SJF는 선점 스케줄링과 비선점 스케줄링 이 두가지의 종류를 가진다. 선점형 SJF 는 SRTF라고도 한다. SJF는 스케줄링 알고리즘들 중 가장 짧은 평균 대기 시간을 가지는 스케줄링 알고리즘이다.

하지만, 위 내용만 보고 꼭 장점만이 가득한 알고리즘은 아니다.
SJF에서 최소의 오버헤드로 최적의 성능을 보장하도록 알고리즘을 구현하는 난이도는 상당히 높다.
또, 선점형 SJF즉, SRTF에서는 프로세스끼리 서로 끼어들기 때문에 다음 CPU 점유 시간을 예측하기에는 매우 어렵다. 즉, SJF는 미래를 예측하는 알고리즘을 구현해야하기때문에 선점형 SJF(SRTF)는 구현하는것이 힘들다.

SRTF

Shortest Remaining Time First의 약어이다. 위에서도 몇 번 언급을 하였는데, 선점형 SJF 스케줄링을 SRTF라고 하기도 한다고 했다.

Priority Scheduling

높은 우선순위를 가진 프로세스를 먼저 CPU 에 할당하는 스케줄링 이다.

우선순위가 높은 프로세스를 먼저 할당하여 작업을 끝낸다는 장점이 있지만, 우선순위가 낮은 프로세스는 언제 할당이 될 지 모르는 기아현상이 발생하게 된다.

이러한 문제를 해결하고자 Aging-Method기법이 탄생하였다.
이 기법은 모든 프로세스는 Ready → Running 상태로 흐름이 흘러가는데, 이 때 Ready상태에 있는 프로세스들은 Ready Queue에 들어가게 된다. 여기서 우선순위가 낮은 프로세스가 Ready Queue에 너무 오랜기간 기다리게 되면 해당 프로세스의 우선순위를 계속해서 높혀주는 기법이다.

이 우선순위 스케줄링은 SJF에서의 예측 CPU점유시간과 동일한 역할을 수행한다. 이게 무슨소리냐, 예측 CPU의 대기시간이 짧은 프로세스부터 우선 CPU를 사용할 수 있도록 해주는 것이 매우 흡사하다.

Round Robin

RR이라고도 불리는 이 Round Robin 스케줄링은 모든 프로세스가 시간을 공평하게 나누어 CPU를 사용하는 알고리즘이다. 정해진 시간이 끝나면 CPU에 할당되어있던 프로세스들은 선점형으로 추방을 당하고 레디큐에 다시 들어가게 된다. 여기서 나오는 “정해진 시간”은 Time Quantum 이라고 한다.

만약 레디큐에 n개의 프로세스가 존재하고, q의 Time Quantum을 가지고 있다하면 모든 프로세스는 (n-1)q 의 시간안에 CPU를 사용할 수 있음을 보장받는다.

SJF와 잠깐 비교를 해본다면,

프로세스가 CPU와 반응을 하는 속도를 따지자면 Round Robin이 더 좋지만,
프로세스 간 대기시간을 따지면 SJF 스케줄링이 더 좋다 !