Homework SourseWhat is the turnaround time of each process for each of the
Solution
First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1
P2
P3
0 24 27 30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
Suppose that the processes arrive in the order
P2 , P3 , P1 .
The Gantt chart for the schedule is:
P2
P3
P1
0 3 6 30
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
SJF:
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (non-preemptive)
P1
P3
P2
P4
0 7 8 12 16
Average waiting time = [0 +(8-2)+(7-4) +(12-5)] /4 =4
Example of Preemptive SJF
Proces Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF (preemptive)
P1
P2
P3
P2
P4
P1
0 2 4 5 7 11 16
Average waiting time = (9 + 1 + 0 +2)/4 =3
Round Robin (RR):
Each process gets a small unit of CPU time (time quantum), 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
1. q large _ FIFO
2. 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 Gantt chart is:
P1
P2
P3
P1
P1
P1
P1
P1
0 4 7 10 14 18 22 26 30
Average waiting time = [(30-24)+4+7]/3 = 17/3 =5.66
| P1 | P2 | P3 |
