使用信号量实现N进程屏障

Question

我目前正在为一次包含早先的迭代的OS考试做准备，我遇到了这个问题:

实现一个“N进程屏障”，即确保每个进程都在其执行过程中的某个点等待其他进程到达给定点。

您可以使用以下操作：

init(sem,value)，wait(sem) 和 signal(sem)

N是任意数字。我可以使它适用于给定数量的进程，但不适用于任何数量。

有什么想法吗？您可以用伪代码进行回复，这不是作业，只是自己的学习。

- F. P.

Answer 1

这在《Semaphore 小书》中有很好的阐述。

n = the number of threads
count = 0
mutex = Semaphore(1)
barrier = Semaphore(0)


mutex.wait()
count = count + 1
mutex.signal()

if count == n: barrier.signal() # unblock ONE thread

barrier.wait()
barrier.signal() # once we are unblocked, it's our duty to unblock the next thread

- cnicutar

---

谢谢！我想到了非常接近的东西。 - F. P.

把 if count... 放在互斥锁块中会更好，以确保它只被输入一次吗？现在的情况看起来可能会输入两次。 - Jean-Bernard Pellerin

NVM - 看了一下小书，如果信号被触发两次也是可以的，因为这个屏障不会被重用，所以它的最终状态并不重要，只要达到了它的目标就可以了。 - Jean-Bernard Pellerin

如果您想重新使用它，则必须在最后一个barrier.signal()之后再次获取互斥锁并递减计数变量。不要忘记在此之后解锁互斥锁。但是为什么在if对count进行检查时不需要持有互斥锁呢？ - Hafnernuss

举个例子：假设线程5获取了互斥锁，增加计数并释放了互斥锁。现在调度程序切换到另一个线程，该线程再次获取互斥锁，增加计数并释放互斥锁。计数现在为6，并且屏障将永远不会向其线程发送信号。 - Hafnernuss

点赞给《信号量小书》的参考。太棒了！谢谢！ - rocarvaj

Answer 2

使用N个信号量。不太确定...

semaphore barr[N]
semaphore excl=1
int count=0

int i=1
while (i<=N)
   barr[i]=0 #initialization
   i=i+1

# use, each thread (tid)
wait(excl)
count=count+1
if (count==N)
   int j=1
   while (j<=N)
       signal(barr[j])
       j=j+1
   count=0
signal(excl)
wait(barr[tid])

- Sergio.Uma

---

这会遇到一个错误。应该是 while (i<N)。下一个 while 循环同理：while (j<N)。 - MPKenning

Answer 3

只有2个屏障信号量，但不确定...

semaphore barr[0..1] # two semaphores: barr[0] and barr[1]
semaphore excl=1
int count=0
int whichOne=0 # select semaphore to avoid race conditions

barr[0]=0 #initialization
barr[1]=0

# sample use
int current   #local for each thread
wait(excl)
current=whichOne
count=count+1
if (count==N)
   int j=1
   while (j<=N)
       signal(barr[current])
       j=j+1
   count=0
   whichOne=1-whichOne # swap barrier to avoid race conditions
signal(excl)
wait(barr[current])

- Sergio.Uma

Answer 4

我认为这也应该可以，只使用一个信号量（至少如果不需要可重用的屏障）？

n = number of threads
barrier = Semaphore(1 - n)

barrier.signal()
barrier.wait()
barrier.signal()

- user19668187