操作系统的进程调度算法有哪些？时间片轮转和多级反馈队列有什么区别？

知识点详解：两个任务争一个 CPU，先让谁运行？

先区分就绪与等待，再比较目标

咱们假设只有一个 CPU，忽略切换开销。A 是较长计算，B 是短交互任务，两者都已就绪。

等待磁盘或网络的任务，不是“排队后立刻能跑”的任务。调度器主要从能够运行的就绪任务里选择，等待 I/O 的任务需要先满足条件再回来。

比较策略时，还要区分几个指标：响应时间是到第一次得到执行机会的等待；周转时间是从到达到完成的总时间；公平关注任务是否获得合理机会。短任务早完成，不代表每个长任务都公平。

常见算法的好处和限制，来自不同选择规则

先来先服务容易理解，但长任务挡在前面，后面的短任务也可能等很久。

短任务优先在明确的简化条件下，可以改善平均周转时间，但真实系统通常不知道任务准确时长。抢占式版本也要估计剩余工作，不能假设系统提前知道所有任务的未来。

优先级调度能优先服务重要任务，但低优先级任务可能长期等待，需要老化等措施。时间片轮转则用轮流运行来照顾响应，但要付出切换成本。

因此，面试中不要只背“哪个算法最优”。先说明它优化什么，以及依赖什么条件。

时间片轮转，按两单位推演一次

假设 A 需要 5 个时间单位，B 需要 2 个，两者在 0 时刻到达，A 先排在队首，时间片为 2。

0 到 2 运行 A，A 还剩 3；2 到 4 运行 B，B 完成；4 到 6 继续 A，A 还剩 1；6 到 7 仍然只有 A 就绪，它继续完成。

这里 A 首次响应等待是 0，B 是 2。B 的周转时间是 4，A 是 7。全部工作总共仍然要 7，轮转没有让 CPU 凭空多做工作，只是改变完成和响应的安排。

如果使用先来先服务，B 要等 A 完整跑到 5，首次响应更慢。反过来，时间片缩得很小，虽然获得机会更频繁，但上下文切换也更频繁。真实系统要把这份开销算进去。

多级反馈队列，为什么不需要事先知道时长？

它根据已经观察到的行为调整优先级。例如新任务先有较高优先级；如果持续用完 CPU 预算，就向较低队列移动；短交互任务可以较早得到执行机会。

这个判断是反馈，不是提前知道“这个任务一定短”。为了防止任务通过反复主动让出 CPU 欺骗规则，算法也会统计累计使用预算，而不是每次让出就完全清零。

低优先级任务仍可能被持续到来的高优先级任务压住，因此需要定期提升等措施。具体队列数量、预算和提升周期都是策略参数，没有一份适用于所有系统的固定表。

机制依据 OSTEP 调度教材。现代 Linux 的普通公平调度还应结合 EEVDF 文档 理解，不能把教材图直接当成内核实现。

面试官继续追问

时间片用完以后，一定切换到别的进程吗？

不一定。没有其他合适的就绪任务时，当前任务可以继续获得 CPU。不能把每个时间片边界都当成必然换进程。

为什么不让所有任务都最高优先级？

大家都最高就失去区分作用，还可能挤压其他工作。优先级应服务明确目标，而不是成为单个任务无限抢占的理由。

面试速记卡

• 调度对象：已经就绪、能够运行的任务。
• 指标：响应时间、周转时间、公平与切换开销分开看。
• RR：轮流使用时间片，不会凭空减少总计算量。
• MLFQ：根据运行反馈调整队列，不要求提前知道准确时长。
• 饥饿：低优先级可能长期等待，需要提升或老化等机制。
• 实现边界：教材算法不是当前 Linux 的固定实现说明。