Tutorial 05 Solution.doc

TOS2461: Operating SystemsTutorial 51. 1. Suppose that a system employs priority scheduling, where a small integer means a high priority. Assume that all the processes arrive at time 0 millisecond. The process load is shown next:ProcessBurst timePriorityP0803P1201P2104P3205P4502 Present a Gantt chart illustrating the execution of these processes. What is the turnaround time for process P2 under this scheduling? What is the average wait time for the processes?Priority scheduling schedules the tasks based on priority. Therefore, the scheduled sequence will be P1, P4, P0, P2, P3.Gantt chartP1P4P0P2P3 020 70 150 160 180Turnaround time is the time a process reaching the queue till it is served, thus equivalent to waiting time + serving time. Turnaround time for process P2 = 160 milliseconds Average waiting time for the processes = (70+0+150+160+20)/5 = 80 milliseconds2. Suppose that a system employs first-come, first-serve scheduling. Assume that all the processes arrive at time 0 millisecond and in the sequence provided. The process load is shown next:ProcessBurst timeP080P120P210P320P450 Present a Gantt chart illustrating the execution of these processes. What is the average wait time for the processes?First-come, first-serve (FCFS) scheduling schedules tasks base on the sequence of arrival. Thus, the sequence of serving will be P0, P1, P2, P3, P4.Gantt chartP0P1P2P3P4 080100 110130180Average waiting time for the processes = (0+80+100+110+130)/5 = 84 milliseconds3. Suppose that a system employs first-come, first-serve scheduling. Note that now the arrival time for each process is varied. The process load is shown next:ProcessBurst timeArrival timeP080100P12010P21080P32050P4500 Present a Gantt chart illustrating the execution of these processes. What is the average wait time for the processes?First-come, first-serve (FCFS) scheduling schedules tasks base on the sequence of arrival. Thus, the sequence of serving will be P4, P1, P3, P2, P0.Gantt chartP4P1P3P2P0 0 50 70 90100180Wait time =Serving time-Arrival timeAverage waiting time for the processes = (100-100)+(50-10)+(90-80)+(70-50)+(0-0)/5=14 milliseconds4. Suppose that a system employs non-preemptive shortest-job-first scheduling. The process load is shown next:ProcessBurst timeArrival timeP080100P12010P21080P32050P4500 Present a Gantt chart illustrating the execution of these processes. What is the average wait time for the processes?Shortest-Job-First (SJF) Scheduling schedules the tasks based on the burst times. The non-preemptive version of SJF dictates that whenever a process is started, it must execute till its completion before passing on to the next process. If two or more processes are in the waiting list, then the order of execution is based on the burst times. If waiting processes have the same burst time, then the ordering is based on FCFS basis.At time 0, only process P4 arrived, thus it is executed directly. In the middle of its execution, process P1 arrives. As the system is non-preemptive, P1 will be put in the waiting list. At time 50, P3 comes in. Now the waiting list contains P1 and P3. The system will try to sort the processes according to burst time. However, as both P1 and P3 are having 20 ms burst time, the system resolves to FCFS. P1 thus executes first. Finishing at 70ms, the system resumes with P3 as no other process is waiting now. At time 80 ms, process P2 comes in. It is put in the waiting list. At time 90ms, upon completing P3, P2 is selected for execution as it is the only process in the waiting list. Finally when P2 finishes at time 100ms, P0 comes in and is executed. Gantt chartP4P1P3P2P0 0 50 70 90100180Average waiting time for the processes = (100-100)+(50-10)+(90-80)+(70-50)+(0-0)/5=14 millisecondsCoincidentally, this solution is exactly the same as the solution for FCFS Scheduling above. However, please do not get the wrong perception that this will always be the case.5. Suppose that a system employs preemptive shortest-job-first scheduling. The process load is shown next:ProcessBurst timeArrival timeP080100P12010P21080P32050P4500 Present a Gantt chart illustrating the execution of these processes. What is the average wait time for the processes?Shortest-Job-First (SJF) Scheduling schedules the tasks based on the burst times. The preemptive version of SJF dictates that whenever a new process is having burst time lesser than the remaining burst time for currently executing process, it must be executed straight away, effectively stealing the CPU from the existing executing process. The rest of the considerations are similar to the non-preemptive version. At time 0, only process P4 arrived, thus it is executed directly. In the middle of its execution (at time 10ms), process P1 arrives. As the burst time for P1 (20ms) is shorter than the remaining burst time for the P4 (50-10=40), P4 is preempted and put in the waiting list to allow P1 to execute first. At time 30ms, P1 is completed, allowing P4 (the only process in the waiting list) to resume its execution. At time 50ms, process P3 arrives. As the remaining burst time for P4 is the same as the burst time for process P3, P3 is put in waiting list and P4 continues. At time 70ms, P4 finished and P3 (the only remaining process in the waiting list) is executed. At time 80ms, P2 arrives. However, as its burst time is the same as the remaining burst time for process P3 (10ms), it cannot preempt P3, and being put into the waiting list. Upon completion of P3 at time 90ms, P2 is selected next as it is the only process in the waiting list. Finally when P2 finishes at time 100ms, P0 comes in and is executed. Gantt chartP4P1P4P3P2P0 0 10 30 70 90 100180Average waiting time for the processes = (100-100)+(10-10)+(90-80)+(70-50)+(0-0)+(30-10)/5=10 milliseconds6. Sketch a Gantt chart illustrating the execution of these processes using Round Robin scheduling with time quant