{"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=&#8221;banner&#8221;]\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=&#8221;banner&#8221;]\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] &gt; 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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ C++ program for implementation of RR scheduling<br\/>#include&lt;iostream&gt;<br\/>using namespace std;<br\/> <br\/>\/\/ Function to find the waiting time for all<br\/>\/\/ processes<br\/>void findWaitingTime(int processes[], int n,<br\/>             int bt[], int wt[], int quantum)<br\/>{<br\/>    \/\/ Make a copy of burst times bt[] to store remaining<br\/>    \/\/ burst times.<br\/>    int rem_bt[n];<br\/>    for (int i = 0 ; i &lt; n ; i++)<br\/>        rem_bt[i] =  bt[i];<br\/> <br\/>    int t = 0; \/\/ Current time<br\/> <br\/>    \/\/ Keep traversing processes in round robin manner<br\/>    \/\/ until all of them are not done.<br\/>    while (1)<br\/>    {<br\/>        bool done = true;<br\/> <br\/>        \/\/ Traverse all processes one by one repeatedly<br\/>        for (int i = 0 ; i &lt; n; i++)<br\/>        {<br\/>            \/\/ If burst time of a process is greater than 0<br\/>            \/\/ then only need to process further<br\/>            if (rem_bt[i] &gt; 0)<br\/>            {<br\/>                done = false; \/\/ There is a pending process<br\/> <br\/>                if (rem_bt[i] &gt; quantum)<br\/>                {<br\/>                    \/\/ Increase the value of t i.e. shows<br\/>                    \/\/ how much time a process has been processed<br\/>                    t += quantum;<br\/> <br\/>                    \/\/ Decrease the burst_time of current process<br\/>                    \/\/ by quantum<br\/>                    rem_bt[i] -= quantum;<br\/>                }<br\/> <br\/>                \/\/ If burst time is smaller than or equal to<br\/>                \/\/ quantum. Last cycle for this process<br\/>                else<br\/>                {<br\/>                    \/\/ Increase the value of t i.e. shows<br\/>                    \/\/ how much time a process has been processed<br\/>                    t = t + rem_bt[i];<br\/> <br\/>                    \/\/ Waiting time is current time minus time<br\/>                    \/\/ used by this process<br\/>                    wt[i] = t - bt[i];<br\/> <br\/>                    \/\/ As the process gets fully executed<br\/>                    \/\/ make its remaining burst time = 0<br\/>                    rem_bt[i] = 0;<br\/>                }<br\/>            }<br\/>        }<br\/> <br\/>        \/\/ If all processes are done<br\/>        if (done == true)<br\/>          break;<br\/>    }<br\/>}<br\/> <br\/>\/\/ Function to calculate turn around time<br\/>void findTurnAroundTime(int processes[], int n,<br\/>                        int bt[], int wt[], int tat[])<br\/>{<br\/>    \/\/ calculating turnaround time by adding<br\/>    \/\/ bt[i] + wt[i]<br\/>    for (int i = 0; i &lt; n ; i++)<br\/>        tat[i] = bt[i] + wt[i];<br\/>}<br\/> <br\/>\/\/ Function to calculate average time<br\/>void findavgTime(int processes[], int n, int bt[],<br\/>                                     int quantum)<br\/>{<br\/>    int wt[n], tat[n], total_wt = 0, total_tat = 0;<br\/> <br\/>    \/\/ Function to find waiting time of all processes<br\/>    findWaitingTime(processes, n, bt, wt, quantum);<br\/> <br\/>    \/\/ Function to find turn around time for all processes<br\/>    findTurnAroundTime(processes, n, bt, wt, tat);<br\/> <br\/>    \/\/ Display processes along with all details<br\/>    cout &lt;&lt; &quot;Processes &quot;&lt;&lt; &quot; Burst time &quot;<br\/>         &lt;&lt; &quot; Waiting time &quot; &lt;&lt; &quot; Turn around time\\n&quot;;<br\/> <br\/>    \/\/ Calculate total waiting time and total turn<br\/>    \/\/ around time<br\/>    for (int i=0; i&lt;n; i++)<br\/>    {<br\/>        total_wt = total_wt + wt[i];<br\/>        total_tat = total_tat + tat[i];<br\/>        cout &lt;&lt; &quot; &quot; &lt;&lt; i+1 &lt;&lt; &quot;\\t\\t&quot; &lt;&lt; bt[i] &lt;&lt;&quot;\\t &quot;<br\/>             &lt;&lt; wt[i] &lt;&lt;&quot;\\t\\t &quot; &lt;&lt; tat[i] &lt;&lt;endl;<br\/>    }<br\/> <br\/>    cout &lt;&lt; &quot;Average waiting time = &quot;<br\/>         &lt;&lt; (float)total_wt \/ (float)n;<br\/>    cout &lt;&lt; &quot;\\nAverage turn around time = &quot;<br\/>         &lt;&lt; (float)total_tat \/ (float)n;<br\/>}<br\/> <br\/>\/\/ Driver code<br\/>int main()<br\/>{<br\/>    \/\/ process id&#039;s<br\/>    int processes[] = { 1, 2, 3};<br\/>    int n = sizeof processes \/ sizeof processes[0];<br\/> <br\/>    \/\/ Burst time of all processes<br\/>    int burst_time[] = {10, 5, 8};<br\/> <br\/>    \/\/ Time quantum<br\/>    int quantum = 2;<br\/>    findavgTime(processes, n, burst_time, quantum);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>&nbsp;<\/p>\n<p><strong>[ad type=&#8221;banner&#8221;]<\/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}]}}