{"id":28014,"date":"2017-09-06T00:09:45","date_gmt":"2017-09-05T18:39:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=28014"},"modified":"2017-09-06T00:09:45","modified_gmt":"2017-09-05T18:39:45","slug":"round-robin-scheduling","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/round-robin-scheduling\/","title":{"rendered":"Round Robin scheduling"},"content":{"rendered":"<p>Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way.<\/p>\n<ul>\n<li>It is simple, easy to implement, and starvation-free as all processes get fair share of CPU.<\/li>\n<li>One of the most commonly used technique in CPU scheduling as a core.<\/li>\n<li>It is preemptive as processes are assigned CPU only for a fixed slice of time at most.<\/li>\n<li>The disadvantage of it is more overhead of context switching.<\/li>\n<\/ul>\n<p><strong>Illustration:<\/strong><\/p>\n[ad type=\u201dbanner\u201d]\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-28025\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Round-Robin-1.png\" alt=\"Round Robin scheduling\" width=\"708\" height=\"463\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Round-Robin-1.png 708w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Round-Robin-1-300x196.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Round-Robin-1-130x86.png 130w\" sizes=\"(max-width: 708px) 100vw, 708px\" \/>[ad type=\u201dbanner\u201d]\n<p><strong>How to compute below times in Round Robin using a program?<\/strong><\/p>\n<ol>\n<li>Completion Time: Time at which process completes its execution.<\/li>\n<li>Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time \u2013 Arrival Time<\/li>\n<li>Waiting Time(W.T): Time Difference between turn around time and burst time.<br \/>\nWaiting Time = Turn Around Time \u2013 Burst Time<\/li>\n<\/ol>\n<p><em><strong>In this post, we have assumed arrival times as 0, so turn around and completion times are same.<\/strong><\/em><\/p>\n<p>The tricky part is to compute waiting times. Once waiting times are computed, turn around times can be quickly computed.<\/p>\n<p><strong>Steps to find waiting times of all processes:<\/strong><\/p>\n<pre>1- Create an array <strong>rem_bt[]<\/strong> to keep track of remaining\r\n   burst time of processes. This array is initially a \r\n   copy of bt[] (burst times array)\r\n2- Create another array <strong>wt[]<\/strong> to store waiting times\r\n   of processes. Initialize this array as 0.\r\n3- Initialize time : t = 0\r\n4- Keep traversing the all processes while all processes\r\n   are not done. Do following for i'th process if it is\r\n   not done yet.\r\n    a- If rem_bt[i] > quantum\r\n       (i)  t = t + quantum\r\n       (ii) bt_rem[i] -= quantum;\r\n[ad type=\"banner\"]\r\n    c- Else \/\/ Last cycle for this process\r\n       (i)  t = t + bt_rem[i];\r\n       (ii) wt[i] = t - bt[i]\r\n       (ii) bt_rem[i] = 0; \/\/ This process is over\r\n<\/pre>\n<p>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]\n<p>Below is C++ implementation of above steps.<\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u2019s%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>\u00a0<\/p>\n<p><strong>[ad type=\u201dbanner\u201d]<\/strong><\/p>\n<p><strong>Output:<\/strong><\/p>\n<pre>Processes  Burst time  Waiting time  Turn around time\r\n 1\t\t10\t 13\t\t 23\r\n 2\t\t5\t 10\t\t 15\r\n 3\t\t8\t 13\t\t 21\r\nAverage waiting time = 12\r\nAverage turn around time = 19.6667<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Round Robin scheduling- Operating System &#8211; Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a cyclic way.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71771,82275],"tags":[82499,82494,82496,82497,82498,82495,82500],"class_list":["post-28014","post","type-post","status-publish","format-standard","hentry","category-cs-subjects","category-operating-systems","tag-priority-scheduling","tag-round-robin-scheduling-example-with-arrival-time","tag-round-robin-scheduling-example-with-gantt-chart","tag-round-robin-scheduling-generator","tag-round-robin-scheduling-pdf","tag-round-robin-scheduling-program-in-c","tag-shortest-job-first-scheduling"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28014","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=28014"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28014\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28014"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28014"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28014"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}