操作系统中的进程调度算法：完全公平调度器（Completely Fair Scheduler, CFS） 1. 问题描述 完全公平调度器（CFS）是Linux内核默认的进程调度算法，其核心目标是 公平分配CPU时间 给所有可运行进程，同时兼顾交互式进程的响应速度。与传统的基于时间片轮转或优先级的调度器不同，CFS通过 虚拟运行时间（vruntime） 量化进程的CPU使用量，并选择vruntime最小的进程执行，以实现“完全公平”。 2. 核心思想：公平性与权衡 CFS的设计需解决两个关键问题： 如何定义公平？ 理想情况下，每个进程应获得相等的CPU时间（例如，有n个进程时，每个进程获得1/n的CPU时间）。 但需考虑进程优先级（优先级高的进程应获得更多资源）。 如何避免频繁切换？ 调度频率过高会导致上下文切换开销，过低则降低响应速度。 3. 关键机制：虚拟运行时间（vruntime） （1）vruntime的计算 每个进程有一个 vruntime 变量，记录其“已使用的CPU时间”经优先级加权后的值。 公式： \[ \text{vruntime} = \text{实际运行时间} \times \frac{\text{优先级权重基准}}{\text{进程优先级权重}} \] 优先级权重 ：Linux中优先级（0~139）映射为权重值，优先级越高权重越大。 效果 ：高优先级进程的vruntime增长更慢，低优先级进程的vruntime增长更快，从而让高优先级进程获得更多CPU时间。 （2）示例说明 假设系统基准权重为1024： 进程A（优先级高，权重=2048）：运行1秒后，vruntime增加 \( 1 \times \frac{1024}{2048} = 0.5 \) 秒。 进程B（优先级低，权重=512）：运行1秒后，vruntime增加 \( 1 \times \frac{1024}{512} = 2 \) 秒。 调度策略 ：选择vruntime最小的进程执行。因此，进程A的vruntime增长慢，更易被再次调度。 4. 数据结构：红黑树（Red-Black Tree） CFS使用红黑树维护可运行进程的vruntime排序： 键值 ：进程的vruntime。 最小节点 ：树的最左节点是vruntime最小的进程，即下一个待调度进程。 操作效率 ：插入、删除、查找最小节点的时间复杂度均为O(log n)，高效支持大量进程。 5. 调度过程详解 （1）调度触发时机 进程主动放弃CPU（如等待I/O）。 时钟中断（定期检查是否需要切换进程）。 新进程创建或唤醒。 （2）调度决策 从红黑树中选择vruntime最小的进程。 计算该进程的 实际运行时间 ： CFS设定一个目标延迟（ sched_latency ，默认6ms），表示所有可运行进程至少轮流执行一次的时间。 每个进程的时间片 = sched_latency / n （n为进程数）。 若进程数过多，为保证响应速度，时间片下限为 min_granularity （默认0.75ms）。 （3）新进程的vruntime初始化 为避免新进程的vruntime远小于老进程（导致长时间垄断CPU），新进程的vruntime初始值设为当前红黑树中的最小vruntime。 6. 应对交互式进程的优化 睡眠奖励 ：若进程因I/O操作休眠，唤醒后其vruntime会被适当减小，使其更易被调度，提升响应速度。 示例 ：文本编辑器休眠后唤醒，vruntime临时调低，快速获得CPU以响应用户输入。 7. 总结：CFS的优势与特点 公平性 ：通过vruntime实现按优先级加权的公平分配。 高效性 ：红黑树保障调度决策的高效性。 自适应 ：时间片动态调整，平衡吞吐量与响应速度。 可配置 ：参数如 sched_latency 可针对不同负载优化。 通过以上机制，CFS在服务器、桌面、嵌入式等场景均能提供良好的性能表现。