{"id":27986,"date":"2017-09-06T00:06:08","date_gmt":"2017-09-05T18:36:08","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27986"},"modified":"2018-10-25T20:14:54","modified_gmt":"2018-10-25T14:44:54","slug":"27986-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/27986-2\/","title":{"rendered":"Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive)"},"content":{"rendered":"<h2 id=\"sjfshortest-job-first\"><span style=\"color: #ff0000;\">SJF(shortest job first)<\/span><\/h2>\n<p><span style=\"color: #000000;\">Shortest job first (SJF) or shortest job next, is a <a href=\"https:\/\/www.wikitechy.com\/technology\/program-priority-scheduling-set-1\/\">scheduling<\/a> policy that selects the waiting process with the smallest execution time to execute next. SJN is a non-preemptive algorithm.<\/span><\/p>\n<ul>\n<li><span style=\"color: #000000;\">Shortest Job first has the advantage of having minimum average waiting time among all scheduling algorithms.<\/span><\/li>\n<li><span style=\"color: #000000;\">It is a <a href=\"https:\/\/www.wikitechy.com\/technology\/greedy-algorithms-set-9-boruvkas-algorithm\/\">Greedy<\/a> Algorithm.<\/span><\/li>\n<li><span style=\"color: #000000;\">It may cause starvation if shorter processes keep coming. This problem can be solved using the concept of aging.<\/span><\/li>\n<li><span style=\"color: #000000;\">It is practically infeasible as <a href=\"https:\/\/www.wikitechy.com\/technology\/update-operating-system-ipod\/\">Operating System<\/a> may not know burst time and therefore may not sort them. While it is not possible to predict execution time, several methods can be used to estimate the execution time for a job, such as a weighted average of previous execution times. SJF can be used in specialized environments where accurate estimates of running time are available.<\/span><\/li>\n<\/ul>\n<h2 id=\"how-sjf-works\"><span style=\"color: #339966;\">How SJF works?<\/span><\/h2>\n<p><span style=\"color: #000000;\">Shortest Job First scheduling works on the process with the shortest\u00a0<b>burst time<\/b>\u00a0or\u00a0<b>duration<\/b>\u00a0first.<\/span><\/p>\n<ul class=\"content\">\n<li><span style=\"color: #000000;\">This is the best approach to minimize waiting time.<\/span><\/li>\n<li><span style=\"color: #000000;\">This is used in<a href=\"https:\/\/www.wikitechy.com\/technology\/batch-rename-files-windows\/\">\u00a0Batch<\/a> Systems.<\/span><\/li>\n<li><span style=\"color: #000000;\">It is of two types:<\/span>\n<ol class=\"content\">\n<li><span style=\"color: #000000;\">Non Pre-emptive<\/span><\/li>\n<li><span style=\"color: #000000;\">Pre-emptive<\/span><\/li>\n<\/ol>\n<\/li>\n<li><span style=\"color: #000000;\">To successfully <a href=\"https:\/\/www.wikitechy.com\/technology\/efficiently-implement-k-stacks-single-array\/\">implement<\/a> it, the burst time\/duration time of the processes should be known to the processor in advance, which is practically not feasible all the time.<\/span><\/li>\n<li><span style=\"color: #000000;\">This scheduling algorithm is optimal if all the jobs\/processes are available at the same time. (either Arrival time is\u00a0<code>0<\/code>\u00a0for all, or Arrival time is same for all)<\/span><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\" wp-image-31456\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/09\/shortest-job-first-scheduling.png\" alt=\"\" width=\"691\" height=\"524\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/09\/shortest-job-first-scheduling.png 550w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/09\/shortest-job-first-scheduling-300x227.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/09\/shortest-job-first-scheduling-74x55.png 74w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/09\/shortest-job-first-scheduling-111x83.png 111w\" sizes=\"(max-width: 691px) 100vw, 691px\" \/><\/p>\n<p>As you can see in the\u00a0<b>GANTT chart<\/b>\u00a0above, the process\u00a0<b>P4<\/b>\u00a0will be picked up first as it has the shortest burst time, then\u00a0<b>P2<\/b>, followed by\u00a0<b>P3<\/b>\u00a0and at last\u00a0<b>P1<\/b>.<br \/>\nWe scheduled the same set of processes using the\u00a0First come first serve\u00a0algorithm , and got average waiting time to be\u00a0<code>18.75 ms<\/code>, whereas with SJF, the average waiting time comes out\u00a0<code>4.5 ms<\/code>.<\/p>\n<h2 id=\"algorithm\"><span style=\"color: #800000;\"><strong>Algorithm:<\/strong><\/span><\/h2>\n<p><span style=\"color: #000000;\">1- Sort all the processes in increasing order according to burst time. <\/span><\/p>\n<p><span style=\"color: #000000;\">2- Then simply, apply <a href=\"https:\/\/www.wikitechy.com\/technology\/fcfs-scheduling-set-2\/\">FCFS<\/a>.<\/span><\/p>\n[ad type=&#8221;banner&#8221;]\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-28007\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1.png\" alt=\"Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive)\" width=\"758\" height=\"505\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1.png 758w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1-300x200.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1-414x276.png 414w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1-470x313.png 470w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1-640x426.png 640w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1-130x86.png 130w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/SJF1-187x124.png 187w\" sizes=\"(max-width: 758px) 100vw, 758px\" \/><\/p>\n[ad type=&#8221;banner&#8221;]\n<h2 id=\"how-to-compute-below-times-in-round-robin-using-a-program\"><span style=\"color: #800080;\"><strong>How to compute below times in Round Robin using a program?<\/strong><\/span><\/h2>\n<ol>\n<li><span style=\"color: #000000;\">Completion Time: Time at which process completes its execution.<\/span><\/li>\n<li><span style=\"color: #000000;\">Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time \u2013 Arrival Time<\/span><\/li>\n<li><span style=\"color: #000000;\">Waiting Time(W.T): Time Difference between turn around time and burst time.<\/span><br \/>\n<span style=\"color: #000000;\">Waiting Time = Turn Around Time \u2013 Burst Time<\/span><\/li>\n<\/ol>\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 to implement Shortest Job first<br\/>#include&lt;bits\/stdc++.h&gt;<br\/>using namespace std;<br\/> <br\/>struct Process<br\/>{<br\/>   int pid; \/\/ Process ID<br\/>   int bt;  \/\/ Burst Time<br\/>};<br\/> <br\/>\/\/ This function is used for sorting all<br\/>\/\/ processes in increasing order of burst<br\/>\/\/ time<br\/>bool comparison(Process a, Process b)<br\/>{<br\/>     return (a.bt &lt; b.bt);<br\/>}<br\/> <br\/>\/\/ Function to find the waiting time for all<br\/>\/\/ processes<br\/>void findWaitingTime(Process proc[], int n, int wt[])<br\/>{<br\/>    \/\/ waiting time for first process is 0<br\/>    wt[0] = 0;<br\/> <br\/>    \/\/ calculating waiting time<br\/>    for (int i = 1; i &lt; n ; i++ )<br\/>        wt[i] = proc[i-1].bt + wt[i-1] ;<br\/>}<br\/> <br\/>\/\/ Function to calculate turn around time<br\/>void findTurnAroundTime(Process proc[], int n,<br\/>                        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] = proc[i].bt + wt[i];<br\/>}<br\/> <br\/>\/\/Function to calculate average time<br\/>void findavgTime(Process proc[], int n)<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(proc, n, wt);<br\/> <br\/>    \/\/ Function to find turn around time for all processes<br\/>    findTurnAroundTime(proc, n, wt, tat);<br\/> <br\/>    \/\/ Display processes along with all details<br\/>    cout &lt;&lt; &quot;\\nProcesses &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; proc[i].pid &lt;&lt; &quot;\\t\\t&quot;<br\/>             &lt;&lt; proc[i].bt &lt;&lt; &quot;\\t &quot; &lt;&lt; wt[i]<br\/>             &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 proc[] = {{1, 6}, {2, 8}, {3, 7}, {4, 3}};<br\/>    int n = sizeof proc \/ sizeof proc[0];<br\/> <br\/>    \/\/ Sorting processes by burst time.<br\/>    sort(proc, proc + n, comparison);<br\/> <br\/>    cout &lt;&lt; &quot;Order in which process gets executed\\n&quot;;<br\/>    for (int i = 0 ; i &lt; n; i++)<br\/>        cout &lt;&lt; proc[i].pid &lt;&lt;&quot; &quot;;<br\/> <br\/>    findavgTime(proc, n);<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n[ad type=&#8221;banner&#8221;]\n<p><strong>Output:<\/strong><\/p>\n<pre>Order in which process gets executed\r\n4 1 3 2 \r\nProcesses  Burst time  Waiting time  Turn around time\r\n 4\t\t3\t 0\t\t 3\r\n 1\t\t6\t 3\t\t 9\r\n 3\t\t7\t 9\t\t 16\r\n 2\t\t8\t 16\t\t 24\r\nAverage waiting time = 7\r\nAverage turn around time = 13<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Shortest Job First (or SJF) scheduling | Set 1 (Non- preemptive) &#8211; Operating System &#8211; Shortest job first (SJF) or shortest job next<\/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":[85586,85587,82500,82484,82480,82481,85588,85585,82483,82485,82486,82482],"class_list":["post-27986","post","type-post","status-publish","format-standard","hentry","category-cs-subjects","category-operating-systems","tag-preemptive-shortest-job-first-calculator","tag-preemptive-sjf-scheduling-example-ppt","tag-shortest-job-first-scheduling","tag-shortest-job-first-scheduling-algorithm","tag-shortest-job-first-scheduling-example","tag-shortest-job-first-scheduling-program-in-c","tag-sjf-in-os","tag-sjf-non-preemptive-scheduling-example","tag-sjf-non-preemptive-scheduling-program-in-c","tag-sjf-non-preemptive-scheduling-program-in-c-with-gantt-chart","tag-sjf-non-preemptive-scheduling-program-in-c-with-output","tag-sjf-scheduling-preemptive"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27986","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=27986"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27986\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27986"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27986"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27986"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}