传统Unix进程调度机制的问题

——从优先级映射到公平调度算法的技术解析

一、时间片映射的公平性失衡

问题核心

传统调度器将nice值直接映射为绝对时间片，导致不同优先级进程的处理器时间分配比例失衡，且与任务类型需求矛盾。

示例与后果

一般来说，交互型前台进程需要高优先级及时响应用户输入；而赋予低优先级的往往是后台进程，且多是计算密集型。

• 高优先级任务（如nice 0）：被赋予大时间片（如100ms），适合计算密集型任务，但前台交互任务（如GUI）反而需要短时间片以减少响应延迟。
• 低优先级任务（如nice +20）：仅分配极小时间片（如5ms），导致计算密集型后台任务（如编译）因频繁切换而效率低下。

现代改进（CFS）

系统维护一个按 vruntime 排序的红黑树，优先调度 vruntime 最小的进程。例如：
- 若文本编辑器（高交互性）和视频解码器（计算密集型）具有相同 nice 值，它们的初始权重相等，理想情况下各占 50% CPU。
- 文本编辑器因频繁等待用户输入，实际运行时间远小于视频解码器，其 vruntime 增长缓慢，从而在唤醒时优先被调度，既保证交互响应性，又让计算任务充分利用空闲CPU。

---

二、相对nice值的非线性影响

问题核心

传统调度器中，nice值的调整对处理器时间的影响在高/低优先级区域呈现非线性差异，导致优先级操作的不可预测性。

示例与后果

• 低nice值区域（如nice 0→1）：时间片从100ms→95ms，处理器时间仅减少约2.6%，用户难以感知差异。
• 高nice值区域（如nice +18→+19）：时间片从10ms→5ms，处理器时间直接减半，调整幅度剧烈且不合理。

现代改进（CFS）

引入虚拟时间（vruntime）机制，保证nice值调整的线性比例效果（如权重差恒为1.25倍），避免优先级操作的区域敏感性。

---

三、时间片与定时器节拍的强耦合

问题核心

时间片必须为定时器节拍（Timer Tick）的整数倍（如10ms），导致调度粒度粗糙且依赖硬件配置。

示例与后果

• 最小时片限制：若定时器节拍为10ms，进程无法分配更短时间片（如1ms），交互任务响应延迟增加。
• 配置依赖性：定时器节拍从100Hz（10ms）改为1000Hz（1ms）会导致时间片长度突变，系统行为不一致。

现代改进（CFS）

彻底解耦时间片与定时器节拍，允许纳秒级调度决策，动态计算时间片长度，适应不同任务需求。

---

四、唤醒进程的公平性漏洞

问题核心

传统调度器对唤醒进程（如交互任务）的优先级临时提升，为恶意进程伪装“交互性”打开后门，破坏全局公平性。

示例与后果

• 恶意进程伪装：计算密集型任务通过频繁睡眠/唤醒（如每1ms一次），被误判为交互任务，持续获得高优先级和时间片重置。
• 资源垄断：其他进程因优先级压制无法公平获取CPU时间，导致饥饿现象。

现代改进（CFS）

• 睡眠补偿机制：通过减少睡眠进程的虚拟时间（vruntime）补偿其等待时间，而非直接提升优先级。
• 全局公平性：基于虚拟时间排序调度队列，避免任何进程获得超额时间片。