Scheduling Algorithms
FCFS
First-Come-First-Serve Scheduling
먼저 들어간 것을 먼저 실행하는 알고리즘이다. 가장 단순한 스케줄링 기법이다. 순서대로 실행되므로 강제성이 없는 비선점 스케줄링이다. 레디큐로써 FIFO를 사용하면 용이하게 관리된다. 앞에 있는 프로세스가 끝날 때까지 기다려야 하기 때문에 평균 대기 시간이 매우 클 수가 있다.
위 사진에서 첫번째 표와 같이 프로세스 P1, P2, P3 순서로 도착했다면 P1은 대기시간이 0, P2는 대기시간이 24, P3는 대기시간이 27이다. 따라서 평균 대기시간은 (0+24+27)/3 = 17이다.
만약 두번째 표와 같이 프로세스 P2, P3, P1 순서로 도착했다면 P2는 대기시간이 0, P3는 대기시간이 3, P1은 대기시간이 6이다. 따라서 평균 대기시간은 (0+3+6)/3 = 3이다.
이처럼 어떤 프로세스가 먼저 도착하느냐에 따라 평균 대기시간은 천차만별이다.
예를 들어 1개의 CPU-bound(A)프로세스와 여러개의 I/O-bound(B)프로세스가 FCFS를 사용한다. A가 CPU를 사용하고 있는 중에 B는 I/O작업을 끝내고 CPU를 사용하기를 기다리고 있다. A가 CPU사용을 완료하고 B는 아주 짧게 CPU를 사용하는 동안 A는 I/O를 완료하고 B에게서 CPU를 넘겨 받는다. 그리고 A의 CPU 사용을 또 길게 기다려야 한다. 이것처럼 B가 A를 끝날 때까지 짧은 CPU사용을 위해 쫓아다니며 길게 기다리는 것을 convoy effect라고 부른다.
convoy effect 때문에 CPU와 I/O장치들의 기다리는 시간이 커지면서 장치들의 사용률이 낮아진다.
이것을 해결하기 위한 알고리즘이 SJF(Short Job First)이다.
SJF
(Shortest Job First)
다음에 수행해야 할 CPU burst들 중에서 가장 작은 수행시간을 가지는 프로세스부터 선택한다. 만약, 2개 이상의 프로세스가 모두 동일한 수행시간을 가진다면, 그들 중에서는 FCFS로 스케줄링한다.
우선순위가 실행시간이 짧은 것부터 정해진다.
위 사진에서 실행시간이 가장 짧은 것은 P4이다. 그리고 P1, P3, P2 순서로 실행시간이 짧다. SJF는 도착하는 대로 수행하는 것이 아니고 레디큐에 받아 놓고 수행한다. 평균 대기시간은 (0+3+9+16)/4=7이다. 만약 FCFS 스케줄링이라면 평균 대기시간은 (0+6+14+21)/4=10.25으로 SJF가 FCFS보다 대기시간이 더 적은 것을 알 수 있다.
SRTF
(Shortest-Remaining-Time-First)
잔여 CPU burst가 가장 작은 프로세스를 선택한다. 이 알고리즘은 SJF의 preemptive version이다. 프로세스의 레디큐에는 도착시간이 명시되어야 한다. 프로세스 수행중 다른게 레디큐에 들어오면 잔여시간을 계산하여 어떤 것을 먼저 수행할지 결정한다.
프로세스 P1, P2, P3, P4 순서로 도착했다고 하자.
t=1, 그럼 P1먼저 수행될 것이고 P2가 도중에 도착할 것이다. 그럼 이때 잔여시간을 비교한다. P1의 잔여시간은 8-1=7이고 P2의 잔여시간은 4이므로 P2가 선택되어 수행된다.
t=2, P2 수행중 P3가 도착할 것이고 레디큐의 모든 프로세스의 잔여시간을 계산한다. P1의 잔여시간 7, P2의 잔여시간 3, P3의 잔여시간 9로 P2가 선택된다.
t=3, P4가 도착한다. 2번과 같이 잔여시간을 계산한다. P1: 7, P2: 2, P3: 9, P4: 5. P2가 선택되어 P2가 계속 수행된다.
t=5, P2가 끝나고 잔여시간을 계산한다. P1: 7, P3: 9, P4: 5. P4가 선택되고 계속 수행된다.
t=10, P4가 끝난다. P1이 선택되고 계속 수행된다.
t=17, P1이 끝난다. P3가 선택되고 계속 수행된다.
따라서 대기시간(시작시간-도착시간)은 순서대로 9, 0(P2는 들어오자마자 수행됨), 15, 2이다. 평균 대기시간은 6.5이다.
