• Document: ICS 143A: Principles of Operating Systems Due Date: May 4, 2017 at 11:55 pm Homework #2 (100 pts)
  • Size: 230.86 KB
  • Uploaded: 2019-04-16 23:59:01
  • Status: Successfully converted


Some snippets from your converted document:

ICS 143A: Principles of Operating Systems Due Date: May 4, 2017 at 11:55 pm Homework #2 (100 pts) Last/First name: Student ID #: Question 1: Scheduling [5pts] a) ​Which of the following scheduling algorithms could result in starvation? Briefly explain your answer. 1. First-Come First-Served (FCFS) 2. Shortest Job First (SJF) (Non-preemptive) 3. Shortest Remaining Time First​ ​(SRTF) (Preemptive) 4. Round Robin (RR) 5. Priority (Preemptive) All except RR could lead to starvation. (1) FCFS is non preemptive, so it can lead to starvation if one of the processes runs forever (2) SJF can lead to starvation if there are many small jobs continuously arriving. Longer jobs may never execute. Same explanation of FCFS could be used here since it’s non-preemptive (3) SRTF can lead to starvation if there are many small jobs continuously arriving. Longer jobs may never execute. (5) Priority can lead to starvation if there are many high priority jobs. Lower priority jobs may never execute. [20pts]​ b) Consider the set of process: Process ID Arrival Time Burst Time Priority P1 0 60 3 P2 3 30 2 P3 4 40 1 P4 9 10 4 Draw the GANTT chart for the following scheduling algorithms. ● First-Come First-Served (FCFS) ● Shortest Job First (SJF) (Non-preemptive) ● Shortest Remaining Time First​ ​(SRTF) (Preemptive) ● Round Robin (RR) (Time Quantum = 10) ● Priority (Preemptive) When priority is being used, a smaller priority value means higher execution priority . For tie-breaking cases, the process with the earlier arrival time should execute. First-Come First-Served (FCFS) P1 P2 P3 P4 60 90 130 140 Average waiting time: (0 + (60 - 3) + (90 - 4) + (130 - 9)) /4 = (0 + 57 + 86 + 121) / 4 = 66 Average turnaround time: ((60 – 0) + (90 - 3) + (130 - 4) + (140 - 9)) / 4 = (60 + 87 + 126 + 131) / 4 = 101 Shortest Job First (SJF) (Non-preemptive) P1 P4 P2 P3 ​60 70 100 140 Average waiting time: (0 + (60 – 9) + (70 - 3) + (100 - 4)) / 4 = (0 + 51 + 67 + 96) / 4 = 53.5 Average turnaround time: ((60 - 0) + (70 - 9) + (100 - 3) + (140 - 4)) / 4 = (60 + 61 + 97 + 136) / 4 = 88.5 Shortest Remaining Time First (SRTF) (Preemptive) P1 P2 P4 P2 P3 P1 0 3 9 19 43 83 140 Average waiting time: (0+(83-3)) + (0+(19-9)) + (43-4) + 0 = (80+10+39+0) / 4 = 32.24 Average turnaround time: (140-0) + (43-3) + (83-4) + (19-9) = 67.25 Round Robin (RR) (Time Quantum = 10) P1 P2 P3 P4 P1 P2 P3 P1 P2 P3 P1 P3 P1 P1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 P1 waiting time: 0 + (40 - 10) + (70 - 50) + (100 - 80) + (120 - 110) = 30 + 20 + 20 + 10 = 80 P2 waiting time: (10 - 3) + (50 - 20) + (80 - 60) = 7 + 30 + 20 = 57 P3 waiting time: (20 - 4) + (60 - 30) + (90 - 70) + (110 - 100) = 16 + 30 + 20 + 10 = 76 P4 waiting time: (30 - 9) = 21 Average waiting time: (80 + 57 +76 + 21) / 4 = 58.5 Average turnaround time: ((140 - 0) + (90 - 3) + (120 - 4) + (40 - 9)) / 4 = (140 + 87 + 116 + 31) / 4 = 93.5 Priority (Preemptive) P1 P2 P3 P2 P1 P4 0 3 4 44 73 130 140 Average waiting time: ((0 + (70-3))+ (0 + (44-4))+ 0+ (130-9)) / 4 = (70 + 40 + 0 + 121) / 4 = 57.75 Average turnaround time: ((130 – 0) + (73 - 3) + (44 - 4) + (140 - 9)) / 4 = 92.75 [20pts]​ c) Complete the following table with the average waiting time and turnaround time of each algorithm: Scheduling Algorithm Average waiting time Average turnaround time First Come First Served (FCFS) 66 101 Shortest Job First (SJF) (Non-preemptive) 53.5 88.5 Shortest Remaining Time First (Preemptive) 32.2

Recently converted files (publicly available):