Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way.
- It is simple, easy to implement, and starvation-free as all processes get fair share of CPU.
- One of the most commonly used technique in CPU scheduling as a core.
- It is preemptive as processes are assigned CPU only for a fixed slice of time at most.
- The disadvantage of it is more overhead of context switching.
Illustration:
[ad type=”banner”]
[ad type=”banner”]
How to compute below times in Round Robin using a program?
- Completion Time: Time at which process completes its execution.
- Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time
- Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time
In this post, we have assumed arrival times as 0, so turn around and completion times are same.
The tricky part is to compute waiting times. Once waiting times are computed, turn around times can be quickly computed.
Steps to find waiting times of all processes:
1- Create an array rem_bt[] to keep track of remaining
burst time of processes. This array is initially a
copy of bt[] (burst times array)
2- Create another array wt[] to store waiting times
of processes. Initialize this array as 0.
3- Initialize time : t = 0
4- Keep traversing the all processes while all processes
are not done. Do following for i'th process if it is
not done yet.
a- If rem_bt[i] > quantum
(i) t = t + quantum
(ii) bt_rem[i] -= quantum;
[ad type="banner"]
c- Else // Last cycle for this process
(i) t = t + bt_rem[i];
(ii) wt[i] = t - bt[i]
(ii) bt_rem[i] = 0; // This process is over
Once we have waiting times, we can compute turn around time tat[i] of a process as sum of waiting and burst times, i.e., wt[i] + bt[i]
Below is C++ implementation of above steps.
C++ Programming:
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20for%20implementation%20of%20RR%20scheduling%0A%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Function%20to%20find%20the%20waiting%20time%20for%20all%0A%2F%2F%20processes%0Avoid%20findWaitingTime(int%20processes%5B%5D%2C%20int%20n%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20int%20bt%5B%5D%2C%20int%20wt%5B%5D%2C%20int%20quantum)%0A%7B%0A%20%20%20%20%2F%2F%20Make%20a%20copy%20of%20burst%20times%20bt%5B%5D%20to%20store%20remaining%0A%20%20%20%20%2F%2F%20burst%20times.%0A%20%20%20%20int%20rem_bt%5Bn%5D%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%20%3B%20i%20%3C%20n%20%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20rem_bt%5Bi%5D%20%3D%20%20bt%5Bi%5D%3B%0A%20%0A%20%20%20%20int%20t%20%3D%200%3B%20%2F%2F%20Current%20time%0A%20%0A%20%20%20%20%2F%2F%20Keep%20traversing%20processes%20in%20round%20robin%20manner%0A%20%20%20%20%2F%2F%20until%20all%20of%20them%20are%20not%20done.%0A%20%20%20%20while%20(1)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20bool%20done%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20all%20processes%20one%20by%20one%20repeatedly%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%20%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20burst%20time%20of%20a%20process%20is%20greater%20than%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20then%20only%20need%20to%20process%20further%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(rem_bt%5Bi%5D%20%3E%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20done%20%3D%20false%3B%20%2F%2F%20There%20is%20a%20pending%20process%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(rem_bt%5Bi%5D%20%3E%20quantum)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Increase%20the%20value%20of%20t%20i.e.%20shows%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20how%20much%20time%20a%20process%20has%20been%20processed%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20t%20%2B%3D%20quantum%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Decrease%20the%20burst_time%20of%20current%20process%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20by%20quantum%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rem_bt%5Bi%5D%20-%3D%20quantum%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20burst%20time%20is%20smaller%20than%20or%20equal%20to%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20quantum.%20Last%20cycle%20for%20this%20process%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Increase%20the%20value%20of%20t%20i.e.%20shows%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20how%20much%20time%20a%20process%20has%20been%20processed%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20t%20%3D%20t%20%2B%20rem_bt%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Waiting%20time%20is%20current%20time%20minus%20time%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20used%20by%20this%20process%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20wt%5Bi%5D%20%3D%20t%20-%20bt%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20As%20the%20process%20gets%20fully%20executed%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20make%20its%20remaining%20burst%20time%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rem_bt%5Bi%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20all%20processes%20are%20done%0A%20%20%20%20%20%20%20%20if%20(done%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Function%20to%20calculate%20turn%20around%20time%0Avoid%20findTurnAroundTime(int%20processes%5B%5D%2C%20int%20n%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20bt%5B%5D%2C%20int%20wt%5B%5D%2C%20int%20tat%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20calculating%20turnaround%20time%20by%20adding%0A%20%20%20%20%2F%2F%20bt%5Bi%5D%20%2B%20wt%5Bi%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%20%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20tat%5Bi%5D%20%3D%20bt%5Bi%5D%20%2B%20wt%5Bi%5D%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20calculate%20average%20time%0Avoid%20findavgTime(int%20processes%5B%5D%2C%20int%20n%2C%20int%20bt%5B%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20quantum)%0A%7B%0A%20%20%20%20int%20wt%5Bn%5D%2C%20tat%5Bn%5D%2C%20total_wt%20%3D%200%2C%20total_tat%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20waiting%20time%20of%20all%20processes%0A%20%20%20%20findWaitingTime(processes%2C%20n%2C%20bt%2C%20wt%2C%20quantum)%3B%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20turn%20around%20time%20for%20all%20processes%0A%20%20%20%20findTurnAroundTime(processes%2C%20n%2C%20bt%2C%20wt%2C%20tat)%3B%0A%20%0A%20%20%20%20%2F%2F%20Display%20processes%20along%20with%20all%20details%0A%20%20%20%20cout%20%3C%3C%20%22Processes%20%22%3C%3C%20%22%20Burst%20time%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20Waiting%20time%20%22%20%3C%3C%20%22%20Turn%20around%20time%5Cn%22%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20total%20waiting%20time%20and%20total%20turn%0A%20%20%20%20%2F%2F%20around%20time%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20total_wt%20%3D%20total_wt%20%2B%20wt%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20total_tat%20%3D%20total_tat%20%2B%20tat%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22%20%22%20%3C%3C%20i%2B1%20%3C%3C%20%22%5Ct%5Ct%22%20%3C%3C%20bt%5Bi%5D%20%3C%3C%22%5Ct%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20wt%5Bi%5D%20%3C%3C%22%5Ct%5Ct%20%22%20%3C%3C%20tat%5Bi%5D%20%3C%3Cendl%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Average%20waiting%20time%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20(float)total_wt%20%2F%20(float)n%3B%0A%20%20%20%20cout%20%3C%3C%20%22%5CnAverage%20turn%20around%20time%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20(float)total_tat%20%2F%20(float)n%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20code%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20process%20id’s%0A%20%20%20%20int%20processes%5B%5D%20%3D%20%7B%201%2C%202%2C%203%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof%20processes%20%2F%20sizeof%20processes%5B0%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Burst%20time%20of%20all%20processes%0A%20%20%20%20int%20burst_time%5B%5D%20%3D%20%7B10%2C%205%2C%208%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20Time%20quantum%0A%20%20%20%20int%20quantum%20%3D%202%3B%0A%20%20%20%20findavgTime(processes%2C%20n%2C%20burst_time%2C%20quantum)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]
[ad type=”banner”]
Output:
Processes Burst time Waiting time Turn around time 1 10 13 23 2 5 10 15 3 8 13 21 Average waiting time = 12 Average turn around time = 19.6667