FCFS 调度算法：操作系统里最朴素的公平

先来后到，最简单的调度，也是所有调度的起点。

一、调度的本质是排队

操作系统里，CPU 只有一个，进程却可能挤破头。

当多个进程同时就绪，谁先用 CPU？这就像银行窗口只有一个、顾客却排了一队——柜员必须先决定服务谁。

调度算法直接决定系统的响应速度、吞吐量、用户体验。

而先来先服务（First Come First Served，FCFS），是所有调度算法里最简单、最直观的一个。

二、FCFS 的核心：先来后到

四个字的精髓：先来后到。

无论是作业调度还是进程调度，FCFS 都按任务到达系统的先后顺序安排 CPU。先进入就绪队列的进程，先获得 CPU。

生活里随处可见 FCFS 的影子——超市收银、银行叫号、食堂打饭，本质都是同一套逻辑。

三个关键特征

1. 非抢占式

一旦进程获得 CPU，就会一直跑下去，直到完成或因 I/O 阻塞。期间哪怕有更高优先级的进程到达，也不能打断当前进程。

2. 公平

按到达顺序依次服务，不存在长期饥饿。

3. 实现极简

一个 FIFO 队列就够了。

三、一个具体例子

四个进程先后到达：

进程	到达时间	服务时间
A	0	20
B	5	15
C	10	5
D	15	10

0 时刻只有 A 到达，立即调度 A。运行过程中（0~20），B、C、D 分别在 5、10、15 时刻到达，依次排队。A 完成后，系统按 B→C→D 顺序服务。

三个时间指标：

• 完成时间 = 开始时间 + 运行时间
• 周转时间 = 完成时间 − 到达时间（从提交到完成的总耗时）
• 带权周转时间 = 周转时间 / 运行时间（单位服务时间对应的等待代价）

进程	完成时间	周转时间	带权周转时间
A	20	20	1
B	35	30	2
C	40	30	6
D	50	35	3.5

问题暴露：进程 C 只要 5 个时间单位的服务，却等了 30 个时间单位，带权周转时间高达 6。

这就是 FCFS 的典型问题——短作业被长作业拖累。

四、FCFS 的优缺点

优点

• 实现最简单：一个 FIFO 队列搞定
• 公平性好：按序服务，无饥饿
• 开销小：不需要复杂优先级计算，上下文切换成本低
• 善待长作业和 CPU 密集型作业：一旦获得 CPU 就能持续运行，不被打断

缺点

1. 不利于短作业

短作业排在长作业后面，等待时间可能极长。

2. 护航效应（Convoy Effect）——FCFS 最著名的缺陷

一个大作业（CPU 密集型）占着 CPU 不放，后面排队的许多小作业（I/O 密集型）只能干等。一支车队被一辆慢车挡住，后面的快车全被迫低速行驶。

期间 I/O 设备可能完全空闲，资源严重浪费。

3. 平均等待时间可能很长

一个长作业率先到达，后续所有作业的等待时间都会被拉长。

4. 不适合交互式系统

分时系统、实时系统需要快速响应，FCFS 保证不了。

五、代码实现

struct JCB {
    int id;              // 作业号
    double submittime;   // 提交时间
    double runtime;      // 运行时间
    double starttime;    // 开始时间
    double finishtime;   // 完成时间
    double cycletime;    // 周转时间
    double qtt;          // 带权周转时间
};

void FCFS(int num) {
    for (int i = 0; i < num; i++) {
        if (i == 0) {
            // 第一个作业：开始时间 = 提交时间
            jcb[i].starttime = jcb[i].submittime;
        } else {
            // 提交时间早于上一个完成时间 → 需要等待
            if (jcb[i].submittime <= jcb[i-1].finishtime) {
                jcb[i].starttime = jcb[i-1].finishtime;
            } else {
                jcb[i].starttime = jcb[i].submittime;
            }
        }
        jcb[i].finishtime = jcb[i].starttime + jcb[i].runtime;
        jcb[i].cycletime = jcb[i].finishtime - jcb[i].submittime;
        jcb[i].qtt = jcb[i].cycletime / jcb[i].runtime;
    }
}

关键步骤：先按到达时间排序，再依次计算每个进程的开始、完成、周转时间。

六、适用场景

虽然缺陷明显，FCFS 仍有它的用武之地：

• 批处理系统：作业不需用户交互，简单就是优势
• 作业长度相近：所有任务执行时间差不多时，FCFS 表现理想
• CPU 密集型为主：需要长时间计算的任务，FCFS 不会频繁打断
• 对响应时间不敏感：能接受等待的场景

七、总结

FCFS 是操作系统调度家族的基础款。

它的核心价值是简单 + 公平——用最朴素的方式解决了"谁先运行"的问题。

但朴素本身也是代价：护航效应让短作业苦等，平均等待时间居高不下。

所以现代操作系统很少单独使用 FCFS，更多是把它作为更复杂算法（如多级反馈队列）的一个组件。

学习 FCFS，不只是学一个算法，更是理解调度思想演进的起点——

从「先来后到」的朴素公平，到「短作业优先」的效率追求，再到「时间片轮转」的交互体验保障，每一步改进都在解决前一步留下的痛点。

---