- Year not given
Scheduling algorithms with numerical
Short answer
FCFS services in arrival order (AWT 4.75 ms, ATAT 8.75 ms); SJF picks shortest job next (AWT 4, ATAT 8); SRTN preempts for shortest remaining time (AWT 3, ATAT 7); Round Robin (q=2 ms) slices time (AWT 5, ATAT 9); Priority schedules by static rank (AWT 5.5, ATAT 9.5); HRRN uses response ratio to limit starvation (AWT 4, ATAT 8).
Explain the FCFS, SJF, SRTN, Round Robin, Priority and HRRN scheduling algorithms with numerical examples.
Common data used for all examples (times in ms; priority 1 = highest, used only for the priority algorithm):
| Process | Arrival | Burst | Priority |
|---|---|---|---|
| P1 | 0 | 7 | 3 |
| P2 | 2 | 4 | 1 |
| P3 | 4 | 1 | 4 |
| P4 | 5 | 4 | 2 |
Turnaround time = completion − arrival; waiting time = turnaround − burst.
1. FCFS
Processes are served in order of arrival; non-preemptive. Simple but suffers from the convoy effect.
| P1 | P2 | P3 | P4 |
0 7 11 12 16
| Process | Arrival | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 | 0 |
| P2 | 2 | 4 | 11 | 9 | 5 |
| P3 | 4 | 1 | 12 | 8 | 7 |
| P4 | 5 | 4 | 16 | 11 | 7 |
AWT = 19/4 = 4.75, ATAT = 35/4 = 8.75
2. SJF (non-preemptive)
At each completion the ready process with the smallest burst is chosen. It gives minimum average waiting time among non-preemptive algorithms but needs burst estimates and may starve long jobs.
| P1 | P3 | P2 | P4 |
0 7 8 12 16
| Process | Arrival | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 | 0 |
| P2 | 2 | 4 | 12 | 10 | 6 |
| P3 | 4 | 1 | 8 | 4 | 3 |
| P4 | 5 | 4 | 16 | 11 | 7 |
AWT = 16/4 = 4, ATAT = 32/4 = 8
3. SRTN (SRTF, preemptive SJF)
The process with the shortest remaining time runs; a new arrival with less remaining time preempts the current one. At t=2 P2 (4) preempts P1 (5 left); at t=4 P3 (1) preempts P2 (2 left); P2 resumes at 5 and ends at 7, then P4 (4) runs, and P1 last.
| P1 | P2 | P3 | P2 | P4 | P1 |
0 2 4 5 7 11 16
| Process | Arrival | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 16 | 9 |
| P2 | 2 | 4 | 7 | 5 | 1 |
| P3 | 4 | 1 | 5 | 1 | 0 |
| P4 | 5 | 4 | 11 | 6 | 2 |
AWT = 12/4 = 3, ATAT = 28/4 = 7
4. Round Robin (q = 2)
Each process runs for at most 2 ms and then goes to the tail of the ready queue; new arrivals join before the preempted process.
| P1 | P2 | P1 | P3 | P2 | P4 | P1 | P4 | P1 |
0 2 4 6 7 9 11 13 15 16
| Process | Arrival | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 16 | 9 |
| P2 | 2 | 4 | 9 | 7 | 3 |
| P3 | 4 | 1 | 7 | 3 | 2 |
| P4 | 5 | 4 | 15 | 10 | 6 |
AWT = 20/4 = 5, ATAT = 36/4 = 9
5. Priority (non-preemptive)
The ready process with the highest priority (smallest number) is chosen at each completion. Low-priority P3 may starve (solved by aging).
| P1 | P2 | P4 | P3 |
0 7 11 15 16
| Process | Arrival | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 | 0 |
| P2 | 2 | 4 | 11 | 9 | 5 |
| P3 | 4 | 1 | 16 | 12 | 11 |
| P4 | 5 | 4 | 15 | 10 | 6 |
AWT = 22/4 = 5.5, ATAT = 38/4 = 9.5
6. HRRN (non-preemptive)
Response ratio = (waiting + burst)/burst. At t=7: P2 = (5+4)/4 = 2.25, P3 = (3+1)/1 = 4, P4 = (2+4)/4 = 1.5, so P3 runs; at t=8: P2 = 2.5, P4 = 1.75, so P2 runs. It limits starvation by aging.
| P1 | P3 | P2 | P4 |
0 7 8 12 16
| Process | Arrival | Burst | Completion | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 | 0 |
| P2 | 2 | 4 | 12 | 10 | 6 |
| P3 | 4 | 1 | 8 | 4 | 3 |
| P4 | 5 | 4 | 16 | 11 | 7 |
AWT = 16/4 = 4, ATAT = 32/4 = 8
Comparison
| Algorithm | AWT | ATAT |
|---|---|---|
| FCFS | 4.75 | 8.75 |
| SJF (non-preemptive) | 4 | 8 |
| SRTN (SRTF, preemptive SJF) | 3 | 7 |
| Round Robin (q = 2) | 5 | 9 |
| Priority (non-preemptive) | 5.5 | 9.5 |
| HRRN (non-preemptive) | 4 | 8 |
Answer: SRTN gives the least AWT (3.0 ms) and ATAT (7.0 ms); FCFS 4.75 / 8.75; SJF and HRRN 4.0 / 8.0; RR 5.0 / 9.0; priority 5.5 / 9.5.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- FCFS, SJF, Priority, RR Gantt; max AWT · Operating System, chapter 2
- Avg turnaround: FCFS, RR, SJF, SRT, HRRN · Operating System, chapter 2
- FCFS, SJF, RR Gantt and turnaround · Operating System, chapter 2
- RR, preemptive priority, preemptive SJF · Operating System, chapter 2
- Disk scheduling algorithms with numerical · Operating System, chapter 6
- HRRN and RR scheduling (q=4) · Operating System, chapter 2
- Round robin scheduling (5, 8, 7 ms, q=2) · Embedded System, chapter 6
- Priority and SJF scheduling with P4 and P5 · Embedded System, chapter 6 · asked 2×
- Round robin scheduling (9, 6, 3 ms, q=2) · Embedded System, chapter 6 · asked 4×
- Round robin scheduling (9, 6, 3 ms, q=3) · Embedded System, chapter 6 · asked 4×