能否在 Linux 上实现正确的故障安全进程共享屏障？

Question

在过去的一个问题中，我询问了关于在没有破坏竞争的情况下实现 pthread barrier 的问题:

How can barriers be destroyable as soon as pthread_barrier_wait returns?

并从 Michael Burr 那里收到了针对进程本地障碍的完美解决方案，但对于进程共享障碍却失败了。我们后来也有过一些想法，但一直没有得出令人满意的结论，甚至没有开始进入资源故障案例。

是否有可能在 Linux 上制作满足这些条件的屏障:

• 进程共享(可以在任何共享内存中创建)。
• 在屏障等待函数返回后立即安全地从任何线程取消映射或销毁屏障。
• 不能因资源分配失败而失败。

Michael 尝试解决进程共享的情况(参见链接的问题)有一个不幸的特性，即必须在等待时分配某种系统资源，这意味着等待可能会失败。并且不清楚当屏障等待失败时调用者可以合理地做什么，因为屏障的全部要点是在剩余的 N-1 线程到达它之前继续进行是不安全的...

内核空间解决方案可能是唯一的方法，但即使这样也很困难，因为信​​号可能会中断等待而没有可靠的方法来恢复它...

Answer 1

这对于 Linux futex API 是不可能的，我认为这也可以被证明。

我们这里基本上有一个场景，其中 N 个进程必须被一个最终进程可靠地唤醒，并且在最终唤醒之后任何进程都不能触及任何共享内存(因为它可能被异步销毁或重用)。虽然我们可以很容易地唤醒所有进程，但基本的竞争条件是在唤醒和等待之间；如果我们在等待之前发出唤醒，掉队者永远不会醒来。

通常解决此类问题的方法是让掉队者在等待时自动检查状态变量；如果唤醒已经发生，这允许它完全避免 sleep 。然而，我们不能在这里这样做——一旦唤醒成为可能，接触共享内存是不安全的!

另一种方法是实际检查是否所有进程都已进入休眠状态。但是，这对于 Linux futex API 是不可能的；等待者数量的唯一指示是 FUTEX_WAKE 的返回值；如果它返回的服务员人数少于您预期的人数，您就知道有些人还没有睡着。然而，即使我们发现我们没有唤醒足够多的服务员，现在做任何事情都为时已晚 - 确实唤醒的进程之一可能已经破坏了屏障!

因此，不幸的是，这种可立即销毁的原语无法使用 Linux futex API 构建。

请注意，在一个服务员，一个叫醒者的特定情况下，可能可以解决该问题；如果 FUTEX_WAKE 返回零，我们知道实际上还没有人被唤醒，所以你有机会恢复。然而，将其变成一个高效的算法非常棘手。

向 futex 模型添加一个强大的扩展来解决这个问题是很棘手的。基本问题是，我们需要知道 N 个线程何时成功进入等待状态，并以原子方式将它们全部唤醒。但是，这些线程中的任何一个都可能随时等待运行信号处理程序 - 实际上，waker 线程也可能等待信号处理程序。

然而，一种可行的方法是对 keyed event 的扩展NT API 中的模型。对于键控事件，线程成对地从锁中释放；如果您有一个没有“等待”的“释放”，则“释放”调用会阻止“等待”。

由于信号处理程序的问题，这本身是不够的；但是，如果我们允许“release”调用指定多个线程以原子方式唤醒，这就可行了。您只需让屏障中的每个线程递减一个计数，然后“等待”该地址上的键控事件。最后一个线程“释放”了 N - 1 个线程。在所有 N-1 个线程都进入此键控事件状态之前，内核不允许处理任何唤醒事件；如果任何线程由于信号(包括释放线程)而离开 futex 调用，这将完全阻止任何唤醒，直到所有线程都返回。