Multilevel and Real-Time Scheduling

The Airport Boarding Gate

The gate agent calls: "We are now boarding first-class passengers." Then: "Business class." Then: "Zone 1 economy." Finally: "All remaining passengers."

Within each group, passengers board by seat row. The policy combines two levels of ordering: first by class (permanent, fixed when you bought the ticket), then by seat position within class.

This two-level structure — broad categories with ordering rules inside each — is exactly how multilevel scheduling works in operating systems. Processes are permanently or dynamically assigned to queues, and each queue has its own scheduling policy.

Multilevel Queue Scheduling

In a Multilevel Queue, processes are permanently divided into distinct groups at creation, each assigned to a separate queue. Each queue has its own scheduling algorithm.

Typical Structure (Five Levels)

Queue 0: System Processes        [Highest Priority]  → FCFS
Queue 1: Interactive Processes                       → Round Robin
Queue 2: Interactive Edit Jobs                       → Round Robin
Queue 3: Batch Processes                             → FCFS
Queue 4: Student/Background Jobs  [Lowest Priority]  → FCFS

The scheduler always services higher-priority queues first. Queue 1 only runs when Queue 0 is empty. Queue 4 runs only when all others are empty.

Problem: If high-priority queues are perpetually busy, lower queues starve. A student batch job might wait indefinitely while interactive and system processes constantly arrive.

Solution: Allocate a fixed percentage of CPU time to each queue. For example: 80% for interactive, 20% for batch. This prevents starvation while preserving priority ordering.

Multilevel Feedback Queue (MLFQ)

The Multilevel Feedback Queue fixes the permanent-assignment problem. Processes can move between queues based on their behavior. This allows the scheduler to adapt dynamically.

Rules

1. New processes enter the highest-priority queue
2. If a process uses its full time quantum without completing, it is demoted to a lower queue
3. If a process finishes early (blocked on I/O), it stays in its current queue or moves up
4. Processes in lower queues get longer time quanta

Queue 0: quantum = 8 ms    [Highest priority — likely interactive]
    ↓ (if uses full quantum)
Queue 1: quantum = 16 ms   [Medium priority — longer jobs]
    ↓ (if uses full quantum)
Queue 2: FCFS              [Lowest priority — CPU-bound batch jobs]

Why This Works

• A new short interactive job enters Queue 0, gets fast service, finishes quickly
• A long CPU-bound job slowly sinks to Queue 2 where it gets long uninterrupted CPU time
• The scheduler learns process behavior through observation — no static classification needed

MLFQ is used in Windows (with priority levels), macOS, and forms the conceptual basis for many production schedulers.

Real-Time Scheduling

Real-time systems have tasks with strict timing requirements. Missing a deadline is not just slow — it is incorrect. Two categories exist:

Real-time scheduling is not about being fast — it is about being predictable and guaranteed.

Key Concepts

• Period (T): how often a task must execute (e.g., every 50 ms)
• Deadline (D): when each execution must complete (often D = T)
• Execution Time (C): how long one execution takes

Utilization: U = C / T for each task. Total system utilization = sum of all tasks' U values.

Rate Monotonic Scheduling (RMS)

Type: Static priority, preemptive

Rule: Assign priority based on period — shorter period = higher priority. Priorities are fixed and never change at runtime.

Example

Total utilization: 0.90 (within the RMS bound for 2 tasks: 2(2^(1/2)−1) ≈ 0.83... this set is actually over the bound and may miss deadlines, illustrating the limit)

RMS Schedulability Bound: n tasks are schedulable if:

Sum(Ci/Ti) ≤ n × (2^(1/n) − 1)

For 1 task: ≤ 1.0; for 2 tasks: ≤ 0.828; for ∞ tasks: approaches ln(2) ≈ 0.693

Earliest Deadline First (EDF)

Type: Dynamic priority, preemptive

Rule: Always run the task whose absolute deadline is earliest. Priorities change dynamically as deadlines approach.

EDF is theoretically optimal for preemptive scheduling — it can schedule any feasible task set (one with total utilization ≤ 1.0).

Time 0: T1 deadline=50, T2 deadline=25 → run T2 (earlier deadline)
Time 10: T2 done. T1 still active → run T1 (only task)
Time 25: T2 period restarts, deadline=50 → T1 still has earlier deadline (50 vs 50, tie)

Advantage over RMS: EDF can schedule utilizations up to 100% (vs ~69% for RMS with many tasks)

Disadvantage: Higher runtime overhead (must re-evaluate priorities on every event); harder to implement correctly

Linux Completely Fair Scheduler (CFS)

Linux's default scheduler (since kernel 2.6.23) is neither pure Round Robin nor pure priority. It uses a concept called virtual runtime.

Core idea: Every process should receive exactly its fair share of CPU time. CFS tracks how much CPU time each process has received (virtual runtime). The process with the smallest virtual runtime always runs next.

vruntime += actual_runtime × (1024 / process_weight)

Higher-priority processes have higher weights, so their virtual runtime increases more slowly — meaning they get selected more often.

Data structure: CFS stores processes in a red-black tree sorted by virtual runtime. The leftmost node (smallest vruntime) is always the next process to run. Selection is O(log n).

Algorithm Comparison

Summary

Scheduling at scale is not a single algorithm — it is a layered policy:

1. Separate processes by class (multilevel queue) — system vs user vs batch
2. Adapt to process behavior (MLFQ) — reward interactive processes, deprioritize CPU hogs
3. Meet timing guarantees (RMS, EDF) — real-time tasks have deadlines that must be honored
4. Fair distribution (CFS) — no process monopolizes CPU over time

Modern production operating systems implement variants of MLFQ for general workloads and add real-time scheduling classes (SCHED_FIFO, SCHED_RR in Linux) for processes that declare hard timing requirements.