R..*_*R.. 6 c linux semaphore pthreads race-condition
注意:在公开集思广益之后,我已经大量编辑了这个问题.然而,所描述的实际算法以及关于它们是否足以避免比赛的问题应该是相同的.
我正在尝试实现信号量,避免glibc错误号12674中描述的竞争条件:
http://sourceware.org/bugzilla/show_bug.cgi?id=12674
基本上,如果你不关心这种破坏的竞争条件,写一个基于futex的信号量的有效方法是:
帖子:
等待:
后期操作的第2步是不安全的.
有两个明显的实现可以避免这个问题,但两者都存在重大问题:
第一种解决方案是不存储服务员计数或标志,并始终在帖子上执行futex唤醒.这显然是安全的,但却违背了futexes的全部目的(在用户空间中保持无竞争的情况).
第二种解决方案不是存储服务员计数,而是在等待争用时让信号量值减少到-1.然后,post操作从-1转换为1并唤醒所有服务员.其中一个成功将信号量值递减为0,如果有剩余,则将值设置为-1,因此下一个帖子将执行另一个唤醒.这个解决方案显然也是安全的,但是当它发布时,它会导致争夺信号量的线程踩踏.
总之,第一种解决方案仅适用于总是争用的信号量,而后者仅适用于通常不超过一名服务员的信号量.一般用途都不可接受.
现在,尝试一个真正的解决方案......
此时,应该注意的是,还有一些其他要求使现实世界的实施变得复杂.后期操作需要是异步信号安全的(因此它基本上不能使用锁),并且需要等待操作以允许信号,超时或线程取消中断.实际上,这意味着后期操作必须能够安全地"退出"它对信号量状态所做的任何更改.我已经掩饰了这些问题,因为我的方法似乎对他们没有任何问题,但他们确实做出了一些其他明显的变化/解决方案,所以任何人建议新方法作为答案都应该意识到这些问题......
我有一个建议的解决方案,但我不确定它是否会受到新的(可能更糟)的竞争条件的影响.我将在这里描述它,我希望一些并发神(或者至少是半神人)可能有善意去审查它的正确性.
我的方法是上面描述的第二个"坏"解决方案和原始方法(在glibc错误报告中描述的竞争)的混合.它使用服务器计数和服务器标志(-1存储在信号量值中).
等待操作的关键更改是,只要有服务员(预先存在的服务员计数或本身作为新的服务员),它就会在信号量值中存储-1而不是0.
等待:
对post操作的关键更改是它在递增信号量值之前执行对服务器计数的读取,而不是之后:
帖子:
步骤4中的比较和交换提供了服务员计数仍然正确的一些安全性,但仍然存在ABA竞争 - 在步骤1和4之间,其他线程可能执行等待和后续操作,使信号量值保持不变作为其初始值.
在查找此算法可能无法唤醒服务器的情况时,我们只需考虑初始服务器计数读取为0且读取的信号量值不为-1的情况.此外,如果信号量值为正并且没有预先存在的服务员,则当前帖子不对任何唤醒负责,因此这种情况也不感兴趣.我们还在研究等待操作以零信号量值和零等待计数开始的情况.在这种情况下,为了不具有竞争条件,在步骤2和4之间发生的导致新服务员的任何事件必须改变信号量值,以便步骤4中的比较和交换失败.显然,任何单个插入的帖子或等待都将改变信号量值(分别为1或-1),因此更具体地说,关注的情况是导致信号量值为0但存在服务员的操作序列.
我认为由于等待操作中遵循的程序不会发生这种情况,但我并没有100%相信自己.
最后,这里有一些比赛的例子,如果你削弱了我的算法,为了确定它正在做什么的动机,如果不清楚的话.
失败1:使用纯等待计数,信号量值中没有-1标志.琐碎的比赛看起来像:
失败2:使用服务器计数并让新服务员将信号量值设置为-1,但是等待成功时简单地减少信号量值(如果其他线程仍在等待,则不将其设置为-1):
首先，让我提出您可能希望考虑的两种替代方法。
方法#1（特定于 X86，快速）：CMPXCHG8B/CMPXCHG16B。
x86 平台具有双指针宽度原子比较和交换操作。在 32 位上，这是 8 个字节；在 64 位上，有一个 CMPXCHG16B 可以自动比较和交换完整的16 字节数据。通过使用它，您可以在单个操作中自动交换等待计数和信号量计数。futex 只能等待一个指针大小的字段，但在这种情况下这不应该是一个严重的问题。
方法#2（便携式，有限）：打包计数。
如果服务员和信号量计数的限制为 2^16 是可以接受的，则只需将这两个计数打包在单个 32 位字段中即可。
方法#3（可移植，有一些开销）：使用信号量中的信号量来保护竞争后的情况。
保留信号量计数的 8 位用于锁定后操作。后操作将在增加真实信号量计数的同时增加该计数器（如果溢出则阻塞）。然后它将处理 waiters 字段，然后原子地递减锁定计数器。递减后，如果之前的值为255，则唤醒所有服务员（虽然这会引起惊群，但应该是极其罕见的）。
删除时，获取锁 255 次（您可以一步递增多次），并根据需要进行阻塞。一旦锁被获取 255 次，您就知道所有帖子都已完成，并且可以安全地删除锁。
缺点：帖子现在需要两次原子比较交换，并且最大信号量计数为 2^24-1。此外，递归进入异步信号处理程序 255 次将导致死锁。
这些方法更简单，更容易证明正确，而且可能更快。然而，它们的局限性可能意味着它们对于您的情况来说是不可接受的（但是 CMPXCHG8B 方法应该在 x86 上工作得很好）。还有一个：
方法#4（有点独立于架构；复杂；快速）：修改内核
这里的一个选择是修改内核，以允许使用一种低开销、安全的方法来读取 waiter 字段，而不会在释放内存时导致段错误。例如，您可以添加一个注册线程特定数据结构的系统调用；在该线程特定的数据页中，您可以有一个“故障处理程序跳转地址”。如果程序出现段错误，如果跳转地址非零，内核将简单地跳转到那里，而不是引发 SIGSEGV。或者，您可以使用类似的机制来简单地抑制有问题的指令。
现在你所要做的就是：
就这样 - 您获得了快速算法，但您还获得了针对删除竞争的保护。但你必须破解内核的 segv 处理程序才能做到这一点。Windows 上的 SEH 可能值得一看；类似的机制在这里会非常有效。
在任何演员阵容中，我不认为你的方法有什么问题，但我可能错过了一些东西。最好在适当的邮件列表中提出它，并咨询 futex 维护者；他们可能有兴趣在内核中实现支持，以使这对您来说更容易。