使用二进制信号量实现Barrier(同步构造)

Question

屏障是一种同步构造，其中一组进程全局同步，即集合中的每个进程到达屏障并等待所有其他进程到达，然后所有进程离开屏障。设集合中的进程数为3，S是具有通常的P和V函数的二进制信号量。考虑下面的C语言实现的屏障，它的行号显示在左边。

void barrier (void) {    
    1: P(S);
    2: process_arrived++;
    3: V(S);
    4: while (process_arrived !=3);
    5: P(S);
    6: process_left++;
    7: if (process_left==3) 
       {
         8: process_arrived = 0;
         9: process_left = 0;
    10: }
    11: V(S);
 }

变量process_arrived和process_left在所有进程之间共享，并被初始化为零。在并发程序中，当三个进程需要全局同步时，它们都会调用屏障函数。

上面的实现可以工作吗？我认为如果连续使用两个屏障调用，可能会导致死锁，因为第一个进入屏障的进程不会等到process_arrived变为零才继续执行P(S)。

Answer 1

嗯..。限制为三个线程且仅限二进制信号量，我会尝试使用三个信号量A、B、C。A控制对process_arrived计数的访问，B和C供第一个和第二个线程等待。A初始化为1，B&C初始化为0。线程1得到A，因此阻止2&3进入。process_arrived上的开关导致线程1 inc process_arrived，释放A并等待B。线程2获得A，并且该开关导致它inc process_arrived，切换，因此释放A并等待C。线程3获得A，并且该开关使其发出信号B，信号C，将process_arrived设置为0，信号A，并继续。

线程1和2不能传递B和C，直到3向它们发出信号。当B/C由3发出信号时，1/2可以运行，但不能循环返回并进入屏障，直到3释放A，此时屏障处于正确的状态，可以再次充当屏障-A的计数为1，B和C的计数为零，process_arrived为零。

Answer 2

上面提到有3个过程。就让它成为P1，P2 & P3吧。每个进程都会到达障碍，即它完成了代码的第一部分。因此process_arrived = 3。现在假设P1继续执行并离开屏障并生成屏障。现在假设P1再次立即调用屏障函数。在这个阶段，process_arrived =4。P1现在等待。很快，P2离开了制造process_left=2的屏障，现在P3离开了制造process_left=3的屏障。"If“条件为真，现在process_arrived和process_left被重置为0。我们知道P1正在等待。在此阶段，假设P2调用了屏障函数，因此会执行process_arrived=1并等待。P3调用屏障函数，因此调用process_arrived=2。所有进程都已到达屏障，但自process_arrived=2以来，所有进程都继续等待。因此出现了死锁。