2.3.5_1_1 生产者-消费者问题

新困难：满缓冲时必须先等 empty，若先占 mutex 会把消费者堵死

容量2的缓冲区，信号量初值 empty=2, full=0, mutex=1。生产顺序A、B、C，消费者在C尝试阻塞后取走一个元素。正确生产次序是 P(empty)→P(mutex)→放入→V(mutex)→V(full)；消费者对称地先P(full)。

from collections import deque

class BoundedBuffer:
    def __init__(self,n): self.n=n; self.empty=n; self.full=0; self.mutex=1; self.q=deque()
    def invariant(self):
        assert self.empty+self.full==self.n and self.full==len(self.q) and self.mutex==1
    def try_produce(self,item):
        if self.empty==0: return False
        self.empty-=1; self.mutex-=1; assert self.mutex==0
        self.q.append(item)
        self.mutex+=1; self.full+=1; self.invariant(); return True
    def try_consume(self):
        if self.full==0: return None
        self.full-=1; self.mutex-=1; assert self.mutex==0
        item=self.q.popleft()
        self.mutex+=1; self.empty+=1; self.invariant(); return item

b=BoundedBuffer(2)
assert b.try_produce('A') and b.try_produce('B')
assert not b.try_produce('C') and list(b.q)==['A','B']
assert b.try_consume()=='A'
assert b.try_produce('C') and list(b.q)==['B','C']
assert (b.empty,b.full,b.mutex)==(0,2,1)

陪走：放A后 (empty,full)=(1,1)，放B后 (0,2)；C执行P(empty)时阻塞，尚未取得mutex。消费者仍能P(full)、取得mutex、取A并V(empty)，于是C被唤醒后放入，最终缓冲为B、C。若C先P(mutex)再P(empty)，它会拿着mutex阻塞；消费者虽看到full>0，却无法取得mutex取走元素，形成死锁。

依据：在每个完整操作边界，empty+full=N 且 full 等于已占槽数；mutex保证修改队列的临界区最多一个执行者。容量信号量必须在互斥锁外等待，使可能解除条件的对方仍能进入临界区，这是次序依据。

每次入队出队时间 O(1)，缓冲空间 O(N)。错误反馈：mutex只保互斥，不能表达有货/有空位；P操作可能阻塞，不能当普通减法；等待资源时持有mutex会死锁；生产结束V(full)，不是V(empty)；真实阻塞信号量计数语义可能含负等待数，本课状态表采用非负可用数表示。

迁移答案：多生产者、多消费者仍共享同一组 empty/full/mutex，不应给每个线程各建容量计数；若缓冲无限，可去掉empty，但full与mutex仍需要。

桥接：错误的资源申请次序会死锁；下一课用检测算法说明多实例资源图中即使看见环，也不能立刻断言死锁。