1Definition
- First-Come, First-Served (FCFS): Non-preemptive algorithm that dispatches CPU time strictly by arrival order.
- Convoy Effect: A performance hazard in FCFS where short processes are trapped waiting behind a single long, CPU-bound process.
- Shortest Job First (SJF): Non-preemptive algorithm that assigns CPU to the process with the smallest burst time.
- Shortest Remaining Time First (SRTF): Preemptive version of SJF.
- Priority Scheduling: Allocates CPU based on assigned priority scores.
- Aging: Technique that gradually increases the priority of waiting processes over time to eliminate Starvation.
2Simple Explanation
- FCFS is like a single line at a grocery store checkout. If a person with 500 items is at the front of the line (long burst time), 10 people with 1 item each (short burst time) have to stand waiting for an hour. This is the Convoy Effect.
- SJF / SRTF fixes this by serving people with the fewest items first. This minimizes total waiting time across all shoppers. However, if people with 1 item keep arriving continuously, a person with 50 items will wait forever (Starvation).
- Priority Scheduling gives VIP treatment to high-priority jobs. To stop low-priority jobs from starving, Aging raises their priority score by 1 point every 10 minutes until they get served.
3Real-Life Example / Analogy
- FCFS: Airport security line processing travelers strictly by arrival order.
- SJF: An emergency room triage nurse seeing patients with minor cuts before performing lengthy wellness checkups.
- Priority & Aging: Airline boarding priority (First Class boards first). If a Basic Economy passenger waits over 2 hours (Aging), the gate agent upgrades their ticket priority so they can board.
4Diagram / Visual Representation
5Working / How It Works
- FCFS Algorithm: Ready Queue managed as FIFO -> Execute head process until completion -> Pop head -> Repeat.
- SJF (Non-Preemptive): Search Ready Queue -> Select process with minimum -> Execute to completion.
- SRTF (Preemptive SJF): At every new process arrival -> Compare new job against remaining time of current running job -> If new job is smaller, preempt running job -> Dispatch new job.
- Priority Scheduling + Aging: Select process with highest priority score -> If lower-priority process waits for time interval , increment its priority parameter by units.
6Types / Components / Characteristics
- Algorithm Comparison Matrix:
| Algorithm | Preemptive? | Criteria | Convoy Effect? | Starvation Risk? | Major Disadvantage |
|---|---|---|---|---|---|
| FCFS | No | Arrival Time | Severe | No | High Average Waiting Time |
| SJF | No | Burst Time | Yes (If 1st job long) | Yes (Long jobs) | Requires impossible future BT estimation |
| SRTF | Yes | Remaining BT | No | Yes (Long jobs) | High context-switching overhead |
| Priority | Both | Priority Score | Yes | Severe (Low priority) | Low priority processes may starve indefinitely |
7Solved Examples / Problems
Problem: Given the following processes, calculate Average Waiting Time for SJF (Non-Preemptive):
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 ms | 7 ms |
| P2 | 2 ms | 4 ms |
| P3 | 4 ms | 1 ms |
| P4 | 5 ms | 4 ms |
Solution:
- t = 0 ms: Only P1 is available. P1 starts executing (runs t=0 to 7 ms).
- t = 7 ms: P1 completes. Ready Queue contains P2 (BT=4), P3 (BT=1), P4 (BT=4).
- Smallest BT is P3 (1 ms). P3 runs t=7 to 8 ms.
- t = 8 ms: P3 completes. Ready Queue contains P2 (BT=4), P4 (BT=4). FCFS tie-breaker -> P2 runs t=8 to 12 ms.
- t = 12 ms: P2 completes. P4 runs t=12 to 16 ms.
- Gantt Chart:
[ P1 (0-7) | P3 (7-8) | P2 (8-12) | P4 (12-16) ] - CT: P1=7, P3=8, P2=12, P4=16.
- TAT (CT - AT): P1=7, P2=10, P3=4, P4=11.
- WT (TAT - BT): P1=0, P2=6, P3=3, P4=7.
- Average Waiting Time: .
8Advantages, Disadvantages & Applications
- SRTF Advantage: Gives mathematically minimum average waiting time for a given set of processes.
- SRTF Disadvantage: Impossible to implement perfectly in general OSs because predicting a process's exact future CPU burst time is impossible.
9Important Points to Remember
- Aging is the primary technique used to eliminate starvation in Priority scheduling.
- SJF is a special case of general Priority scheduling where Priority is inversely proportional to Burst Time.
10Test Your Understanding
- MCQ: Which CPU scheduling algorithm yields the theoretical minimum average waiting time for a set of processes?
- A) FCFS
- B) Round Robin
- C) Preemptive Shortest Job First (SRTF)
- D) Multilevel Queue
Show answer
C. - Conceptual Question: Define the Convoy Effect and explain why it occurs in FCFS scheduling.
- Application Question: Explain how Aging prevents process starvation in priority-based schedulers.
