CPU 调度如何工作，有哪些常见算法？

Question

CPU 调度如何工作，有哪些常见算法？

IT Interview Practice · Accepted Answer

**CPU 调度（CPU scheduling）** 是 kernel 决定*哪个*就绪线程*接下来*获得 CPU、以及运行*多久*。由于可运行的线程通常比 core 多，**scheduler** 把它们多路复用，力求在相互竞争的目标之间取得平衡——**吞吐量（throughput）**、**低延迟 / 响应时间**和**公平性**——同时避免**饥饿（starvation）**。

## 常见算法

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin** 展示了那个核心旋钮——**quantum**：

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## 真实的 scheduler

Linux 长期以来的默认是 **CFS（Completely Fair Scheduler）**：它不用固定时间片，而是跟踪每个任务的 **virtual runtime（vruntime）**，并总是运行到目前为止获得 CPU 最少的线程，再按其 **nice** 值加权——近似于“人人都得到公平的一份”。它用红黑树（red-black tree）以 vruntime 为键，因此挑选下一个任务是 O(log n)。（更新的 kernel 使用 EEVDF，一种目标相同、并带有更紧延迟边界的改良。）

**抢占式 vs 协作式（Preemptive vs cooperative）：** 现代操作系统是**抢占式**的——一个 timer interrupt 让 scheduler 能强行收回 CPU，因此一个线程无法独占一个 core。

## 为什么这很重要

调度直接塑造用户感受到的延迟和吞吐量。面试官探讨它，是想看你是否理解取舍——为什么交互式工作负载想要短 quantum 或优先级提升，为什么 priority scheduling 需要 **aging** 来防止饥饿，以及 MLFQ/CFS 如何在事先不知道 job 长度的情况下得到良好的交互行为。这也是调整 `nice`、real-time priority，以及诊断一个被饿死或卡顿的 service 背后的思维模型。

常见算法

真实的 scheduler

为什么这很重要

相关问题