FCFS调度算法是否会引发饥饿？客观题答案及Stalling观点合理性求证

原题回顾 #

下列哪些调度算法可能引发饥饿？
A. First-in First-Out（FCFS）
B. Round Robin（轮转调度）
C. Priority Scheduling（优先级调度）
D. Shortest Job First（短作业优先）

核心疑问与参考依据 #

我仅对选项A存在疑问，其余选项无异议，整理的参考资料如下：

• 伯克利大学cs162课程2007年中期考试解答第15页问题5b指出：FCFS算法仅当某线程无限运行时才会导致饥饿
• William Stalling的教材明确表示FCFS不会引发饥饿，但未提及前提假设
• Galvin的教材提到，操作系统会通过定时器防止用户程序进入无限循环（判断程序是否无限运行属于不可判定问题）

问题解答 #

1. 客观题的正确答案 #

正确答案是 C、D。

• FCFS：在操作系统调度的常规场景下（默认任务为有限时长，或系统具备超时限制机制），不会引发饥饿；仅当出现无限运行的异常任务时才会导致后续任务饥饿，但这种情况不属于基础调度算法的讨论范畴。
• Round Robin：每个任务都会按轮次获得固定时间片，不存在永远无法执行的情况，不会引发饥饿。
• Priority Scheduling：高优先级任务会持续抢占CPU资源，低优先级任务可能永远得不到执行机会，必然存在饥饿风险。
• Shortest Job First（SJF）：若持续有更短的新任务进入调度队列，长任务可能始终被排在队列末尾，无法获得执行机会，存在饥饿风险。

2. William Stalling观点的证明逻辑 #

Stalling的结论基于操作系统调度的标准默认假设：所有待调度任务均为有限执行时长。
在这个前提下，FCFS队列中的任务会严格按顺序执行，每个任务最终都会执行完毕，后续任务总能等到CPU资源，不存在“永远得不到执行”的情况，因此不会引发饥饿。

3. 关于Stalling未提及假设的解惑 #

操作系统教材在讲解基础调度算法时，通常会默认行业共识性的前提，无需专门点明：

• 首先，默认用户提交的任务都是有限时长的，无限循环的任务属于异常场景，而非常规调度的讨论对象。
• 其次，现代操作系统普遍具备定时器、进程超时终止等机制，即使出现无限运行的异常任务，也会被系统强制剥夺CPU或终止，不会持续阻塞后续任务。
  Stalling的结论正是建立在这些默认前提之上，因此无需额外说明。

内容的提问来源于stack exchange，提问作者user3699192