{"id":27973,"date":"2017-09-05T23:50:55","date_gmt":"2017-09-05T18:20:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27973"},"modified":"2017-09-05T23:50:55","modified_gmt":"2017-09-05T18:20:55","slug":"fcfs-scheduling-set-1","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/fcfs-scheduling-set-1\/","title":{"rendered":"FCFS Scheduling | Set 1"},"content":{"rendered":"<p>Given n processes with their burst times, the task is to find average waiting time and average turn around time using FCFS scheduling algorithm.<br \/>\nFirst in, first out (FIFO), also known as first come, first served (FCFS), is the simplest scheduling algorithm. FIFO simply queues processes in the order that they arrive in the ready queue.<br \/>\nIn this, the process that comes first will be executed first and next process starts only after the previous gets fully executed.<br \/>\nHere we are considering that arrival time for all processes is 0.<\/p>\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><br \/>\n<strong>In this post, we have assumed arrival times as 0, so turn around and completion times are same.<\/strong><\/em><\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27977\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/FCFS.png\" alt=\"FCFS Scheduling | Set 1\" width=\"582\" height=\"390\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/FCFS.png 582w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/FCFS-300x200.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/FCFS-414x276.png 414w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/FCFS-130x86.png 130w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/FCFS-187x124.png 187w\" sizes=\"(max-width: 582px) 100vw, 582px\" \/><\/p>\n[ad type=\u201dbanner\u201d]\n<p><b>Implementation:<\/b><\/p>\n<pre>1-  Input the processes along with their burst time (bt).\r\n2-  Find waiting time (wt) for all processes.\r\n3-  As first process that comes need not to wait so \r\n    waiting time for process 1 will be 0 i.e. wt[0] = 0.\r\n4-  Find <strong>waiting time<\/strong> for all other processes i.e. for\r\n     process i -> \r\n       wt[i] = bt[i-1] + wt[i-1] .\r\n5-  Find <strong>turnaround time<\/strong> = waiting_time + burst_time \r\n    for all processes.\r\n6-  Find <strong>average waiting time<\/strong> = \r\n                 total_waiting_time \/ no_of_processes.\r\n7-  Similarly, find <strong>average turnaround time<\/strong> = \r\n                 total_turn_around_time \/ no_of_processes.<\/pre>\n<p>\u00a0<\/p>\n<p><strong>[ad type=\u201dbanner\u201d]<\/strong><\/p>\n<p><strong>C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20for%20implementation%20of%20FCFS%20%0A%2F%2F%20scheduling%0A%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Function%20to%20find%20the%20waiting%20time%20for%20all%20%0A%2F%2F%20processes%0Avoid%20findWaitingTime(int%20processes%5B%5D%2C%20int%20n%2C%20%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%20int%20bt%5B%5D%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%20%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%20%20bt%5Bi-1%5D%20%2B%20wt%5Bi-1%5D%20%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20calculate%20turn%20around%20time%0Avoid%20findTurnAroundTime(%20int%20processes%5B%5D%2C%20int%20n%2C%20%0A%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%20%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%2FFunction%20to%20calculate%20average%20time%0Avoid%20findavgTime(%20int%20processes%5B%5D%2C%20int%20n%2C%20int%20bt%5B%5D)%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%2FFunction%20to%20find%20waiting%20time%20of%20all%20processes%0A%20%20%20%20findWaitingTime(processes%2C%20n%2C%20bt%2C%20wt)%3B%0A%20%0A%20%20%20%20%2F%2FFunction%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%2FDisplay%20processes%20along%20with%20all%20details%0A%20%20%20%20cout%20%3C%3C%20%22Processes%20%20%22%3C%3C%20%22%20Burst%20time%20%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20Waiting%20time%20%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%20%0A%20%20%20%20%2F%2F%20around%20time%0A%20%20%20%20for%20(int%20%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%20%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%20%20%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20wt%5Bi%5D%20%3C%3C%22%5Ct%5Ct%20%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%2Fprocess%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%2FBurst%20time%20of%20all%20processes%0A%20%20%20%20int%20%20burst_time%5B%5D%20%3D%20%7B10%2C%205%2C%208%7D%3B%0A%20%0A%20%20%20%20findavgTime(processes%2C%20n%2C%20%20burst_time)%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>Processes  Burst time  Waiting time  Turn around time\r\n 1\t\t10\t 0\t\t 10\r\n 2\t\t5\t 10\t\t 15\r\n 3\t\t8\t 15\t\t 23\r\nAverage waiting time = 8.33333\r\nAverage turn around time = 16\r\n[ad type=\"banner\"]\r\n<\/pre>\n<p><strong>Important Points:<\/strong><\/p>\n<ol>\n<li>Non-preemptive<\/li>\n<li>Average Waiting Time is not optimal<\/li>\n<li>Cannot utilize resources in parallel : Results in Convoy effect (Consider a situation when many IO bound processes are there and one CPU bound process. The IO bound processes have to wait for CPU bound process when CPU bound process acquires CPU. The IO bound process could have better taken CPU for some time, then used IO devices).<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>FCFS Scheduling | Set 1 &#8211;  Operating System &#8211; Given n processes with their burst times, the task is to find average waiting time and average turn around<\/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":[82462,82470,82471,82437,82473,82464,82472,82469],"class_list":["post-27973","post","type-post","status-publish","format-standard","hentry","category-cs-subjects","category-operating-systems","tag-cpu-scheduling-algorithms","tag-fcfs-scheduling-example","tag-fcfs-scheduling-program-in-c","tag-preemptive-and-nonpreemptive-scheduling","tag-scheduling-algorithms-examples","tag-scheduling-algorithms-in-operating-system-with-examples-pdf","tag-sjf-scheduling-example","tag-sjf-scheduling-program-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27973","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=27973"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27973\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}