Topic 4.2 · CPU Scheduling Algorithms

FCFS & Convoy Effect, SJF & SRTF, Priority & Aging

4 min read1 question to test yourself

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

000 ms000 ms000 ms000 ms000 ms000 ms000 msP1 · 30 ms P2 · 2 ms P3 · 2 ms CPUFCFS convoy effect · illustrative schedule
000 ms500 ms000 ms500 ms000 ms500 ms000 ms500 ms000 ms500 ms000 ms500 ms000 msP1 · runs first P2 · arrives at t=2 P1 · resumes CPUSRTF · shorter arriving job preempts P1

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 BTBT -> Execute to completion.
  • SRTF (Preemptive SJF): At every new process arrival -> Compare new job BTBT against remaining time of current running job -> If new job BTBT 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 TT, increment its priority parameter by KK 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:

  1. t = 0 ms: Only P1 is available. P1 starts executing (runs t=0 to 7 ms).
  2. 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.
  3. t = 8 ms: P3 completes. Ready Queue contains P2 (BT=4), P4 (BT=4). FCFS tie-breaker -> P2 runs t=8 to 12 ms.
  4. 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: 0+6+3+74=164=4.0 ms\frac{0 + 6 + 3 + 7}{4} = \frac{16}{4} = \mathbf{4.0 \text{ ms}}.

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

  1. 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.
  2. Conceptual Question: Define the Convoy Effect and explain why it occurs in FCFS scheduling.
  3. Application Question: Explain how Aging prevents process starvation in priority-based schedulers.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic