{"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>\u00a0<\/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=\u201dbanner\u201d]\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=\u201dbanner\u201d]\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[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20implement%20Shortest%20Job%20first%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%20%0Astruct%20Process%0A%7B%0A%20%20%20int%20pid%3B%20%2F%2F%20Process%20ID%0A%20%20%20int%20bt%3B%20%20%2F%2F%20Burst%20Time%0A%7D%3B%0A%20%0A%2F%2F%20This%20function%20is%20used%20for%20sorting%20all%0A%2F%2F%20processes%20in%20increasing%20order%20of%20burst%0A%2F%2F%20time%0Abool%20comparison(Process%20a%2C%20Process%20b)%0A%7B%0A%20%20%20%20%20return%20(a.bt%20%3C%20b.bt)%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20find%20the%20waiting%20time%20for%20all%0A%2F%2F%20processes%0Avoid%20findWaitingTime(Process%20proc%5B%5D%2C%20int%20n%2C%20int%20wt%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20waiting%20time%20for%20first%20process%20is%200%0A%20%20%20%20wt%5B0%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20calculating%20waiting%20time%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%20%3B%20i%2B%2B%20)%0A%20%20%20%20%20%20%20%20wt%5Bi%5D%20%3D%20proc%5Bi-1%5D.bt%20%2B%20wt%5Bi-1%5D%20%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20calculate%20turn%20around%20time%0Avoid%20findTurnAroundTime(Process%20proc%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%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%20proc%5Bi%5D.bt%20%2B%20wt%5Bi%5D%3B%0A%7D%0A%20%0A%2F%2FFunction%20to%20calculate%20average%20time%0Avoid%20findavgTime(Process%20proc%5B%5D%2C%20int%20n)%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(proc%2C%20n%2C%20wt)%3B%0A%20%0A%20%20%20%20%2F%2F%20Function%20to%20find%20turn%20around%20time%20for%20all%20processes%0A%20%20%20%20findTurnAroundTime(proc%2C%20n%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%22%5CnProcesses%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%20%3D%200%3B%20i%20%3C%20n%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%20proc%5Bi%5D.pid%20%3C%3C%20%22%5Ct%5Ct%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20proc%5Bi%5D.bt%20%3C%3C%20%22%5Ct%20%22%20%3C%3C%20wt%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20%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%20Process%20proc%5B%5D%20%3D%20%7B%7B1%2C%206%7D%2C%20%7B2%2C%208%7D%2C%20%7B3%2C%207%7D%2C%20%7B4%2C%203%7D%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof%20proc%20%2F%20sizeof%20proc%5B0%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Sorting%20processes%20by%20burst%20time.%0A%20%20%20%20sort(proc%2C%20proc%20%2B%20n%2C%20comparison)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Order%20in%20which%20process%20gets%20executed%5Cn%22%3B%0A%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%20cout%20%3C%3C%20proc%5Bi%5D.pid%20%3C%3C%22%20%22%3B%0A%20%0A%20%20%20%20findavgTime(proc%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\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=\u201dbanner\u201d]\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}]}}