题目

某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行。进程创建时由用户指定一个 nice 作为静态优先数。

为了动态调整优先数，引入：

• 运行时间 cpuTime（初值 0）
• 等待时间 waitTime（初值 0）

更新规则：

• 进程处于执行态时：cpuTime 定时加 1，且 waitTime 置 0
• 进程处于就绪态时：cpuTime 置 0，waitTime 定时加 1

请回答下列问题：

(1) 若调度程序只将 nice 的值作为进程的优先数，即 priority = nice，则可能会出现饥饿现象，为什么？

(2) 使用 nice、cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用。

解析

（1）静态优先数为何会饥饿

答：因为优先数永不变。

策略 priority = nice：每个进程从创建那一刻起，优先数就钉死为 nice 值。考虑下面的场景：

• 系统里持续有 priority 较小的"高优"进程被创建（如系统服务、定时任务）
• 一个 priority 较大的"低优"进程进了就绪队列
• 调度永远选 priority 最小的 → 低优进程永远等不到机会

只要"高优"进程的产生速率 ≥ 它们的完成速率，低优进程就会无限期地停留在就绪队列——这就是 饥饿（starvation）。

编者注（关键概念）：饥饿 ≠ 死锁。

• 死锁：双方都在等对方释放资源，全员卡住，无法继续
• 饥饿：少数进程无限期得不到资源，但系统整体仍在前进

静态优先级最常见的副作用就是饥饿，本题问的就是这一点。

（2）设计动态优先数公式

公式

其中 是两个常数，分别调节"运行时间惩罚"和"等待时间奖励"的力度。

三项的物理意义

项	系数符号	作用
nice	+	静态基准——保留用户指定的初始优先级倾向
+ k₁ × cpuTime	+	跑得越多，优先数越大（越不优先）——防止单个进程长时间霸占 CPU
− k₂ × waitTime	−	等得越久，优先数越小（越优先）——防止饥饿

为什么这三项组合就能避免饥饿？

考虑那个被冷落的低优进程：

• 它一直在就绪队列里等 → cpuTime 持续被置 0、waitTime 持续累加
• 随时间推移，−k₂ × waitTime 这一项线性增大其负贡献 → priority 单调下降
• 当 waitTime 累计到一定程度，priority 终于跌到比当前活跃进程更小 → 被调度选中
• 选中后开始运行，cpuTime 涨、waitTime 清零，priority 反弹 → 让出 CPU 后又开始下降

这样形成自动平衡——再低优的进程，等够时间一定会跑到。

waitTime 的作用（题目特别问的）

**waitTime 的核心作用是补偿长期等待的进程，避免饥饿。**它让"等待时间"成为优先级的负向贡献——等得越久越优先，最终把饥饿问题转化为"延迟时间有上界"的问题。

编者注（评分细节 + 答题模板）：

标答评分细则给出三处采分点：

1. 包含 nice（1 分）—— 体现保留用户指定优先级
2. 利用 cpuTime 增大优先数（1 分）—— 即写成 + k₁ × cpuTime 这种符号
3. 利用 waitTime 减少优先数（1 分）—— 即写成 − k₂ × waitTime 这种符号

三个采分点符号方向必须对——把 cpuTime 写成 "−" 就拿不到第 2 分。

还可以写成乘除法变体（如 priority = nice × cpuTime / waitTime），思路对、方向对同样给分。但加减法形式最直观、最不易写错符号，推荐考场用。

类比 Linux 真实调度：CFS（完全公平调度器）的 vruntime 计算就是这个思路的工业级版本——vruntime += 实际运行时间 × 权重因子，等价于"跑得越多虚拟时间走得越快、越不优先"。考场答题时若想加分项，可以简单提一句"该思路与 Linux CFS 的虚拟运行时间机制类似"——展现知识面。