The Algorithm Family
Five classic algorithms cover the bulk of OS textbooks: FCFS, SJF, Priority, Round Robin, and Multilevel Queue.
Sample Workload
We will reuse this set throughout:
| Process | Arrival | Burst | Priority |
|---|---|---|---|
| P1 | 0 | 8 | 3 |
| P2 | 1 | 4 | 1 |
| P3 | 2 | 9 | 4 |
| P4 | 3 | 5 | 2 |
Lower priority number = higher priority.
1. First-Come First-Served (FCFS)
Processes run in arrival order. Non-preemptive. Simple but suffers from the convoy effect when a long process blocks short ones.
Completion: P1=8, P2=12, P3=21, P4=26. Turnaround = completion - arrival = 8, 11, 19, 23. Waiting = TAT - burst = 0, 7, 10, 18. Average waiting = 35/4 = 8.75.
2. Shortest Job First (SJF, non-preemptive)
Pick the ready process with the smallest CPU burst. Optimal for average waiting time but requires knowing burst length in advance.
At time 0 only P1 is ready, so P1 runs (0–8). At time 8 ready set is {P2,P3,P4} → pick P2 (burst 4): 8–12. Then {P3,P4} → P4 (5): 12–17. Then P3: 17–26. Waiting = 0,7,15,9. Average = 31/4 = 7.75.
3. Shortest Remaining Time First (SRTF, preemptive SJF)
A process can be preempted if a newcomer has a shorter remaining time.
4. Priority Scheduling
Each process has a priority; the highest-priority ready process runs. Can be preemptive or not. Risk: starvation — low-priority processes may never run. Solution: aging — increase priority over time spent waiting.
Using our table (lower number = higher priority), preemptive priority schedule order: P1 (0–1), P2 (1–5, higher priority arrives), P4 (5–10), P1 resumes (10–17), P3 (17–26).
5. Round Robin (RR)
Each ready process gets a fixed time quantum q. After q, it is preempted and placed at the back of the ready queue. Excellent for time-sharing.
With q=4 and ready queue P1,P2,P3,P4 (ignoring exact arrivals for clarity):
If q is too large, RR degenerates to FCFS. If too small, context-switch overhead dominates. Rule of thumb: 80% of CPU bursts should fit in one quantum.
6. Multilevel Queue Scheduling
Processes are partitioned into queues, each with its own algorithm:
- System processes — highest priority, RR.
- Interactive — RR with short quantum.
- Batch — FCFS, lowest priority.
Queues themselves are scheduled by fixed priority or time slice.
Multilevel Feedback Queue lets processes move between queues based on observed behaviour — CPU-bound processes drift down, I/O-bound stay high.
Comparison
| Algo | Preemptive | Avg Wait | Starvation | Notes |
|---|---|---|---|---|
| FCFS | No | High | No | Convoy effect |
| SJF | No | Lowest | Possible | Needs burst estimate |
| SRTF | Yes | Very low | Possible | Optimal preemptive |
| Priority | Either | Variable | Yes | Use aging |
| RR | Yes | Moderate | No | Quantum size critical |
| MLQ | Yes | Variable | Possible | Workload matched |
Summary
- FCFS is simplest, SJF/SRTF give the lowest average waiting time, RR is the king of interactivity, MLQ blends them for real workloads.