Scheduling Algorithms Explained: What the Cafeteria Lady Teaches About First‑Come‑First‑Serve

Imagine a university cafeteria at noon where a staff member serves students one by one; this simple scenario illustrates the most basic scheduling algorithm—First‑Come‑First‑Serve (FCFS). In operating systems, CPU scheduling decides which process gets the CPU first, essentially answering "who uses the CPU first, who uses it later".

The scheduling hierarchy consists of three levels: (1) high‑level (job) scheduling, deciding which jobs enter the system; (2) mid‑level (swap) scheduling, deciding which processes are swapped out of memory; and (3) low‑level (process) scheduling, deciding which ready process runs on the CPU.

First‑Come‑First‑Serve (FCFS)

时间线：
T1: 进程A到达，开始执行（需要5ms）
T6: 进程B到达，开始执行（需要3ms）
T9: 进程A完成，进程B执行
T12: 进程B完成

A的等待时间 = 0ms
B的等待时间 = 3ms（T6到达，T9才执行）
平均等待时间 = 1.5ms

Simple and fair: whoever arrives first runs first.

Even a cafeteria worker would use it.

"Guard‑effect": a long task can block many short tasks behind it.

比如：你只打一个菜，前面大哥点了10个菜
等轮到你，黄花菜都凉了

Shortest Job First (SJF)

进程：
A：需要5ms
B：需要2ms  ← 先做这个！
C：需要4ms

执行顺序：B → C → A
平均等待时间最短

Minimizes average waiting time.

Short tasks finish quickly.

Can cause starvation of long tasks.

Requires knowing execution time in advance, which is hard.

Round Robin (RR)

时间片 = 10ms

进程A（需要30ms）：
10ms → 放回去排队
10ms → 放回去排队
10ms → 完成

进程B（需要20ms）：
10ms → 放回去排队
10ms → 完成

Key Parameter: Time‑Slice Size

时间片太大 → 退化成FCFS，响应差
时间片太小 → 上下文切换开销大，系统变慢
理想时间片 ≈ 80%的进程在这个时间内完成

Fair: every process gets CPU time.

Good response time, suitable for time‑sharing systems.

Choosing the slice is difficult.

Context‑switch overhead can degrade performance.

Priority Scheduling

优先级高 → 先执行

进程A：优先级3（低）
进程B：优先级7（中）
进程C：优先级10（高）

执行顺序：C → B → A

Problem: Priority Inversion

高优先级进程P1在等待
中优先级进程P2在运行
低优先级进程P3持有P1需要的资源

结果：P2抢占了P3的CPU时间
      P3没机会释放资源
      P1只能一直等

这就是"优先级反转"，火星探测器曾因此出事！

Solution: Priority Inheritance

P1等P3的资源 → P3临时继承P1的优先级
          → P3不会被P2抢占
          → P3快速完成任务释放资源
          → P1继续执行

Multilevel Feedback Queue (MLFQ)

队列结构：
[第一级队列] ← 高优先级，时间片2ms
[第二级队列] ← 中优先级，时间片4ms
[第三级队列] ← 低优先级，时间片8ms

New processes enter the first‑level queue.

If a time slice expires without completion, the process moves down one level.

Short tasks finish quickly in the first level.

Long tasks gradually descend but are never starved.

示意图：
        新进程进来
            ↓
    ┌─────────────────────┐
    │   第一级（2ms）      │
    │   做完了 → 走人      │
    │   没完 → 降到第二级  │
    └─────────────────────┘
            ↓
    ┌─────────────────────┐
    │   第二级（4ms）      │
    │   做完了 → 走人      │
    │   没完 → 降到第三级  │
    └─────────────────────┘
            ↓
    ┌─────────────────────┐
    │   第三级（8ms）      │
    │   按FCFS轮转         │
    └─────────────────────┘

Real‑World Implementations

Windows

Before Vista: single‑priority queue.

After Vista: multilevel feedback queue with dynamic adjustments.

Linux

Kernel < 2.6: O(n) scheduler.

2.6 and later: Completely Fair Scheduler (CFS) – each process has a "virtual run time"; the one with the smallest virtual time runs first, ensuring fairness rather than strict FCFS.

macOS / iOS

Based on MLFQ.

Different queues for foreground and background processes.

Summary of Core Points

Scheduling algorithms determine the order in which processes use the CPU.

FCFS is simple but suffers from the guard‑effect.

SJF yields the shortest average wait but can starve long tasks.

RR provides fair, responsive time‑sharing; slice size is critical.

Priority scheduling favors urgent tasks but may cause inversion.

MLFQ combines multiple advantages and is widely used in modern OSes.