考研复试操作系统算法这东西，说难也难，说简单也简单。难是因为它横跨了并发、调度、内存、文件系统、死锁五座大山，每座山里都蹲着几个绕不开的经典问题；简单是因为复试考来考去就那么几十道题，出题人绕不开那些“祖宗级”的经典场景。我当年备考时最深的感触是：算法总结做得越早，后期越稳。现在回头看，复试里操作系统算法题基本上就分成两大类——一类是要“会算”的，比如调度算法的周转时间、银行家算法的安全性检查、页面置换的缺页次数；另一类是要“会写”的，比如信号量同步、LRU淘汰策略、生产者消费者模型。这篇文章就把这两条线的核心考点整理成一份可以直接拿来背、拿来练的总结，覆盖从必背模板到考场踩坑的完整链路，无论是机试还是面试都能用上。

1. 复试备考的优先级判断：哪些算法必须手撕，哪些“看懂了就行”

1.1 机试和面试的考察方式差异

先把话说在前面：不同学校对操作系统的考察方式差异非常大。有的学校机试只考数据结构，操作系统放在面试环节口头问；有的学校机试里就有一道“模拟银行家算法”或者“实现LRU页面置换”的大题；还有的学校直接发一张卷子让你手写代码。所以复习之前第一件事是搞清楚目标院校的复试形式，别把精力用错地方。

从我接触到的历年情况来看，面试里的操作系统算法题一般分三个层级：

• 概念层：问你“什么是饥饿”“什么是抖动”“LRU和FIFO的区别”，这类题不需要写代码，但需要用语言把逻辑讲清楚。
• 计算层：给你一组进程或页面访问序列，让你算平均周转时间、缺页次数。这类题在面试中经常以“纸笔演算”的形式出现，有时候面试官会隔着屏幕让你一步一步说过程。
• 手撕层：给你一个场景，让你直接写代码或者伪代码。最常见的是信号量同步（生产者消费者）、LRU缓存、银行家算法安全性检测。

这三个层级的复习策略完全不同。概念层靠背诵框架，计算层靠刷真题练手算速度和准确率，手撕层则需要真正敲代码，不能只看不练。我见过不少同学把“看懂了”当成“会了”，结果机试上手就卡壳，这种教训太常见了。

1.2 算法掌握程度分档表

结合复试实际考察频率和难度，我把操作系统里的核心算法分成了三档，备考时可以按这个优先级分配时间：

这里给一个非常实用的建议：第一档的算法不要只准备一种实现方式。比如生产者-消费者模型，至少要能写出信号量版本；如果时间充裕，再把条件变量版本也准备一下，因为面试官经常会追问“还有没有别的写法”。LRU也是，光会说“用哈希表加双向链表”不够，得能真的写出来，后面我会单开一节讲代码实现。

2. 并发与同步经典题：生产者-消费者、读者-写者、哲学家就餐的代码重点

2.1 生产者-消费者：信号量的核心模板

生产者-消费者问题是复试中出现频率最高的操作系统算法题，没有之一。它包含两个核心要素：互斥访问缓冲区、同步协调生产与消费的节奏。对应到信号量上就是经典的“三个信号量”模型：mutex管互斥，empty记录空位，full记录满位。

下面这个版本是复试中最好用的通用模板，用类C语言写的伪代码，机试时改造成具体语言也非常方便：

#define N 100 // 缓冲区大小 semaphore mutex = 1; // 互斥信号量 semaphore empty = N; // 空闲缓冲区数量 semaphore full = 0; // 已占用缓冲区数量 void producer() { while (1) { // 生产一个产品，放入 nextp P(empty); // 申请一个空闲缓冲区 P(mutex); // 进入临界区 // 将 nextp 放入缓冲区 buffer V(mutex); // 退出临界区 V(full); // 已占用缓冲区数量加1 } } void consumer() { while (1) { P(full); // 申请一个已占用缓冲区 P(mutex); // 进入临界区 // 从缓冲区取出一个产品 V(mutex); // 退出临界区 V(empty); // 空闲缓冲区数量加1 // 消费产品 } }

这段代码有几个地方是面试官最爱追问的，提前准备好答案：

为什么P(empty)和P(full)一定要放在P(mutex)外面？如果反过来，先加互斥锁再检查资源数量，一旦缓冲区满或空，持有mutex的进程就会在P(empty)或P(full)上阻塞，而其他进程又进不了临界区释放资源，这就造成了死锁。这个点几乎每次面试都会问到，务必要能讲清。

P/V操作必须成对出现，但不一定在同一进程内。P(empty)和V(empty)分别出现在生产者和消费者中，是通过资源共享实现同步的关键。很多初学者会误以为信号量操作只能在一个进程内配对，这是一个常见的理解误区。

机试时如果用C语言写，需要注意semaphore在C语言里没有现成类型，通常用sem_t；如果允许用Python，可以直接用threading.Semaphore，逻辑和上面完全一致。但我个人的建议是：复试机试尽量用C语言准备，因为很多学校的判题环境对Python多线程支持并不友好。

2.2 读者-写者：读写锁的思想和代码

读者-写者问题考察的是对“读写锁”思想的理解。核心规则是：多个读者可以同时读，写者必须独占，读者和写者不能同时操作。复试中最常考的版本是“读者优先”，也就是只要有读者在读，后来的读者可以无条件进入，写者必须等待所有读者退出。

用信号量实现的经典代码如下：

semaphore rw_mutex = 1; // 控制写者互斥 semaphore mutex = 1; // 保护读者计数 int read_count = 0; // 当前读者数量 void reader() { while (1) { P(mutex); read_count++; if (read_count == 1) P(rw_mutex); // 第一个读者加锁，阻止写者 V(mutex); // 执行读操作 P(mutex); read_count--; if (read_count == 0) V(rw_mutex); // 最后一个读者解锁，允许写者 V(mutex); } } void writer() { while (1) { P(rw_mutex); // 执行写操作 V(rw_mutex); } }

这段代码的逻辑核心在于：只有第一个读者和最后一个读者才需要操作rw_mutex，中间的读者只是增减计数，不需要碰写者锁。这个设计精妙在把“一个写者对比多个读者”的互斥关系，通过读者计数转换成了“是否有人正在读”的布尔判断。

面试追问一般有两个方向：一是“这个版本有什么问题”，答案是写者可能被饿死，因为只要读者源源不断地来，写者就永远等不到锁；二是“如何实现写者优先”，标准做法是增加一个write_mutex让写者排队优先，这会复杂一些，但如果能答出来，是很加分的表现。

2.3 哲学家就餐与吸烟者问题：死锁避免思路

哲学家就餐问题在复试中更多是以“问思路”的形式出现，而不是要求完整写代码。它的经典死锁场景是五个哲学家同时拿起左边的叉子，导致所有人都无法拿到右边的叉子。解决思路通常有三个：

• 最多允许四位哲学家同时就餐：设置一个计数信号量room = 4，这样至少有一位哲学家能拿到两把叉子，吃完后释放，打破循环等待。
• 要求哲学家先拿编号较小的叉子：给叉子按序编号，每人先拿小号，再拿大号，破坏“循环等待”条件。
• 借助互斥锁保证拿叉子动作的原子性：取叉子时加锁，这样不会出现“每人拿一把”的中间状态。

我建议复试时重点准备第一种方案，因为它最简单，三句话就能说明白：引入一个信号量限制同时就餐人数为4人，死锁就不会发生。回答时补一句“这只是破坏死锁条件中循环等待的一种方式”，会让面试官觉得你不是死记答案，而是真的理解了死锁成因。吸烟者问题和哲学家问题类似，考察的是三个进程与三种资源的匹配关系，思路也是“用互斥信号量保护资源分配过程”，一般面试里出现频率不高，但概率论上有一个“P/V操作描述吸烟者”的经典题目，建议还是把代码过一遍。

3. 调度算法与计算题：平均周转时间、带权周转时间怎么算

3.1 FCFS、SJF、RR、优先级、多级反馈队列

处理机调度这块，复试笔试的计算题占了很大的比重。本科课程和复试参考书里最常出现的算法有五种：先来先服务（FCFS）、短作业优先（SJF，分为抢占式和非抢占式）、时间片轮转（RR）、优先级调度、多级反馈队列（MLFQ）。

需要明确的是，实际复试题目里“短作业优先”和“短进程优先”混用的情况很常见，计算时都按“运行时间短的先执行”来处理。而时间片轮转关键的考点是时间片大小的选择：时间片太大就退化成FCFS，时间片太小则上下文切换开销占比过高。回答这类问题时，试着用“极端化假设”来证明思路——把时间片设成无限大和设成无限小，分别看效果，这个推演过程本身就是面试官想听的。

优先级调度需要额外注意“饥饿”问题：低优先级进程可能永远无法运行。解决方案是老化（Aging）——随着等待时间增长逐步提升优先级，看过的同学都知道这是《现代操作系统》里的经典解法，答出来非常加分。

多级反馈队列这个算法在复试中常以概念题出现，它的核心是“优先级高的队列时间片小，用完降级；新的高优先级任务可以抢占”。最好准备一个三步描述：建立多个不同时间片的队列、新任务进入最高优先级队列、任务时间片用完未结束则降级。这三点说全基本上就拿到分了。

3.2 一个完整的计算示例

计算题只看概念是不够的，我直接给出一个完整的例子，这是复试里非常典型的题目，建议自己动手算一遍：

有四个进程 A、B、C、D，到达时间分别为 0、1、2、3，运行时间分别为 5、3、2、1。分别计算非抢占式 SJF 和时间片为 2 的 RR 调度的平均周转时间和平均带权周转时间。

非抢占式 SJF：

调度顺序推导：时刻 0 只有 A 到达，A 运行5个时间单位到时刻5。此时 B、C、D 都已到达，运行时间分别为 3、2、1，按短作业优先排序为 D（1）、C（2）、B（3）。所以执行顺序是 A → D → C → B。

• A：完成时间5，周转时间 5-0=5，带权周转时间 5/5=1
• D：完成时间6，周转时间 6-3=3，带权周转时间 3/1=3
• C：完成时间8，周转时间 8-2=6，带权周转时间 6/2=3
• B：完成时间11，周转时间 11-1=10，带权周转时间 10/3≈3.33

平均周转时间 = (5+3+6+10)/4 = 6；平均带权周转时间 = (1+3+3+3.33)/4 ≈ 2.58。

时间片为 2 的 RR 调度：

用甘特图推演：时刻0 A开始（用掉2，剩余3）；时刻2 B进入，运行到4（B剩余1）；时刻4 C进入，运行到6（C完成）；时刻6 D进入，运行到7（D完成）；时刻7 A恢复，运行到9（A剩余1）；时刻9 B进入，运行到10（B完成）；时刻10 A进入，运行到11（A完成）。

• A：完成11，周转时间11
• B：完成10，周转时间9
• C：完成6，周转时间4
• D：完成7，周转时间4

平均周转时间 = (11+9+4+4)/4 = 7。对比可以发现，这个例子里 RR 的平均周转时间比 SJF 差，这说明在已知运行时间的前提下，SJF 的周转时间确实有优势，RR 的优势在响应时间而非周转时间。

提示：计算周转时间尤其是 RR 调度，一定要画甘特图或者时间轴，心算非常容易漏恢复执行的时间片。我见过太多考生在这道题上因为少算了最后一段恢复执行而丢分。

3.3 面试追问：如何证明SJF最优

关于 SJF 的最优性，正确的说法是：在非抢占式调度中，SJF 能使平均等待时间最小。证明思路很经典，用交换论证法：假设调度序列中存在两个相邻进程，前一个运行时间更长而后一个更短，交换它们的执行顺序，前者的等待时间减少量大于后者的等待时间增加量，因此总体平均等待时间下降。反复交换直到任意相邻位置都满足“短作业在前”的规则，就是 SJF 的顺序。

这个证明过程复试时不需要写得很长，用两三句话说清“交换相邻两项后总等待时间减少”就够了。但这句话说得好不好，直接决定了面试官对这一问的印象分——因为十个考生里八个都在背结论，只有真正理解的人能把“为什么”讲明白。

4. 内存管理：分区分配、页面置换算法和LRU手写实现

4.1 动态分区分配算法对比

内存管理在复试笔试中常考的是动态分区分配算法：首次适应（FF）、最佳适应（BF）、最差适应（WF）、循环首次适应（NF）。别看名字多，抓住一个核心维度就全记住了——空闲分区按什么顺序组织、找什么样的空闲区。

我在复习的时候做过一个对比表，基本上一张表就能把这几个算法记牢：

面试中这个知识点的追问方向一般是“为什么最佳适应不是真的最佳”——因为从名字上看“最佳”容易让人误解，但它追求的是“每次留下的碎片最小”，而大量小碎片反而导致后续大请求无法被满足，所以从整体看并不最优。这个“名不副实”的点是面试官非常喜欢的陷阱，复习时一定不要只记名字。

4.2 页面置换算法：OPT、FIFO、LRU、Clock

页面置换算法是内存管理中最核心的计算题考点。四种算法必须掌握：

• OPT（最佳置换）：淘汰未来最长时间不被访问的页面，理论最优但无法实现，只用于对比衡量。
• FIFO（先进先出）：淘汰最早进入内存的页面，实现简单，但可能出现Belady异常——分配的物理块数增加反而缺页次数增加。
• LRU（最近最久未使用）：淘汰最长时间未被访问的页面，性能接近OPT，实现开销高。
• Clock（时钟）：也称NRU（最近未使用），给每个页面加一个引用位，指针扫描，遇到引用位为0就淘汰，为1则置0并继续。本质是LRU的近似实现，开销远低于真正的LRU。

这里特别提醒：FIFO和LRU在“分配物理块数增加时缺页次数是否一定不增加”这个问题上表现不同，FIFO可能增加（Belady异常），LRU不会。这一点复试笔试中经常作为辨析题出现。

真题计算示例：

页面访问序列：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，物理块数3，分别求FIFO和LRU的缺页次数。

FIFO：初始内存为空，前3次必缺页。按先进先出逻辑推演：访问4时淘汰1，访问5时淘汰2，后续访问1缺页（淘汰3），访问2缺页（淘汰4），访问3缺页（淘汰5），访问4缺页（淘汰1），访问5缺页（淘汰2）。总缺页次数9次。

LRU：前3次同样缺页。访问4时淘汰1（因为1最久未用），访问5时淘汰2（1刚被访问过变新），后续访问1缺页（淘汰3），访问2缺页（淘汰4），访问3缺页（淘汰5），访问4缺页？这时候需要看：内存中当前是1、2、3，访问4要淘汰最久未使用的1，缺页+1；访问5时淘汰2，缺页+1。总缺页次数10次。

这个例子其实非常经典，也说明LRU“比FIFO更好”的说法不能一概而论，要看具体序列。复试时如果时间紧张，不需要把整个序列都背下来，但一定要把计算过程从头到尾推演一遍，熟练掌握“每一步淘汰谁”的判断规则。

4.3 LRU的代码实现（哈希表加双向链表）

复试机试里LRU是出现频率极高的考题，很多学校会直接考“实现一个LRU缓存”的 LeetCode 原题。标准解法是哈希表 + 双向链表，哈希表保证 O(1) 的查找，双向链表保证 O(1) 的节点移动和删除。

// 双向链表节点 typedef struct Node { int key; int value; struct Node *prev; struct Node *next; } Node; // LRU缓存结构 #define CAPACITY 3 Node *head, *tail; Node *hashTable[10000]; // 简化版：直接用数组当哈希表 int cacheSize = 0;

因为篇幅原因这里给的是最核心的伪代码框架，完整实现并不长，大致包括三个操作：get时若命中则把节点移到链表头部，put时若已存在则更新值并移到头部，若不存在则插入头部，如果容量已满则删除尾部节点。只要“每次访问都更新到头部”“淘汰时删尾部”这两条规则写对，核心逻辑就通了。

机试实际写的时候有几个非常容易出错的细节，提前避坑：

• 双向链表一定要设置虚拟头尾节点，否则边界判断非常容易出错，导致空链表时访问空指针。
• 哈希表的结构体里不能只存value，还必须存key，因为淘汰尾部节点时需要通过哈希表删除对应的键，如果没有key字段就删不掉。这是我当年第一版代码里踩过的坑。
• Python 实现的collections.OrderedDict也支持 LRU 语义，但复试手撕代码时反而不建议用，因为面试官更想看你对底层结构的理解。

5. 死锁与银行家算法：安全性检查的完整推理过程

5.1 死锁的四个必要条件与处理策略

死锁这一块在复试中几乎从不缺席。四个必要条件是：互斥、持有并等待、不可剥夺、循环等待。这里有一个非常经典的复习技巧：处理策略和必要条件是一一对应的。

• 破坏互斥：一般做不到，因为有些资源本质就是互斥的，比如打印机。
• 破坏持有并等待：让进程一次性申请所有资源，但资源利用率会下降。
• 破坏不可剥夺：允许系统强行抢占，但可能导致数据不一致。
• 破坏循环等待：给资源编号，按序申请，这正是哲学家就餐“先拿小号叉子”方案的原理。

复试题里更常考的是“死锁避免”，也就是银行家算法。它与“死锁预防”的区别在于：预防是提前破坏条件，避免是运行过程中动态判断安全性。这个对比最好记在心里，因为面试官问完概念大概率会跟一句“那预防和避免有什么区别”，用一句话说清楚就赢了。

5.2 银行家算法的安全性检查流程

银行家算法的核心是安全性检查，整个流程可以用四步描述：

1. 维护三个数据结构：Available（可用资源向量）、Max（各进程最大需求矩阵）、Allocation（各进程已分配矩阵），还需要Need = Max - Allocation来表示还需资源。
2. 寻找一个进程满足Need[i] <= Available且未完成，则假定它执行完并释放所有资源，Available += Allocation[i]，标记该进程完成。
3. 重复步骤2，直到所有进程都能完成，则系统处于安全状态。
4. 如果找不到这样的进程，则系统处于不安全状态。

复试时银行家算法最常见的考法是手算安全序列。这里有一个我反复强调的提醒：一个系统处于安全状态，则一定不会死锁；但一个系统处于不安全状态，不代表它一定已经死锁。不安全只是“未来可能进入死锁”，因为实际执行路径可能并不会真的走到那一步。这个“可能”字咬得特别紧，每年都有考生在这里栽跟头。

5.3 手算题目练习

看一个经典的手算题：

系统有 A、B、C 三类资源，Available = (3, 3, 2)，五个进程的 Allocation 和 Need 如下表：

安全性检查推导过程：

• 初始Available = (3, 3, 2)。检查各进程：P1 的 Need (1,2,2) <= (3,3,2)，满足，假设 P1 执行完，释放资源后Available = (3,3,2) + (2,0,0) = (5,3,2)。
• 当前 Available (5,3,2)，检查剩余进程：P3 的 Need (0,1,1) <= (5,3,2)，满足，P3 执行完，Available = (5,3,2) + (2,1,1) = (7,4,3)。
• P0 的 Need (7,4,3) <= (7,4,3)，满足，P0 执行完，Available = (7,4,3) + (0,1,0) = (7,5,3)。
• P2 的 Need (6,0,0) <= (7,5,3)，满足，P2 执行完，Available = (7,5,3) + (3,0,2) = (10,5,5)。
• P4 的 Need (4,3,1) <= (10,5,5)，满足，全部完成。

安全序列：P1 → P3 → P0 → P2 → P4，系统安全。

这个推导过程的书写规范在笔试里非常影响得分，我建议每一步都明确写出“哪个进程能执行、释放后 Available 变成多少”，不要在心算中省略过程。面试口述时也一样，一步一步说，面试官能跟上你的思路，这本身就是在展示你思维的严谨性。

注意：银行家算法机试如果要求写代码，核心就是“反复扫描进程集合直到找不到可分配进程”，实现时用一个finish[]数组标记已完成进程即可，复杂度是 O(n²·m)，n 是进程数，m 是资源类型数，复杂度本身也经常被问到。

6. 磁盘调度与文件系统算法：SSTF、SCAN、CSCAN和索引节点

6.1 磁盘调度算法对比

磁盘调度考察的频率在考研复试里略低于内存和并发，但属于“不能丢分”的送分题。核心算法是这几个：先来先服务（FCFS）、最短寻道时间优先（SSTF）、扫描算法（SCAN，电梯算法）、循环扫描（C-SCAN）、LOOK和C-LOOK。

SSTF选择离当前磁头最近的请求，平均寻道时间短，但远端的请求可能被饿死。SCAN让磁头沿一个方向移动，途中处理所有请求，到最远端后反向，避免了饥饿。C-SCAN则只沿一个方向服务，返回时快速空移，这样两端请求的等待时间更均匀。LOOB 和 C-LOOK 的区别是不一定移动到最远端点，只移动到该方向上最远的请求位置就反向，效率更高。

面试的常见追问是“为什么 C-SCAN 的等待时间比 SCAN 更均匀”——因为 SCAN 在反向后的第一个服务区间的请求，等待时间可能极短，而同一批被服务过的请求要等一圈，不同区域的请求等待时间差异很大；C-SCAN 统一了“从头扫到尾、快速返回”的模式，每圈内服务次序更规则。

计算题一般会给一个当前磁道号和请求序列，让算磁头移动的总磁道数。这种题就是仔细加细心，画出移动路径就不会错。磁道序列长的时候，推荐用表格记录当前磁道、下一目标、移动距离和累计距离，防止算到最后一步时对不上数。

6.2 文件系统的常见考点

文件系统在算法层面的考试内容相对固定，主要是索引节点和目录结构。复试高频考点是：

• 连续分配：支持随机访问，但会产生外部碎片。
• 链接分配：消除了外部碎片，但只能顺序访问。
• 索引分配：每个文件维护一个索引块，支持随机访问，是主流方案。

IP 节点的计算题几乎是每年必出，典型问题如下：

某文件系统索引节点中有13个地址项，其中10个为直接地址项，1个一级间接地址项，1个二级间接地址项，1个三级间接地址项。磁盘块大小4KB，每个磁盘块号占4B。求单个文件最大长度。

计算步骤：一个磁盘块能存放的地址项数量 = 4KB / 4B = 1024 个。一级间接能寻址 1024 × 4KB = 4MB；二级间接 = 1024 × 4MB = 4GB；三级间接 = 1024 × 4GB = 4TB。最大文件长度 = 10 × 4KB + 4MB + 4GB + 4TB，约等于 4.04TB。

这道题的变形在于地址项数量和块号字节数会变，但思路完全一致。我建议把这个模板记牢，考试时直接套数字就行。文件系统这块的内容不太需要写代码，主要是计算和理解，但它每年都能在复试卷上占据10分左右的分值，不复习等于白送分给别人。

7. 复试现场与机试备考的经验教训

7.1 踩过的坑

先讲一个很多人都会踩的坑：只背不练代码。操作系统算法不像数据结构那样有直观的“写错就运行不起来”的反馈，很多同学把代码背下来就觉得万事大吉，但复试时面试官会要求在纸上写，或者机试环境下没有提示和自动补全。我强烈建议复习期间把第一档的算法全部手写三遍以上，写的过程中你会发现很多细节根本没记住——比如信号量初始化参数、读者写者里 read_count 是谁在保护、银行家算法在哪一步更新 Available。

第二个坑是以为公平一定是好的。面试中一旦讨论到算法优劣，不要下意识觉得“不让任何进程饿死好的”。比如10道任务里有1个需要1秒完成、1个需要100秒完成，SJF 可以让平均等待时间最少，但会让长任务无限等待。真正的答案是“权衡”——操作系统算法本质上都是 trade-off。用这个词回答问题，面试官会觉得你是有真实理解而非背书。

第三个坑是忽略陈述的表达。复试不是笔试，不是算出正确答案就行。很多计算题面试官会让你现场口算并说出来，如果心里会算但说不清楚，很容易被误判为“半懂”。提前练习“把计算过程讲解给别人听”这个能力，比多刷十道题更有价值。

7.2 手撕代码的考场技巧

关于复试时手写代码，我总结几个亲测有效的经验，尤其对考场上容易紧张的同学特别管用：

• 先写函数签名和数据结构，再写逻辑。很多考生一上来就埋头写核心逻辑，写到一半发现局部变量没声明、函数参数没定好，涂涂改改，卷面非常难看。先搭框架是减小心理压力的关键一步。
• 用伪代码不丢分。面试手写题很多时候没有编译器，伪代码反而能更快把算法思想表达清楚。只要关键逻辑和变量定义清晰，面试官通常不会因为语法细节扣分。
• 主动解释每一步的意图。写代码时边写边说“这里用 mutex 保护缓冲区”“这里是第一个读者才加锁”，既展示了你的逻辑，又避免了冷场。大部分面试官对“能讲代码”的考生印象分都很高。
• 如果卡住了，先讲思路再下手写。很多时候思路说出来你自己就发现卡点在哪了，而且面试官给的提示也会更精准。闷头硬写是最差的选择。

最后再分享一个小技巧，是我自己备考后期一直在用的：把第一档算法做成索引卡片，每张卡片只写题目和关键提示词，比如“生产者消费者——三个信号量”“LRU——哈希加双向链表”“银行家——Available推出安全序列”。每天随机抽五张，对着卡片在纸上花五分钟写完一个算法的骨架。坚持两周，机试时你会发现这些代码就像条件反射一样自然。复试说到底是一场“稳健性”比拼，不是比谁掌握的知识更前沿，而是比谁在有限时间和高压力环境下能把基础算法稳定输出出来。把上面这些内容踏踏实实过一遍，操作系统算法这一关就没有过不去的道理。