CPU Scheduling

EuroSys 2016, London. Lozi, Lepers and the EPFL/UBC team publish "The Linux Scheduler: A Decade of Wasted Cores." They find four bugs in CFS, the default Linux scheduler since 2007. Symptom: cores idle for seconds while ready threads wait in the runqueue. Impact: kernel make 13% slower, TPC-H throughput down 14-23%, sync-heavy workloads losing performance by orders of magnitude. A decade of production servers under-using their CPUs, unnoticed, because the invariant "a ready thread on a free core" was never checked. The OS scheduler is not an academic discipline, it is money.

• **Smartphones**: the scheduler prioritizes UI threads (touch, animation) to keep the interface responsive even while background sync and antivirus are running. Android uses CFS with priorities.
• **Web servers**: Nginx handles thousands of concurrent connections. The scheduler distributes CPU among worker processes, keeping latency low for all clients.
• **Video editors**: rendering burns CPU, but the scheduler gives UI threads time-slices so the interface stays interactive. Priority scheduling with preemption keeps the editor usable.

Цели урока

• Compare FCFS, SJF, RR, Priority, MLFQ, CFS by latency vs throughput vs fairness
• Draw a Gantt chart for a job set under different scheduling disciplines
• Reason with the right metrics: turnaround time, waiting time, response time, jitter
• Explain Linux CFS internals: vruntime, red-black tree, weights derived from nice values
• Know when SCHED_FIFO/SCHED_DEADLINE are required and the trade-offs of real-time scheduling

Historical context

In 1961 Fernando Corbato presented CTSS (Compatible Time-Sharing System) at MIT - the first system to share CPU time among multiple users. Before CTSS, computers ran in batch mode: one program at a time, no switching. CTSS implemented Round Robin at the user level. In 1964 Multics (Unix's direct ancestor) extended it with multilevel priority queues. Linux's CFS, shipped in 2007, replaced the old O(1) scheduler with a red-black tree keyed on virtual runtime - same core idea, 46 years later.

Scheduling Criteria

Five metrics determine how well a scheduler uses CPU time. Every algorithm optimizes some subset - no algorithm wins on all five simultaneously.

For interactive systems (desktop, mobile), Response Time and Waiting Time dominate. For batch systems (data pipelines, rendering farms), Throughput and Turnaround Time matter most.

FCFS (First-Come, First-Served)

FCFS is the simplest scheduler: processes run in arrival order. Non-preemptive - once a process starts, it runs to completion.

Principle: first come, first served. A plain FIFO queue.

The Convoy Effect is the core FCFS pathology. One long-running process blocks all short processes behind it - like cars stuck behind a slow truck on a one-lane road.

FCFS advantages: trivial implementation (FIFO queue), fair in arrival-order sense, zero switching overhead. Disadvantages: high average waiting time (convoy effect), unusable for interactive systems, short processes suffer.

SJF (Shortest Job First)

SJF picks the process with the shortest burst time next. It is provably optimal for minimizing average waiting time. The catch: real systems cannot know burst times in advance.

Two variants: non-preemptive (SJF) - current process runs to completion; preemptive (SRTF - Shortest Remaining Time First) - a shorter arriving process can preempt the running one.

SJF's fatal flaw: Starvation. A long process may wait forever if short processes keep arriving. Solution: Aging - gradually increase priority the longer a process waits.

The Prediction Problem: burst time is unknown at submission. Production systems use exponential averaging of past bursts:

Round Robin (RR)

Round Robin is the backbone of time-sharing. Each process gets a fixed time quantum; when it expires, the process goes to the back of the queue. Preemptive by definition, starvation-free by construction.

Principle: processes rotate through the CPU in fixed-size slices. Equal share for all, no process waits forever.

RR advantages: fairness (every process gets CPU), no starvation, excellent response time for interactive systems, simple implementation. Disadvantages: average waiting time higher than SJF, context switch overhead, poor for processes with different priorities.

Priority Scheduling

Each process carries a priority number. The CPU goes to the highest-priority ready process. This is the basis of every production OS scheduler - including Linux CFS and Windows thread priorities.

Priority can be static (fixed at creation) or dynamic (adjusted during execution). The latter prevents starvation through Aging.

Modern systems use hybrid approaches. Linux CFS (Completely Fair Scheduler) combines priorities with virtual runtime (vruntime): the process with the lowest accumulated CPU time runs next. Windows uses 32 priority levels with dynamic boost for foreground threads.

Key Ideas

• Five metrics: CPU utilization, Throughput, Turnaround Time, Waiting Time, Response Time. No algorithm wins all five.
• FCFS: simple FIFO, suffers from Convoy Effect - one long process blocks all short ones
• SJF: optimal for average wait time, but burst time is unknowable - use exponential averaging in practice
• Round Robin: fixed time quantum, starvation-free, excellent response time - the default for interactive systems
• Priority Scheduling: combine with Aging to prevent starvation; Linux CFS uses virtual runtime for fairness

Related Topics

CPU Scheduling underpins several other OS mechanisms:

• Processes and Context Switching — Context switch cost constrains time quantum choice in Round Robin
• Synchronization — Priority inversion arises when scheduling meets mutex ownership
• Deadlocks — Priority inversion is a deadlock-adjacent pathology in priority-based systems

Вопросы для размышления

• Which scheduling algorithm makes sense for a smartwatch OS? Why do response time and energy efficiency pull in opposite directions?
• Can SJF and Round Robin be combined - SJF for batch processes, RR for interactive ones? What problems arise at the boundary?
• Linux CFS uses virtual runtime (vruntime) instead of priorities. How does this achieve fairness without starvation?

Связанные уроки

• os-02-processes — Process lifecycle and context switching are prerequisites for scheduling concepts
• os-03-threads — Modern schedulers work at thread level, not process level
• os-05-sync — Priority inversion - a scheduling pathology caused by improper synchronization
• os-06-deadlocks — Priority inversion (like on Mars Pathfinder) is a deadlock-like condition produced by bad scheduler interaction
• ds-04-queues — FCFS is literally a FIFO queue; Round Robin is a circular buffer - scheduling is queuing theory applied to processes
• rt-24