第3章先来先服务（FCFS）

3、先来先服务（FCFS）：算法原理、convoy effect（护航效应）分析、适用场景

先来先服务，简称 FCFS。这个名字起得很直白——谁先到，谁先上。我刚开始学操作系统时，觉得这算法也太简单了吧？不就是排个队嘛。但后来在项目中吃过亏，才发现这背后藏着不少门道。

3.1 算法原理：排队，就这么简单

FCFS 的核心思想，说白了就是维护一个就绪队列。新来的进程排到队尾，调度器从队头取进程执行。嗯，跟食堂打饭一个道理。

具体流程是这样的：

进程到达时，PCB（进程控制块）被插入就绪队列尾部
调度器每次从队列头部取出一个进程
该进程一直运行，直到主动释放 CPU（比如 I/O 请求）或终止
然后调度器再取下一个队首进程

代码实现也非常直白：

// FCFS 调度器核心逻辑（简化版）
struct pcb *ready_queue_head = NULL;
struct pcb *ready_queue_tail = NULL;

void enqueue(struct pcb *proc) {
    if (ready_queue_tail == NULL) {
        ready_queue_head = ready_queue_tail = proc;
    } else {
        ready_queue_tail->next = proc;
        ready_queue_tail = proc;
    }
    proc->next = NULL;
}

struct pcb *dequeue(void) {
    if (ready_queue_head == NULL) return NULL;
    struct pcb *proc = ready_queue_head;
    ready_queue_head = ready_queue_head->next;
    if (ready_queue_head == NULL) ready_queue_tail = NULL;
    return proc;
}

void fcfs_scheduler(void) {
    while (1) {
        struct pcb *current = dequeue();
        if (current == NULL) {
            // 没有进程可运行，CPU 空闲
            continue;
        }
        // 运行当前进程，直到它主动让出 CPU
        run_process(current);
    }
}

你看，代码就这么几行。但别小看它，很多实时系统、批处理系统至今还在用。

3.2 Convoy Effect（护航效应）：一个慢进程拖垮所有人

这是 FCFS 最要命的问题。我当年在一个嵌入式项目中就踩过这个坑。

什么叫护航效应？想象一下：一个耗时很长的 CPU 密集型进程排在前面，后面跟着一堆短进程。长进程霸占 CPU 不放，短进程只能干等。就像一艘大货轮在前面慢悠悠地开，后面一队快艇全被堵住了。

为什么会这样？因为 FCFS 是非抢占式的。一旦进程获得 CPU，除非它自己主动放弃，否则没人能把它赶下来。

典型场景：

假设有三个进程：P1（CPU 密集，运行 100ms）、P2（I/O 密集，运行 1ms）、P3（I/O 密集，运行 1ms）。

如果到达顺序是 P1 → P2 → P3：

P1 先跑 100ms，期间 P2、P3 干等
P2 跑 1ms，然后可能发起 I/O
P3 跑 1ms，然后可能发起 I/O

平均周转时间 = (100 + 101 + 102) / 3 ≈ 101ms

如果换成短作业优先（SJF），平均周转时间 = (1 + 2 + 102) / 3 ≈ 35ms

差了将近 3 倍！

我曾经在一个数据采集系统中用过 FCFS。有个传感器处理进程特别慢，每次要算 200ms 的傅里叶变换。结果其他几个轻量级进程（比如按键响应、LED 刷新）全被堵死了。用户体验极差——按了按钮要等 200ms 才有反应。后来我改成优先级调度，问题才解决。

避坑指南：

我曾经在项目里犯过一个错误——把 FCFS 用在了交互式系统中。结果用户操作延迟高得离谱。记住：FCFS 不适合交互式场景。如果你发现系统里有一个进程特别能吃 CPU，FCFS 会让其他所有进程都跟着遭殃。

3.3 适用场景：不是不能用，要用对地方

FCFS 虽然简单，但也不是一无是处。我个人觉得，它最适合以下场景：

场景	原因	我的经验
批处理系统	所有作业性质相似，没有交互需求	我在一个离线数据分析工具里用过，效果不错
实时系统中的非关键任务	对延迟不敏感的后台任务	日志写入、数据备份这类任务可以用
进程执行时间相近的场景	护航效应不明显	比如所有进程都是 1-2ms 的短任务
系统负载极低时	队列几乎为空，调度开销最小化	单用户嵌入式设备，偶尔跑一个任务

你想想看，FCFS 最大的优势是什么？实现简单、没有饥饿问题（每个进程迟早都能轮到）、上下文切换开销小。这些特点在某些场景下反而是宝贝。

我的建议：

如果你不确定该不该用 FCFS，先问自己三个问题：

系统里有没有 CPU 密集型的长进程？如果有，慎用。
用户对响应时间有要求吗？如果有，别用。
进程到达时间是否相对集中？如果分散，FCFS 的公平性反而好。

3.4 知识体系总览

下面这张图是我自己整理的 FCFS 知识结构，方便你快速回顾：

嗯，FCFS 就是这么个算法。简单，但坑也不少。我个人觉得，学调度算法不能光看理论，一定要结合自己的项目去体会。你想想看，护航效应这个坑，我当年可是实实在在踩进去过。希望你能从我的经验里少走些弯路。