CPU 스케줄링 FIFO, SJF, STCF, RR

FIFO은 선입선출(First In Frist Out, FIFO) 많은  장점을 가진다. 단순하고 구현하기 쉽다. 

간단하게 예를 스케줄 해보자. 시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정하자.

간발의 차이로 A,B,C 순서대로 도착했다고 가정하자. 또한 각 작업은 10초 동안 실행된다고 가정하자. 

이 작업들의 평균 반환 시간은 얼마인가? 

 

 

 

 

 

 

선입선출(First In First Out, FIFO)

A는 10, B는 20, C는 30에 종료했다는 것을 알 수 있다. 세 작업IFO은 선입선출(First In Frist Out, FIFI) 많은 장점을 가진다. 단순하고 구현하기 쉽다. 

간단하게 예를 스케줄 해보자. 시스템에 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정하자.

간발의 차이로 A,B,C 순서대로 도착했다고 가정하자. 또한 각 작업은 10초 동안 실행된다고 가정하자. 

이 작업들의 평균 반환 시간은 얼마인가? 

A는 10, B는 20, C는 30에 종료했다는 것을 알 수 있다. 세 작업의 평균 반환 시간은 (10+20+30) 3 = 20이다. 반환 시간의 계산은 쉽다.

 

 

 

 

 

 

 

 

최단 작업 우선(Shortest Job First, SJF)

SJF은 가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다. 

B, C, A 순서로 실행시킴으로써 SJF는 평균 반환 시간을 110초에서 50초로 2배 이상 향상시켰다. 

모든 작업이 동시에 도착한다면 SJF가 최적의 스케줄링 알고리즘임을 증명할 수 있다.

 

 

 

 

 

 

 

 

최단 잔여시간 우선(Shortest Time-to-Completion First, STCF)

이 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 실행 시간을 가진 작업을 스케줄한다. 

STCF는 A를 선점하고 B와 C를 끝날 때까지 실행시킨다. 그 결과 평균 반환 시간이 단축되어 50초가 된다. 작업들이 동시에 도착할 경우, SFJ가 최적의 결과를 낸다는 것을 고려하면, STCF가 최적의 스케줄링이 되는 이유를 쉽게 알 수 있다.

 

 

 

 

 

 

 

 

 

라운드 로빈(Round-Robin, RR)

응답 시간 문제를 해결하기 위하여 라운드 로빈 스케줄링이라 불리는 스케줄링 알고리즘을 도입한다. 

기본 발상은 간단하다. RR은 작업이 끝날때까지 기다리지 않는다. 대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환된다. 

3개의 작업 A, B, C가 시스템에 동시에 도착하고, 각각 5초간 실행된다고 가정한다. SJF 스케줄러는 다른 작업을 실행하기 전에 각 작업을 종료할 때까지 실행한다.