스케줄링 알고리즘 / RR

Round Robin

Time Sharing System에서는 주기적으로 Context Switching을 진행한다. Running 상태의 프로세스가 I/O 작업을 수행하지 않더라도 일정시간이 되면 Ready 상태로 만드는데, 이 때 사용하는 스케줄링 방법이 라운드로빈 스케줄링이다. 라운드로빈이라는 이름처럼 뱅뱅 돌면서 프로세싱을 수행하게 된다.

특징

1. Time Slice(Time Quantum)

• 라운드로빈 스케줄링에서는 일정시간만다 프로세스가 강제로 교체되는데, 이 때 사용되는 일정시간이 바로 Time Slice (타임 슬라이스, Δ 델타로 표시)이다. 다른말로 Time Quantum (타임 퀀텀)이라고도 한다. 라운드로빈의 ATT(Average Turnaround Time)은 Time Slice에 매우 큰 영향을 받게 되는데, 그럼 양 극한인 무한대와 0으로 Time Slice를 보내면 어떻게 될까?
  -
  - Time Slice → 무한대 :
  FCFS 스케줄링과 동일해진다. 해당 프로세스가 끝나야만 전환된다
  - Time Slice → 0 :
  Processor Sharing 상태이다. 사실상 3개의 프로세스가 동시에 수행된다.
  그러나 Context Switching의 Overhead가 너무 커지게 된다 (디스패쳐 등)

2. 라운드로빈 스케줄링은 반드시 선점 스케줄링이다.
해당 프로세스가 Time Slice만큼 작업을 수행하면 프로세스가 진행중이여도 강제로 다른 프로세스에게 작업을 넘겨줘야한다. 때문에 라운드로빈은 가장 대표적인 선점 스케줄링 기법이다.

실습) 위의 그림을 바탕으로 표를 채우시오, (𝞭 = 2)

Process ID	Arrival time	Burst Time(BT)	Wating Time(WT)	Turnarround Time(TT)	Normalized TT NTT = (TT/BT)
P1	0	3	2	5	5/3
P2	1	7	11	18	18/7
P3	3	2	2	4	4/2
P4	5	5	10	15	15/5
P5	6	3	9	12	12/3

참고)
Average response time(ATT)(𝞭 = 2) = (5+18+4+15+12) / 5 = 10.8
Average response time(ATT)(𝞭 = 3) = (3+19+5+14+8) / 5 = 9.8
-> Time quatum 에 따라 ATT가 달라진다.