[OS] Process Scheduling II (Round Robin, SRT, HRRN)

Round Robin

Round Robin은 스케줄링 알고리즘에서 가장 중요하다고 해도 과언이 아닌 알고리즘이다. Round Robin은 기본적으로 FIFO와 동일하다. FIFO가 하나의 Process를 전부 끝내고 나서 다음 Process로 넘어가는 것과 달리 Round Robin은 일정한 시간 간격을 두어 Process를 Time-Out 시켜버린다. 일정한 시간 간격을 Quantum이라고 한다. Process가 Quantum을 다 사용하면 해당 Process는 Time-Out되어 다시 Ready Queue로 보내버린다. 따라서 FIFO에서는 Long한 Process들이 우선적으로 선택되는 Convoy Effect가 자주 발견이 되었는데 이 Side Effect를 방지할 수 있는 것이 Round Robin이다. 이 방식은 Overhead가 작다. Quantum을 확인하고 계속 pop, front만 해주면 되기 때문이다. 따라서 Selection Function은 Constant가 되며, Process를 전부 끝내는 것이 아니라 시간 안에 끝내지 못하면 다른 것으로 넘어가기 때문에 Decision Mode는 Preemption이 된다. 

위의 그림을 보자. Time Quantum이 4일때를 가정한 그림이다. 0시점에서 2시점까지 A는 잘 실행된다. 이제 2에서 6시점을 보면 Process B는 Time Slice를 4를 소진했기 때문에 Time Out되고 Queue에 들어간다. 4시점에는 C가 들어와있고, 6시점에는 CDB가 들어가게 된다. 여기서 CDB 순서가 될 수도 있고, CBD 순서가 될 수도 있는데 이는 OS가 어떤 것을 먼저 Queue에 먼저 넣는지에 따라 다르다. 여기에서는 편의상 Time Out된 Process가 제일 뒤로 간다고 가정하겠다. C는 정상적으로 4의 Time Slice를 전부 소진했고, D는 4를 소진했으니 D의 한개의 Slice는 다시 Queue에 넣어지게 된다. 그 후 남아있는 B와 E를 Queue에 들어온 순서대로 수행한 후에 D까지 수행하면 끝마치게 된다. Turnaround Time은 A: 2, B: 15, C: 6, D: 14, E: 11 이고 Average Turnaround Time은 9.6이 된다. 

 

Round Robin에서는 Time Quantum의 길이를 잘 Design하는 것이 가장 중요한 Isuue이다. Time Quantum을 너무 작게 하면 할수로 Short Job들이 우선적으로 수행되는 경향이 있어 SPN과 같이 동작하게 되는데, 이는 경국 길이가 길 Process들이 뒤로 밀리는 경향이 생겨버린다. 또한 Time Quantum이 너무 작다면 Context Switch를 사주하게 되는데 이는 앞에서 다루었듯이 Overhead가 상당히 크다. 반대로 Round Robin의 Time Quantum을 너무 길게 설정하면 FIFO같이 동작하게 된다. 따라서 절충점이 필요하다. 아래의 그림은 Time Quantum을 1로 잡았을 때 긴 Process가 뒤로 밀리는 경향을 보여주는 그림이다. 따라서 오히려 성능적으로 FIFO가 더 유리할 수 있다. 

Ready Queue에 N개의 Process가 있다고 하면, 최악의 경우에도 Process는 (N-1)q 시간 만큼 걸리지는 않는다. 이때 q가 작아질수록 SPN에 가까워지고, q가 커지면 FIFO에 가까워 진다고 정리하면 좋겠다. 

SRT (Shortest-Remaining-Time)

다음으로 살펴볼 알고리즘은 SRT이다. 이 알고리즘은 SPN의 개선된 버전이라고 보면 될 것이다. SPN과 다르게 Preemption 전략을 취하고 있다. 또한 Selection Function도 min[S]가 아닌 min[S - E]가 된다. 따라서 이 알고리즘은 Process가 들어올 때 S - E를 비교하게 된다. 이 비교를 하고나서 min값을 선택에 Preemption된다. 이는 가장 Optimal하다고 할 수 있는 알고리즘이다. Turnaround Time관점에서 SPN보다 뛰어난 성능을 보인다. 하지만 문제는 Overhead가 매우 크다는 단점이 있다. 모든 Process에 대해서 최솟값을 계산해야 하고, 최솟값을 유지해야하기 때문에 최소 O(n)이 걸릴것이다. 또한 이 역시 S - E값이 크다면 Long Process에 대한 Starvation이 발생할 수도 있다. 

시간대에 아래에 새로운 Process가 들어왔을 때의 min값을 계산해놓았다. 최솟값을 비교하는 과정에서 tie 상황이 일어날 수도 있다. 이때의 Tie-Breaker는 max[W]가 될 수도 있고, pid값이 될 수도 있는데 이는 OS마다 규정하는 것이 다르다. 여기에서는 임의로 max[W] 전략을 사용했다. Turnaround Time은 A:2, B:13, C: 4, D:14, E:2 이고, 평균은 7이 된다. 이는 우리가 지금까지 살펴본 Turnaround Time중 최상의 성능을 보여준다. 

HRRN (Highest-Response-Ration-Next)

HRRN은 Response Ratio가 가장 높은 값을 고르는 것이다. Response Ratio란 정규화된 Turnaround Time이다. 이는 실제 Service Time과 Turnaround Time에 대한 비율이다. 따라서 Ratio는 (q + s) / s 가 된다. 선택함수는 아래와 같아진다.

$$ Selection Function : max[ \frac{q+s}{s} ] $$

Decision Mode는 Non-Preemption이다. HRRN이 나온 이유는 SPN이나 SRT에서 Long Process들에게 Starvation이 발생한다는 것이었다. 이제는 위의 Ratio를 통해서 Process를 선택하기 때문에 s가 작을수록 값이 커지고, q가 길어질수록 값이 커진다. 이래서 Long Process도 뒤로 밀리지 않고 선택을 받아 수행될 수 있는 것이다. HRRN을 Starvation을 회피하기 위한 Corner Case라고 말하기도 한다. 

이떄의 Turnaround Time은 A: 2, B: 7, C: 9, D: 14, E:7 이고, Average Turnaround Time은 7.8이 된다. 물론 HRRN을 사용하게 되면 SPN이나 SRT보다는 응답성이 떨어진다. 그러나 비율을 고려하기 때문에 어느정도 공평하다고 할 수 있을 것이다. 또한 여전히 예측값인 S를 사용하기 때문에 구현의 어려움 또한 존재한다. 

Reference

William Stallings. (2018). Operating Systems: Internals and Design Principles (8th Edition): Pearson.