进程调度：从 CFS 到 EEVDF 的哲学演变
内容提要
本文讨论了Linux调度器的演变历程，包括O(1)调度器、CFS和EEVDF。O(1)调度器通过启发式方法检测交互性，复杂性较高；CFS引入虚拟运行时间以实现公平性，但在短期公平性方面存在不足。EEVDF通过虚拟合格时间和虚拟截止时间的引入，改善了CFS的缺陷，确保了更好的短期公平性和延迟控制。调度器设计的关键在于用数学模型替代启发式方法，以实现更高效的资源分配。
关键要点
-
Linux调度器的演变历程包括O(1)调度器、CFS和EEVDF。
-
O(1)调度器通过启发式方法检测交互性，但复杂性较高。
-
CFS引入虚拟运行时间以实现公平性，但在短期公平性方面存在不足。
-
EEVDF通过虚拟合格时间和虚拟截止时间的引入，改善了CFS的缺陷，确保了更好的短期公平性和延迟控制。
-
调度器设计的关键在于用数学模型替代启发式方法，以实现更高效的资源分配。
延伸解读
调度器设计的挑战
调度器的设计面临多重挑战，包括公平性、响应性和吞吐量之间的权衡。每一代调度器都在这些目标中寻找平衡，O(1)调度器偏向响应性，而CFS则更注重公平性。EEVDF的引入旨在解决CFS在短期公平性上的不足，确保更好的延迟控制。
EEVDF的优势与应用
EEVDF通过引入虚拟合格时间和虚拟截止时间，消除了CFS中的许多启发式补丁，使得调度决策更加可预测。它在处理短期公平性和延迟控制方面表现优越，适合对延迟敏感的应用场景，如实时音频和视频处理。
调度器的数学模型
调度器的演变从启发式方法转向数学模型，反映了系统设计的深刻变化。CFS通过虚拟运行时间实现了更高效的资源分配，而EEVDF进一步优化了这一模型，确保了在多核环境下的公平性和响应性。这种数学化的设计理念值得在其他系统设计中借鉴。
延伸问答
CFS调度器的核心思想是什么？
CFS调度器的核心思想是维护每个进程的虚拟运行时间（vruntime），每次调度选择vruntime最小的进程运行。
EEVDF相较于CFS有哪些改进？
EEVDF通过引入虚拟合格时间和虚拟截止时间，改善了CFS的短期公平性和延迟控制问题。
O(1)调度器的主要缺陷是什么？
O(1)调度器的主要缺陷在于其启发式交互性检测，导致对进程类型的误判和不可预测的调度行为。
调度器设计中公平性、响应性和吞吐量之间的关系是什么？
这三者形成了一个不可能三角，追求极致的公平性会导致频繁抢占和上下文切换开销增加，从而降低吞吐量。
EEVDF如何确保延迟控制？
EEVDF通过引入虚拟截止时间和lag的概念，确保进程在获得CPU时不会出现过度补偿，从而控制延迟。
CFS调度器的响应性如何影响用户体验？
CFS调度器的响应性影响用户体验，因为它需要优先调度I/O密集型进程，以确保系统在用户交互时能够快速响应。
