Shortest Remaining Time(SRT)
- Select Function: min[s-e]
- Decision Mode: Preemptive
SRT는 SPN의 선점 버전이다.(선점 방식을 통해 TAT를 극대화한다.)
Remaining time 즉, 가장 짧은 남은 시간을 보유한 process에게 유리하다.
이는 가장 좋은 TAT 성능을 보인다.
SPN과 비슷한 단점과 장점을 가지며, Process switch overhead가 더 크다.
Highest Response Ratio Next(HRRN)
- Select Function: max[(w+s)/s]
- Decision Mode: Non-preemptive
SRN, SRT의 문제점인 longer process의 starvation의 문제를 TAT를 희생하여 해결한 스케줄링이다. 실행시간이 작거나, 기다린 시간이 긴 프로세스들이 먼저 선택된다.
짧은 프로세스를 먼저 처리하나, 기다린 시간이 오래된 longer process들도 처리할 수 있게 된다.
단점으로 실행시간 예측이 필요하며, Select Function의 계산으로 overhead가 발생한다.
가장 좋은 TAT를 보인다.
Round-Robin
- Select Function: constant
- Decision Mode: preemption
FIFO의 문제점 중 short process들이 처리되지 않는 것(convoy effect)을 줄인 스케줄링 기법이다.
short process는 대개 I/O bound process일텐데, I/O를 수행하게 되면 CPU는 idle해진다. 이 때 timer를 둬 time-out이 발생하면 process switch를 발생시키는 것이다.
FIFO + timer라고 생각하면 된다.
큐에 도착한 순서대로 진행되지만 timer로 인한 process switch를 발생시킨다.
TAT는 굉장히 나쁘지만, 응답시간을 줄이기 위함이다. short process나 long process나 응답시간이 빠를 것이다.
(time-slice가 1인 경우)
그런데 Round-Robin을 왜 사용할까? TAT면에서 너무 안 좋아 보인다.
사실 Round-Robin의 핵심은 time slice 크기이다. 이 크기가 엄청 커진다면 FIFO와 같을 것이고 0과 가까우면 SPN과 가까울 것이다.
n개의 프로세스가 존재하고 time slice가 q라고 하자. 프로세스는 최대 (n-1)q 시간을 기다려야한다. q를 줄이면 응답시간은 줄어들고 길게하면 늘어날 것이다.
예씨 1을 보면 time slice를 줄였을 때 TAT, 응답시간 모두 줄었다. 응답시간은 확실히 줄 것이다. 당연하다. process switch가 빠르게 일어나기 때문에,
그런데 TAT는 무조건 늘까? 예시 2를 보면 그렇지 않다. 이는 work load에 따라 TAT는 나빠질 수도 있고, 좋아질 수도 있다.(프로세스를 질질 끌어 맨 끝까지 간다.)
Round-Robin with System Utilization
지금까지 I/O burst process를 제외하고 스케줄링 기법들을 봤다.
I/O bound process도 고려해보자.
time slice가 너무 크다면, I/O request가 계속 들어온다 한들, long process에 막혀서 I/O가 돌지 않는다. 거기에다 B가 종료되고 CPU가 idle 해지는 상황까지 갈 수 있다.
time slice가 작으면 I/O utilization이 확실히 좋아진다.
위의 그래프는 CPU burst에 따른 process의 빈도수를 나타낸다. short process가 더 많다.
그러나 long process를 버릴 수 없다.
전형적인 process보다 큰 time slice라면 idle해지는 모습을 볼 수 있다.
작다면, q(n-1)만큼 기다려야할 것이다.(TAT 측면에서 안좋다.)
Drawback of Round-Robin
FIFO의 convoy effect를 줄이기 위해 고안된 기법이다. 하지만 여전히 long process에게 유리하다. 왜냐하면 long process는 time-slice를 다 쓸 확률이 높지만 short process는 I/O bound일 확률이 높기 때문에, 다 못쓸 확률이 높다.
Solution 1: Virtual Roud Robin
이 방법은 CPU bound process에 패널티를 부여한다. time-slice를 다 못 쓴 process를 특별한 queue에 모아놓고 CPU bound process보다 높은 우선순위를 부여한다.
Solution 2: Multi-Level Feedback Queues
이 방법은 현재 word load에 따라 time-slice를 조정하는 방법이다.
많은 queue를 만들어 놓고, time slice를 다르게 설정한다. 그리고 long process일 경우 계속해서 time-slice가 높은 queue로 옮겨진다. short process일 경우 time-slice가 작은 곳으로 간다. 이는 time-slice를 다 쓰냐 못 쓰냐로 판단되며, time-slice가 작을수록 우선순위가 높다.
그러나, 이러면 또 long process에 starvation이 나타난다. 그렇다면 w를 판단하여 오래 기다린 경우 time-slice가 작은 곳으로 옮겨준다.
Implementation
구현을 위한 고려사항은 다음과 같다.
- 몇 개의 queue를 쓸거냐?
- queue마다 scheduling 기법
- 강등과 승급의 방법
