FIFO, SJF, STCF를 살펴보기 전에 Turnaround time이라는 Performance metric을 알아야 한다. Turnaround time이란 job이 도착해서 완료까지 걸리는 시간이다. 이를 수식으로 나타내면 T(turnaround) = T(completion) - T(arrival)이다. 이 시간이 짧을수록 성능이 좋다고 할 수 있다.
1. FIFO ( First In, First Out )
가장 심플한 개념이다. 먼저 들어온 JOB을 먼저 처리해주는 것이다. JOB A, B, C가 거의 동시에 순차적으로 도착하고 각각의 runtime은 20s라고 가정해보자. 그러면 A의 turnaround time은 20 - 0 = 20s, B는 40 - 0 = 40s, C는 60 - 0 = 60s라고 하자. 그러면 평균 turnaround time은 (20 + 40 + 60) / 3 = 40s이다.
그렇다면 위와 다른 가정은 다 동일하고 A의 runtime만 50s로 늘었다고 가정해보자. 그러면 A의 turnaround time = 50s, B의 turnaround time = 70s, C의 turnaroundtime = 90s로 평균 turnaround time = 70s가 된다. 이 경우에는 B와 C는 20초만 수행하면 되는데 훨씬 많은 시간을 기다려야만 하는 convoy effect가 발생한다.
2. SJF ( Shortest Job First )
위 단락에서 설명한 FIFO의 단점이 보완된 알고리즘이다. JOB들이 거의 동시에 도착한 경우 실행시간이 짧은 JOB을 먼저 수행한다. 이전 예제의 가정을 동일하게 사용해보자. A의 수행시간이 가장 기므로 가장 나중에 실행하고 B와 C를 먼저 수행한다. 그러면 B의 turnaround time = 20s, C의 turnaround time = 40s, A의 turnaround time = 90s이다. 그렇다면 평균 turnaround time은 50s이다. 이전에 비하면 성능이 좋아진 셈이다.
하지만 JOB이 동시에 도착하는 경우는 드물다. A, B, C의 수행시간은 이전과 동일하고 B, C의 도착시간이 10s라고 가정해보자. 그러면 A는 혼자 도착했으니 먼저 수행된다. 따라서 A의 turnaround time은 50s이다. B의 turnaround time은 A가 끝날 때까지 40초를 기다리고 본인이 수행되어야 하니 60s이고 C는 같은 방식으로 80s이다. 따라서 66초 정도가 평균 turnaround time이다. 이 경우 역시 convoy effect가 발생한다.
3. STCF ( Shortest Time to Completion First )
SJF의 convoy effect를 보완하기 위한 방법으로 완료까지 걸리는 시간이 짧은 것을 먼저 수행한다. 때문에 A가 실행되는 도중이어도 B의 완료까지 걸리는 시간이 더 짧으면 A에게서 중간에 뺏어와서 B를 먼저 완료시켜 줄 수 있다. 아까의 예시를 그대로 사용해보자. A가 실행중이다가 B, C가 10초에 들어왔다. 그러면 10초일 때의 상황을 보면 A는 완료까지 시간이 40초나 남았는데 B는 20초밖에 남지 않았으므로 B를 먼저 수행한다. B를 완료시키고 난 후에도 여전히 A는 완료까지 40초가 남았는데 C는 20초가 남았으므로 C를 수행하고 난 후, A를 마저 실행한다. 이 경우에 A는 B, C가 끝날 때까지 기다리므로 A의 turnaround time은 50 + 20 + 20 = 90s이고 B는 오자마자 수행하였으므로 20s이고 C는 B가 끝날 때까지 기다렸으므로 40s다. 평균 turnaround time은 50s가 된다.