스케줄링 알고리즘_Round Robin(RR)

Round Robin(RR) Algorithm

 

프로세스를 ready queue에 도착한 순서대로 스케줄링 하되, CPU를 점유할 수 있는 최대 시간(time quantum)을 정해 놓고 해당 시간이 지나면 다음 프로세스를 스케줄링 하는 방식입니다. Running 중이던 프로세스가 중간에 interrupt 혹은 system call을 받으면, 정해진 time quantum을 모두 사용하지 못하고 CPU에서 내려오게 됩니다. 그러나 중간에 아무런 방해를 받지 않고 쭉 수행되게 된다면, CPU의 timer가 interrupt를 발생시켜 커널 모드로 전환되게 됩니다. 

 

Round Robin Algorithm의 성능은 time quantum의 길이에 따라 달라지게 되는데,

 

1) time qunatum의 길이가 무한하다면, FCFS(First Come First Served)와 같아집니다.

2) time quantum의 길이가 매우 작다면, reponse time(반응 시간)은 좋아지나 context switching이 빈번하게 발생함에 따라 overhead가 커지고 cpu utlization이 떨어집니다.

 

통상적으로는 CPU burt time의 80% 정도를 time quantum으로 지정하고 있으며, Linux의 경우 time qunatum을 60ms 정도로 지정하고 있다고 합니다.

 

Example

 

 

Ready queue에 P1, P2, P3 순서로 프로세스가 도착했다면, P1 -> P2 -> P3 -> P1 -> P2 .... 순서대로 스케줄링이 이루어집니다. time quantum의 값이 4 이므로, 각 프로세스가 한번 스케줄링 되었을 때 CPU를 점유할 수 있는 최대 시간은 4가 됩니다. 

 

가장 먼저 P1이 스케줄링 된 뒤, Burst Time 24 중 4만큼 실행이 되고 timer interrupt가 발생하여 P1은 CPU에서 내려오게 됩니다.

다음으로 P2가 스케줄링 되는데, P2의 Burst time 3은 time quantum 4보다 작으므로 모두 수행이 되고 프로세스는 종료됩니다. 

P3도 P2와 마찬가지로 스케줄링 되어 모든 작업이 수행되고 다시 P1이 스케줄링 됩니다.

 

이 때, P2와 P3가 모두 종료되고 P1만 남는다 하더라도, time quantum은 여전히 4이기 때문에 P1은 4만큼씩만 실행이 가능합니다. 따라서 P1은 추가적으로 5번 더 스케줄링 되어 모든 프로세스가 종료됩니다.