可重用的屏障算法

发布于 2024-10-17 22:01:39 字数 1444 浏览 2 评论 0原文

我正在研究《信号量小书》一书中的可重用屏障算法（存档此处）。

这个难题在第 31 页（基本同步模式/可重用屏障），我提出了一个（或不是）与书中解决方案（两相屏障）不同的“解决方案”。

这是我为每个线程编写的“代码”：

# 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

这似乎确实有效，我什至在线程的不同部分插入了不同的睡眠计时器，并且它们仍然等待所有线程到来，然后再继续每个循环。我错过了什么吗？是否有一个条件会失败？

我已经使用 Windows 库 Semaphore 和互斥函数。

更新：

感谢 starblue 的回答。事实证明，如果出于某种原因，线程在 mutex.release() 和 semaphore.wait() 之间运行缓慢，则任何到达 semaphore.wait 的线程都会变慢() 在完整循环之后将能够再次执行，因为将剩下 N 未使用的信号之一。

并且为线程 3 添加了 Sleep 命令后，我得到了 this< /a> 结果可以看到线程 3 第一次错过了一个回合，而线程 1 完成了 2 个回合，然后赶上第二个回合（实际上是它的第一个回合）。

再次感谢大家的意见。

原文

I'm looking into the Reusable Barrier algorithm from the book "The Little Book Of Semaphores" (archived here).

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 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.

分享到QQ

分享到微博