SPN (Shortest-Process-Next)
- SJF(Shortest-Job-First) 스케줄링과 동치.
- burst time (실행시간)이 가장 작은 프로세스를 먼저 처리하는 기법이다.
- 비선점 스케줄링이다.
- SJF + 선점 -> SRTF(Shortest Remaining Time First)
특징
1. SJF는 Average Waiting Time이 짧다
SJF와 FCFS와 AWT(Average Waiting Time)를 비교해보자. 3개의 프로세스 P1, P2, P3가 순서대로 있고 각각 대기시간이 24(대변), 3(소변), 3(소변) msec이라고 해보자. 만약 FCFS 스케줄링을 적용하여 가장 먼저 도착한 P1부터 실행하면 P1의 대기시간은 0msec(바로실행), P2의 대기시간은 24msec, P3의 대기시간은 27msec으로 평균 대기시간은 (0 + 24 + 27) / 3으로 17msec이 된다.
그러나 SJF를 적용하여 P2, P3, P1 순으로 실행한다면 P2의 대기시간은 0msec, P3의 대기시간은 3msec, P1의 대기시간은 6msec이 되어 평균 대기시간은 (0 + 3 + 6) / 3으로 3msec이 된다. 수학적으로도 SJF가 최적의 결과를 낸다는 것이 증명되었다. (여기에서 증명은 중요한게 아니니 생략한다)
2. 그러나 SJF는 비현실적인 스케줄링 기법이다.
위처럼 프로세스를 실행하기도 전에 그 프로세스가 얼마걸릴지 알고, 짧은 순서대로 실행할 수 있다면 참 좋겠지만, 프로세스 시작전에 프로세스가 얼마나 걸릴지 어떻게 알겠는가. 즉, SJF는 이상적이고 매우 빠른 스케줄링 기법이지만 실행하기 전에 그 프로세스가 얼마나 걸릴지 모르기 때문에 어떠한 예측 과정을 거쳐야한다. 때문에 현실적으로 SJF를 그대로 적용하는 것은 매우 어렵다.
+) 예측은 어떻게 할까?
일반적으로 Time Sharing System을 지원하는 OS라면 프로세스가 계속 실행(Running)되는 것이 아니라 일정 분량의 작업을 수행하고 다시 Ready Queue에 들어가거나(Ready), I/O 작업을 실행하기 위해 Device Queue에 들어간다.(Waiting) 프로세스가 CPU의 서비스를 받을 때마다 CPU는 프로세스별로 어떤 프로세스가 한번의 서비스에서 얼마나 많은 CPU Time을 소모했는지 계속해서 기록해놓다가 미래에 일어날 작업의 CPU 시간을 예측하게 된다. 그러나 이런 예측과정을 거치기 위해서는 더 많은 오버헤드가 발생한다는 단점이 있다. (Context Switching은 매우 잦기 때문에 오버헤드가 굉장히 많이 일어나게 된다)
3. SJF는 비선점 스케줄링이지만, SRTF는 선점 스케줄링이다.
일반적으로 SJF 스케줄링은 비선점 스케줄링 (non Preemptive) 이다. 그러나 약간 바꾸면 선점 스케줄링으로도 사용 가능하다. SJF의 선점 스케줄링 버전은 SRTF(Shortest Remaining Time First)라고 불린다.
-> P2에서 Starvation 발생
SRTN (Shortest Remaining Time Next)
- SPN의 변형
- Preemptive scheduling : 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
- 장점 :
ㆍSPN의 장점 극대화 - 단점 :
ㆍ프로세스 생성 시, 총 실행 시간 예측이 필요함
ㆍ잔여 실행을 계속 추적해야함 = overhead
ㆍContext switching overhead
-> 구현 및 사용이 비현실적 (총 실행 시간 예측, 잔여 실행 추적이 힘듬)
HRRN (High Response Ratio Next)
- SPN의 현실적인 변형 (SPN + Aging concepts, Non-preemptive scheduling)
- Aging concepts : 프로세스의 대기 시간(WT)를 고려하여 기회를 제공
- 스케줄링 기준
ㆍ Response ratio가 높은 프로세스 우선 - 응답률 Response ratio = (WT + BT) / (BT) : BT 대비 얼마나 기다렸는가
ㆍSPN의 장점 + Starvation 방지
ㆍ실행 시간 예측 기법 필요 (overhead)
