- Asked 2/19
- 2078 Baisakh · 3 marks
Priority and SJF scheduling with P4 and P5
Short answer
Preemptive priority: AWT = 8 ms, ATAT = 13.8 ms. Preemptive SJF (SRT): AWT = 6.2 ms, ATAT = 12 ms.
Three processes with process ID P1, P2, P3 with estimated completion time 4, 10, 5 ms and priorities 1, 4, 3 respectively enter the ready queue together. New process P4 with estimated completion time 3 ms and priority 2 enters the ready queue after 5 ms of start of operation and P5 with estimated completion time 7 ms and priority 0 enters the ready queue after 2 ms of start of P4. Calculate WT, TAT for each process and calculate AWT and ATAT using preemptive priority-based and shortest job first scheduling algorithms.
Preemptive priority
Assumed: P1, P2, P3 arrive at 0; P4 arrives at 5 ms; P5 arrives 2 ms after P4, i.e. at 7 ms. Lower priority number means higher priority. Burst times 4, 10, 5, 3, 7 ms; priorities 1, 4, 3, 2, 0.
Gantt chart
| P1 | P3 | P4 | P5 | P4 | P3 | P2 |
0 4 5 7 14 15 19 29
Trace
- 0-4: P1 (priority 1, best of the three) runs and finishes.
- 4-5: P3 (priority 3) runs; it beats P2 (priority 4).
- 5: P4 (priority 2) arrives and preempts P3 (4 ms left).
- 7: P5 (priority 0) arrives and preempts P4 (1 ms left).
- 7-14: P5 runs to completion.
- 14-15: P4 finishes; 15-19: P3 finishes; 19-29: P2 runs.
Calculation
TAT = completion time - arrival time; WT = TAT - burst time.
| Process | AT | BT | CT | TAT = CT - AT | WT = TAT - BT |
|---|---|---|---|---|---|
| P1 | 0 | 4 | 4 | 4 | 0 |
| P2 | 0 | 10 | 29 | 29 | 19 |
| P3 | 0 | 5 | 19 | 19 | 14 |
| P4 | 5 | 3 | 15 | 10 | 7 |
| P5 | 7 | 7 | 14 | 7 | 0 |
AWT = (0 + 19 + 14 + 7 + 0) / 5 = 40/5 = 8 ms
ATAT = (4 + 29 + 19 + 10 + 7) / 5 = 69/5 = 13.8 ms
Answer: AWT = 8 ms, ATAT = 13.8 ms.
Shortest job first (preemptive)
Shortest job first, applied in its preemptive form (shortest remaining time first). The CPU always runs the process with the smallest remaining burst; priorities are ignored.
Gantt chart
| P1 | P3 | P4 | P3 | P5 | P2 |
0 4 5 8 12 19 29
Trace
- 0-4: P1 (4 ms) is the shortest and finishes.
- 4-5: P3 (5 ms) runs, as P2 needs 10 ms.
- 5: P4 (3 ms) arrives; P3 has 4 ms left, so P4 preempts it.
- 5-8: P4 finishes. At 7, P5 (7 ms) arrives but is longer than the remaining 1 ms of P4, so no preemption.
- 8-12: P3 (4 left) finishes; 12-19: P5 (7 ms); 19-29: P2.
Calculation
TAT = completion time - arrival time; WT = TAT - burst time.
| Process | AT | BT | CT | TAT = CT - AT | WT = TAT - BT |
|---|---|---|---|---|---|
| P1 | 0 | 4 | 4 | 4 | 0 |
| P2 | 0 | 10 | 29 | 29 | 19 |
| P3 | 0 | 5 | 12 | 12 | 7 |
| P4 | 5 | 3 | 8 | 3 | 0 |
| P5 | 7 | 7 | 19 | 12 | 5 |
AWT = (0 + 19 + 7 + 0 + 5) / 5 = 31/5 = 6.2 ms
ATAT = (4 + 29 + 12 + 3 + 12) / 5 = 60/5 = 12 ms
Answer: AWT = 6.2 ms, ATAT = 12 ms.
If non-preemptive SJF is meant instead, the order is P1, P3, P4, P5, P2 (finish 4, 9, 12, 19, 29), giving AWT = (0+4+4+5+19)/5 = 6.4 ms and ATAT = (4+9+7+12+29)/5 = 12.2 ms.
Comparison
SJF (AWT 6.2 ms) gives a lower average waiting time than priority scheduling (AWT 8 ms) here, because it always favours the shortest remaining work.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Preemptive priority scheduling (4, 10, 5 ms) · 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×
- Preemptive SJF/SRT scheduling (10, 5, 7 ms) · Embedded System, chapter 6
- Non-preemptive priority scheduling (10, 5, 7 ms) · Embedded System, chapter 6 · asked 2×
- Preemptive priority scheduling (4, 6, 5 ms) · Embedded System, chapter 6
- Non-preemptive SJF with P4 arriving · Embedded System, chapter 6 · asked 2×
- FCFS, SJF, Priority, RR Gantt; max AWT · Operating System, chapter 2
- RR, preemptive priority, preemptive SJF · Operating System, chapter 2
- Real-time scheduling; two-processor numerical · Operating System, chapter 2