1. 第二章的习题地图先搞清楚这一章在讲什么1.1 教材第二章的知识骨架翻开“计算机操作系统慕课版”第二章的标题是“进程的描述与控制”。很多同学第一章学得挺顺一到第二章就开始懵原因很简单第一章讲的是操作系统“长什么样”第二章讲的是操作系统“怎么跑起来”。这一章的核心是把“程序”这个静态的东西变成“进程”这个动态的实体然后再解决多个进程抢资源时怎么不打架的问题。这一章的骨架其实就四块。第一块是进程的基本概念包括前趋图、程序的顺序执行与并发执行、进程的定义与特征、进程的三种基本状态加两种挂起状态、PCB 的作用。第二块是进程控制也就是创建、终止、阻塞、唤醒、挂起、激活这几个原语。第三块是进程同步临界区、同步机制的四条准则、信号量机制、经典同步问题。第四块是进程通信与线程共享内存、消息传递、管道以及线程的引入和实现方式。课后习题基本就是围着这四块出题只不过把知识点揉进选择题、填空题、简答题和应用题里。我当年第一遍做的时候把概念题当成阅读理解随便勾结果一对答案错一片后来才明白这一章的题不是考记忆是考你脑子里有没有一张“状态流转图”和一套“PV 操作模板”。1.2 课后习题的四种题型与分值分布把第二章的课后题按题型分类大概能分成四类每类的备考策略完全不同。题型典型考法占比感觉备考重点选择题状态判断、概念辨析约 30%抠字眼区分“一定”“可能”填空题PCB 内容、准则名称约 15%记术语别写错顺序简答题进程与程序区别、状态转换约 25%背模板但要理解着背应用题信号量解决同步问题约 30%套模板 判死锁选择题最容易掉以轻心。比如“进程是程序的一次执行过程”这种话在选择题里会被改成“进程就是程序”一字之差就是错的。填空题看着是送分题但“空闲让进、忙则等待、有限等待、让权等待”这四条同步准则写反顺序或者漏一条分就没了。应用题是重头戏也是最能拉开差距的地方因为它不只考你会不会写 PV还考你会不会分析为什么这样写、会不会判断哪里可能死锁。我个人的建议是复习顺序不要按题号来而是先啃应用题把同步问题彻底搞懂再回头刷选择填空。因为应用题搞懂了第一部分的概念自然就串起来了很多选择题甚至不用背就能选对。1.3 复习顺序的建议很多同学喜欢从第一题顺着做到最后一题做完对答案错的抄一遍然后就没有然后了。这种刷题方式对第二章基本无效因为第二章的知识点是网状的不是线性的。更靠谱的顺序是这样第一步先画一张进程状态转换图把就绪、执行、阻塞、创建、终止这五个状态以及它们之间的箭头背下来这是所有题的基础。第二步理解 PCB 是什么为什么每个进程必须有一个。第三步进入同步问题把信号量的物理意义搞清楚。第四步动手把生产者-消费者、哲学家进餐、读者-写者三个经典问题各写两遍第一遍照抄模板第二遍合上书自己写。第五步再回头做选择填空你会发现正确率明显上去了。这个顺序的道理在于第二章的难点集中在同步而同步的基础是状态和 PCB所以要从根往叶走而不是从叶往根爬。2. 概念类习题看着简单实则处处是坑2.1 进程与程序的区别别只背那四句话课后第一道简答题几乎固定是“试说明进程与程序的区别”。标准答案一般是四点进程是动态的程序是静态的进程有生命周期程序可以长期存在一个程序可以对应多个进程一个进程也可以包含多个程序进程是资源分配和调度的基本单位程序不是。但真正做题的时候光背这四句是不够的。你得能举例子。比如我用记事本写文档记事本这个可执行文件是程序它是躺在硬盘上的静态的。我双击打开它内存里就多了一个进程它有 PCB、有程序计数器、有寄存器现场。我再打开一个记事本又多了个进程两个进程对应的是同一个程序。这样一解释四个区别就全活了。还有一个常见的坑题目会把“进程是资源分配的基本单位”和“线程是调度的基本单位”放一起考。在没有引入线程之前进程既是资源分配单位也是调度单位。引入线程之后这两个角色分家了。这个点如果记混选择题必错。2.2 进程的五个状态与转换条件进程状态题是第二章的送分题也是最容易因为“方向搞反”而丢分的题。基本状态有三个就绪、执行、阻塞。再加上创建和终止一共五个。状态转换的关键在于“什么事导致了这次转换”。就绪到执行是调度程序选中了它这是唯一一个由“外部调度”引起的转换。执行到就绪是时间片用完或者被更高优先级抢占。执行到阻塞是进程主动请求资源没得到比如等 I/O、等信号量。阻塞到就绪是等待的事件发生了比如 I/O 完成、信号量被 V 操作释放。注意阻塞到执行不存在必须先回到就绪再被调度。这个点每年都有人画错箭头。我在做题时总结了一句口诀主动走阻塞被动回就绪。意思是进程自己请求资源失败会主动进入阻塞而阻塞结束是因为别的进程帮了忙所以是被动回到就绪。这句话帮我记住了所有箭头方向。注意状态转换图里“就绪→阻塞”和“阻塞→执行”这两条箭头是绝对不存在的前者因为就绪进程还没上处理机谈不上请求资源失败后者因为阻塞态不能直接上处理机。2.3 PCB 里到底存了什么PCB进程控制块是第二章出填空题的高频点。标准答案通常列四类信息进程标识符、处理机状态、进程调度信息、进程控制信息。但具体展开很多人记不全。我用一个便于记忆的分类PCB 就是进程的“身份证 存款单 行程表”。身份证是 PID 和用户标识说明它是谁存款单是资源清单说明它占了哪些内存、哪些设备、打开了哪些文件行程表是处理机现场和调度信息包括程序计数器、寄存器值、进程优先级、等待时间、队列指针。这里有个容易被忽略的点PCB 是进程存在的唯一标志。也就是说创建一个进程本质就是创建它的 PCB撤销一个进程本质就是回收它的 PCB。系统区里有一张 PCB 表所有进程的 PCB 都挂在这张表上。理解这一点进程创建、终止、阻塞、唤醒的原语就都好懂了因为原语干的事基本就是“改 PCB 里的状态字段然后把 PCB 挂到对应的队列上”。2.4 进程控制原语动作顺序不能乱进程控制部分的简答题常问“创建进程需要做哪些工作”或者“阻塞原语和唤醒原语的关系”。这里的关键是记住进程控制都是通过原语实现的而原语是原子操作执行期间不允许被中断。以创建为例顺序大概是这样申请空白 PCB分配唯一 PID为新进程分配资源包括内存、I/O 设备、文件初始化 PCB填好各种字段把 PCB 插入就绪队列。这四步的顺序不能乱尤其是先有 PCB 再挂队列反过来就找不到挂什么了。阻塞和唤醒的配合也很典型。一个进程调用阻塞原语时是把自身 PCB 的状态改为阻塞然后插入对应事件的等待队列最后转调度程序。唤醒原语通常是另一个进程调用的它把等待队列里某个 PCB 移出状态改为就绪再插入就绪队列。注意阻塞是进程自己调用的唤醒是别人调用的这个“自己 vs 别人”的对应关系是选择题很喜欢设的陷阱。3. 进程同步与信号量第二章真正的核心3.1 临界资源、临界区以及那四条准则进程同步是第二章的分水岭。概念部分先要搞清楚三组词临界资源、临界区、同步与互斥。临界资源是一次只允许一个进程使用的资源比如打印机、共享变量。临界区是访问临界资源的那段代码。注意临界资源是“东西”临界区是“代码”题目经常故意混着说。同步是多个进程为了完成同一个任务而协调先后顺序互斥是多个进程争用同一个资源而必须排他。同步是“你走完我再走”互斥是“我进了你别进”两者不是一回事。为了让临界区的管理可靠同步机制必须满足四条准则空闲让进、忙则等待、有限等待、让权等待。这四条我一开始只是背后来才想明白它们各防什么。“空闲让进”防的是资源闲着没人用效率低“忙则等待”防的是多个进程同时进破坏互斥“有限等待”防的是某个进程永远等不到即饥饿“让权等待”防的是进程占着处理机干等浪费 CPU。每一条都对应一个具体的坏结果这样记就不会漏。3.2 信号量的物理意义必须彻底搞懂信号量是第二章应用题的核心工具。教材里信号量定义为一个整型量 S除了初始化之外只能通过 P、V 两个原语访问。很多人会背 PV 操作的代码但说不清 S.value 的正负到底代表什么。我用一句话概括S.value 大于零表示当前还可用的资源数等于零表示资源刚好用完小于零表示有 |S.value| 个进程正在排队等待这个资源。这个理解至关重要因为应用题里判断死锁、判断等待队列长度全靠它。P 操作可以理解成“申请一个资源”先把 S.value 减 1如果减完还大于等于零说明资源分得起继续走如果减完小于零说明资源不够把自己阻塞挂到 S 的等待队列上。V 操作可以理解成“释放一个资源”先把 S.value 加 1如果加完还小于等于零说明刚才有人在等于是从等待队列里唤醒一个进程。// P 操作wait P(S) { S.value--; if (S.value 0) { 将当前进程插入 S 的等待队列; 阻塞当前进程; } } // V 操作signal V(S) { S.value; if (S.value 0) { 从 S 的等待队列取出一进程; 将其插入就绪队列; } }注意一个细节P 操作是先减再判V 操作是先加再判。为什么因为减完为负说明“资源被透支了”也就是有人要来排队加完小于等于零说明“还清透支后还有人没被满足”。这两处的比较符号一个用0一个用0差一个等号含义完全不同考试时写错就丢分。3.3 用信号量解题的通用套路同步问题的应用题虽然花样多但解题套路是固定的我总结成五步找出题目里所有的进程和它们的任务。找出所有的临界资源每类资源配一个互斥信号量初值一般设为 1。找出所有的“先后依赖关系”每一对依赖配一个同步信号量初值一般设为 0。按“先 P 后 V、同步在前、互斥在内”的原则写出各进程代码。检查是否有死锁重点看 P 操作的顺序。这里面最容易错的是第四步的 P 操作顺序。原则是同步信号量的 P 操作放在互斥信号量的 P 操作之前。为什么因为如果先把互斥锁拿到手再去等同步信号量万一同步条件不满足你就抱着锁睡过去了别的进程想进来释放条件也进不来直接死锁。反过来先等同步条件条件满足了再去抢锁就不会出现这种局面。V 操作的顺序则无所谓因为 V 是释放不会阻塞。提示判断死锁的一个速记法是看同一个进程里是不是先 P 了一个互斥量又去 P 一个可能长期为负的同步量。如果是基本就是死锁。4. 经典同步问题手把手拆解4.1 生产者-消费者所有同步题的祖宗生产者-消费者问题是第二章应用题的必考题型。题目通常描述为一组生产者进程往缓冲区里放产品一组消费者进程从缓冲区里取产品缓冲区有 n 个单元要求生产者和消费者不能同时操作同一个单元且缓冲区满了生产者要等空了消费者要等。解题第一步设定信号量。这里需要三个mutex用来互斥访问缓冲区初值 1empty表示空单元数初值 nfull表示满单元数初值 0。这三个初值一定要想清楚一开始缓冲区全空所以空位有 n 个满位是 0 个。生产者代码producer() { while (true) { 生产一个产品; P(empty); // 申请一个空位 P(mutex); // 申请进入缓冲区 把产品放入缓冲区; V(mutex); // 退出缓冲区 V(full); // 满位加一 } }消费者代码consumer() { while (true) { P(full); // 申请一个产品 P(mutex); // 申请进入缓冲区 从缓冲区取出产品; V(mutex); // 退出缓冲区 V(empty); // 空位加一 消费产品; } }这里最经典的坑就是 P 操作的顺序。如果把P(mutex)写在P(empty)前面会发生什么假设缓冲区已经满了一个生产者先拿到 mutex然后执行P(empty)发现没有空位就把自己阻塞了。可 mutex 还在它手里消费者想进来消费就得先P(mutex)结果也阻塞。两边都卡死这就是死锁。所以顺序必须是P(empty)在前P(mutex)在后。我当初做这道题的时候满脑子想着“互斥优先”结果就栽在这个顺序上。后来想明白一个道理互斥锁保护的是“进入缓冲区”这个动作而不是“等待资源”这个状态。等待资源用的是同步信号量它应该在外面。理解了这一层就不会再写反了。4.2 哲学家进餐考的是怎么破死锁哲学家进餐问题描述的是五个哲学家围一张圆桌每两人之间放一根筷子哲学家要同时拿到左右两根筷子才能吃饭。如果每个哲学家都先拿左边的再拿右边的那么当五个人同时拿起左边筷子时每人都握着别人需要的那根谁也拿不到右边的死锁。教材里通常给三种解法。第一种是限制人数最多允许四个哲学家同时去拿筷子这样至少有一人能拿到两根。用一个初值为 4 的信号量控制入场即可。第二种是给筷子编号奇数号哲学家先拿左边再拿右边偶数号哲学家先拿右边再拿左边破坏循环等待条件。第三种是用 AND 信号量一次申请两根筷子要么都拿到要么都不拿。我个人觉得最容易在考试里写对的是第一种。代码如下semaphore count 4; // 最多四人同时进餐 semaphore chopstick[5] {1,1,1,1,1}; philosopher(int i) { while (true) { 思考; P(count); // 控制人数 P(chopstick[i]); // 拿左筷 P(chopstick[(i1)%5]); // 拿右筷 进餐; V(chopstick[i]); V(chopstick[(i1)%5]); V(count); 思考; } }为什么count初值是 4 而不是 5因为如果允许 5 个人同时拿筷子就等于没限制死锁依旧。限制到 4根据鸽笼原理至少有一个哲学家能凑齐两根筷子也就不可能五个人都卡住。这个 4 的来源要能说清楚否则简答题会被扣分。4.3 读者-写者细致到 rcount 的判断读者-写者问题要求允许多个读者同时读但写者写的时候不允许任何其他读者或写者操作。这道题的难点在于“第一个读者进来时要上锁最后一个读者离开时要解锁”中间的那几次读者进出不要碰写锁。需要的信号量有两个wmutex用于读写互斥初值 1mutex用于保护读者计数器rcount初值 1。rcount是普通整型变量初值 0。读者代码reader() { P(mutex); if (rcount 0) P(wmutex); // 第一个读者上写锁 rcount; V(mutex); 读操作; P(mutex); rcount--; if (rcount 0) V(wmutex); // 最后一个读者释放写锁 V(mutex); }写者代码writer() { P(wmutex); 写操作; V(wmutex); }最大的坑在于rcount的判断和修改必须整个包在mutex里面。如果判断rcount0在P(mutex)外面两个读者可能同时判断出 0然后都去P(wmutex)第二个就会被阻塞第一个读者反而会等第二个出现逻辑错乱。这种“检查-修改”必须原子的场景是信号量应用题里的高频考点。另外如果题目要求“写者优先”防止写者饥饿就要再加一个信号量让后续读者在看到有写者等待时先放行写者。这类变式题在慕课版的习题里偶尔出现属于加分项理解原理后按同样套路加一个同步量就能解决。4.4 变式题怎么套除了三大经典问题第二章课后题还会出一些变式比如“过桥问题”“理发师问题”“水果盘问题”。这些题的共同特点是有一个容量有限的容器有多类进程有互斥也有同步。遇到没见过的题不要慌套前面那个五步套路就行。先列出进程类型再数一下有几类临界资源需要互斥再找几对先后依赖需要同步最后按“先同步后互斥”的顺序把 P 排好。我做过一道“父亲放苹果、母亲放橘子、女儿吃苹果、儿子吃橘子”的题一开始被吓住了后来发现它其实就是两个生产者两个消费者共享一个容量为 1 的缓冲区信号量和生产者-消费者几乎一样只是产品类型分开了而已。5. 进程通信与线程容易被忽略的考点5.1 三种进程通信方式进程通信这一块课后题通常考三种方式的区别。共享内存、消息传递、管道各有适用场景。共享内存是在内存里划一块区域两个进程都映射到自己地址空间读写最快但需要自己配同步机制否则会数据竞争。消息传递是以消息为单位交换数据有直接通信和间接通信两种间接通信靠信箱适合分布式环境天然不需要额外同步。管道就是一块共享文件数据按字节流读写通常半双工Linux 里pipe系统调用就是它。题目常问“哪种通信方式效率最高”答案是共享内存因为数据不需要拷贝来拷贝去。但共享内存必须配信号量来互斥这是它和管道的区别所在管道本身是阻塞式读写自带同步。5.2 线程与进程的区别、线程的实现方式线程是第二章的收尾内容。线程是进程内的一个执行单元同一个进程的多个线程共享进程的地址空间和资源但有各自的栈和寄存器现场。所以线程切换开销比进程小得多这是引入线程的根本原因。区别要会列进程是资源分配单位线程是调度单位进程切换要换地址空间线程切换不用进程之间通信要特殊机制同一进程的线程之间直接共享内存就行一个线程崩了可能拖垮整个进程进程之间相对隔离。线程的实现方式通常考三种内核支持线程KLT、用户级线程ULT、混合实现。内核支持线程由内核管理一个线程阻塞不影响其他线程但切换要陷入内核开销大。用户级线程在用户空间由库管理切换快但一个线程阻塞会导致整个进程阻塞利用多核也不理想。混合实现就是两者结合多对多模型就是典型。这部分填空和选择居多把三个名词和各自的优缺点记熟基本就够了。如果考简答重点说清楚“为什么线程切换比进程快”理由是线程共享地址空间切换时不需要更新页表、刷新 TLB。6. 常见错误与做题心得6.1 错题速查表把第二章课后题里最常错的地方整理成一张表复习时对着看一遍比重新刷题效率高。错误点错误写法正确做法状态转换箭头阻塞→执行阻塞必须先回就绪P 操作顺序先 P(mutex) 后 P(empty)同步量在前互斥量在后信号量初值empty 初值设 0empty 初值为空位数 nrcount 保护判断在 mutex 外判断和修改都在 mutex 内哲学家人数count 初值设 5设 4 才能真正防死锁PCB 地位说 PCB 是进程的一部分PCB 是进程存在的唯一标志同步准则漏掉“让权等待”四条准则一条不能少这张表里的每一条我几乎都栽过。尤其是 P 操作顺序和 rcount 保护这两个坑属于“看答案懂了自己写又忘”的类型必须反复写几遍才能形成肌肉记忆。6.2 几个实用的做题习惯第一个习惯是写信号量代码前先在草稿纸上把每个信号量的含义和初值列出来。很多错误其实在设初值那一步就埋下了写代码只是把错误放大。把emptyn, full0, mutex1这一行先写清楚后面的代码就顺了。第二个习惯是写完 PV 代码后用一个具体的场景跑一遍。比如缓冲区 n1 的情况模拟一个生产者一个消费者交替执行看看会不会卡住。这种“打表验证”的方法能发现大部分死锁。第三个习惯是简答题别写太长但关键词必须齐。比如问“同步机制应遵循的准则”四个词一个都不能少多了反而可能被扣分。阅卷看的是关键词不是文采。第四个习惯是理解优先于背诵。第二章的可背诵内容其实不算多状态图、PV 操作、三个经典问题加起来就那点东西。但如果不理解换个变式题就抓瞎。我自己复习的时候会把生产者-消费者的代码默写出来然后改一改条件比如把缓冲区改成 1把消费者改成两个看看代码要不要调整。这种自我拷问比刷十道原题都有用。最后再分享一个小技巧做题时如果一时想不起某个信号量初值就用“最极端情况”反推。缓冲区为空时应该有几个空位、几个产品想清楚这个极限场景初值自然就出来了。这个办法我在考场上用过好几次屡试不爽。 操作系统第二章习题解析：进程同步、信号量与PV操作
1. 第二章的习题地图先搞清楚这一章在讲什么1.1 教材第二章的知识骨架翻开“计算机操作系统慕课版”第二章的标题是“进程的描述与控制”。很多同学第一章学得挺顺一到第二章就开始懵原因很简单第一章讲的是操作系统“长什么样”第二章讲的是操作系统“怎么跑起来”。这一章的核心是把“程序”这个静态的东西变成“进程”这个动态的实体然后再解决多个进程抢资源时怎么不打架的问题。这一章的骨架其实就四块。第一块是进程的基本概念包括前趋图、程序的顺序执行与并发执行、进程的定义与特征、进程的三种基本状态加两种挂起状态、PCB 的作用。第二块是进程控制也就是创建、终止、阻塞、唤醒、挂起、激活这几个原语。第三块是进程同步临界区、同步机制的四条准则、信号量机制、经典同步问题。第四块是进程通信与线程共享内存、消息传递、管道以及线程的引入和实现方式。课后习题基本就是围着这四块出题只不过把知识点揉进选择题、填空题、简答题和应用题里。我当年第一遍做的时候把概念题当成阅读理解随便勾结果一对答案错一片后来才明白这一章的题不是考记忆是考你脑子里有没有一张“状态流转图”和一套“PV 操作模板”。1.2 课后习题的四种题型与分值分布把第二章的课后题按题型分类大概能分成四类每类的备考策略完全不同。题型典型考法占比感觉备考重点选择题状态判断、概念辨析约 30%抠字眼区分“一定”“可能”填空题PCB 内容、准则名称约 15%记术语别写错顺序简答题进程与程序区别、状态转换约 25%背模板但要理解着背应用题信号量解决同步问题约 30%套模板 判死锁选择题最容易掉以轻心。比如“进程是程序的一次执行过程”这种话在选择题里会被改成“进程就是程序”一字之差就是错的。填空题看着是送分题但“空闲让进、忙则等待、有限等待、让权等待”这四条同步准则写反顺序或者漏一条分就没了。应用题是重头戏也是最能拉开差距的地方因为它不只考你会不会写 PV还考你会不会分析为什么这样写、会不会判断哪里可能死锁。我个人的建议是复习顺序不要按题号来而是先啃应用题把同步问题彻底搞懂再回头刷选择填空。因为应用题搞懂了第一部分的概念自然就串起来了很多选择题甚至不用背就能选对。1.3 复习顺序的建议很多同学喜欢从第一题顺着做到最后一题做完对答案错的抄一遍然后就没有然后了。这种刷题方式对第二章基本无效因为第二章的知识点是网状的不是线性的。更靠谱的顺序是这样第一步先画一张进程状态转换图把就绪、执行、阻塞、创建、终止这五个状态以及它们之间的箭头背下来这是所有题的基础。第二步理解 PCB 是什么为什么每个进程必须有一个。第三步进入同步问题把信号量的物理意义搞清楚。第四步动手把生产者-消费者、哲学家进餐、读者-写者三个经典问题各写两遍第一遍照抄模板第二遍合上书自己写。第五步再回头做选择填空你会发现正确率明显上去了。这个顺序的道理在于第二章的难点集中在同步而同步的基础是状态和 PCB所以要从根往叶走而不是从叶往根爬。2. 概念类习题看着简单实则处处是坑2.1 进程与程序的区别别只背那四句话课后第一道简答题几乎固定是“试说明进程与程序的区别”。标准答案一般是四点进程是动态的程序是静态的进程有生命周期程序可以长期存在一个程序可以对应多个进程一个进程也可以包含多个程序进程是资源分配和调度的基本单位程序不是。但真正做题的时候光背这四句是不够的。你得能举例子。比如我用记事本写文档记事本这个可执行文件是程序它是躺在硬盘上的静态的。我双击打开它内存里就多了一个进程它有 PCB、有程序计数器、有寄存器现场。我再打开一个记事本又多了个进程两个进程对应的是同一个程序。这样一解释四个区别就全活了。还有一个常见的坑题目会把“进程是资源分配的基本单位”和“线程是调度的基本单位”放一起考。在没有引入线程之前进程既是资源分配单位也是调度单位。引入线程之后这两个角色分家了。这个点如果记混选择题必错。2.2 进程的五个状态与转换条件进程状态题是第二章的送分题也是最容易因为“方向搞反”而丢分的题。基本状态有三个就绪、执行、阻塞。再加上创建和终止一共五个。状态转换的关键在于“什么事导致了这次转换”。就绪到执行是调度程序选中了它这是唯一一个由“外部调度”引起的转换。执行到就绪是时间片用完或者被更高优先级抢占。执行到阻塞是进程主动请求资源没得到比如等 I/O、等信号量。阻塞到就绪是等待的事件发生了比如 I/O 完成、信号量被 V 操作释放。注意阻塞到执行不存在必须先回到就绪再被调度。这个点每年都有人画错箭头。我在做题时总结了一句口诀主动走阻塞被动回就绪。意思是进程自己请求资源失败会主动进入阻塞而阻塞结束是因为别的进程帮了忙所以是被动回到就绪。这句话帮我记住了所有箭头方向。注意状态转换图里“就绪→阻塞”和“阻塞→执行”这两条箭头是绝对不存在的前者因为就绪进程还没上处理机谈不上请求资源失败后者因为阻塞态不能直接上处理机。2.3 PCB 里到底存了什么PCB进程控制块是第二章出填空题的高频点。标准答案通常列四类信息进程标识符、处理机状态、进程调度信息、进程控制信息。但具体展开很多人记不全。我用一个便于记忆的分类PCB 就是进程的“身份证 存款单 行程表”。身份证是 PID 和用户标识说明它是谁存款单是资源清单说明它占了哪些内存、哪些设备、打开了哪些文件行程表是处理机现场和调度信息包括程序计数器、寄存器值、进程优先级、等待时间、队列指针。这里有个容易被忽略的点PCB 是进程存在的唯一标志。也就是说创建一个进程本质就是创建它的 PCB撤销一个进程本质就是回收它的 PCB。系统区里有一张 PCB 表所有进程的 PCB 都挂在这张表上。理解这一点进程创建、终止、阻塞、唤醒的原语就都好懂了因为原语干的事基本就是“改 PCB 里的状态字段然后把 PCB 挂到对应的队列上”。2.4 进程控制原语动作顺序不能乱进程控制部分的简答题常问“创建进程需要做哪些工作”或者“阻塞原语和唤醒原语的关系”。这里的关键是记住进程控制都是通过原语实现的而原语是原子操作执行期间不允许被中断。以创建为例顺序大概是这样申请空白 PCB分配唯一 PID为新进程分配资源包括内存、I/O 设备、文件初始化 PCB填好各种字段把 PCB 插入就绪队列。这四步的顺序不能乱尤其是先有 PCB 再挂队列反过来就找不到挂什么了。阻塞和唤醒的配合也很典型。一个进程调用阻塞原语时是把自身 PCB 的状态改为阻塞然后插入对应事件的等待队列最后转调度程序。唤醒原语通常是另一个进程调用的它把等待队列里某个 PCB 移出状态改为就绪再插入就绪队列。注意阻塞是进程自己调用的唤醒是别人调用的这个“自己 vs 别人”的对应关系是选择题很喜欢设的陷阱。3. 进程同步与信号量第二章真正的核心3.1 临界资源、临界区以及那四条准则进程同步是第二章的分水岭。概念部分先要搞清楚三组词临界资源、临界区、同步与互斥。临界资源是一次只允许一个进程使用的资源比如打印机、共享变量。临界区是访问临界资源的那段代码。注意临界资源是“东西”临界区是“代码”题目经常故意混着说。同步是多个进程为了完成同一个任务而协调先后顺序互斥是多个进程争用同一个资源而必须排他。同步是“你走完我再走”互斥是“我进了你别进”两者不是一回事。为了让临界区的管理可靠同步机制必须满足四条准则空闲让进、忙则等待、有限等待、让权等待。这四条我一开始只是背后来才想明白它们各防什么。“空闲让进”防的是资源闲着没人用效率低“忙则等待”防的是多个进程同时进破坏互斥“有限等待”防的是某个进程永远等不到即饥饿“让权等待”防的是进程占着处理机干等浪费 CPU。每一条都对应一个具体的坏结果这样记就不会漏。3.2 信号量的物理意义必须彻底搞懂信号量是第二章应用题的核心工具。教材里信号量定义为一个整型量 S除了初始化之外只能通过 P、V 两个原语访问。很多人会背 PV 操作的代码但说不清 S.value 的正负到底代表什么。我用一句话概括S.value 大于零表示当前还可用的资源数等于零表示资源刚好用完小于零表示有 |S.value| 个进程正在排队等待这个资源。这个理解至关重要因为应用题里判断死锁、判断等待队列长度全靠它。P 操作可以理解成“申请一个资源”先把 S.value 减 1如果减完还大于等于零说明资源分得起继续走如果减完小于零说明资源不够把自己阻塞挂到 S 的等待队列上。V 操作可以理解成“释放一个资源”先把 S.value 加 1如果加完还小于等于零说明刚才有人在等于是从等待队列里唤醒一个进程。// P 操作wait P(S) { S.value--; if (S.value 0) { 将当前进程插入 S 的等待队列; 阻塞当前进程; } } // V 操作signal V(S) { S.value; if (S.value 0) { 从 S 的等待队列取出一进程; 将其插入就绪队列; } }注意一个细节P 操作是先减再判V 操作是先加再判。为什么因为减完为负说明“资源被透支了”也就是有人要来排队加完小于等于零说明“还清透支后还有人没被满足”。这两处的比较符号一个用0一个用0差一个等号含义完全不同考试时写错就丢分。3.3 用信号量解题的通用套路同步问题的应用题虽然花样多但解题套路是固定的我总结成五步找出题目里所有的进程和它们的任务。找出所有的临界资源每类资源配一个互斥信号量初值一般设为 1。找出所有的“先后依赖关系”每一对依赖配一个同步信号量初值一般设为 0。按“先 P 后 V、同步在前、互斥在内”的原则写出各进程代码。检查是否有死锁重点看 P 操作的顺序。这里面最容易错的是第四步的 P 操作顺序。原则是同步信号量的 P 操作放在互斥信号量的 P 操作之前。为什么因为如果先把互斥锁拿到手再去等同步信号量万一同步条件不满足你就抱着锁睡过去了别的进程想进来释放条件也进不来直接死锁。反过来先等同步条件条件满足了再去抢锁就不会出现这种局面。V 操作的顺序则无所谓因为 V 是释放不会阻塞。提示判断死锁的一个速记法是看同一个进程里是不是先 P 了一个互斥量又去 P 一个可能长期为负的同步量。如果是基本就是死锁。4. 经典同步问题手把手拆解4.1 生产者-消费者所有同步题的祖宗生产者-消费者问题是第二章应用题的必考题型。题目通常描述为一组生产者进程往缓冲区里放产品一组消费者进程从缓冲区里取产品缓冲区有 n 个单元要求生产者和消费者不能同时操作同一个单元且缓冲区满了生产者要等空了消费者要等。解题第一步设定信号量。这里需要三个mutex用来互斥访问缓冲区初值 1empty表示空单元数初值 nfull表示满单元数初值 0。这三个初值一定要想清楚一开始缓冲区全空所以空位有 n 个满位是 0 个。生产者代码producer() { while (true) { 生产一个产品; P(empty); // 申请一个空位 P(mutex); // 申请进入缓冲区 把产品放入缓冲区; V(mutex); // 退出缓冲区 V(full); // 满位加一 } }消费者代码consumer() { while (true) { P(full); // 申请一个产品 P(mutex); // 申请进入缓冲区 从缓冲区取出产品; V(mutex); // 退出缓冲区 V(empty); // 空位加一 消费产品; } }这里最经典的坑就是 P 操作的顺序。如果把P(mutex)写在P(empty)前面会发生什么假设缓冲区已经满了一个生产者先拿到 mutex然后执行P(empty)发现没有空位就把自己阻塞了。可 mutex 还在它手里消费者想进来消费就得先P(mutex)结果也阻塞。两边都卡死这就是死锁。所以顺序必须是P(empty)在前P(mutex)在后。我当初做这道题的时候满脑子想着“互斥优先”结果就栽在这个顺序上。后来想明白一个道理互斥锁保护的是“进入缓冲区”这个动作而不是“等待资源”这个状态。等待资源用的是同步信号量它应该在外面。理解了这一层就不会再写反了。4.2 哲学家进餐考的是怎么破死锁哲学家进餐问题描述的是五个哲学家围一张圆桌每两人之间放一根筷子哲学家要同时拿到左右两根筷子才能吃饭。如果每个哲学家都先拿左边的再拿右边的那么当五个人同时拿起左边筷子时每人都握着别人需要的那根谁也拿不到右边的死锁。教材里通常给三种解法。第一种是限制人数最多允许四个哲学家同时去拿筷子这样至少有一人能拿到两根。用一个初值为 4 的信号量控制入场即可。第二种是给筷子编号奇数号哲学家先拿左边再拿右边偶数号哲学家先拿右边再拿左边破坏循环等待条件。第三种是用 AND 信号量一次申请两根筷子要么都拿到要么都不拿。我个人觉得最容易在考试里写对的是第一种。代码如下semaphore count 4; // 最多四人同时进餐 semaphore chopstick[5] {1,1,1,1,1}; philosopher(int i) { while (true) { 思考; P(count); // 控制人数 P(chopstick[i]); // 拿左筷 P(chopstick[(i1)%5]); // 拿右筷 进餐; V(chopstick[i]); V(chopstick[(i1)%5]); V(count); 思考; } }为什么count初值是 4 而不是 5因为如果允许 5 个人同时拿筷子就等于没限制死锁依旧。限制到 4根据鸽笼原理至少有一个哲学家能凑齐两根筷子也就不可能五个人都卡住。这个 4 的来源要能说清楚否则简答题会被扣分。4.3 读者-写者细致到 rcount 的判断读者-写者问题要求允许多个读者同时读但写者写的时候不允许任何其他读者或写者操作。这道题的难点在于“第一个读者进来时要上锁最后一个读者离开时要解锁”中间的那几次读者进出不要碰写锁。需要的信号量有两个wmutex用于读写互斥初值 1mutex用于保护读者计数器rcount初值 1。rcount是普通整型变量初值 0。读者代码reader() { P(mutex); if (rcount 0) P(wmutex); // 第一个读者上写锁 rcount; V(mutex); 读操作; P(mutex); rcount--; if (rcount 0) V(wmutex); // 最后一个读者释放写锁 V(mutex); }写者代码writer() { P(wmutex); 写操作; V(wmutex); }最大的坑在于rcount的判断和修改必须整个包在mutex里面。如果判断rcount0在P(mutex)外面两个读者可能同时判断出 0然后都去P(wmutex)第二个就会被阻塞第一个读者反而会等第二个出现逻辑错乱。这种“检查-修改”必须原子的场景是信号量应用题里的高频考点。另外如果题目要求“写者优先”防止写者饥饿就要再加一个信号量让后续读者在看到有写者等待时先放行写者。这类变式题在慕课版的习题里偶尔出现属于加分项理解原理后按同样套路加一个同步量就能解决。4.4 变式题怎么套除了三大经典问题第二章课后题还会出一些变式比如“过桥问题”“理发师问题”“水果盘问题”。这些题的共同特点是有一个容量有限的容器有多类进程有互斥也有同步。遇到没见过的题不要慌套前面那个五步套路就行。先列出进程类型再数一下有几类临界资源需要互斥再找几对先后依赖需要同步最后按“先同步后互斥”的顺序把 P 排好。我做过一道“父亲放苹果、母亲放橘子、女儿吃苹果、儿子吃橘子”的题一开始被吓住了后来发现它其实就是两个生产者两个消费者共享一个容量为 1 的缓冲区信号量和生产者-消费者几乎一样只是产品类型分开了而已。5. 进程通信与线程容易被忽略的考点5.1 三种进程通信方式进程通信这一块课后题通常考三种方式的区别。共享内存、消息传递、管道各有适用场景。共享内存是在内存里划一块区域两个进程都映射到自己地址空间读写最快但需要自己配同步机制否则会数据竞争。消息传递是以消息为单位交换数据有直接通信和间接通信两种间接通信靠信箱适合分布式环境天然不需要额外同步。管道就是一块共享文件数据按字节流读写通常半双工Linux 里pipe系统调用就是它。题目常问“哪种通信方式效率最高”答案是共享内存因为数据不需要拷贝来拷贝去。但共享内存必须配信号量来互斥这是它和管道的区别所在管道本身是阻塞式读写自带同步。5.2 线程与进程的区别、线程的实现方式线程是第二章的收尾内容。线程是进程内的一个执行单元同一个进程的多个线程共享进程的地址空间和资源但有各自的栈和寄存器现场。所以线程切换开销比进程小得多这是引入线程的根本原因。区别要会列进程是资源分配单位线程是调度单位进程切换要换地址空间线程切换不用进程之间通信要特殊机制同一进程的线程之间直接共享内存就行一个线程崩了可能拖垮整个进程进程之间相对隔离。线程的实现方式通常考三种内核支持线程KLT、用户级线程ULT、混合实现。内核支持线程由内核管理一个线程阻塞不影响其他线程但切换要陷入内核开销大。用户级线程在用户空间由库管理切换快但一个线程阻塞会导致整个进程阻塞利用多核也不理想。混合实现就是两者结合多对多模型就是典型。这部分填空和选择居多把三个名词和各自的优缺点记熟基本就够了。如果考简答重点说清楚“为什么线程切换比进程快”理由是线程共享地址空间切换时不需要更新页表、刷新 TLB。6. 常见错误与做题心得6.1 错题速查表把第二章课后题里最常错的地方整理成一张表复习时对着看一遍比重新刷题效率高。错误点错误写法正确做法状态转换箭头阻塞→执行阻塞必须先回就绪P 操作顺序先 P(mutex) 后 P(empty)同步量在前互斥量在后信号量初值empty 初值设 0empty 初值为空位数 nrcount 保护判断在 mutex 外判断和修改都在 mutex 内哲学家人数count 初值设 5设 4 才能真正防死锁PCB 地位说 PCB 是进程的一部分PCB 是进程存在的唯一标志同步准则漏掉“让权等待”四条准则一条不能少这张表里的每一条我几乎都栽过。尤其是 P 操作顺序和 rcount 保护这两个坑属于“看答案懂了自己写又忘”的类型必须反复写几遍才能形成肌肉记忆。6.2 几个实用的做题习惯第一个习惯是写信号量代码前先在草稿纸上把每个信号量的含义和初值列出来。很多错误其实在设初值那一步就埋下了写代码只是把错误放大。把emptyn, full0, mutex1这一行先写清楚后面的代码就顺了。第二个习惯是写完 PV 代码后用一个具体的场景跑一遍。比如缓冲区 n1 的情况模拟一个生产者一个消费者交替执行看看会不会卡住。这种“打表验证”的方法能发现大部分死锁。第三个习惯是简答题别写太长但关键词必须齐。比如问“同步机制应遵循的准则”四个词一个都不能少多了反而可能被扣分。阅卷看的是关键词不是文采。第四个习惯是理解优先于背诵。第二章的可背诵内容其实不算多状态图、PV 操作、三个经典问题加起来就那点东西。但如果不理解换个变式题就抓瞎。我自己复习的时候会把生产者-消费者的代码默写出来然后改一改条件比如把缓冲区改成 1把消费者改成两个看看代码要不要调整。这种自我拷问比刷十道原题都有用。最后再分享一个小技巧做题时如果一时想不起某个信号量初值就用“最极端情况”反推。缓冲区为空时应该有几个空位、几个产品想清楚这个极限场景初值自然就出来了。这个办法我在考场上用过好几次屡试不爽。