PV操作这四个字母几乎就是操作系统中“进程同步”的代名词。我见过不少同学把P和V背成“P就是减一V就是加一”结果一写例题就翻车。原因很简单减一加一只是表面动作背后那套“阻塞”“唤醒”和“等待队列”的机制才是PV操作真正难的地方。这篇文章我会从一个真实的并发事故讲起把信号量、P/V原语、互斥与同步的套路拆开揉碎再配上六个经典例题的完整推导最后把我自己踩过的高频错误和解题顺序一并交代清楚。不管是刚学操作系统、准备期末/考研还是去面后端岗位这篇都应该能让你少走很多弯路。1. 从并发混乱到临界区PV操作到底解决了什么1.1 一个购票系统是怎么被并发搞崩的假设你现在写了一个“余票查询购买”的接口数据库里某场演唱会的余票还剩1张。用户A和用户B几乎同时发起购买后台如果用两个线程/进程来跑代码可能是这样的if (ticket 0) { ticket--; return 购票成功; } return 已售罄;这段代码看着没问题但并发一上来就崩A先检查ticket大于0还没等它执行ticket--B也检查到ticket大于0接着A把票减成了0B又把票减成了-1。实际只卖出去1张票系统却答应了两张订单。这就是经典的“检查-修改-写回”三步不是原子的产生的竞争条件。读书的时候觉得这种bug很遥远工作之后你会在订单系统、库存系统、分布式锁相关代码里反复见到它的影子。解决思路也朴素多个进程/线程在访问共享资源时必须保证同一时刻只有一个能进“危险区”。这个思想并不难难的是操作系统怎么把“保证”落地。操作系统里的“临界critical”一词指的就是这种一旦并发执行就会出问题的区域。古人说“破窗效应”在并发这里同样成立如果临界区不设防任何一点小小的资源竞争都可能被并发放大成系统级的错误。所以我们需要的是一套被称为“PV操作”的基础工具让进程在进入临界区之前统一“申请”退出之后统一“归还”。1.2 临界资源、临界区与四个必备条件操作系统的术语里像余票这种一次只能被一个进程访问的资源叫临界资源打印机、共享变量、缓冲池都算。访问临界资源的这段代码叫临界区Critical Section。我们要做的是满足四个要求互斥同一时刻最多一个进程在临界区内。前进临界区空闲时不能阻止想进来的进程进入。有限等待进程不会永远等不到临界区。让权等待进不去时应该让出CPU而不是原地空转。这四个要求是后边评价PV解法好不好的标尺。很多同学死记PV题目却不管为什么这样写一旦题目变形就傻眼。我的建议是每次写完伪代码都用这四个标准检查一遍——有没有破坏互斥会不会活活饿死一个进程会不会有进程死锁这样练习二十道题之后你对PV的感觉就不一样了。这里有个容易忽视的细节临界区是代码区不是资源本身。我们在PV题目里经常说“进入临界区前P一下”准确理解是“用互斥信号量保证这段代码在同一个时刻只被一个进程执行”而不是“这个资源被锁住了”。概念一旦搞混后面分析复杂题目时很容易绕晕。2. 信号量与P、V的底层语义不是加加减减那么简单2.1 信号量的结构一个整数加一个等待队列PV操作由荷兰计算机科学家Dijkstra提出P是荷兰语Proberen尝试的缩写V是Verhogen增加的缩写。信号量Semaphore其实是一个结构体教科书上常常简化成typedef struct { int value; // 信号量值 queueprocess list; // 等待队列 } semaphore;value的正负很有讲究。value 0表示当前还有多少个可用资源value 0表示有多少个进程因为等待这个信号量而被阻塞。记住这一点读题时会很有用。P操作和V操作通常翻译成wait和signal含义应该这样记// P 操作申请资源 P(s) { s.value--; if (s.value 0) block(该进程进入s的等待队列); } // V 操作释放资源 V(s) { s.value; if (s.value 0) wakeup(从s的等待队列移除一个进程); }这里最容易被忽略的是P操作并不是“只要大于0就能进去”这么简单。它等于先把资源数减一减完发现是负数说明本来就没资源于是把自己挂到等待队列如果减完还是非负说明拿到了资源可以继续往下走。V操作先加一如果发现加完还是小于等于0说明等待队列里还有人必须唤醒一个。为什么是0而不是0因为加一之后等于0意味着之前是-1必然有人等着如果之前是0加完后变成1说明原本没有阻塞者。这个判断不要背错。2.2 为什么“原子性”是灵魂P和V都必须是原子操作也就是说P内部的“判断-修改-阻塞”一气呵成不能被其他进程打断。如果没有原子性两个进程同时在执行P的时候都修改了value那互斥保护就失效了。原子的实现不一定靠硬件关中断现代系统可能用软件算法、硬件指令或调度器的锁但使用层面你要把P/V当做一个不可拆分的原语。理解底层语义后可以用一个生活类比信号量像一个停车场。value是剩余车位P就是“申请车位”先看有没有位把剩余数减一如果发现负数说明超排了车只能在闸机口排队等V就是“一辆车离开”剩余数加一然后如果还有车在排队放进来一个。你要管理的是“剩余车位数”和“排队车辆数”而不是简单地把一个只用来计数的int加加减减。2.3 初值决定了P/V的性质同一套P/V信号量初值不同作用完全不同初值作用典型场景1互斥锁保护临界区同一时刻只有一个进程进入0事件同步一个进程没完成时另一个进程必须等待N资源计数允许最多N个进程同时使用同类资源这三种初值接下来都会用到。建议你在桌边贴一张小卡片“初值资源数量P一次申请一个资源V一次归还一个资源。资源可以是锁、席位、缓冲区格子、事件是否发生。”3. 互斥问题从一把锁到多把锁的正确姿势3.1 标准互斥写法要用PV实现互斥最标准的模板是semaphore mutex 1; 进程P1循环: P(mutex); // 临界区 V(mutex); // 非临界区 进程P2循环: P(mutex); // 临界区 V(mutex); // 非临界区为什么互斥锁初值是1因为初始时有1个“进入令牌”。第一个进程P之后value变成0还能进入第二个进程P之后value变成-1进入等待。第一个进程V之后value变成0唤醒等待者如果没有等待者value变成1恢复到初始状态。这套机制保证任意时刻临界区内最多一个进程。很多初学者不理解为什么非临界区之后不能立刻进入下一个循环如果P1在执行完V之后马上又P会再抢到锁P2可能一直饿着。互斥锁只保证“同一时刻只有一个”并不保证公平。所以在写更完整的程序时我们还要考虑PV之外的调度策略比如是否在非临界区让出CPU这也是“有限等待”要求的来源。3.2 我犯过的低级错误在临界区里重复P先说一个我在实际项目调试时遇过的死锁有个线程封装了一个日志缓冲区进入写日志的临界区后内部又调用了一个辅助函数辅助函数开头又P了同一个mutex结果同一线程自己把自己堵死了。这个叫重复加锁死锁。对应到PV题里就是同一进程在不释放锁的情况下再次P同一个信号量。比如P(mutex); // 临界区开始 P(mutex); // 错误自己等自己释放 // 临界区结束 V(mutex);第一次P后value0进入第二次P后value-1于是当前进程被挂起。但能唤醒它的V还在它后边永远执行不到死锁。这也是为什么很多工程里要求“P和V必须成对出现且临界区内不要再碰同一把锁”。另外要注意多个锁的顺序。如果你有两个不同资源比如缓冲区的mutex和某个状态标志的flagMutex不同进程必须用同样的加锁顺序。进程1先P(mutexA)再P(mutexB)进程2如果先P(mutexB)再P(mutexA)两个进程可能各持一把锁然后互相等对方释放经典的死锁场景。PV解题时如果涉及多把锁顺序一致性要写清楚。4. 同步问题用PV描述前驱后继关系4.1 一个“先S1后S2”的最小模型互斥解决的是“大家别同时进”同步解决的是“你必须先完成我才能开始”。最简单的同步模型是两个进程进程A做任务S1进程B做任务S2要求S1先执行S2后执行。只用一个信号量就能搞定semaphore s 0; A: S1; V(s); B: P(s); S2;这里信号量初值必须为0。如果初值是1B可能不等A执行完就往下跑同步关系就失效了。V(s)放在S1之后意味着“S1完成的信号发出”P(s)放在S2之前代表“没收到信号就等着收到了才继续”。你把这个模型练熟所有前置后继问题都是它的扩展。4.2 前驱图一条边一个信号量很多题目画出一张前驱图比如S1 完成后才能执行 S2 和 S3 S2 和 S3 都完成后才能执行 S4。实现方法很简单为每个依赖关系分配一个同步信号量初值都是0。每条边“前驱完成后V一次后继开始前P一次”。具体来说semaphore a12 0, a13 0, a24 0, a34 0; S1: { S1; V(a12); V(a13); } S2: { P(a12); S2; V(a24); } S3: { P(a13); S3; V(a34); } S4: { P(a24); P(a34); S4; }每个后继进程在开始前把属于自己的所有入边信号量都P一遍每个前驱进程在结束后把属于自己的所有出边信号量都V一遍。这样信号量的数量等于依赖边的数量。这个方法非常机械但极其可靠。遇到“进程之间有先后关系”的题目先画前驱图再逐边翻译成P/V基本不会出错。理解了同步模型后再去看生产者-消费者这类题你会发现它其实是同步和互斥的叠加缓冲区有空间是生产者对消费者的“前驱条件”缓冲区有数据是消费者对生产者的“前驱条件”而缓冲区本身是临界区又需要互斥锁。两套关系叠在一起就成了几乎所有PV复杂题的骨架。5. 六大经典例题逐题拆解5.1 生产者-消费者两队进程一个缓冲区这是PV操作的“hello world”。题目描述一组生产者进程不断生产产品放入大小为n的缓冲区一组消费者进程不断从缓冲区取产品消费。要求缓冲区空时消费者不能取缓冲区满时生产者不能放多个进程不能同时访问缓冲区。解法定义三个信号量mutex 1保护缓冲区的互斥锁empty n缓冲区中空闲格子数full 0缓冲区中已占用格子数。producer: P(empty); // 申请一个空位 P(mutex); // 进入缓冲区 把产品放入缓冲区; V(mutex); // 退出缓冲区 V(full); // 已满格子数1 consumer: P(full); // 申请一个产品 P(mutex); // 进入缓冲区 从缓冲区取出产品; V(mutex); // 退出缓冲区 V(empty); // 空位1这里有两个关键点。第一P操作的顺序不能反。如果把P(mutex)放到P(empty)前面当缓冲区满时生产者会先拿到锁然后阻塞在P(empty)消费者要取产品又必须先拿这把锁才能进缓冲区结果消费者也进不去。生产者占着锁等空位消费者拿着空位等锁互相等待死锁。所以正确顺序一定是“先申请资源信号量再申请互斥锁”。第二empty和full本质是两种资源的数量。empty的初值n是“缓冲区一共有n个单位”full的初值0是“现在有0个产品”。每次生产把空位减一、产品数加一每次消费反过来。用这个视角看生产者消费者没有多复杂。我还见过一个变体把缓冲区换成“有界缓冲区 多个生产者和多个消费者”解法完全一样。面试官如果想加难度会在“同时只能取一个”和“每次取多个”之间加限制但核心模型不变。5.2 读者-写者读读不互斥读写互斥问题一个共享数据区允许多个读者同时读写者必须独占读者在写者写时不能读写者在读者读时不能写。先实现读者优先版。定义rw_mutex 1控制写者之间、写者与第一个/最后一个读者之间的互斥mutex 1保护读者计数变量readcountreadcount 0记录当前读者数量。reader: P(mutex); readcount; if (readcount 1) P(rw_mutex); // 第一个读者要锁住写者 V(mutex); // 读数据 P(mutex); readcount--; if (readcount 0) V(rw_mutex); // 最后一个读者解锁 V(mutex); writer: P(rw_mutex); // 写数据 V(rw_mutex);这里最妙的是只有第一个读者会去竞争写锁后续读者只增加计数不需要再P(rw_mutex)最后那个读者负责释放。mutex保护的是readcount不是数据区不要搞混。读者优先版的缺点是只要有读者源源不断进来写者可能长时间无法执行称为“写者饥饿”。如果需求改成写者优先通常需要再加一个信号量write_wait让新读者在写者等待时也会被挡住。写者优先实现比读者优先复杂我面试时被问过思路是新增一个计数信号量或队列使得当有写者等待时读者不能进入。这里先不展开但你要知道“读者优先”不是唯一答案题目如果没有特别说明默认读者优先但实际系统往往更看重写者不被饿死。5.3 哲学家进餐怎么拿筷子才能不饿死五个哲学家围坐一张圆桌每个人面前有一盘意面每两个人之间放一支筷子。哲学家需要同时拿起左右两支筷子才能吃吃完放下。问题是每人先拿左边再拿右边五个哲学家同时拿了左边筷子就会都等待右边筷子形成死锁。常规解法有三种最多允许4个人同时上桌。限制并发哲学家数量不超过4保证至少一个人能拿到两支筷子。要求拿起两支筷子这个动作必须一次性完成用互斥锁包住左右筷子的拿取这样不会出现“只拿一边”的中间状态。奇偶编号策略奇数号哲学家先拿左边偶数号先拿右边打破循环等待。其中最容易写错的是第二种很多人一上来给每根筷子一个信号量然后写think: P(chopstick[i]); P(chopstick[(i1)%5]); eat; V(chopstick[i]); V(chopstick[(i1)%5]);这只能描述“拿筷子”的动作不能解决死锁。如果题目没说特别策略默认会死锁。所以解题时要写明另一把锁semaphore chopstick[5] {1,1,1,1,1}; semaphore room 4; // 最多4人同时就餐 philosopher i: P(room); P(chopstick[i]); P(chopstick[(i 1) % 5]); eat; V(chopstick[i]); V(chopstick[(i 1) % 5]); V(room);或者用一个互斥锁保护“拿两只筷子”的动作semaphore mutex 1; philosopher i: P(mutex); P(chopstick[i]); P(chopstick[(i 1) % 5]); V(mutex); eat; V(chopstick[i]); V(chopstick[(i 1) % 5]);注意第二种方案下mutex要等到两支筷子都拿到才释放否则其他哲学家可能又卡在半路。这个题的点不在“信号量多”而在“破坏死锁的四个必要条件”。考试时一定要写出你选择哪种策略而不是默认别人都能看出你的思路。5.4 过桥问题共享容量与方向互斥假设一条只能容纳N辆车的单车道桥两个方向的车都可能上桥。桥上不能会车且桥上最多N辆。要求用PV实现。这个题有陷阱很多人把信号量定义成“桥1”只实现了互斥但桥明明可以让N辆车同时同向通过。更合理的定义bridge N桥上还能容纳的车数量mutex 1保护方向计数防止两个方向的车同时上桥。每个方向维护一个计数变量进入时先看方向是否和当前占用方向一致如果桥空第一个车占用方向只有当某一方向的车全部离开后另一个方向的车才能上桥。简化实现只考虑同向多车、异向互斥非常像读者-写者只不过“同一方向的多个车”像多个读者“另一方向的车”像写者。方向计数需要单独保护。伪代码可以这样写semaphore bridge N; // 剩余通行席位 semaphore mutexN 1; // 保护 northCount semaphore mutexS 1; // 保护 southCount int northCount 0, southCount 0; semaphore directionLock 1; // 方向互斥 // 北向南方向的车 north_to_south: P(mutexN); northCount; if (northCount 1) P(directionLock); V(mutexN); P(bridge); 过桥; V(bridge); P(mutexN); northCount--; if (northCount 0) V(directionLock); V(mutexN);同理写南向北的车。这里bridge限流directionLock保证同一时刻只有一个方向的车在桥上。这类“共享容量方向互斥”的问题本质上就是读者-写者加了一个容量信号量掌握好基础模型就能拆。5.5 零件装配工问题三个工人与一个供应者经典PV题里有一道“吸烟者问题”因为名字有健康风险我描述成“零件装配工问题”解法一模一样更安全。题目三个工人分别需要三种零件工人A要零件1和2工人B要零件2和3工人C要零件1和3。一个供应者每次随机提供一组两种零件放在共享桌上只有需要的那个工人能拿走并装配其他工人只能等待。信号量设计materialA 0,materialB 0,materialC 0分别对应三个工人表示“材料已备好”finish 0表示“工人已取走并用完材料”供应者等finish后才能放下一组材料。工艺上供应者和工人之间的同步也可以再加一个canPlace 1表示桌子空。经典解法里用finish作为通知供应者放料的信号量初值为0供应者放完料后V对应的工人信号量。provider: P(finish); 随机选择一组材料放到桌上; if (材料组为1和2) V(materialA); else if (材料组为2和3) V(materialB); else V(materialC); worker A: P(materialA); 拿走材料并装配; V(finish);如果把canPlace桌子是否空也加进来可以写得更严谨一开始finish1供应者先P(finish)再放料。注意如果只有一个工人被唤醒其他工人的P都在等自己的信号量不会抢走不属于自己的材料。这个题的关键是每个工人各等一个独立的信号量供应者按材料组合特判V哪个。如果题目改成“供应者随机放任意两种”道理也一样只是分支判断多几个。5.6 理发师问题睡觉的理发师与等待椅理发店有一把理发椅、n把等待椅。没有顾客时理发师坐着睡觉顾客来了如果理发师在睡觉就叫醒他如果理发师在忙且等候区有空位就坐下等否则离开。这是典型的“多资源 一个服务者”模型。信号量设计barber 0表示理发师是否空闲可用于唤醒理发师customers 0表示等待的顾客数理发师等待顾客的同步信号量mutex 1保护等待椅计数变量waiting 0记录当前等待人数maxChairs n也可以用chairs n表示空位但更常见的做法是维护waiting。一个常用解法customer: P(mutex); if (waiting n) { waiting; V(mutex); V(customers); // 告诉理发师有顾客 P(barber); // 等待被理发 理发; } else { V(mutex); // 没位置直接走 } barber: while (true) { P(customers); // 等顾客信号 P(mutex); waiting--; V(mutex); V(barber); // 允许一个顾客进入理发椅 为顾客理发; }这里可能让人困惑的是V(customers)和V(barber)的顺序以及为什么理发师要先P(customers)再P(mutex)。思路是先让顾客数增加并退出mutex然后发信号通知理发师顾客再P(barber)等理发师叫他。理发师因为被customers唤醒去mutex里减掉顾客数然后V(barber)让一个正在等待的顾客进入理发。这个顺序保证waiting变量不会混乱。这个模型在很多场景都能复用比如单服务窗口排队、任务队列工作线程。记住一句话customers是给服务者的“有活干”信号barber是给顾客的“轮到你”信号两者各自同步一方不是互斥锁。6. 我踩过的高频错误与解题套路总结6.1 高频错误与修正清单我把平时答疑和看代码时遇到的高频错误整理成一张表方便复习时自查错误类型现象修正思路同步信号量与互斥信号量的P顺序混乱缓冲区满时生产者占锁等空位消费者等锁死锁先P资源信号量后P互斥信号量在临界区内再次P同一信号量进程自己把自己阻塞保证P/V成对不要在临界区里重复申请同一把锁V操作写在了分支里某个进程成功执行完后没有释放信号量其他进程被永久阻塞确保任意退出路径都有对应的V多个锁的加锁顺序不一致两个进程各持一把锁互等死锁所有进程按同一全局顺序加锁互斥锁初值写成0第一个进程进来就阻塞互斥锁初值为1同步信号量初值通常为0或资源数只看信号量加减忘记唤醒条件P后value0时需要blockV后value0时需要wakeup从“剩余资源排队进程”两个维度理解信号量这张表不一定全面但覆盖了PV初学阶段九成的坑。6.2 一套从题干到伪代码的快速拆解流程做题或者面试手撕PV时我习惯按下面五个步骤走找进程。圈出题干里所有独立执行流比如生产者、消费者、读者、写者、供应者、工人每个都当作一个进程。找共享资源。共享资源有哪些类型缓冲区、数据区、筷子、桥、理发椅、等待椅每一类都要考虑是否需要互斥或限流。找同步关系。用前驱图或箭头画出“谁必须先完成谁必须在后开始”。每条边配一个同步信号量。定初值。互斥信号量初值1资源数量信号量初值为资源总数同步信号量初值一般0除非“一开始就满足条件”。写伪代码后做极端情况推演。模拟缓冲区满/空、所有哲学家同时拿筷子、理发店满员等边界条件检查会不会死锁或饥饿。推演极端情况这步最容易被跳但它恰恰是区分“背答案”和“真理解”的关键。比如生产者消费者你只要在脑子里跑一遍“empty0时生产者卡在哪消费者能不能继续”答案就会很清晰。6.3 我自己的练习心得最后分享一点个人经验。我当年复习PV时没有直接背答案而是把每个经典题都用三四种不同信号量设计去尝试故意写错再观察错在哪里。比如哲学家进餐我先写出必死锁的版本再逐步加“最多四人上桌”或“拿两把筷子加锁”的改造这个过程让我对死锁的四个条件有了肌肉记忆。后来面试被问到“这个方案会不会饿死”我也能立刻从代码里指出风险点。如果你正被PV折磨我的建议是先死磕最小同步模型一个V唤醒一个P再练生产者-消费者然后把读者-写者和哲学家进餐作为进阶训练。练到能不看答案把伪代码默写出来并且能解释每一行P/V为什么在这里出现就说明真的过关了。
