首页 文章

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

提问于
浏览 次
6

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

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

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

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

帖子：

  • 原子增量信号量值 .

  • 检查服务员数量 . 如果它非零，则执行futex唤醒 .

等待：

  • 信号量值的原子递减 - 如果为正（如果成功则返回） .

  • 如果此操作失败，请增加服务员并执行futex等待 .

  • 唤醒时，减少服务员，循环并重试 .

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

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

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

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

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

Now, on to an attempt at a real solution...

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

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

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

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

等待：

  • 读取信号量值 .

  • 如果值为正，则按如下方式确定新的信号量值：如果值正好为1且有服务员，则新值应为-1;否则只是递减旧值 . 使用compare-and-swap更新值，如果成功则返回成功 .

  • 否则，递增等待者，用-1原子地将值0替换为0，并以-1作为值执行futex等待 .

  • 唤醒时，减少服务员，循环并重试 .

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

帖子：

  • 读取并保存信号量值 .

  • 阅读并保存服务员人数 .

  • 确定新的信号量值（-1变为1，否则只是增量） .

  • 原子比较和交换以更新信号量值 . 失败时，转到1 .

  • 如果保存的服务员计数非零或信号量值为-1，则执行futex wake .

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

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

I believe this cannot happen due to the procedure followed in the wait operation, but I haven't convinced myself 100%.

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

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

  • 信号量值从0开始

  • 线程1开始发布，读取0信号量值和0等待计数 .

  • 线程2开始等待，增加等待计数和futex等待 .

  • 线程1执行成功的比较和交换，返回时不会唤醒服务员 .

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

  • 信号量值从0开始

  • 线程1开始发布，读取0信号量值和0等待计数 .

  • 线程2和3等待，递增等待计数和futex等待 .

  • Thread 4帖子，将信号量值设置为1 .

  • 线程2唤醒并将信号量值减少为0，服务器计数为1 .

  • 线程1执行成功的比较和交换，返回而不唤醒线程3 .

c linux pthreads semaphore race-condition

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（有点独立;复杂;快速）：修改内核

    这里的一个选择是修改内核以允许用于读取服务器字段的低开销，安全的方法，而不会在释放存储器的情况下导致段错误 . 例如，您可以添加一个注册特定于线程的数据结构的系统调用;在那个特定于线程的数据页面中，你可以有一个'错误处理程序跳转地址' . 如果程序段错误，如果跳转地址非零，内核只是跳转到那里而不是提升SIGSEGV . 或者，您可以使用类似的机制来简单地抑制违规指令 .

    现在你所要做的就是：

    • 在libc init和线程启动时，注册这些特定于线程的结构，并在TLS数据中保存指向它们的指针

    • 在帖子中，安排在服务员数量周围抑制故障 . 如果确实发生了故障，请不要进行唤醒（如果有问题的内存被重用于其他用途，则唤醒无害）

    你去了 - 你得到了快速的算法，但你也得到了保护，以防止删除比赛 . 但你必须破解内核的segv处理程序才能做到这一点 . 可能值得在Windows上查看SEH;类似的机制在这里可以很好地运作 .

    在任何演员阵容中，我认为你的方法并没有出现任何问题，但我可能会遗漏一些东西 . 在适当的邮件列表上提出它并与futex维护者协商可能会很好;他们可能会对在内核中实现支持感兴趣，以使您更容易 .

    回复于

相关问题