Appearance
FCFS 先来先服务调度
2026 大纲 二（二）4 CPU 调度算法的 FCFS（先来先服务）部分，它同时是后续各算法的对比基准。指标口径与算例数据沿用 调度的基本概念与目标。
交互可视化
最省事的规则：谁先来谁先跑
上一节把地基打好了：三个层次、一组冲突的指标、一套评价口径。 从这一节起进入正题——具体怎么挑下一个。
八种算法里，FCFS 是最省事的一个：谁先来谁先跑。 它的比较键是到达时间，而这个键有个特别的性质——正在跑的那个永远比后来的早。 于是"要不要换人"这个问题永远得不出"要换"的结论，所以 FCFS 只可能是非抢占式的。
这条推导给出一个通用判据，后面每个算法都能用： 看它的比较键在运行期间会不会被别人超越。超不过就没有抢占式版本， 超得过才谈得上抢占——而"什么时候会被超越"还进一步决定了抢占检查该放在哪。
FCFS 的好处很实在：简单、规则公平、不会饥饿（排在你前面的人只会越来越少）。
代价叫护航效应：一个长作业排在前面，后面一串短作业全被它堵着。 更要命的是这笔账不止落在等待时间上——排在后面的进程拿不到 CPU 就发不出 I/O 请求， 设备跟着一起闲置。所以准确的评价是"对 CPU 密集型有利、对 I/O 密集型不利"。
一、"只有非抢占式"背后的通用判据
FCFS 属于非抢占式这条结论不用背，可以从比较键推出来——它的比较键是到达时间，而运行者永远比后来者早，所以抢占检查永远得不出"该换人"的结论。这条推导给出一个通用判据：一个算法有没有抢占式版本，看它的比较键在运行期间会不会被别的进程超越。超越发生在什么时候，还决定了抢占式版本好不好用——这一层必须一起问，否则会把"能被超越"直接等同于"抢占式可行"：
| 比较键被超越的方式 | 抢占检查要在什么时候做 | 结论 | 例子 |
|---|---|---|---|
| 永远不会被超越 | 不必检查 | 没有抢占式版本 | FCFS（键=到达时间，运行者必然最早） |
| 在新进程到达的那一刻就可能被超越 | 只需在每个到达时刻检查一次 | 抢占式可行且开销可控 | SJF→SRTF（新来的可能更短）、优先级（新来的可能更高） |
| 到达时超越不了，只能随等待逐渐超越 | 没有固定检查时刻，必须连续重算 | 抢占式有意义但不实用，故只保留非抢占式 | HRRN（新到者响应比恒为最小值 1，但等下去就会涨上来，见高响应比优先调度） |
所以判据要问两句：比较键会不会被超越？如果会，是在一个离散的时刻（有地方下手）还是连续地（无处下手）？
二、护航效应：真正的代价在 I/O 设备闲置
护航效应（Convoy Effect）：一个长作业先到达时，后面所有进程都必须等它跑完。就像一辆大卡车堵住了后面的小轿车——即使小轿车只需要几秒钟通过。
"短作业等得久"只是用户感受层面的代价。系统性代价是 I/O 设备闲置，这条要从进程行为推：
I/O 密集型进程的典型行为是"用一小段 CPU → 发起 I/O → 等待"，它需要频繁但短暂地占用 CPU ⇒ 在 FCFS 下它排在一个 CPU 密集型长作业后面，要等长作业整段跑完才能拿到 CPU ⇒ 这段时间里它发不出 I/O 请求 ⇒ I/O 设备无事可做 ⇒ 等它终于拿到 CPU，只用很短一段就又去等 I/O，此时 CPU 又空下来 ⇒ CPU 与 I/O 设备轮流闲着，两类资源的利用率同时下降。
这正是调度目标里「平衡性」被破坏的典型场景。
三、优缺点与适用场景
| 维度 | 结论 | 判据／理由 |
|---|---|---|
| 实现复杂度 | 最简单 | 只需一个 FIFO 队列，无任何比较运算 |
| 是否饥饿 | 不会 | 排在它前面的进程数确定且只减不增 |
| 抢占性 | 只有非抢占式 | 比较键（到达时间）不会被后来者超越 |
| 对 CPU 密集型 | 有利 | 拿到 CPU 后能一直用下去，没有切换损失 |
| 对 I/O 密集型 | 不利 | 排在长作业后面时发不出 I/O，设备闲置 |
| 平均周转时间 | 通常较差 | 长作业在前会把所有后来者的周转时间整体抬高 |
为什么常用于作业调度、较少单独用于进程调度，两条理由都落在"调度频率"和"可用信息"上：
- 进程调度对响应时间敏感（分时系统里用户在终端前等着），而 FCFS 完全不管响应时间；作业调度面向批处理，本来就没人在等。
- 作业调度的对象是尚未创建进程的作业，系统对它了解很少——服务时间往往只是估计值，用不了需要精确预知时间的算法；而 FCFS 只要一个到达顺序。
所以现实中的用法是把它与其他算法组合使用，典型形态是当作多级队列里某一条队列的内部算法，见 多级队列调度。
同一组数据跑一遍 FCFS：甘特图与四个指标怎么落到数字上（想核对做题步骤时展开）
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
第一步：按到达时间排序，首尾相接排出甘特图。 FCFS 没有任何比较过程，排序即调度结果——这就是它"简单"的全部含义。
| 时间区间 | 0–7 | 7–11 | 11–12 | 12–16 |
|---|---|---|---|---|
| 执行进程 | P1 | P2 | P3 | P4 |
第二步：用统一口径逐个套定义式。 等待时间一律用「周转 − 服务」，不要去数等待段——这条式子对抢占与非抢占都成立，换算法时不必改写。
| 进程 | 完成时间 | 周转时间 | 带权周转时间 | 等待时间 | 响应时间 |
|---|---|---|---|---|---|
| P1 | 7 | 7−0 = 7 | 7/7 = 1.00 | 0 | 0 |
| P2 | 11 | 11−2 = 9 | 9/4 = 2.25 | 5 | 5 |
| P3 | 12 | 12−4 = 8 | 8/1 = 8.00 | 7 | 7 |
| P4 | 16 | 16−5 = 11 | 11/4 = 2.75 | 7 | 7 |
| 平均 | 8.75 | 3.50 | 4.75 | 4.75 |
第三步：读数。 P3 只要 1 个单位服务时间，带权周转时间却高达 8.00——它 87.5% 的"生命"耗在排队上，这就是护航效应被量化的样子。另外平均等待与平均响应恰好相等（都是 4.75），这是非抢占式的必然结果。
考点速记
- FCFS 按到达先后分配 CPU，只可能是非抢占式的——比较键是到达时间，运行者永远比后来者早，抢占检查得不出换人的结论。
- 由此得到通用判据（后面每个算法都能用）：看比较键会不会被超越、以及是在离散时刻还是连续地被超越。超不过就没有抢占版；超得过，超越发生的时刻就是抢占检查该放的位置。
- 优点：简单、规则公平、不会饥饿（排在前面的进程数只减不增）。
- 缺点是护航效应：一个长作业堵住后面一串短作业。最灵敏的指标是带权周转时间（短作业等同样久，带权值被放大得最厉害）。
- ⚠️护航效应的实质代价不止是等待：排在后面的进程拿不到 CPU 就发不出 I/O 请求，设备跟着闲置。所以准确评价是"对 CPU 密集型有利、对 I/O 密集型不利"。
- FCFS 更适合作业调度；进程调度中通常只作为多级队列里某一条队列的内部算法。
这一节在真题里被考过的形式：
cpu-scheduling-algorithm 这个标签下挂了 12 道题、由 8 篇算法共享， 平均每篇不到 2 道，所以本页下方练习区渲染的题里大部分不是本节内容，属正常。 真正落在 FCFS 的只有一道，而且是和 SJF 一起考的：
- 给四个作业的到达时刻与运行时间，比较 FCFS 与 SJF 的平均周转时间（2017-23，与 SJF 共享）。⚠️ 这类题唯一的坑是"已到达"这个前提——SJF 只能在当前已经到达的作业里挑最短的，不能挑一个还没来的。按时刻推进、每次调度前先圈出"此刻已到达且未完成"的集合，就不会错。
复习优先级：性质要记，手算跟着 SJF 一起练。 速记第一、二条那个通用判据 是后面七篇的公共工具，务必理解；第五条（护航效应连累 I/O 设备）是选项里的常见素材。 FCFS 本身的手算最简单，不必单练。
易错：认为 FCFS 也有抢占式版本。比较键是到达时间，后来者永远超不过运行者。
易错：认为护航效应只是让后面的进程多等一会儿。它还让设备闲置——拿不到 CPU 就发不出 I/O。
易错：认为 FCFS 会饥饿。不会——排在你前面的进程只会越来越少。
易错：用平均周转时间衡量护航效应。带权周转时间更灵敏。
教材出处
- 汤小丹《计算机操作系统》3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法（FCFS 规则、"运行到完成或阻塞才换人"、"在单处理机系统中已很少作为主调度算法，常与其他算法结合使用"），印刷 p89
相关知识
调度的基本概念与目标｜SJF 短作业优先调度｜高响应比优先调度｜多级队列调度