操作系统任务调度案例分析

我们来看这么一个场景：

在拥有成百上千个进程/线程的现代操作系统中，如何决定下一个该由哪个任务运行，既要保证响应性（交互式任务），又要保证吞吐量（计算密集型任务），还要防止饥饿？

在Linux CFS中使用了红黑树来解决这样的问题。红黑树 用于组织所有可运行的进程。并基于优先级、时间片轮转、虚拟运行时间进行进程调度。进程按照其计算出的 vruntime（虚拟运行时间）作为键值存储在红黑树中。当进程变为可运行或阻塞时，高效（O(log n)）地将其插入或从红黑树中删除。

调度器总是选择 vruntime 最小的进程（即红黑树最左侧节点），这保证了最“欠”CPU 时间的进程优先运行，实现近似完美的公平调度（O(1) 选择复杂度）。红黑树优秀的 O(log n) 插入/删除性能和 O(1) 获取最小值性能，完美支撑了 CFS 调度算法的公平性和高效性要求。而其他数据结构（如简单链表）很难实现这种高效的公平调度。