CPU调度

CPU调度是操作系统的一项功能，它决定了下一个在处理器上运行的就绪进程或线程，旨在平衡响应性、吞吐量、公平性和满足截止日期等目标。

Definition

CPU调度是操作系统从可运行进程或线程中选择一个分配给处理器并决定分配时长，以优化所选性能和公平性目标的策略和机制。

Scope

本主题涵盖调度策略及其评估：先来先服务、最短作业优先、轮转调度、优先级调度和多级反馈队列；抢占式调度与非抢占式调度；CPU利用率、吞吐量、周转时间、等待时间和响应时间等衡量标准；以及多处理器和实时系统中的调度。它不包括被调度任务的表示（进程和线程管理）和同步（并发）。

Core questions

• 调度质量通过哪些标准来衡量？
• 常见的调度算法在公平性和效率方面有何不同？
• 调度程序何时应该抢占正在运行的任务？
• 调度如何适应多处理器和实时截止日期？

Key concepts

• 先来先服务
• 最短作业优先
• 轮转调度和时间片
• 优先级调度
• 多级反馈队列
• 抢占式与非抢占式
• 周转时间、等待时间和响应时间
• 饥饿和老化
• 实时调度

Key theories

调度目标和权衡

没有单一策略能优化所有目标：最短作业优先能最小化平均等待时间但可能导致长作业饥饿，轮转调度在牺牲一定吞吐量的情况下限制了响应时间，优先级方案存在饥饿风险，因此调度程序需要为其工作负载平衡吞吐量、公平性和响应性。

Mechanisms

当进程阻塞、让出或其时间片到期时，调度程序会运行，并根据其策略从就绪队列中选择下一个任务。轮转调度依次为每个任务分配一个时间片；优先级调度和多级反馈队列根据重要性和观察到的行为对任务进行排序，并使用老化机制防止饥饿。抢占式调度程序可以中断正在运行的任务，以切换到更高优先级的任务，这对于交互性和实时截止日期至关重要。

Clinical relevance

调度直接影响用户体验和系统效率：它决定了交互式应用程序是否响应迅速，批处理工作负载是否能快速完成，以及实时任务是否能满足截止日期。Linux等生产系统中的调度程序在众多核心和多样化工作负载之间平衡这些相互竞争的目标。

History

调度问题随着20世纪60年代多道程序设计和分时系统的出现而产生，当时开发了轮转调度和优先级方案来共享处理器。实时调度理论，包括速率单调和最早截止日期优先分析，于20世纪70年代正式确立，现代多核调度程序将这些思想扩展到多个处理器。

Debates

公平性与吞吐量和优先级

调度程序必须在任务间的公平性、最大化吞吐量和尊重优先级之间进行协调；激进的优先级划分可以改善重要任务的性能，但有使其他任务饥饿的风险，而严格的公平性可能导致系统利用率不足，因此实际的调度程序会调整这种平衡。

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

抢占式调度和非抢占式调度有什么区别？

非抢占式调度允许正在运行的任务一直占用处理器，直到它阻塞或完成。抢占式调度可以强制剥夺处理器——例如当其时间片到期或更高优先级的任务就绪时——这提高了响应性，并且是实时保证所必需的。

什么是饥饿，如何防止？

饥饿是指一个任务因为更高优先级的任务持续优先而从未被调度。通常通过老化机制来防止，老化机制会逐渐提高长时间等待任务的优先级，使其最终能够运行。