原子广播（Atomic Broadcast）同步问题自研Pascal方案的正确性与效率问询

问题背景 #

我正在通过分析常见同步问题学习并发编程，当前尝试解决原子广播（Atomic Broadcast）问题：单生产者与N消费者模型，要求生产者将数据放入单元素缓冲区后，所有消费者必须都读取该数据，才能进入下一轮循环。以下是我用并发Pascal语法实现的解决方案：

Program AtomicBroadcast;

const
    N = ...;
    
var
    buffer : dataType;
    mutex, p_sem, c_sem : semaphore;
    counter : integer;

procedure Producer;
var
    data : dataType;
begin
    while true do
    begin
        data := ProduceData();
        
        wait(p_sem);
        
        buffer := data;
        
        signal(c_sem);
    end;
end;

procedure Consumer(id: integer);
begin
    while true do
    begin
        wait(mutex);
        counter := counter + 1;
        if (counter = 1) then
            wait(c_sem);
        signal(mutex);
        
        ConsumeData(buffer);
        
        wait(mutex);
        if (counter = N) then
        begin
            counter := 0;
            signal(p_sem);
        end;
        signal(mutex);
        
        
    end;
end;

{MAIN PROGRAM}
begin
    init(mutex, 1);
    init(p_sem, 1);
    init(c_sem, 0);
    
    counter := 0;
    
    cobegin
        Producer();
        Consumer(1);
        ...
        Consumer(N);
    coend;
end.

一、方案正确性分析 #

你的实现可以正常工作，不存在竞态条件、死锁或活锁问题，核心依据如下：

• 无竞态条件：共享变量counter的所有读写操作都被mutex严格保护，同一时间仅允许一个消费者访问，彻底避免了竞态。
• 无死锁：
  生产者仅会在p_sem上阻塞，而p_sem的唤醒由最后完成消费的消费者触发，不会出现无法唤醒的情况；
  消费者的两个临界区（入口计数、出口收尾）都正确释放mutex，不会持有互斥量阻塞其他消费者，也不会在持有mutex时等待其他信号量（第一个消费者等待c_sem时，其他消费者因mutex被持有无法进入入口临界区，不会形成循环等待）。
• 满足原子广播语义：只有第一个消费者通过wait(c_sem)确认生产者已写入数据后，后续消费者才能进入消费阶段；直到所有N个消费者完成消费，counter才会被重置并唤醒生产者，确保一轮数据被全量读取后才会启动下一轮生产。

二、潜在的效率问题 #

虽然方案正确，但存在以下可优化的效率瓶颈：

• 消费者串行化程度高：所有消费者必须依次获取mutex来递增counter，即便生产者已经写入数据，消费者也无法并行进入消费阶段，必须逐个通过临界区检查，当N较大时，会显著限制并发性能。
• 信号量唤醒的串行依赖：c_sem是单个信号量，生产者调用signal(c_sem)仅会唤醒一个等待的消费者（第一个进入入口临界区的实例），其他消费者必须等待该实例释放mutex后才能进入临界区，进一步加剧了串行等待的情况。
• 注：该方案不存在饥饿问题——假设调度策略公平，每个消费者都能依次获取mutex，不会出现长期无法进入临界区的情况。

内容的提问来源于stack exchange，提问作者Billy Lynch