第2章 · 播客 第3集
操作系统 · 同步互斥、P/V 操作与死锁
🎙️ 本集播客：第3集：互斥与同步的定义逐项辨析、临界资源与临界区、四条协调准则、信号量与 P/V 原语的完整流程（含 mutex 逐步演算），把生产者消费者的两个信号量念成话，再把死锁的四个必要条件和预防、避免、检测、恢复四类策略连银行家算法一起钉死。 语音由微软 Edge 神经网络语音预生成（女声·晓伊，男声·云希）。点击下方任意对话可直接从该句开始播，当前句朗读时下一句已预先加载，无缝衔接。
明
阿明
上集把进程三态和 PCB 都捋顺了。可机器上跑的是一堆进程，它们抢同一台打印机时，操作系统凭什么拦得住？
雅
小雅
这就进到本章最出题的一块：进程互斥与同步。进程互斥定义为：一组并发进程中一个或多个程序段，因共享某一共有资源而导致必须以一个不允许交叉执行的单位执行。也就是说，互斥是要保证临界资源在某一时刻只被一个进程访问。
雅
小雅
进程同步定义为：把异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程，称为进程同步。教材还专门给了一句提示：简单一点来说，互斥是资源的竞争关系，而同步是进程间的协作关系。
明
阿明
我复述一遍——互斥是进程之间互相配合，同步是大家抢资源，对吧？
雅
小雅
整个反了，而这一反正好是这道题的头号陷阱。方向记牢：互斥是资源的竞争关系，同步是进程间的协作关系。四个选项就围着这一句转——把两者对调的那个最像正确答案；说「互斥和同步是完全相同的概念」的直接排除；最阴的一个说「同步是资源的竞争关系，互斥与资源无关」，可互斥的定义头一句就是共享共有资源。
明
阿明
竞争对互斥、协作对同步。那「临界资源」到底指哪些东西？
雅
小雅
系统中有些资源可以供多个进程同时使用，有些资源则一次仅允许一个进程使用，将一次仅允许一个进程使用的资源称为临界资源。很多物理设备如打印机、磁带机等都属于临界资源；某些软件的变量、数据、表格也不允许两个进程同时使用，所以也是临界资源——别漏后半句。
雅
小雅
再往下，把一个进程访问临界资源的那段程序代码称为临界区，于是进程间的互斥就可以描述为：禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。临界资源是那个东西，临界区是那段代码。
明
阿明
那协调它们有明文规矩吗？
雅
小雅
协调准则四条，每条四个字。空闲让进：无进程处于临界区时，若有进程要求进入则立即允许其进入。忙则等待：当已有进程进入其临界区时，其他试图进入各自临界区的进程必须等待。有限等待：应在有限时间内使一进程进入临界区，不应相互等待而谁也不进入。让权等待：对于等待进入临界区的进程，必须释放其占有的 CPU，「权」指的就是处理机。
明
阿明
那用什么机制实现这四条？
雅
小雅
信号量可以有效地实现进程的同步和互斥。在操作系统中，信号量是一个整数：当信号量大于等于 0 时，代表可供并发进程使用的资源实体数；当信号量小于零时，则表示正在等待使用临界区的进程数。建立信号量必须说明它代表的意义、设置初值，并建立相应的数据结构，以便指向那些等待使用该临界区的进程。
明
阿明
最后那句「指向等待的进程」就是等待队列吧？信号量是负数时，绝对值就等于排队的进程数？
雅
小雅
对。而对信号量只能施加 P 操作和 V 操作两种，它们都是不可分割的原子操作，也称为原语，因此 P 原语和 V 原语执行期间不允许中断发生。
雅
小雅
定义连伪代码一起念。P 括号 sem：第一步 sem 等于 sem 减 1；第二步如果 sem 小于 0，进程进入等待状态，也就是调用 P 操作的进程暂停执行，直到另一个进程对同一信号量做 V 操作；否则继续进行。V 括号 sem：第一步 sem 等于 sem 加 1；第二步如果 sem 小于等于 0，就从相应队列，也就是与 sem 有关的那个队列里选一个进程唤醒它；否则继续进行。
明
阿明
我要问准。P 操作把 sem 减 1 后发现小于 0，这个进程到底是继续执行、被唤醒、被终止，还是停下来等？
雅
小雅
答案是进入等待状态，要说完整：该进程被阻塞，插入与这个信号量相关的等待队列。四个选项挨个排——「继续执行」是减 1 之后大于等于 0 那条分支，被摘出来当干扰项；「被唤醒」不是 P 操作干的事，唤醒是 V 操作的动作，这是把 P 和 V 的职责对调；「终止」根本不存在，进程只是暂停，资源还捏在手里。
雅
小雅
还有个不对称必须记死：P 操作判 sem 小于 0，V 操作判 sem 小于等于 0，一个不带等号一个带等号。拿数走一遍。设互斥信号量 mutex 初值为 1，表示没有并发进程使用该临界区。进程甲做 P：mutex 从 1 减到 0，不小于 0，继续进行，甲进临界区。进程乙也做 P：从 0 减到负 1，小于 0，乙被阻塞入队；负 1 的绝对值是 1，正对应「有 1 个进程在等」。
雅
小雅
接着甲出临界区做 V：mutex 从负 1 加到 0，小于等于 0 成立，从队列里选一个进程唤醒，乙醒了。V 要是写成小于 0 才唤醒，乙就永远睡死——这就是那个等号必须在的理由。顺带把互斥的标准写法收了，就三行：P 括号 mutex、临界区、V 括号 mutex。
明
阿明
那我要的不是互斥而是同步呢，比如必须甲做完乙才能做？
雅
小雅
这里有一对术语。要用 P、V 操作实现进程同步，需要引进私用信号量；私用信号量只与制约进程和被制约进程有关，而不是与整组并发进程相关。与此相对，进程互斥使用的信号量为公用信号量。三步：设置私用信号量、赋初值、再用 P、V 原语规定各进程的执行顺序。
明
阿明
同步用私用、互斥用公用。那经典的生产者消费者要几个信号量？
雅
小雅
两个，原文的理由是：这要求存后再取、取后再存，即有两个制约关系，为此需要两个信号量，表示缓冲区中的空单元数和非空单元数，记为 Bufempty 和 Buffull，它们的初值分别是 1 和 0。为什么这么设？非负时代表可用资源数，缓冲区一开始空着，空单元数 1、非空单元数 0。
明
阿明
所以初值就把先后顺序定死了？
雅
小雅
生产者做 P 括号 Bufempty，1 减到 0 能过；消费者做 P 括号 Buffull，0 减到负 1 被阻塞——初值天然保证了「先存后取」。程序段这么念：生产者是个循环，生产一产品 next，P 括号 Bufempty，next 产品存缓冲区，V 括号 Buffull。消费者也是个循环，P 括号 Buffull，V 括号 Bufempty，从缓冲区中取产品、使用产品。
明
阿明
要是把生产者的 P、V 对调，先 V 括号 Buffull 再存产品，会怎么样？
雅
小雅
会出脏数据。V 括号 Buffull 的语义是「缓冲区多了一件成品，可以来取了」，你还没放进去就先喊，消费者取到的就是空的或残留。反过来，生产者不先做 P 括号 Bufempty 就往里存，等于没查有没有空位，会覆盖掉还没取走的产品。规律是：P 是申请，必须在动作前；V 是释放兼通知，必须在动作后。
明
阿明
P/V 我算踩实了。那这套东西用歪了，就出死锁？
雅
小雅
对。原文：当若干个进程互相竞争对方已占有的资源，无限期地等待，不能向前推进时，会造成死锁。例子最好背：P1 占有资源 R1，P2 占有资源 R2，这时 P1 又需要 R2，P2 也需要 R1，它们在等待对方占有的资源时又不会释放自己占有的资源，因而双方都进入无限等待状态。死锁是系统的一种出错状态，甚至会导致系统崩溃。
明
阿明
产生死锁要几个条件？我记得是四个。
雅
小雅
根因是：供共享的系统资源不足，资源分配策略和进程的推进顺序不当。然后是必考的一句——产生死锁的必要条件是：互斥条件、保持和等待条件、不剥夺条件和环路等待条件。四条对上刚才的例子：互斥条件，R1、R2 都是一次只能给一个进程用的临界资源；保持和等待条件，P1 攥着 R1 不放又在等 R2；不剥夺条件，谁也不能强行把 R1 从 P1 手里夺走；环路等待条件，P1 等 P2、P2 等 P1，接成一个圈。
明
阿明
考题问「四个必要条件不包括哪一项」，选项里塞了个「先来先服务」，算不算？
雅
小雅
不算，它就是答案。先来先服务，缩写 FCFS，又称先进先出 FIFO，是进程调度算法，就绪队列按先来后到原则排队，管的是「下一个让谁上 CPU」，跟资源占用格局无关。套路很固定：四条里抄三条，第四个位置换个调度算法，把四条背成一串就不会错。
明
阿明
那治死锁有几类办法？
雅
小雅
原文分两大类：一种是在死锁发生前采用的预防和避免策略，另一种是在死锁发生后采用的检测与恢复策略；细分就是预防、避免、检测、恢复四种。先说预防：死锁的预防主要是通过打破死锁产生的 4 个必要条件之一来保证不会产生死锁，通常采用资源的静态分配法或有序分配法，它们分别打破了资源动态分配条件和循环等待条件；代价是会大大降低系统资源的利用率和进程之间的并行程度。
明
阿明
那银行家算法是预防还是避免？这俩我一直分不清。
雅
小雅
银行家算法属于死锁避免。原文：死锁避免策略，则是在系统进行资源分配时，先执行一个死锁避免算法，典型的如银行家算法，以保证本次分配不会导致死锁发生。分界线在这儿——预防是事前一刀切，把四个必要条件之一从制度上废掉；避免不废条件，每次分配前临时跑一遍算法，会出事就先不给。看到「银行家算法」就答死锁避免，答预防就掉进最常见的坑。
雅
小雅
避免的代价：由于资源分配很频繁，因此死锁避免策略要耗费大量的 CPU 和时间。还有一句口径要背：实际上，系统出现死锁的概率很小，故从系统所花的代价上看，采用死锁发生后的检测与恢复策略，要比采用死锁发生前的预防与避免策略代价小一些。问「哪种策略代价更小」，就答检测与恢复。
明
阿明
有点反直觉，但记住了：概率小，事后收拾更便宜。
雅
小雅
本集必背。互斥是资源的竞争关系、同步是进程间的协作关系，别对调；一次仅允许一个进程使用的资源叫临界资源，访问它的代码叫临界区；准则是空闲让进、忙则等待、有限等待、让权等待。P 操作先减 1，小于 0 则进程进入等待状态、阻塞入队，否则继续；V 操作先加 1，小于等于 0 则唤醒队列中的一个等待进程，否则继续——等号别丢。互斥用公用信号量初值 1，同步用私用信号量，Bufempty 和 Buffull 初值分别是 1 和 0。
雅
小雅
死锁半边：四个必要条件是互斥、保持和等待、不剥夺、环路等待，先来先服务是调度算法不在其中；预防靠打破四条件之一，手段是静态分配法或有序分配法；避免靠分配前跑算法，代表是银行家算法；检测与恢复是事后策略，代价反而小。
明
阿明
进程这块闭环了。下一集进存储管理，页式段式，还有那个页面越给越缺页的怪事吧？