图 1:本文封面,写者集齐三张「读完」票才能写下一次。
先说明属性:这是一篇经典题解析,题目出自本地历史面试资料,与任何公司的当前招聘无关。信号量题见过生产者-消费者的人不少,但这题的约束形状不一样:A 往缓冲区写数据,B、C、D 各读一次之后 A 才能再写。考点不是互斥,而是「多读者各读一次」的计数同步。
先把约束翻译成不变量。
题目拆开是三条铁律。第一,A 写新数据前,缓冲区里上一轮的数据必须已被 B、C、D 各自读过一遍——少一个都不行。第二,每个读者只能读到「自己这轮该读的」新数据,不能重复读旧数据,也不能跳过。第三,读者之间互不等待:B 读不读,不影响 C 读。第三条最容易漏,它意味着这不是一个「读者们抢一把锁」的互斥问题,而是写者对三个独立读者的同步计数问题。
信号量设计:角色与信号量一一对应。
回忆 P、V 语义:P 操作把信号量减一,减不动就阻塞等待;V 操作加一并唤醒等待者。按角色配信号量:
empty初值 1:缓冲区是否可写。A 每次写之前 P(empty),拿到「可写许可」。b、c、d初值 0:分别表示「有没有新数据给 B/C/D 读」。A 写完一次,对三个各做一次 V,相当于给每位读者各发一张「新数据到了」的票。done初值 0:累计读完次数。每个读者读完各做一次 V(done),交回一张「读完」票;A 写完、发完票之后,连续做三次 P(done),集齐三票才进入下一轮。
伪代码骨架:
写者 A: 读者 B(C、D 同构):
loop: loop:
P(empty) P(b) // 等属于自己的新数据
写缓冲区 读缓冲区
V(b); V(c); V(d) V(done) // 交回读完票
P(done); P(done); P(done)
V(empty)
验证三条不变量:A 的两次写之间,恰好隔着三次 V(done),第一条成立;读者只在收到自己的 V 之后才动手读,而 V(bcd) 只发生在新数据写完之后,第二条成立;读者各自的票互不共用,第三条成立。done 被消费三次后回到零,与下一轮自动对齐,不会串轮。
与生产者-消费者的差别要能说清。
经典生产者-消费者里,多个消费者竞争同一份资源,需要互斥锁保护缓冲区;本题读者之间不竞争——每个人都必须读到同一份数据,所以完全不需要互斥锁,只用计数信号量。另一个易错点是想用一个 full 信号量让三个读者都去 P:那样一份数据只有一张票,三个读者抢,必然有人读不到。考点本质上就是把「三个各一次」翻译成「三个独立信号量加一个计数到三的汇合」。
用模拟跑一遍验证。
用 Node.js 22.15.0 实现一组真实的 P/V 语义信号量,让四个异步进程按上述协议跑 5 轮,并检查「相邻两次写之间恰好三次读」「没有读到旧数据」(node pv.js):
class Sem {
constructor(v) { this.v = v; this.q = []; }
async P() { // 计数减一,不够就排队等
if (this.v > 0) { this.v--; return; }
await new Promise(res => this.q.push(res));
}
V() { // 计数加一,唤醒一个等待者
this.v++;
const w = this.q.shift();
if (w) { this.v--; w(); }
}
}
const empty = new Sem(1), b = new Sem(0), c = new Sem(0), d = new Sem(0), done = new Sem(0);
// 写者:P(empty) → 写 → V(b)V(c)V(d) → 连做三次 P(done) → V(empty)
// 读者:P(自己的信号量) → 读 → V(done)
实测输出:
事件序列(前 12 条): 写0 B读0 C读0 D读0 写1 B读1 C读1 D读1 写2 B读2 C读2 D读2
总事件数: 20 (应为 5 写 + 15 读 = 20)
约束违反次数: 0
5 轮共 20 个事件,写读严格交替,无一违反约束。
图 2:四个进程的伪代码、信号量状态条与三条不变量。
答题顺序建议。
先复述约束并点出「读者之间不竞争、无需互斥锁」,再亮信号量配置表(五个信号量、各自初值和含义),然后走一遍写者和读者的伪代码,最后用不变量收束:两次写之间必有三次 V(done)。面试官若追问「读者多到几十上百个怎么办」,可以顺势聊计数信号量加读写者变形。你做信号量题时有没有把「互斥」和「同步」混用踩过坑?欢迎交流。