SPN(Shortest-Process-Next)
- Non-preemptive scheduling(한번 할당받으면 끝날 때 까지 실행)이며, 실행시간(burst time)이 가장은 프로세스를 먼저 처리한다.
장점으로는 평균 대기시간(Waiting Time)을 최소화 할 수 있다. 또한 프로세스 수를 최소화 할 수 있기 때문에 스케줄링 부하가 줄어들고, 메모리를 절약할 수 있다. 그리고 많은 프로세스들에게 빠른 응답시간을 제공한다.
단점으로는 Starvation(무한대기, 기아현상) 현상 발생이다. BT가 긴 프로세스는 자원을 할당받지 못할 수 있다. BT가 짧은 프로세스가 계속 들어오면 긴 프로세스보다 먼저 일을 처리하기 때문이다. 또한 정확한 실행 시간을 알 수 없기 때문에 실행시간 예측 기법이 필요하다.
SRTN(Shortest Remaining Time Next)
- SPN의 변형이다. Peremptive scheduling이며 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점된다. SPN의 장점을 극대화 한 것이다. 단점으로는 프로ㅔ스 생성 시 총 실행 시간을 예측하는 것이 필요하다. 그리고 잔여 실행시간을 계속 추적해야 하기 때문 Context switch overhead가 계속 발생한다. 단점 때문에 현실적으로 구현은 어렵다. 이상적이지만 비현실적이다.
HRRN(High-Response-Ratio-Next)
- SPN의 변형이며, Non-preemptive이다. Starvation을 고려해서 SPN에 Aging concepts을 더했다. 이는 프로세스의 대기 시간을 고려한 것이다. 아래는 응답률을 구하는 식이다.
Response ratio(응답률) = WT + BT / BT
오래 기다렸으면 응답률이 높아지고, 응답률이 높은 프로세스 먼저 실행한다. 평균 대기 시작을 줄인다는 SPN의 장점을 최대화 할 수 있다. 하지만 여전히 실행 시간 예측 기법이 필요하다(overhead 발생).
한계
- SPN, SRTN, HRRN은 효율과 성능을 고려했다. 하지만 실행시간 예측이라는 문제가 남아있다. 그래서 이문제를 해결해주는 것이 MLQ(Multi-level Queue), MFQ(Multi-level Feedback Queue)다.
