可重用屏障算法 [英] Reusable Barrier Algorithm

问题描述

我正在研究信号量小书"一书中的可重用屏障算法，可在此处http://greenteapress.com/semaphores/downey08semaphores.pdf

谜题在第 31 页(基本同步模式/可重用障碍)，我想出了一个解决方案"(或不是)，它与书中的解决方案(两阶段障碍)不同.

这是我每个线程的代码":

# n = 4;线程正在运行# semaphore = n max., 初始化为 0# 互斥锁，无主.开始:互斥锁.wait()计数器 = 计数器 + 1如果计数器 = n:semaphore.signal(4) # 一次加4计数器 = 0互斥锁.release()信号量.wait()# 临界区semaphore.release()转到开始

这似乎有效，我什至在线程的不同部分插入了不同的睡眠定时器，它们仍然等待所有线程到来，然后再继续每个循环.我错过了什么吗?是否存在失败的条件?

我已经使用 Windows 库 Semaphore 和 Mutex 函数实现了这一点.

更新:

感谢 starblue 的回答.事实证明，如果在 mutex.release() 和 semaphore.wait() 之间的线程由于某种原因很慢，任何到达 semaphore.wait 的线程() 在一个完整的循环之后将能够再次通过，因为将剩下 N 个未使用的信号之一.

并且为线程编号 3 设置了睡眠命令，我得到了这个结果 http://pastebin.com/raw.php?i=FfXcCMZ3 在这里可以看到线程 3 第一次错过了一个转弯，线程 1 已经完成了 2 个转弯，然后在第二个转弯(实际上是它的第一回合).

再次感谢大家的投入.

解决方案

一个线程可以多次运行通过屏障，而其他线程根本不运行.

I'm looking into the Reusable Barrier algorithm from the book "The Little Book Of Semaphores", available here http://greenteapress.com/semaphores/downey08semaphores.pdf

The puzzle is on page 31 (Basic Synchronization Patterns/Reusable Barrier), and I have come up with a 'solution' (or not) which differs from the solution from the book (a two-phase barrier).

This is my 'code' for each thread:

# n = 4; threads running
# semaphore = n max., initialized to 0
# mutex, unowned.

start:
    mutex.wait()
        counter = counter + 1
        if counter = n:
            semaphore.signal(4) # add 4 at once
            counter = 0
    mutex.release()
    semaphore.wait()
        # critical section
    semaphore.release()
goto start

This does seem to work, I've even inserted different sleep timers into different sections of the threads, and they still wait for all the threads to come before continuing each and every loop. Am I missing something? Is there a condition that this will fail?

I've implemented this using the Windows library Semaphore and Mutex functions.

Update:

Thank you to starblue for the answer. Turns out that if for whatever reason a thread is slow between mutex.release() and semaphore.wait() any of the threads that arrive to semaphore.wait() after a full loop will be able to go through again, since there will be one of the N unused signals left.

And having put a Sleep command for thread number 3, I got this result http://pastebin.com/raw.php?i=FfXcCMZ3 where one can see that thread 3 missed a turn the first time, with thread 1 having done 2 turns, and then catching up on the second turn (which was in fact its 1st turn).

Thanks again to everyone for the input.

解决方案

One thread could run several times through the barrier while some other thread doesn't run at all.

这篇关于可重用屏障算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！