1. 一个看着简单的经典同步问题为什么能卡住大部分人如果你在操作系统课上第一次听到理发师问题多半会觉得它没什么难度——不就是把顾客和理发师用信号量串起来嘛。可真到了要动手把它写成一个能跑的进程模型时很多人会卡在同一类地方顾客明明看到有空座位理发师却继续睡觉或者等候区还没坐满程序却莫名卡死。这个问题在每学期的进程同步章节里反复出现不是因为概念多复杂而是因为它把进程PV操作唤醒与阻塞这几个词背后的时序细节全压缩进了一个极小的场景里。先把场景摆清楚这也是所有推导的地基。一间理发店配置固定1 把理发椅、1 位理发师、N 把供顾客等候的椅子N 通常大于 0。规则有几条每一条都对应着程序里的一段逻辑没有顾客时理发师就坐在椅子上睡觉顾客进门时如果等候椅还有空位他就坐下等待同时如果发现理发师在睡觉要负责把他叫醒如果等候椅已经坐满这位顾客只能直接走人不能站在店里干等理发师每次只服务一位顾客服务完顺手把这位顾客从等候区移走再看还有没有下一位。这个描述里的每一句话在并发代码里都不是自然而然成立的。比如把理发师叫醒是一个跨进程的动作顾客进程必须想办法通知理发师进程从阻塞中恢复等候椅还有没有空位是一个共享状态的判断必须有互斥保护否则两个顾客同时看到最后一个空位就会发生计数错误。所以理发师问题的真正看点是它同时包含了互斥多个顾客/理发师竞争访问等候区计数和同步顾客与理发师之间的等待与唤醒两种机制而且这两种机制用同一套 PV 操作表达出来。适合读这篇内容的人大致有三类正在啃操作系统进程同步这一章的学生准备考试、被写出理发师问题的 PV 操作这道题反复折磨的备考者以及工作里偶尔要写点并发控制、想把信号量那套思维用顺手的人。不管你是哪一类我建议都别停留在能背出那几行伪代码的层面因为真正决定你答对还是答错的往往是某两个 V 操作的先后顺序——而这恰恰是背不出来的东西。1.1 三个角色、两种等待别把它们混成一锅在写任何代码之前先把场景里的角色和他们的状态列清楚这一步能省掉后面一大半的调试时间。角色其实只有三类顾客进程可能有很多个、理发师进程通常只有一个、以及被它们共享的那几个变量等候区的计数、几个信号量。等待在这个场景里有两种性质完全不同很多人一上来就把它们混为一谈。第一种是理发师等待顾客理发师无事可做主动进入阻塞状态直到有顾客到来才被唤醒这是一种服务方等资源的等待。第二种是顾客等待理发师顾客已经坐进等候区或理发椅但理发师还在忙他必须等理发师空出手来这是一种请求方等响应的等待。这两种等待的触发条件和唤醒条件正好是交叉的一个用 P 阻塞、另一个用 V 唤醒方向一旦搞反程序要么全体睡死要么空转。还有一点容易被忽略顾客走人这个动作是没有等待的。他判断等候区满了直接离开不进入任何阻塞队列。这意味着顾客进程里存在一个提前退出的分支这个分支同样要释放已经拿到的互斥锁否则下一个顾客会永远卡在锁上。你看光是角色和状态这一层就已经藏了好几个坑点。1.2 为什么先判断再行动的直觉写法一定出问题把理发店规则直接翻译成自然语言式的代码很多人的第一反应是这样顾客进店看一眼等候区如果没满就坐下顺便叫醒理发师如果满了就走。理发师则循环如果没顾客就睡有顾客就理发。这段逻辑在单线程的世界里完美无缺但在并发世界里它是错的原因就藏在看一眼这个动作里。看一眼等候区和坐下这两个动作之间必须没有其他进程能插进来修改等候区。假设现在的空位数是 1顾客 A 和顾客 B 几乎同时执行这段逻辑A 看到有空位还没来得及把计数加一B 也看到了那个同样存在的空位于是两个人都以为自己有位置计数就被写成了不该有的值或者等候区里被塞进了超额的顾客。这就是典型的竞态条件也是为什么要引入一个互斥信号量来保护那段判断 修改的临界区。更隐蔽的问题出在唤醒上。理发师睡觉本质上是阻塞在一个信号量上顾客要唤醒他必须对正确的信号量做 V 操作。如果你让顾客在没真正占到座位的情况下就去唤醒理发师那理发师醒来会面对一个空荡荡的等候区直接导致后续的计数和等待错乱。想清楚这一点你就会明白唤醒动作必须和确实占到一个位置这件事绑定在一起并且发生在临界区保护之下。这也是接下来所有推导的核心线索。2. 把理发店场景翻译成信号量谁该被唤醒谁该去睡眠从生活规则到信号量代码中间的桥梁是找共享资源和定信号量职责。很多人写完代码自己都说不清每个信号量到底代表什么于是遇到问题只能瞎改。我习惯的做法是先把所有需要保护的共享变量列出来再决定用几个信号量每个信号量负责通知哪一方。在这个场景里共享状态其实很少但每一个都很关键。等候区的顾客数量是一个共享整数我们用count表示注意它统计的是等候区等待的人不含正在理发椅上那位。这个变量会被所有顾客读、被顾客和理发师写所以必须有一个互斥信号量保护它我们叫它mutex。除了共享变量还有两组通知关系要用信号量表达一组是顾客来了要通知理发师有人等着别睡了另一组是理发师准备好了要通知某位顾客轮到你了过来坐。这两组通知方向相反所以需要两个独立的信号量customers负责从顾客到理发师的通知barber负责从理发师到顾客的通知。名字看着朴素但你只要记住它们的指向就不会用错。2.1 customers 和 barber 这两个信号量各管一件事customers这个信号量本质上是一个待服务顾客的计数器。顾客成功占到一个等候位置后对customers做 V 操作相当于在告诉理发师现在至少有一个人等着了你该醒了。理发师在循环开头对customers做 P 操作如果没有顾客P 操作会把他阻塞这就是睡觉一旦有顾客 V 过他就能从 P 里返回相当于被叫醒。它的初值应该是 0因为开店时没有顾客在等。barber这个信号量方向正好相反它表达的是理发师是否已经招呼你去坐理发椅。顾客做完V(customers)之后要对barber做 P 操作意思是我已经占好位了现在等理发师叫我。理发师每处理完一位顾客、把等候区的人移走之后对barber做 V 操作唤醒一位正在等的顾客。它的初值也是 0因为一开始没有顾客能等到理发师。这里有个特别容易记混的点customers是顾客 V、理发师 Pbarber是理发师 V、顾客 P。你可以用一句话记住——谁被唤醒谁就在那个信号量上 P。理发师被顾客唤醒所以理发师在customers上 P顾客被理发师唤醒所以顾客在barber上 P。把这句话刻在脑子里后面写代码时基本不会把 V 和 P 安反。2.2 mutex 保护的从来不是理发椅而是 count 这个数我见过不少人在讲解时会说用 mutex 保护理发椅这个说法很误导。理发椅本身在这一版模型里并没有争用——同一时刻只有一个人能坐上去这是由barber信号量的等待机制保证的不需要 mutex 额外保护。真正需要保护的是count这个共享计数以及围绕它做的判断是否满员 修改计数这一整段操作。为什么这段必须原子回到上一节说的竞态两位顾客同时判断是否还有空位如果判断和加法之间被别人插进来就可能出现超员或者幻影空位。把这段放进P(mutex)和V(mutex)之间就等于给等候区计数上了一把锁任何时刻只有一个进程能读写它。还有一处特别容易被忽略理发师减少count的那段代码同样要在 mutex 里。因为理发师把一个顾客从等候区移到理发椅这个动作会改变count如果不同步保护顾客读到的就是旧值可能出现计数对不上的情况。所以mutex是顾客和理发师共同遵守的规则不是只给顾客用的。提示判断count是否满员这一句一定要写在P(mutex)之后、V(mutex)之前。任何把判断挪到锁外的写法都会让整个互斥保护形同虚设。2.3 从顾客进门到理发椅空出来的完整状态流转把信号量职责定清楚后整个流程就可以顺下来了。理发师进程的主循环是先P(customers)等待顾客没顾客就睡醒来后拿mutex把count减一这位顾客已经从等候区移到理发椅再对barber做 V 唤醒那位顾客释放mutex然后开始理发理完继续下一轮循环。顾客进程则是一个判断分支进门先P(mutex)如果count小于等候椅数量 N就说明有空位把count加一接着对customers做 V告诉理发师有人来了释放mutex然后P(barber)等待被招呼去理发椅如果count已经等于 N说明满了直接释放mutex然后离开不做任何等待。这一进一出的对称结构是整个问题的骨架。你会注意到真正被唤醒去理发的顾客不是那个刚进门的顾客而是理发师从等候区移走的那一位。这一点在很多讲解里被含糊带过导致有人以为顾客一进门就直接被理发从而写错了等待位置。理清这个流转第 3 节的逐行拆解就会顺畅很多。3. 逐行拆经典代码每一句 P/V 背后的时序推演前面讲的是应该怎么想这一节讲代码到底长什么样为什么每一句都长这样。我把信号量初始化和两个进程的代码完整摆出来然后逐句解释其意图。这里的 P 操作等价于 wait/down表示申请资源、可能阻塞V 操作等价于 signal/up表示释放资源、可能唤醒等待者。// 共享变量与信号量初始化 semaphore mutex 1; // 保护 count 的互斥锁 semaphore customers 0; // 等候的顾客数理发师等待它 semaphore barber 0; // 理发师就绪信号顾客等待它 int count 0; // 等候区当前人数不含理发椅上的人 const int CHAIRS N; // 等候椅数量 // 理发师进程 while (true) { P(customers); // 没有顾客就在这里睡有顾客则醒来 P(mutex); // 进入临界区 count count - 1; // 一位顾客离开等候区坐上理发椅 V(barber); // 招呼这位顾客轮到你了 V(mutex); // 退出临界区 cut_hair(); // 理发耗时操作不占锁 } // 顾客进程每一个进店的顾客都执行这一段 P(mutex); // 进入临界区准备检查空位 if (count CHAIRS) { count count 1; // 占到一个等候位 V(customers); // 通知理发师有顾客在等 V(mutex); // 退出临界区 P(barber); // 等待理发师招呼去坐理发椅 get_haircut(); } else { V(mutex); // 没位置释放锁后直接离开 }3.1 理发师主循环为什么必须是先 P 再抢锁理发师循环的第一句是P(customers)而不是先抢mutex。这个顺序不是随意安排的。如果理发师先拿mutex再等顾客那么当他没有顾客要服务时会阻塞在P(customers)上却还握着mutex此时任何顾客进门都无法获得锁去修改count整个系统直接僵住。所以等待资源的 P 操作必须放在抢互斥锁之前让它阻塞时手里不持有任何锁。第二句进来才P(mutex)这时理发师已经确定确实有顾客存在了他需要做的只是把这个顾客从等候区划掉也就是count count - 1。紧接着V(barber)唤醒那位等待的顾客再V(mutex)释放锁。这里V(barber)放在V(mutex)之前是没问题的因为顾客在barber上的等待和mutex无关唤醒后顾客会自己去排队拿mutex。cut_hair()放在临界区之外是刻意的。理发是个耗时动作如果把它放进mutex里那么整个理发过程中没有第二个进程能碰count等候区的管理就彻底停摆了。耗时的、不需要保护共享数据的操作一律挪出临界区这是写并发代码的一条通用准则不只是理发师问题。3.2 顾客进程的 if-else 藏着两个完全不同的出口顾客进程从P(mutex)开始这段是它的临界区入口。进来第一件事就是判断count CHAIRS也就是还有没有空位。走if分支时顾客占位成功count加一V(customers)唤醒理发师然后释放mutex最后P(barber)等理发师招呼。注意这里的顺序——先 V(customers) 再 V(mutex)看似无所谓但其实有讲究。如果先V(mutex)再V(customers)在两者之间理发师可能已经抢到锁、把count减掉了紧接着才收到customers的通知逻辑上虽然还能跑通但时序会变得不那么直观。放在锁内先通知能保证占位和通知这两件事对外表现为一个原子动作。走else分支时顾客发现满员唯一要做的是V(mutex)把锁还回去然后头也不回地离开。这个分支里绝不能出现任何 P 操作否则这位本该走人的顾客会挂在那里永远不释放后面所有人都会被拖住。P(barber)这一句是顾客真正被服务的入口。它和理发师的V(barber)一一配对谁先执行谁后执行都不影响正确性——如果顾客先到他就在这里等如果理发师的V先执行顾客的 P 会直接穿过。信号量的这种允许先 V 后 P的性质正是它能用来做同步的原因。3.3 用一张时序表把边界情况走一遍光看代码不够我建议你拿几种边界情况手动推一遍尤其是只有一个顾客等候区刚好坐满理发师正在忙时来一串顾客这三种。下表是我推演等候椅 N2顾客依次到达时的关键状态。时刻事件countcustomersbarber说明t1顾客 A 进店0→10→10A 占位并唤醒理发师t2理发师被唤醒移走 A1→01→00→1A 得到招呼坐上理发椅t3顾客 B 进店0→10→10B 占位理发师正在忙t4顾客 C 进店1→21→20C 占到第二个位置t5顾客 D 进店220D 发现满员直接离开t6理发师理完 A移走 B2→12→10→1B 得到招呼这张表最有价值的地方是 t5 那一行顾客 D 来的时候count正好等于 N2他走的是else分支什么都没通知就离开了没有影响任何信号量。很多人写错的地方就是让 D 也去做了V(customers)结果理发师被唤醒后count却是满的下一步count count - 1直接把数字减成了超出实际情况的值后续全部乱套。只有真正占到位置的顾客才有资格去唤醒理发师这句话就是这张表的结论。4. 真正让人掉坑的三处细节顺序、位置与初值信号量的代码往往只有十几行但只要有一个 P 或 V 放错地方程序的行为就会从正确直接跳到死锁或静默错误。理发师问题里出错率高得离谱的就是下面这三类。我把它们和排查方法一起讲因为它们也是考试和面试里最爱追问的点。4.1 P 操作顺序一旦写反死锁立刻出现最经典的错误是把顾客进程写成先P(barber)再V(customers)或者把理发师的两句 P 顺序对调。我们来看理发师这一侧如果写成先P(mutex)再P(customers)结果就是前面说过的——理发师在没有顾客时会握着锁睡过去顾客永远拿不到锁去count两端互相等待经典死锁。判断一段 PV 代码会不会死锁有个简单的口诀资源的 P 放在互斥的 P 之前。凡是我在等别人给我东西的等待都应该先于我要抢那个保护共享数据的锁。理发师等顾客顾客并不等理发师的锁所以P(customers)必须在P(mutex)外面、前面。这条口诀同样适用于生产者-消费者等问题是通用经验。注意P 操作顺序错误的死锁往往不会在程序刚启动时就暴露而是在某种特定到达顺序下才复现。所以跑一次没崩不代表代码是对的一定要有意构造边界情况去压。4.2 count 的判断必须待在 mutex 的保护圈里第二个高频错误是把是否满员的判断搬到P(mutex)之外。有人会觉得判断又不修改数据读一下而已放外面应该没关系。这种想法在并发下是危险的判断动作读的是count而count随时可能被别的进程改写。如果你在锁外判断完进锁后再count那么这段时间里count可能已经从 N-1 变成 N你的有空位结论早已失效结果是等候区被塞进超过 N 个人。正确的做法是判断和修改连在一起整体进临界区。你可以把它理解成只要你的逻辑依赖某个共享变量的值来决定下一步做什么这个判断就必须和它依赖的那次读取一起被保护起来。这条原则比保护写操作更严格也更接近并发的本质。排查这个问题有个笨办法但很有效把临界区里的所有语句都标出来然后问自己如果在我判断之后、修改之前别的进程插进来改了count会怎样。如果答案是会出错那说明这段必须待在锁里如果答案是无所谓那才可以考虑挪出去。用这个方法扫一遍绝大多数位置错误都能揪出来。4.3 信号量初值错一个程序行为就全变信号量初值看着是小事实际上它直接决定了程序在初始状态下的行为。理发师问题里mutex初值是 1同一时刻只允许一个进程进入临界区customers初值是 0开店时没有顾客barber初值也是 0没有顾客在等理发师。这三个初值改错任何一个都会出事。假如把customers初值写成 1那么程序一启动理发师的第一句P(customers)就能直接穿过他会以为已经有个顾客在等了于是抢锁、把count减到 -1、V(barber)唤醒一个根本不存在的顾客然后开始对着空气理发。接着count变成了负数后续所有判断都错。这种错误的特点是——程序不崩溃但行为诡异比直接死锁更难查。假如把barber初值写成 1那么第一个顾客在P(barber)时不会等待他会直接跳过去理发和理发师的节奏对不上。所以初值这件事正确的记法不是背数字而是回到语义这个信号量在系统刚启动、所有进程都还没跑时应该处于什么状态。mutex初始没有进程持锁所以是 1customers初始没有顾客所以是 0barber初始没有可招呼的对象所以是 0。想清楚语义初值自然就出来了。5. 从理发师问题抽象出 PV 操作的通用解题框架理清楚这一个问题之后我建议你把它往上抽象一层因为考试或者实际工作中你会遇到一堆换了个马甲的同类问题图书馆座位、停车场车位、生产者往缓冲区放数据……它们的骨架其实是一样的。掌握了这个骨架你面对新问题时就不需要从零推导。5.1 资源计数 唤醒握手的两段式结构几乎所有这类同步问题都可以拆成两块。第一块是资源计数有一个共享的状态变量记录现在还剩多少可用的东西空座位、空缓冲区、可读数据它必须被互斥保护判断和修改要在同一个临界区里完成。第二块是唤醒握手等待方和通知方通过一对信号量建立我等你我通知你的关系等待方 P、通知方 V方向必须严格对应。理发师问题里count和mutex就是资源计数那块customers和barber这一对就是唤醒握手那块。你以后遇到任何同步题先问自己这里有没有一个共享的计数需要保护谁在等谁通知的方向是从哪到哪把这两个问题回答了代码框架基本就搭起来了。这个方法比死记硬背每种问题的标准答案要靠谱得多因为问题的变体可以无穷多但骨架就那么几根。还有一个小技巧画出等待图。把每个进程画成一个节点如果 A 会等 B 的通知就从 A 画一条指向 B 的箭头。正确的解法里箭头应该是单向或者有明确的传递顺序的如果画出来发现出现了环A 等 B、B 又等 A且都握着对方需要的锁那基本就是死锁的信号。这个图不一定画在纸上脑子里过一遍就够用。5.2 拿它和生产者-消费者、读者-写者放在一起看把理发师问题和两个最经典的同步问题对比能帮你看出共性和差异。生产者-消费者问题里缓冲区是一个共享的资源池生产者等空位、消费者等数据用两个信号量分别表示空位数和数据数再配一个mutex。你会发现理发师问题的资源计数块和它几乎是同构的只是资源从缓冲区槽位变成了等候椅。读者-写者问题的重心则在互斥的粒度上它要处理的是多个读者可以同时进但写者必须独占这种更细的规则信号量的用法更偏向控制并发度。理发师问题没有这种多读共存的需求所以它的互斥是简单的二元锁。用一张表对比会更清楚问题资源计数信号量同步握手信号量互斥信号量核心难点理发师问题无独立计数信号量用 count mutexcustomers、barbermutex唤醒时机与计数一致生产者-消费者empty、full同左mutex缓冲区空满判断读者-写者读者计数写者优先用信号量mutex并发度控制看这张表你会发现理发师问题其实把资源计数和互斥压在了一个mutex里这也是它常被拿来当考试题的原因——它更考验你对临界区的理解而不是单纯套信号量。5.3 常见变体题的破题思路这类题最常见的变化是改 N 的值、加一个理发师、或者改成顾客理完发还要付钱。面对变体别急着改代码先做两件事。第一确认资源数量有没有变——比如把等候椅从 N 改成 1那么count的判断上界就是 1其他不动如果改成两个理发师你就需要重新思考barber这个信号量的语义因为现在可能同时有两位顾客被招呼。第二确认有没有新增的先后依赖。如果题目要求顾客理完发必须付钱后才能离开那就等于在原来流程后面又接了一段同步你需要新增一对信号量表达理发师等付款和顾客付款通知思路和第 5.1 节说的握手完全一致。万变不离其宗先找新资源再找新依赖这是我认为最靠得住的破题顺序。切忌一上来就凭印象改 P/V那样改出来往往是看着像但跑不通。6. 把代码跑起来验证互斥与同步的实操方法纸上推演再多也不如让程序真跑一遍来得踏实。理发师问题虽然是教学模型但用一门支持线程和信号量的语言实现出来能帮你看清很多纸上看不到的时序。下面讲的是一种可复现的实现思路不绑定具体语言重点是思路和验证手段。6.1 用语言级信号量写一个可运行的模拟在实现层面你需要三样东西一个能充当信号量的对象带 P/wait 和 V/signal、一组线程/进程、以及一个打印日志的手段。伪代码层面它就是这样mutex Semaphore(1) customers Semaphore(0) barber Semaphore(0) count 0 function barber_thread(): while true: customers.wait() // 没顾客就睡 mutex.wait() count count - 1 barber.signal() // 招呼顾客 mutex.wait() 替换为 mutex.signal() // 释放锁 log(理发师开始服务) sleep(随机时长) // 模拟理发耗时 log(理发师服务结束) function customer_thread(id): mutex.wait() if count CHAIRS: count count 1 customers.signal() mutex.signal() barber.wait() log(顾客 %d 正在理发 % id) else: mutex.signal() log(顾客 %d 没位置离开 % id)上面这段伪代码里我把理发师释放锁那句写成了mutex.signal()前面标注的地方是笔误提醒实际就是释放锁。真正写代码时注意几个细节理发耗时用随机 sleep 来模拟能制造出不同的到达交错顾客的数量要设得比等候椅多才能触发满员离开的分支日志里一定要带上时间戳和进程标识否则并发日志交织在一起会看不懂。6.2 打印时序日志来验证而不是靠眼睛盯代码跑起来之后最有价值的输出是日志。我建议每条关键动作都打一行日志格式大致是时间戳 [进程名] 动作count当前值。跑完之后把日志按时间排好逐行检查三件事第一count的值有没有始终落在 0 到 N 之间第二每一次理发师开始服务之前是不是都有一条对应的顾客占位第三走离开分支的顾客有没有留下任何多余的通知动作。这三条检查通过基本可以认为你的互斥和同步是对的。反过来如果日志里出现count为负数那多半是初值或者唤醒时机错了如果出现两个顾客同时打印正在理发却没有对应的理发师日志那就是同步握手出了问题。用日志验证并发程序比用 IDE 单步调试有效得多因为单步会破坏真实的时间交错你看到的执行顺序已经被人为干预了。为了更有说服力我还习惯刻意构造几组到达顺序让 5 个顾客几乎同时来测满员与竞态让顾客间隔较均匀地来测正常流转让一个顾客在理发师刚开始服务时到达测边界。三组都稳定通过代码才敢说靠谱。6.3 调试并发问题时我常用的几个手段最后分享几个我在实际调试这类程序时用着顺手的手段都是纸面推演给不了的。第一招是降低并发度把顾客数量设成 2、等候椅设成 1让所有可能的交错都能被日志穷举出来先在小规模下确认逻辑再放大。小规模下死锁更容易定位因为涉及的交互少。第二招是在临界区入口和出口加计数器记录同一时刻进入临界区的进程数。正常情况下这个数最多是 1因为mutex初值为 1如果日志里出现 2那就说明你的互斥根本没生效可能是某处忘了 P 或者 V 放错了位置。这个手段对排查静默错误特别有用。第三招是故意把耗时操作调长。把理发时间从几毫秒改成几秒顾客的到达间隔也拉长那些原本一闪而过的时序问题会被放大成肉眼可见的卡住或者顺序错乱定位起来容易很多。调完确认逻辑没问题再把时间改回正常值。我个人在实现这类问题的体会是理发师问题的难点从来不在那十几行 PV 代码本身而在于你有没有真正想清楚谁在等谁以及临界区里到底该放哪几句话。把这两个问题用日志和边界用例验证过一遍你就不会再怕它也不会再被那些换汤不换药的变体题难住。 理发师问题：信号量PV操作与进程同步互斥实战
1. 一个看着简单的经典同步问题为什么能卡住大部分人如果你在操作系统课上第一次听到理发师问题多半会觉得它没什么难度——不就是把顾客和理发师用信号量串起来嘛。可真到了要动手把它写成一个能跑的进程模型时很多人会卡在同一类地方顾客明明看到有空座位理发师却继续睡觉或者等候区还没坐满程序却莫名卡死。这个问题在每学期的进程同步章节里反复出现不是因为概念多复杂而是因为它把进程PV操作唤醒与阻塞这几个词背后的时序细节全压缩进了一个极小的场景里。先把场景摆清楚这也是所有推导的地基。一间理发店配置固定1 把理发椅、1 位理发师、N 把供顾客等候的椅子N 通常大于 0。规则有几条每一条都对应着程序里的一段逻辑没有顾客时理发师就坐在椅子上睡觉顾客进门时如果等候椅还有空位他就坐下等待同时如果发现理发师在睡觉要负责把他叫醒如果等候椅已经坐满这位顾客只能直接走人不能站在店里干等理发师每次只服务一位顾客服务完顺手把这位顾客从等候区移走再看还有没有下一位。这个描述里的每一句话在并发代码里都不是自然而然成立的。比如把理发师叫醒是一个跨进程的动作顾客进程必须想办法通知理发师进程从阻塞中恢复等候椅还有没有空位是一个共享状态的判断必须有互斥保护否则两个顾客同时看到最后一个空位就会发生计数错误。所以理发师问题的真正看点是它同时包含了互斥多个顾客/理发师竞争访问等候区计数和同步顾客与理发师之间的等待与唤醒两种机制而且这两种机制用同一套 PV 操作表达出来。适合读这篇内容的人大致有三类正在啃操作系统进程同步这一章的学生准备考试、被写出理发师问题的 PV 操作这道题反复折磨的备考者以及工作里偶尔要写点并发控制、想把信号量那套思维用顺手的人。不管你是哪一类我建议都别停留在能背出那几行伪代码的层面因为真正决定你答对还是答错的往往是某两个 V 操作的先后顺序——而这恰恰是背不出来的东西。1.1 三个角色、两种等待别把它们混成一锅在写任何代码之前先把场景里的角色和他们的状态列清楚这一步能省掉后面一大半的调试时间。角色其实只有三类顾客进程可能有很多个、理发师进程通常只有一个、以及被它们共享的那几个变量等候区的计数、几个信号量。等待在这个场景里有两种性质完全不同很多人一上来就把它们混为一谈。第一种是理发师等待顾客理发师无事可做主动进入阻塞状态直到有顾客到来才被唤醒这是一种服务方等资源的等待。第二种是顾客等待理发师顾客已经坐进等候区或理发椅但理发师还在忙他必须等理发师空出手来这是一种请求方等响应的等待。这两种等待的触发条件和唤醒条件正好是交叉的一个用 P 阻塞、另一个用 V 唤醒方向一旦搞反程序要么全体睡死要么空转。还有一点容易被忽略顾客走人这个动作是没有等待的。他判断等候区满了直接离开不进入任何阻塞队列。这意味着顾客进程里存在一个提前退出的分支这个分支同样要释放已经拿到的互斥锁否则下一个顾客会永远卡在锁上。你看光是角色和状态这一层就已经藏了好几个坑点。1.2 为什么先判断再行动的直觉写法一定出问题把理发店规则直接翻译成自然语言式的代码很多人的第一反应是这样顾客进店看一眼等候区如果没满就坐下顺便叫醒理发师如果满了就走。理发师则循环如果没顾客就睡有顾客就理发。这段逻辑在单线程的世界里完美无缺但在并发世界里它是错的原因就藏在看一眼这个动作里。看一眼等候区和坐下这两个动作之间必须没有其他进程能插进来修改等候区。假设现在的空位数是 1顾客 A 和顾客 B 几乎同时执行这段逻辑A 看到有空位还没来得及把计数加一B 也看到了那个同样存在的空位于是两个人都以为自己有位置计数就被写成了不该有的值或者等候区里被塞进了超额的顾客。这就是典型的竞态条件也是为什么要引入一个互斥信号量来保护那段判断 修改的临界区。更隐蔽的问题出在唤醒上。理发师睡觉本质上是阻塞在一个信号量上顾客要唤醒他必须对正确的信号量做 V 操作。如果你让顾客在没真正占到座位的情况下就去唤醒理发师那理发师醒来会面对一个空荡荡的等候区直接导致后续的计数和等待错乱。想清楚这一点你就会明白唤醒动作必须和确实占到一个位置这件事绑定在一起并且发生在临界区保护之下。这也是接下来所有推导的核心线索。2. 把理发店场景翻译成信号量谁该被唤醒谁该去睡眠从生活规则到信号量代码中间的桥梁是找共享资源和定信号量职责。很多人写完代码自己都说不清每个信号量到底代表什么于是遇到问题只能瞎改。我习惯的做法是先把所有需要保护的共享变量列出来再决定用几个信号量每个信号量负责通知哪一方。在这个场景里共享状态其实很少但每一个都很关键。等候区的顾客数量是一个共享整数我们用count表示注意它统计的是等候区等待的人不含正在理发椅上那位。这个变量会被所有顾客读、被顾客和理发师写所以必须有一个互斥信号量保护它我们叫它mutex。除了共享变量还有两组通知关系要用信号量表达一组是顾客来了要通知理发师有人等着别睡了另一组是理发师准备好了要通知某位顾客轮到你了过来坐。这两组通知方向相反所以需要两个独立的信号量customers负责从顾客到理发师的通知barber负责从理发师到顾客的通知。名字看着朴素但你只要记住它们的指向就不会用错。2.1 customers 和 barber 这两个信号量各管一件事customers这个信号量本质上是一个待服务顾客的计数器。顾客成功占到一个等候位置后对customers做 V 操作相当于在告诉理发师现在至少有一个人等着了你该醒了。理发师在循环开头对customers做 P 操作如果没有顾客P 操作会把他阻塞这就是睡觉一旦有顾客 V 过他就能从 P 里返回相当于被叫醒。它的初值应该是 0因为开店时没有顾客在等。barber这个信号量方向正好相反它表达的是理发师是否已经招呼你去坐理发椅。顾客做完V(customers)之后要对barber做 P 操作意思是我已经占好位了现在等理发师叫我。理发师每处理完一位顾客、把等候区的人移走之后对barber做 V 操作唤醒一位正在等的顾客。它的初值也是 0因为一开始没有顾客能等到理发师。这里有个特别容易记混的点customers是顾客 V、理发师 Pbarber是理发师 V、顾客 P。你可以用一句话记住——谁被唤醒谁就在那个信号量上 P。理发师被顾客唤醒所以理发师在customers上 P顾客被理发师唤醒所以顾客在barber上 P。把这句话刻在脑子里后面写代码时基本不会把 V 和 P 安反。2.2 mutex 保护的从来不是理发椅而是 count 这个数我见过不少人在讲解时会说用 mutex 保护理发椅这个说法很误导。理发椅本身在这一版模型里并没有争用——同一时刻只有一个人能坐上去这是由barber信号量的等待机制保证的不需要 mutex 额外保护。真正需要保护的是count这个共享计数以及围绕它做的判断是否满员 修改计数这一整段操作。为什么这段必须原子回到上一节说的竞态两位顾客同时判断是否还有空位如果判断和加法之间被别人插进来就可能出现超员或者幻影空位。把这段放进P(mutex)和V(mutex)之间就等于给等候区计数上了一把锁任何时刻只有一个进程能读写它。还有一处特别容易被忽略理发师减少count的那段代码同样要在 mutex 里。因为理发师把一个顾客从等候区移到理发椅这个动作会改变count如果不同步保护顾客读到的就是旧值可能出现计数对不上的情况。所以mutex是顾客和理发师共同遵守的规则不是只给顾客用的。提示判断count是否满员这一句一定要写在P(mutex)之后、V(mutex)之前。任何把判断挪到锁外的写法都会让整个互斥保护形同虚设。2.3 从顾客进门到理发椅空出来的完整状态流转把信号量职责定清楚后整个流程就可以顺下来了。理发师进程的主循环是先P(customers)等待顾客没顾客就睡醒来后拿mutex把count减一这位顾客已经从等候区移到理发椅再对barber做 V 唤醒那位顾客释放mutex然后开始理发理完继续下一轮循环。顾客进程则是一个判断分支进门先P(mutex)如果count小于等候椅数量 N就说明有空位把count加一接着对customers做 V告诉理发师有人来了释放mutex然后P(barber)等待被招呼去理发椅如果count已经等于 N说明满了直接释放mutex然后离开不做任何等待。这一进一出的对称结构是整个问题的骨架。你会注意到真正被唤醒去理发的顾客不是那个刚进门的顾客而是理发师从等候区移走的那一位。这一点在很多讲解里被含糊带过导致有人以为顾客一进门就直接被理发从而写错了等待位置。理清这个流转第 3 节的逐行拆解就会顺畅很多。3. 逐行拆经典代码每一句 P/V 背后的时序推演前面讲的是应该怎么想这一节讲代码到底长什么样为什么每一句都长这样。我把信号量初始化和两个进程的代码完整摆出来然后逐句解释其意图。这里的 P 操作等价于 wait/down表示申请资源、可能阻塞V 操作等价于 signal/up表示释放资源、可能唤醒等待者。// 共享变量与信号量初始化 semaphore mutex 1; // 保护 count 的互斥锁 semaphore customers 0; // 等候的顾客数理发师等待它 semaphore barber 0; // 理发师就绪信号顾客等待它 int count 0; // 等候区当前人数不含理发椅上的人 const int CHAIRS N; // 等候椅数量 // 理发师进程 while (true) { P(customers); // 没有顾客就在这里睡有顾客则醒来 P(mutex); // 进入临界区 count count - 1; // 一位顾客离开等候区坐上理发椅 V(barber); // 招呼这位顾客轮到你了 V(mutex); // 退出临界区 cut_hair(); // 理发耗时操作不占锁 } // 顾客进程每一个进店的顾客都执行这一段 P(mutex); // 进入临界区准备检查空位 if (count CHAIRS) { count count 1; // 占到一个等候位 V(customers); // 通知理发师有顾客在等 V(mutex); // 退出临界区 P(barber); // 等待理发师招呼去坐理发椅 get_haircut(); } else { V(mutex); // 没位置释放锁后直接离开 }3.1 理发师主循环为什么必须是先 P 再抢锁理发师循环的第一句是P(customers)而不是先抢mutex。这个顺序不是随意安排的。如果理发师先拿mutex再等顾客那么当他没有顾客要服务时会阻塞在P(customers)上却还握着mutex此时任何顾客进门都无法获得锁去修改count整个系统直接僵住。所以等待资源的 P 操作必须放在抢互斥锁之前让它阻塞时手里不持有任何锁。第二句进来才P(mutex)这时理发师已经确定确实有顾客存在了他需要做的只是把这个顾客从等候区划掉也就是count count - 1。紧接着V(barber)唤醒那位等待的顾客再V(mutex)释放锁。这里V(barber)放在V(mutex)之前是没问题的因为顾客在barber上的等待和mutex无关唤醒后顾客会自己去排队拿mutex。cut_hair()放在临界区之外是刻意的。理发是个耗时动作如果把它放进mutex里那么整个理发过程中没有第二个进程能碰count等候区的管理就彻底停摆了。耗时的、不需要保护共享数据的操作一律挪出临界区这是写并发代码的一条通用准则不只是理发师问题。3.2 顾客进程的 if-else 藏着两个完全不同的出口顾客进程从P(mutex)开始这段是它的临界区入口。进来第一件事就是判断count CHAIRS也就是还有没有空位。走if分支时顾客占位成功count加一V(customers)唤醒理发师然后释放mutex最后P(barber)等理发师招呼。注意这里的顺序——先 V(customers) 再 V(mutex)看似无所谓但其实有讲究。如果先V(mutex)再V(customers)在两者之间理发师可能已经抢到锁、把count减掉了紧接着才收到customers的通知逻辑上虽然还能跑通但时序会变得不那么直观。放在锁内先通知能保证占位和通知这两件事对外表现为一个原子动作。走else分支时顾客发现满员唯一要做的是V(mutex)把锁还回去然后头也不回地离开。这个分支里绝不能出现任何 P 操作否则这位本该走人的顾客会挂在那里永远不释放后面所有人都会被拖住。P(barber)这一句是顾客真正被服务的入口。它和理发师的V(barber)一一配对谁先执行谁后执行都不影响正确性——如果顾客先到他就在这里等如果理发师的V先执行顾客的 P 会直接穿过。信号量的这种允许先 V 后 P的性质正是它能用来做同步的原因。3.3 用一张时序表把边界情况走一遍光看代码不够我建议你拿几种边界情况手动推一遍尤其是只有一个顾客等候区刚好坐满理发师正在忙时来一串顾客这三种。下表是我推演等候椅 N2顾客依次到达时的关键状态。时刻事件countcustomersbarber说明t1顾客 A 进店0→10→10A 占位并唤醒理发师t2理发师被唤醒移走 A1→01→00→1A 得到招呼坐上理发椅t3顾客 B 进店0→10→10B 占位理发师正在忙t4顾客 C 进店1→21→20C 占到第二个位置t5顾客 D 进店220D 发现满员直接离开t6理发师理完 A移走 B2→12→10→1B 得到招呼这张表最有价值的地方是 t5 那一行顾客 D 来的时候count正好等于 N2他走的是else分支什么都没通知就离开了没有影响任何信号量。很多人写错的地方就是让 D 也去做了V(customers)结果理发师被唤醒后count却是满的下一步count count - 1直接把数字减成了超出实际情况的值后续全部乱套。只有真正占到位置的顾客才有资格去唤醒理发师这句话就是这张表的结论。4. 真正让人掉坑的三处细节顺序、位置与初值信号量的代码往往只有十几行但只要有一个 P 或 V 放错地方程序的行为就会从正确直接跳到死锁或静默错误。理发师问题里出错率高得离谱的就是下面这三类。我把它们和排查方法一起讲因为它们也是考试和面试里最爱追问的点。4.1 P 操作顺序一旦写反死锁立刻出现最经典的错误是把顾客进程写成先P(barber)再V(customers)或者把理发师的两句 P 顺序对调。我们来看理发师这一侧如果写成先P(mutex)再P(customers)结果就是前面说过的——理发师在没有顾客时会握着锁睡过去顾客永远拿不到锁去count两端互相等待经典死锁。判断一段 PV 代码会不会死锁有个简单的口诀资源的 P 放在互斥的 P 之前。凡是我在等别人给我东西的等待都应该先于我要抢那个保护共享数据的锁。理发师等顾客顾客并不等理发师的锁所以P(customers)必须在P(mutex)外面、前面。这条口诀同样适用于生产者-消费者等问题是通用经验。注意P 操作顺序错误的死锁往往不会在程序刚启动时就暴露而是在某种特定到达顺序下才复现。所以跑一次没崩不代表代码是对的一定要有意构造边界情况去压。4.2 count 的判断必须待在 mutex 的保护圈里第二个高频错误是把是否满员的判断搬到P(mutex)之外。有人会觉得判断又不修改数据读一下而已放外面应该没关系。这种想法在并发下是危险的判断动作读的是count而count随时可能被别的进程改写。如果你在锁外判断完进锁后再count那么这段时间里count可能已经从 N-1 变成 N你的有空位结论早已失效结果是等候区被塞进超过 N 个人。正确的做法是判断和修改连在一起整体进临界区。你可以把它理解成只要你的逻辑依赖某个共享变量的值来决定下一步做什么这个判断就必须和它依赖的那次读取一起被保护起来。这条原则比保护写操作更严格也更接近并发的本质。排查这个问题有个笨办法但很有效把临界区里的所有语句都标出来然后问自己如果在我判断之后、修改之前别的进程插进来改了count会怎样。如果答案是会出错那说明这段必须待在锁里如果答案是无所谓那才可以考虑挪出去。用这个方法扫一遍绝大多数位置错误都能揪出来。4.3 信号量初值错一个程序行为就全变信号量初值看着是小事实际上它直接决定了程序在初始状态下的行为。理发师问题里mutex初值是 1同一时刻只允许一个进程进入临界区customers初值是 0开店时没有顾客barber初值也是 0没有顾客在等理发师。这三个初值改错任何一个都会出事。假如把customers初值写成 1那么程序一启动理发师的第一句P(customers)就能直接穿过他会以为已经有个顾客在等了于是抢锁、把count减到 -1、V(barber)唤醒一个根本不存在的顾客然后开始对着空气理发。接着count变成了负数后续所有判断都错。这种错误的特点是——程序不崩溃但行为诡异比直接死锁更难查。假如把barber初值写成 1那么第一个顾客在P(barber)时不会等待他会直接跳过去理发和理发师的节奏对不上。所以初值这件事正确的记法不是背数字而是回到语义这个信号量在系统刚启动、所有进程都还没跑时应该处于什么状态。mutex初始没有进程持锁所以是 1customers初始没有顾客所以是 0barber初始没有可招呼的对象所以是 0。想清楚语义初值自然就出来了。5. 从理发师问题抽象出 PV 操作的通用解题框架理清楚这一个问题之后我建议你把它往上抽象一层因为考试或者实际工作中你会遇到一堆换了个马甲的同类问题图书馆座位、停车场车位、生产者往缓冲区放数据……它们的骨架其实是一样的。掌握了这个骨架你面对新问题时就不需要从零推导。5.1 资源计数 唤醒握手的两段式结构几乎所有这类同步问题都可以拆成两块。第一块是资源计数有一个共享的状态变量记录现在还剩多少可用的东西空座位、空缓冲区、可读数据它必须被互斥保护判断和修改要在同一个临界区里完成。第二块是唤醒握手等待方和通知方通过一对信号量建立我等你我通知你的关系等待方 P、通知方 V方向必须严格对应。理发师问题里count和mutex就是资源计数那块customers和barber这一对就是唤醒握手那块。你以后遇到任何同步题先问自己这里有没有一个共享的计数需要保护谁在等谁通知的方向是从哪到哪把这两个问题回答了代码框架基本就搭起来了。这个方法比死记硬背每种问题的标准答案要靠谱得多因为问题的变体可以无穷多但骨架就那么几根。还有一个小技巧画出等待图。把每个进程画成一个节点如果 A 会等 B 的通知就从 A 画一条指向 B 的箭头。正确的解法里箭头应该是单向或者有明确的传递顺序的如果画出来发现出现了环A 等 B、B 又等 A且都握着对方需要的锁那基本就是死锁的信号。这个图不一定画在纸上脑子里过一遍就够用。5.2 拿它和生产者-消费者、读者-写者放在一起看把理发师问题和两个最经典的同步问题对比能帮你看出共性和差异。生产者-消费者问题里缓冲区是一个共享的资源池生产者等空位、消费者等数据用两个信号量分别表示空位数和数据数再配一个mutex。你会发现理发师问题的资源计数块和它几乎是同构的只是资源从缓冲区槽位变成了等候椅。读者-写者问题的重心则在互斥的粒度上它要处理的是多个读者可以同时进但写者必须独占这种更细的规则信号量的用法更偏向控制并发度。理发师问题没有这种多读共存的需求所以它的互斥是简单的二元锁。用一张表对比会更清楚问题资源计数信号量同步握手信号量互斥信号量核心难点理发师问题无独立计数信号量用 count mutexcustomers、barbermutex唤醒时机与计数一致生产者-消费者empty、full同左mutex缓冲区空满判断读者-写者读者计数写者优先用信号量mutex并发度控制看这张表你会发现理发师问题其实把资源计数和互斥压在了一个mutex里这也是它常被拿来当考试题的原因——它更考验你对临界区的理解而不是单纯套信号量。5.3 常见变体题的破题思路这类题最常见的变化是改 N 的值、加一个理发师、或者改成顾客理完发还要付钱。面对变体别急着改代码先做两件事。第一确认资源数量有没有变——比如把等候椅从 N 改成 1那么count的判断上界就是 1其他不动如果改成两个理发师你就需要重新思考barber这个信号量的语义因为现在可能同时有两位顾客被招呼。第二确认有没有新增的先后依赖。如果题目要求顾客理完发必须付钱后才能离开那就等于在原来流程后面又接了一段同步你需要新增一对信号量表达理发师等付款和顾客付款通知思路和第 5.1 节说的握手完全一致。万变不离其宗先找新资源再找新依赖这是我认为最靠得住的破题顺序。切忌一上来就凭印象改 P/V那样改出来往往是看着像但跑不通。6. 把代码跑起来验证互斥与同步的实操方法纸上推演再多也不如让程序真跑一遍来得踏实。理发师问题虽然是教学模型但用一门支持线程和信号量的语言实现出来能帮你看清很多纸上看不到的时序。下面讲的是一种可复现的实现思路不绑定具体语言重点是思路和验证手段。6.1 用语言级信号量写一个可运行的模拟在实现层面你需要三样东西一个能充当信号量的对象带 P/wait 和 V/signal、一组线程/进程、以及一个打印日志的手段。伪代码层面它就是这样mutex Semaphore(1) customers Semaphore(0) barber Semaphore(0) count 0 function barber_thread(): while true: customers.wait() // 没顾客就睡 mutex.wait() count count - 1 barber.signal() // 招呼顾客 mutex.wait() 替换为 mutex.signal() // 释放锁 log(理发师开始服务) sleep(随机时长) // 模拟理发耗时 log(理发师服务结束) function customer_thread(id): mutex.wait() if count CHAIRS: count count 1 customers.signal() mutex.signal() barber.wait() log(顾客 %d 正在理发 % id) else: mutex.signal() log(顾客 %d 没位置离开 % id)上面这段伪代码里我把理发师释放锁那句写成了mutex.signal()前面标注的地方是笔误提醒实际就是释放锁。真正写代码时注意几个细节理发耗时用随机 sleep 来模拟能制造出不同的到达交错顾客的数量要设得比等候椅多才能触发满员离开的分支日志里一定要带上时间戳和进程标识否则并发日志交织在一起会看不懂。6.2 打印时序日志来验证而不是靠眼睛盯代码跑起来之后最有价值的输出是日志。我建议每条关键动作都打一行日志格式大致是时间戳 [进程名] 动作count当前值。跑完之后把日志按时间排好逐行检查三件事第一count的值有没有始终落在 0 到 N 之间第二每一次理发师开始服务之前是不是都有一条对应的顾客占位第三走离开分支的顾客有没有留下任何多余的通知动作。这三条检查通过基本可以认为你的互斥和同步是对的。反过来如果日志里出现count为负数那多半是初值或者唤醒时机错了如果出现两个顾客同时打印正在理发却没有对应的理发师日志那就是同步握手出了问题。用日志验证并发程序比用 IDE 单步调试有效得多因为单步会破坏真实的时间交错你看到的执行顺序已经被人为干预了。为了更有说服力我还习惯刻意构造几组到达顺序让 5 个顾客几乎同时来测满员与竞态让顾客间隔较均匀地来测正常流转让一个顾客在理发师刚开始服务时到达测边界。三组都稳定通过代码才敢说靠谱。6.3 调试并发问题时我常用的几个手段最后分享几个我在实际调试这类程序时用着顺手的手段都是纸面推演给不了的。第一招是降低并发度把顾客数量设成 2、等候椅设成 1让所有可能的交错都能被日志穷举出来先在小规模下确认逻辑再放大。小规模下死锁更容易定位因为涉及的交互少。第二招是在临界区入口和出口加计数器记录同一时刻进入临界区的进程数。正常情况下这个数最多是 1因为mutex初值为 1如果日志里出现 2那就说明你的互斥根本没生效可能是某处忘了 P 或者 V 放错了位置。这个手段对排查静默错误特别有用。第三招是故意把耗时操作调长。把理发时间从几毫秒改成几秒顾客的到达间隔也拉长那些原本一闪而过的时序问题会被放大成肉眼可见的卡住或者顺序错乱定位起来容易很多。调完确认逻辑没问题再把时间改回正常值。我个人在实现这类问题的体会是理发师问题的难点从来不在那十几行 PV 代码本身而在于你有没有真正想清楚谁在等谁以及临界区里到底该放哪几句话。把这两个问题用日志和边界用例验证过一遍你就不会再怕它也不会再被那些换汤不换药的变体题难住。