- 2070 Bhadra · 4+4 marks
FCFS, SJF, Priority, RR Gantt; max AWT
Short answer
FCFS yields the maximum average waiting time of 9.6 ms due to the convoy effect, while SJF gives the minimum at 2.6 ms. The Gantt charts are: FCFS P1-P2-P3-P4-P5; SJF P2-P4-P3-P5-P1; Priority P2-P5-P1-P3-P4; RR P1-P2-P3-P4-P5-P1.
Consider the following set of processes with the length of the CPU burst time given in millisecond.
| Process | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Burst time | 10 | 1 | 2 | 1 | 2 |
| Priority | 3 | 1 | 3 | 4 | 2 |
| Assume the processes arrived in the order P1, P2, P3, P4 and P5 all at time 0, priority 1 as highest and 4 as lowest. | |||||
| a) Draw the Gantt chart for FCFS, SJF, Priority and Round Robin (Quantum = 2). | |||||
| b) Which algorithm results in the maximum average waiting time? |
Assumptions: all processes arrive at time 0 in the order P1 to P5; priority 1 is highest; for the priority algorithm, ties (P1 and P3 both priority 3) are broken by arrival order (FCFS); SJF is non-preemptive. Waiting time = turnaround − burst (arrival is 0, so turnaround = completion time).
a) Gantt charts
FCFS
| P1 | P2 | P3 | P4 | P5 |
0 10 11 13 14 16
SJF (order of burst: P2=1, P4=1, P3=2, P5=2, P1=10)
| P2 | P4 | P3 | P5 | P1 |
0 1 2 4 6 16
Priority (order: P2, P5, P1, P3, P4)
| P2 | P5 | P1 | P3 | P4 |
0 1 3 13 15 16
Round Robin, quantum = 2
| P1 | P2 | P3 | P4 | P5 | P1 |
0 2 3 5 6 8 16
Waiting and turnaround times
| Process | FCFS WT | FCFS TAT | SJF WT | SJF TAT | Priority WT | Priority TAT | RR WT | RR TAT |
|---|---|---|---|---|---|---|---|---|
| P1 | 0 | 10 | 6 | 16 | 3 | 13 | 6 | 16 |
| P2 | 10 | 11 | 0 | 1 | 0 | 1 | 2 | 3 |
| P3 | 11 | 13 | 2 | 4 | 13 | 15 | 3 | 5 |
| P4 | 13 | 14 | 1 | 2 | 15 | 16 | 5 | 6 |
| P5 | 14 | 16 | 4 | 6 | 1 | 3 | 6 | 8 |
| Average | 9.6 | 12.8 | 2.6 | 5.8 | 6.4 | 9.6 | 4.4 | 7.6 |
Example (FCFS): waiting times are 0, 10, 11, 13, 14, so average = 48/5 = 9.6 ms.
b) Algorithm with the maximum average waiting time
| Algorithm | Average waiting time (ms) |
|---|---|
| FCFS | 9.6 |
| SJF | 2.6 |
| Priority | 6.4 |
| Round Robin (q=2) | 4.4 |
Answer: FCFS gives the maximum average waiting time (9.6 ms), because the long process P1 (10 ms) is served first and all short jobs wait behind it (convoy effect). SJF gives the minimum (2.6 ms).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- FCFS, SJF, RR Gantt and turnaround · Operating System, chapter 2
- RR, preemptive priority, preemptive SJF · Operating System, chapter 2
- Real-time scheduling; two-processor numerical · Operating System, chapter 2
- Preemptive priority and SRTF Gantt · Operating System, chapter 2
- Avg turnaround: FCFS, RR, SJF, SRT, HRRN · Operating System, chapter 2
- CPU criteria; RR Gantt and times · Operating System, chapter 2
- Priority and SJF scheduling with P4 and P5 · Embedded System, chapter 6 · asked 2×
- Preemptive priority scheduling with P4 (6 ms) · Embedded System, chapter 6 · asked 2×
- Priority scheduling (7, 8, 5 ms) with P4 · Embedded System, chapter 6 · asked 2×
- Non-preemptive SJF with P4 arriving · Embedded System, chapter 6 · asked 2×