SPN, SRTN, HRRN은 Burst time을 기준으로 한 스케줄링 기법이다!
3. SPN (Shortest Process Next)
= SJF(Shortest Job First Scheduling)
1) 비선점 스케줄링
- Time quantum 개념이 존재하지 않는다.
2) 스케줄링 기준: Burst Time을 기준으로 스케줄링을 한다.
- Ready queue에 도착한 시간은 고려하지 않고, ready queue에 있는 프로세스들 중 burst time이 짧은 프로세스부터 스케줄링한다.
3) 장점
- SPN 기법으로 스케줄링을 하면, Waiting Time의 평균이 최소화된다.(증명있음)
- 시스템에 존재하는 프로세스의 개수도 최소화된다. Ready Queue의 크기도 줄어들고, 전체 시스템의 메모리 space requirement도 줄어든다.
- 많은 프로세스들에게 response를 빠르게 줄 수 있다.
4) 단점
(1) Starvation = Indefinite Postponement : 특정 프로세스는 일찍 ready queue에 들어왔어도 burst time이 길다는 이유로 계속 밀려날 수 있다.
=> aging이라는 방법론으로 해결할 수 있다.
(2) SPN은 Burst Time을 기준으로 하는 것이며 burst time을 사전에 알고 있다고 가정하는 기법인데, 실제로 각 프로세스의 burst time을 미리 알 수 없다. 미리 알 수 없는 정보를 가지고 기준으로 삼을 수 없다. 즉 burst time으로 스케줄링하는 것은 사실상 불가능하다.
➡️ 그렇다면 왜 SPN 기법이 있는가?
이 기법을 구현할 수 있는 방법이 있기 때문이다!
프로세스 Pa가 있을 때, 그 프로세스는 CPU Burst time - I/O 사용 - CPU Burst time - I/O 사용 - CPU Burst time - I/O 사용..의 패턴을 반복할 것이다. 그렇다면 이 패턴에서 초반의 CPU burst time의 정보를 가지고, 다음 CPU Burst Time을 추정할 수 있다.
즉 정확하게 알지는 못하지만, 추정치를 통해 비교할 수 있다!
- 프로세스는 최근의 실행패턴을 이후에 반복할 가능성이 높기 때문에, 모든 burst time에 같은 가중치를 주는 단순 산술평균이 아니라 최근의 burst time에 가중치를 더 많이 주는 기하 평균을 한다.
4. SRTN (Shortest Remaining Time Next)
1) 선점 스케줄링 (SPN 기법의 선점 스케줄링 버전)
- burst time을 알고 있다고 가정 (추정하여 burst time 계산)
- 선점의 기준은 'time quantum'으로 선점하는 것이 아니라, 'burst time'으로 선점
- 현재 running 중인 프로세스가 있을 때, 그 프로세스의 남은 burst time보다 더 짧은 burst time을 가진 프로세스가 ready queue에 들어오면 선점한다.
2) 단점
SPN과 마찬가지로, 커널이 Burst time을 estimation을 해야 한다. (Estimation Overhead)
더불어 남은 remaining burst time을 계산하고 다른 burst time과 비교해야 하기 때문에, 이에 대한 오버헤드가 있다.
context switching 오버헤드가 있다.
5. HRRN (High Response Ratio Next)
1) Aging Concept
SPN 기법은 Starvation 현상이 있는데, 이를 해결하는 'aging' 기법이 있다. HRRN은 Long Burst Time process에게도 기회를 주는 aging concept를 가진 기법이다.
2) 스케줄링 기준 : High-response ration prcess first
burst time이 크더라도 waiting time이 점점 커지면 우선순위가 올라가게 되기 때문에 결국은 실행이 되도록 할 수 있다.
3) 장점
- Starvation 방지
- Aging : waiting time이 길어진 프로세스의 우선순위 증가시킴
- SPN과 비슷한 장점을 가진다. Burst time이 작을수록 response ratio가 올라가기 때문
4) 단점
- SPN 기법과 마찬가지로 burst time을 estimation하는 오버헤드
