{"id":27974,"date":"2017-09-05T23:59:22","date_gmt":"2017-09-05T18:29:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27974"},"modified":"2017-09-05T23:59:22","modified_gmt":"2017-09-05T18:29:22","slug":"fcfs-scheduling-set-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/fcfs-scheduling-set-2\/","title":{"rendered":"FCFS Scheduling | Set 2"},"content":{"rendered":"

We have already discussed FCFS Scheduling of processes with same arrival time. In this post, scenario when processes have different arrival times are discussed. Given n processes with their burst times and arrival times, the task is to find average waiting time and average turn around time using FCFS scheduling algorithm.
\nFIFO simply queues processes in the order they arrive in the ready queue. Here, the process that comes first will be executed first and next process will start only after the previous gets fully executed.<\/p>\n

    \n
  1. Completion Time: Time at which process completes its execution.<\/li>\n
  2. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time \u2013 Arrival Time<\/li>\n
  3. Waiting Time(W.T): Time Difference between turn around time and burst time.
    \nWaiting Time = Turn Around Time \u2013 Burst Time<\/li>\n<\/ol>\n

    \"FCFS[ad type=\u201dbanner\u201d]\n

    \r\nProcess     Wait Time : Service Time - Arrival Time\r\n   P0 \t                   0 - 0   = 0\r\n   P1 \t                   5 - 1   = 4\r\n   P2 \t                   8 - 2   = 6\r\n   P3 \t                   16 - 3  = 13\r\n\r\nAverage Wait Time: (0 + 4 + 6 + 13) \/ 4 = 5.75\r\n<\/pre>\n[ad type=\u201dbanner\u201d]\n
    Service Time :<\/strong> Service time means amount of time after which a process can start execution. It is summation of burst time of previous processes (Processes that came before)<\/p>\n
    Changes in code as compare to code of FCFS with same arrival time:<\/strong>
    \nTo find waiting time: Time taken by all processes before the current process to be started (i.e. burst time of all previous processes) \u2013 arrival time of current process
    \nwait_time[i] = (bt[0] + bt[1] +\u2026\u2026 bt[i-1] ) \u2013 arrival_time[i]<\/strong><\/p>\n
    Implementation:<\/b><\/p>\n
    1- Input the processes along with their burst time(bt)\r\n   and arrival time(at)\r\n2- Find waiting time for all other processes i.e. for\r\n   a given process  i:\r\n       wt[i] = (bt[0] + bt[1] +...... bt[i-1]) - at[i] \r\n3- Now find turn around time <\/strong>\r\n          = waiting_time + burst_time for all processes\r\n4- Average waiting time<\/strong> = \r\n                    total_waiting_time \/ no_of_processes\r\n5- Average turn around time<\/strong> = \r\n                 total_turn_around_time \/ no_of_processes<\/pre>\n[ad type=\u201dbanner\u201d]\n
    C++ Programming:<\/strong><\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20for%20implementation%20of%20FCFS%0A%2F%2F%20scheduling%20with%20different%20arrival%20time%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%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%20int%20wt%5B%5D%2C%20int%20at%5B%5D)%0A%7B%0A%20%20%20%20int%20service_time%5Bn%5D%3B%0A%20%20%20%20service_time%5B0%5D%20%3D%200%3B%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)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Add%20burst%20time%20of%20previous%20processes%0A%20%20%20%20%20%20%20%20service_time%5Bi%5D%20%3D%20service_time%5Bi-1%5D%20%2B%20bt%5Bi-1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20waiting%20time%20for%20current%20process%20%3D%0A%20%20%20%20%20%20%20%20%2F%2F%20sum%20-%20at%5Bi%5D%0A%20%20%20%20%20%20%20%20wt%5Bi%5D%20%3D%20service_time%5Bi%5D%20-%20at%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20waiting%20time%20for%20a%20process%20is%20in%20negative%0A%20%20%20%20%20%20%20%20%2F%2F%20that%20means%20it%20is%20already%20in%20the%20ready%20queue%0A%20%20%20%20%20%20%20%20%2F%2F%20before%20CPU%20becomes%20idle%20so%20its%20waiting%20time%20is%200%0A%20%20%20%20%20%20%20%20if%20(wt%5Bi%5D%20%3C%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20wt%5Bi%5D%20%3D%200%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%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%20%20int%20wt%5B%5D%2C%20int%20tat%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Calculating%20turnaround%20time%20by%20adding%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%20waiting%20and%20turn-around%0A%2F%2F%20times.%0Avoid%20findavgTime(int%20processes%5B%5D%2C%20int%20n%2C%20int%20bt%5B%5D%2C%20int%20at%5B%5D)%0A%7B%0A%20%20%20%20int%20wt%5Bn%5D%2C%20tat%5Bn%5D%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%20at)%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%20%3C%3C%20%22%20Burst%20Time%20%22%20%3C%3C%20%22%20Arrival%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-Around%20Time%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20Completion%20Time%20%5Cn%22%3B%0A%20%20%20%20int%20total_wt%20%3D%200%2C%20total_tat%20%3D%200%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%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%20int%20compl_time%20%3D%20tat%5Bi%5D%20%2B%20at%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%20%22%5Ct%5Ct%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20at%5Bi%5D%20%3C%3C%20%22%5Ct%5Ct%22%20%3C%3C%20wt%5Bi%5D%20%3C%3C%20%22%5Ct%5Ct%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20tat%5Bi%5D%20%20%3C%3C%20%20%22%5Ct%5Ct%20%22%20%3C%3C%20compl_time%20%3C%3C%20endl%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%7B1%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%7B5%2C%209%2C%206%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20Arrival%20time%20of%20all%20processes%0A%20%20%20%20int%20arrival_time%5B%5D%20%3D%20%7B3%2C%203%2C%206%7D%3B%0A%20%0A%20%20%20%20findavgTime(processes%2C%20n%2C%20burst_time%2C%20arrival_time)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
    \u00a0<\/p>\n
    [ad type=\u201dbanner\u201d]<\/strong><\/p>\n
    Output:<\/strong><\/p>\n
    Processes  Burst Time  Arrival Time  Waiting Time  Turn-Around Time  Completion Time \r\n 1\t\t5\t\t3\t\t0\t\t 5\t\t 8\r\n 2\t\t9\t\t3\t\t2\t\t 11\t\t 14\r\n 3\t\t6\t\t6\t\t8\t\t 14\t\t 20\r\nAverage waiting time = 3.33333\r\nAverage turn around time = 10<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
    FCFS Scheduling | Set 2 – Operating System – We have already discussed FCFS Scheduling of processes with same arrival time. In this post, scenario<\/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,82440,82471,82437,82473,82464,82477,82472],"class_list":["post-27974","post","type-post","status-publish","format-standard","hentry","category-cs-subjects","category-operating-systems","tag-cpu-scheduling-algorithms","tag-fcfs-scheduling-algorithm","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","tag-sjf-scheduling-example"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27974","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=27974"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27974\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27974"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27974"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27974"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}