CPU Scheduling - Scheduling Algorithm_4

Round Robin(이하 RR) Algorithm

 

RR알고리즘은 Process에게 일정 시간동안 CPU의 제어권을 주고 시간이 종료되면

다음 Process에게 제어권을 넘기는 알고리즘이다.

 

주로 Time-Sharing System에서 사용하는 알고리즘으로 FCFS 알고리즘에 Time Quantum q(사용제한시간)을 넣어

 

Preemptive 기능을 추가시키고 Ready Queue를 Circle Queue로 구현하여

대기 중인 Process를 순환하면서 제어권을 주는 방법이다.

 

보통 Time Quantum(이하 q)은 10~100 milliseconds정도로 정한다. 만일 Process가 제한시간 q가 끝나기 전에 수행이 종료되면

 

Ready Queue에서 다음 Process를 찾아서 수행시킨다. 하지만 만일 Process가 제한시간 q안에 완료하지 못했을 경우

 

Interrupt가 발생하여 다음 Process로 넘어가기 위해 Context Switching이 발생한다. 예를 들어보자.

 

아래와 같이 Process P1, P2, P3이 있고 CPU-Burst Time이 아래와 같다고 하자. 이때 Time Quantum q는4 milliseconds이다.

 

 

 

 

이를 RR 알고리즘에 따라 수행한 결과를 Grantt Chart로 만들어 보면 아래와 같다.

 

 

 

 

이때 Average Waiting Time은 (6+4+7)/3 = 5.66 milliseconds이다.

 

RR 알고리즘에서 n개의 Process가 존재하고 Time Quantum이 q라면 각각의 Process는  ( n - 1 ) x q 만큼 기다려야

 

Dispatch되어 제한시간 q를 얻을 수 있다.

 

그렇다면 Time Quantum과 Context Swithcing 그리고 Turnaround Time과의 관계를 살펴보자.

 

Turnaround Time이란 Process가 수행종료될때 까지 걸리는 시간을 말한다.

 

먼저 아래 그림을 살펴보자.

 

 

 

 

위의 그림을 보면 알 수 있듯이 Time Quantum이 길어지면 Context Switching 빈도가 줄어들고 Turnaround Time이 짧아 진다.

 

반대로 Time Quantum이 짧아지면 Context Switching 빈도가 늘어나고 Turnaround Time가 길어진다.

 

이번에 예를 들어 보자. CPU-Burst Time이 10인 P1, P2, P3가 있을때 다른 Time Quantum일 때 무엇이 달라질까?

 

 

 

 

위의 그림은 Time Quantum이 1인 System이다. 이때 Average Turnaround Time은 (28+29+30)/3 = 29 milliseconds이다.

 

 

위의 그림은 Time Quantum이 10인 System이다. 이때 Average Turnaround Time은 (10+20+30)/3 = 20 milliseconds이다.

 

정확히 얘기하면 Time Quantum과 Turnaround Time은 반비례 하지는 않지만 Time Quantum내에 Process가 종료된다면 개선되는건 사실이다.