Explain Round Robin (RR) Scheduling In Detail With Example. What Is Round Robin Scheduling
In This Topic & Blog Having Any Query Then Post your Comment and Suggestion Below
Round Robin (RR)
• Each process gets a small unit of CPU time (timequantum), usually 10-100 milliseconds. After this time
has elapsed, the process is preempted and added to the
end of the ready queue.
• If there are n processes in the ready queue and the time
quantum is q, then each process gets 1/n of the CPU
time in chunks of at most q time units at once. No
process waits more than (n-1)q time units.
• Performance
– q large FIFO
– q small q must be large with respect to context switch,
otherwise overhead is too high.
Example of RR with Time
Quantum = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
• The Gantt chart is:
• Typically, higher average turnaround than SJF, but better
response.
• FCFS Scheme: Potentially bad for short jobs!
– Depends on submit order
– If you are first in line at supermarket with milk, you don’t care who is
behind you, on the other hand…
• Round Robin Scheme
– Each process gets a small unit of CPU time
(time quantum), usually 10-100 milliseconds
– After quantum expires, the process is preempted
and added to the end of the ready queue.
– n processes in ready queue and time quantum is q
• Each process gets 1/n of the CPU time
• In chunks of at most q time units
• No process waits more than (n-1)q time units
• Performance
– q large FCFS
– q small Interleaved (really small hyperthreading?)
– q must be large with respect to context switch, otherwise overhead is
too high (all overhead)
Example of RR with Time
Quantum = 20
• Example: Process Burst Time
P1 53
P2 8
P3 68
P4 24
– The Gantt chart is:
– Waiting time for P1=(68-20)+(112-
88)=72 P2=(20-0)=20
P3=(28-0)+(88-48)+(125-108)=85
P4=(48-0)+(108-68)=88
– Average waiting time = (72+20+85+88)/4=66¼
– Average completion time = (125+28+153+112)/4 = 104½
• Thus, Round-Robin Pros and Cons:
– Better for short jobs, Fair (+)
– Context-switching time adds up for long jobs (-)
Round-Robin Discussion
• How do you choose time slice?
– What if too big?
• Response time suffers
– What if infinite ( )?
• Get back FIFO
– What if time slice too small?
• Throughput suffers!
• Actual choices of timeslice:
– Initially, UNIX timeslice one second:
• Worked ok when UNIX was used by one or two people.
• What if three compilations going on? 3 seconds to echo each
keystroke!
– In practice, need to balance short-job performance and
long-job throughput:
• Typical time slice today is between 10ms – 100ms
• Typical context-switching overhead is 0.1ms – 1ms
• Roughly 1% overhead due to context-switching