Operating Systems Deep-Learning Notes: CPU Scheduling (Chapter 5)

1. Core Concepts and Dispatch Mechanism

CPU-I/O Burst Cycle

A process does not occupy the CPU continuously. Instead, its execution consists of alternating CPU bursts and I/O bursts.

Statistics over a large number of processes show that systems contain many short CPU-burst processes and only a small number of long CPU-burst processes. This distribution is an important basis for designing scheduling algorithms.

Dispatcher & Dispatch Latency

The dispatcher is the module that actually performs the “switch” action. Dispatch latency is the time required to stop one process and start another.

In systems with strict requirements, the conflict phase of dispatch latency is the main bottleneck. It includes two steps:

  1. Preempt any process running in kernel mode.
  2. Let low-priority processes release the system resources needed by high-priority processes.

2. Core Scheduling Algorithms

FCFS (First-Come, First-Served)

  • Pain point: the convoy effect. If a long CPU-bound process is at the front of the queue, a group of short I/O-bound processes behind it are forced to wait for a long time, reducing both CPU and I/O-device utilization.

SJF (Shortest Job First) and Burst-Time Prediction

SJF theoretically gives the minimum average waiting time. The hard part is knowing how long the next CPU burst will be.

Operating systems usually use historical data and exponential averaging to predict the next burst length:

$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

  • $t_n$: the actual length of the $n$-th CPU burst.
  • $\tau_n$: the predicted value for the $n$-th burst.
  • $\alpha$: the weight coefficient, often set to 1/2, determining how much recent history affects the prediction.

RR (Round Robin)

Designed for time-sharing systems. Each process receives a time quantum $q$, usually 10 to 100 milliseconds.

  • Core constraint: the time quantum $q$ must be much larger than context-switch time, which is usually less than 10 microseconds. If $q$ is too small, most CPU time is wasted on context-switch overhead.

Multilevel Feedback Queue

This is the most complex but also the most general algorithm. It allows processes to move among multiple queues according to runtime behavior. A multilevel feedback queue scheduler needs these parameters:

  • The number of queues.
  • The scheduling algorithm inside each queue, for example RR at the top level and FCFS at the bottom.
  • The method for promoting a process to a higher-priority queue, such as aging.
  • The method for demoting a process to a lower-priority queue, such as using up its time quantum.
  • The method for deciding which queue a process enters initially.

3. Thread Scheduling

In systems that support threads, the actual scheduling unit is the thread. There are two contention scopes:

  • PCS (Process Contention Scope): the thread library schedules threads in user space, and threads within the same process compete with each other.
  • SCS (System Contention Scope): the operating-system kernel directly schedules kernel-level threads onto logical CPUs, and all threads in the system compete with each other.

In the POSIX API (pthread), programmers can specify the contention scope using PTHREAD_SCOPE_PROCESS or PTHREAD_SCOPE_SYSTEM, but the final result depends on OS support. Linux and macOS support only SCS.

4. Advanced Multiprocessor and Multicore Scheduling

Modern Hardware Architecture

  • Physical Core: a real independent processing unit on the chip.
  • Logical CPU: the execution unit seen by the OS when hardware multithreading, such as hyper-threading, is supported.
  • Two-level scheduling model:
    • Level 1 (OS layer): decides which software thread runs on which logical CPU.
    • Level 2 (hardware layer): the physical core automatically switches which hardware thread to execute based on memory stalls, filling gaps while waiting for data.

Multicore Architecture and Memory Stalls

Modern CPUs often stall while waiting for memory data. To make use of these stall cycles, processors use hardware multithreading, such as hyper-threading. When one hardware thread experiences a memory stall, the physical core can quickly switch to executing instructions from another hardware thread.

NUMA Awareness

In Non-Uniform Memory Access (NUMA) architectures, a CPU accesses local memory much faster than remote memory.

NUMA-aware scheduling: when scheduling, the operating system should not only allocate CPU time but also assign processes to processor domains whose memory nodes are closest to that CPU, reducing migration across physical nodes.

5. Mathematical Constraints in Real-Time CPU Scheduling

Real-time systems handle periodic tasks. These tasks have three core parameters:

  • $t$: processing time
  • $d$: deadline
  • $p$: period

Constraint: $0 \le t \le d \le p$. The task execution rate is $1/p$.

Core Logic of Two Real-Time Algorithms

  • RMS (Rate-Monotonic Scheduling): static priority. Priority is determined by the reciprocal of the period. Shorter period means higher priority. Its drawback is that when CPU utilization is high, it cannot guarantee that every process meets its deadline.
  • EDF (Earliest Deadline First): dynamic priority. The system always checks which task has the nearest deadline, and that task immediately receives the highest priority.
  • POSIX real-time standard: defines SCHED_FIFO, a FIFO policy without time slicing, and SCHED_RR, a round-robin policy with time slicing.

6. Scheduler Implementations in Three Major Operating Systems

Linux CFS (Completely Fair Scheduler)

  • Core idea: instead of allocating fixed time slices, allocate proportions of CPU usage.
  • vruntime (virtual runtime): records actual task runtime. It is scaled by the task’s Nice value, from -20 to +19. Tasks with lower Nice values, hence higher priority, have slower-growing vruntime and therefore receive more real CPU time.
  • Data structure: runnable tasks are stored in a Red-Black Tree keyed by vruntime. The scheduler always selects the leftmost node, namely the node with the smallest vruntime, with $O(\log N)$ time complexity.

Windows (Preemptive Priority Scheduling)

  • Priority system: 32 levels. Levels 1-15 are variable priorities for normal programs, levels 16-31 are real-time priorities, and level 0 is reserved for memory management.
  • Dynamic boost mechanism: when an event a thread is waiting for completes, especially foreground keyboard I/O, Windows gives the thread a large priority boost. The foreground active window also receives three times the time quantum.
  • UMS (User-Mode Scheduling): allows applications to manage a large number of concurrent threads independently of the kernel, greatly improving the efficiency of C++ concurrency frameworks.

Solaris (A Peak Application of Multilevel Feedback Queues)

Solaris’s default time-sharing (TS) scheduler uses a complex Dispatch Table to achieve balance through state transitions:

  • Time quantum expired penalty: if a process uses up its entire time quantum, indicating that it is compute-intensive, it is moved to a lower priority, but receives a longer time quantum next time.
  • Return from sleep reward: if a process gives up the CPU early to wait for I/O, indicating interactivity, it is promoted to a higher priority when it wakes up and receives a shorter time quantum.

7. Algorithm Evaluation Models

To evaluate which scheduling algorithm best fits an operating system, common methods include:

  • Queueing Models: describe the computer as a network of servers and use probability theory to compute steady-state performance. The most famous result is Little’s Law:
    $n = \lambda \times W$
    (average queue length $n$ = average arrival rate $\lambda$ $\times$ average waiting time $W$ in the queue)
  • Simulations: build a model of the computer system through programming, then use real system event logs, called trace tapes, as input to drive the simulation and obtain highly accurate performance statistics.