信号量没有破坏/解除竞争条件

注意：在公开集思广益之后,我已经大量编辑了这个问题.然而,所描述的实际算法以及关于它们是否足以避免比赛的问题应该是相同的.

我正在尝试实现信号量,避免glibc错误号12674中描述的竞争条件：

http://sourceware.org/bugzilla/show_bug.cgi?id=12674

基本上,如果你不关心这种破坏的竞争条件,写一个基于futex的信号量的有效方法是：

帖子：

>原子增量信号量值.
>检查服务员数量.如果它非零,则执行futex唤醒.

等待：

>信号量值的原子递减 – 如果为正(如果成功则返回).
>如果此操作失败,请增加服务员并执行futex等待.
>唤醒时,减少服务员,循环并重试.

后期操作的第2步是不安全的.

有两个明显的实现可以避免这个问题,但两者都存在重大问题：

第一种解决方案是不存储服务员计数或标志,并始终在帖子上执行futex唤醒.这显然是安全的,但却违背了futexes的全部目的(在用户空间中保持无竞争的情况).

第二种解决方案不是存储服务员计数,而是在等待争用时让信号量值减少到-1.然后,post操作从-1转换为1并唤醒所有服务员.其中一个成功将信号量值递减为0,如果有剩余,则将值设置为-1,因此下一个帖子将执行另一个唤醒.这个解决方案显然也是安全的,但是当它发布时,它会导致争夺信号量的线程踩踏.

总之,第一种解决方案仅适用于总是争用的信号量,而后者仅适用于通常不超过一名服务员的信号量.一般用途都不可接受.

现在,尝试一个真正的解决方案……

此时,应该注意的是,还有一些其他要求使现实世界的实施变得复杂.后期操作需要是异步信号安全的(因此它基本上不能使用锁),并且需要等待操作以允许信号,超时或线程取消中断.实际上,这意味着后期操作必须能够安全地“退出”它对信号量状态所做的任何更改.我已经掩饰了这些问题,因为我的方法似乎对他们没有任何问题,但他们确实做出了一些其他明显的变化/解决方案,所以任何人建议新方法作为答案都应该意识到这些问题……

我有一个建议的解决方案,但我不确定它是否会受到新的(可能更糟)的竞争条件的影响.我将在这里描述它,我希望一些并发神(或者至少是半神人)可能有善意去审查它的正确性.

我的方法是上面描述的第二个“坏”解决方案和原始方法(在glibc错误报告中描述的竞争)的混合.它使用服务器计数和服务器标志(-1存储在信号量值中).

等待操作的关键更改是,只要有服务员(预先存在的服务员计数或本身作为新的服务员),它就会在信号量值中存储-1而不是0.

等待：

>读取信号量值.
>如果值为正,则按如下方式确定新的信号量值：如果值正好为1并且有等待者,则新值应为-1;否则只是递减旧值.使用compare-and-swap更新值,如果成功则返回成功.
>否则,递增等待者,用-1原子地将值0替换为0,并以-1作为值执行futex等待.
>唤醒时,循环并重试.

对post操作的关键更改是它在递增信号量值之前执行对服务器计数的读取,而不是之后：

帖子：

>读取并保存信号量值.
>阅读并保存服务员人数.
>确定新的信号量值(-1变为1,否则只是增量).
>原子比较和交换以更新信号量值.失败时,转到1.
>如果保存的服务员计数非零或信号量值为-1,则执行futex wake.

步骤4中的比较和交换提供了服务员计数仍然正确的一些安全性,但仍然存在ABA竞争 – 在步骤1和4之间,其他线程可能执行等待和后续操作,使信号量值保持不变作为其初始值.

在查找此算法可能无法唤醒服务器的情况时,我们只需考虑初始服务器计数读取为0且读取的信号量值不为-1的情况.此外,如果信号量值为正并且没有预先存在的服务员,则当前帖子不对任何唤醒负责,因此这种情况也不感兴趣.我们还在研究等待操作以零信号量值和零等待计数开始的情况.在这种情况下,为了不具有竞争条件,在步骤2和4之间发生的导致新服务员的任何事件必须改变信号量值,以便步骤4中的比较和交换失败.显然,任何单个插入的帖子或等待都将改变信号量值(分别为1或-1),因此更具体地说,关注的情况是导致信号量值为0但存在服务员的操作序列.

我认为由于等待操作中遵循的程序不会发生这种情况,但我并没有100％相信自己.

最后,这里有一些比赛的例子,如果你削弱了我的算法,为了确定它正在做什么的动机,如果不清楚的话.

失败1：使用纯等待计数,信号量值中没有-1标志.琐碎的比赛看起来像：

>信号量值从0开始
>线程1开始发布,读取0信号量值和0等待计数.
>线程2开始等待,增加等待计数和futex等待.
>线程1执行成功的比较和交换,返回时不会唤醒服务员.

失败2：使用服务器计数并让新服务员将信号量值设置为-1,但是等待成功时简单地减少信号量值(如果其他线程仍在等待,则不将其设置为-1)：

>信号量值从0开始
>线程1开始发布,读取0信号量值和0等待计数.
>线程2和3等待,递增等待计数和futex等待.
>线程4帖子,将信号量值设置为1.
>线程2唤醒并将信号量值减少为0,服务器计数为1.
>线程1执行成功的比较和交换,返回而不唤醒线程3. 最佳答案 首先,让我提出您可能希望考虑的两种替代方法.

>方法#1(特定于X86,快速)：CMPXCHG8B / CMPXCHG16B.

x86平台具有双指针宽度的原子比较和交换操作.在32位上,这是8个字节;在64位上有一个CMPXCHG16B,它原子地比较和交换一个完整的16字节数据.通过使用它,您可以在单个操作中自动交换等待计数和信号量计数. futex只能在一个指针大小的字段上等待,但在这种情况下这不应该是一个严重的问题.
>方法#2(便携式,有限)：打包计数.

如果服务员和信号量计数的限制为2 ^ 16,则只需将两个计数打包在一个32位字段中.
>方法#3(便携式,有一些开销)：使用信号量在信号量来保护赛后.

保留8位信号量计数以锁定后期操作. post操作将递增此计数器(阻止它是否会溢出),同时增加真正的信号量计数.然后它将与waiters字段一起工作,然后原子地减少锁定计数器.递减后,如果前一个值为255,则唤醒所有服务员(虽然这会导致一个雷鸣般的群体,但这应该是非常罕见的).

删除后,获取锁定255次(您可以在一个步骤中增加多个),并根据需要进行阻止.一旦获得锁定255次,您就知道所有帖子都已完成,删除锁定是安全的.

缺点：帖子现在需要两次原子比较交换,最大信号量计数为2 ^ 24-1.另外,递归地输入255次异步信号处理程序将会死锁.

这些方法更简单,更容易证明正确,并且可能更快.然而,它们的局限性可能意味着它们对您的情况是不可接受的(但是CMPXCHG8B方法在x86上应该可以很好地工作).还有一个：

>方法#4(有点拱形独立;复杂;快速)：修改内核

（编辑：开发网_开封站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!