P1 24 P2 3 Suppose that the processesP3 3 arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:
P1
0 P2 24 27 30 Waiting time for P1 P3 = 0; P2 = 24; Average waiting time: P3 = 27 (0 + 24 + 27)/3 = 17 FCFS Scheduling (Cont) Suppose that the processes arrive in the order P 2 , P 3 , P1 The Gantt chart for the schedule is:
P2 P3 P1
0 3 30 6 Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect short process behind long process Task (FCFS) Process or Task Time units
A 8 B 4 C 9 D 5
Processes arrive in order A, B, C and D.
Find Waiting time for each process (task) Average waiting time Turnaround time for each process Draw a Gantt Chart Repeat for process arrival order C, B, A, D Shortest-Job-First (SJF) Scheduling Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time SJF is optimal – gives minimum average waiting time for a given set of processes The difficulty is knowing the length of the next CPU request Example of SJF Process Arrival Time Burst Time P1 6
0.0 P2 8
0.0 chart SJF scheduling P3arrive at the same time ( time 0) 7 Assuming all
0.0 P3 P2 P4 P1 P4 3
0 3 0.0 9 16 24
Average waiting time = (3 + 16 + 9 + 0) / 4 = 7
Example of SJF –Different Arrivals Process Arrival Time Burst Time P1 0.0 6 P2 2.0 8 P3 4.0 7 P4 5.0 3 SJF scheduling chart – non-preemptive Assuming different arrival times
P1 P4 P3 P2
6 9 0 Average waiting time = (0+ (16-2) + (9-4) + 16 24 (6-5)) / 4 = (14+5+1)/4 =5 ms Average turnaround time = (6+ (24-2) + (16-4) + (9-5)) = 44/4 = 11 ms Shortest Remaining Time First Scheduling
Preemptive version of SJN
Whenever a new process arrives in the ready queue, the decision on which process to schedule next is redone using the SJN algorithm. Is SRT more “optimal” than SJN in terms of the minimum average waiting time for a given set of processes? SJF and SRT A non-preemptive algorithm will allow the currently running process to finish its CPU burst.
A preemptive SJF algorithm will pre-empt the currently executing
process. A preemptive SJF algorithm is called the shortest remaining time first (SRT) algorithm. SRT Process Arrival Time Burst Time P1 0.0 8 P2 1.0 4 P3 2.0 9 P4 3.0 5 Gantt scheduling chart – remember to subtract time not in queue Assuming different arrival times
P1 P2 P4 P1 P3
1 5 10 0 17 26
Average waiting time = ((10-1)+ 0+(17-2) + (5-3)) / 4 = 26/4 = 6.5 ms
Round Robin (RR) Each process gets a small unit of CPU time (time quantum) q, usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units. Performance q large FIFO q small q must be large with respect to context switch, otherwise overhead is too high Example of RR with Time Quantum = 4 Process Burst Time P1 24 P2 3 P3 3 The time quantum is 4 ms ( q = 4) The Gantt chart is:
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30 Average wait time = ((10-4) + 4+ 7) = 17/3 = 5.66 ms Typically, higher average turnaround than SJF, but better response Example Task
Solve using FCFS, SJF, SRT and RR with quantum 2.
Find average waiting time and average turnaround time for said algorithms and tell which algorithm is more efficient.
Duration (Weeks) Activity Predecessors To TM TP Te A - 5 6 7 6 B - 1 3 5 3 C - 1 4 7 4 D A 1 2 3 2 E B 1 2 9 3 F C 1 5 9 5 G C 2 2 8 3 H E, F 4 4 10 5 I D 2 5 8 5 J H, G 2 2 8 3
Duration (Weeks) Activity Predecessors To TM TP Te A - 5 6 7 6 B - 1 3 5 3 C - 1 4 7 4 D A 1 2 3 2 E B 1 2 9 3 F C 1 5 9 5 G C 2 2 8 3 H E, F 4 4 10 5 I D 2 5 8 5 J H, G 2 2 8 3
