11

在过去的一个问题中，我询问了如何在没有破坏竞赛的情况下实现 pthread 屏障：

一旦 pthread_barrier_wait 返回，障碍如何被销毁？

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

是否可以在 Linux 上制作满足这些条件的屏障：

  • 进程共享（可以在任何共享内存中创建）。
  • 在屏障等待函数返回后立即从任何线程取消映射或销毁屏障是安全的。
  • 由于资源分配失败，不能失败。

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

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

4

3 回答 3

2

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

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

此类问题的通常解决方案是让散乱者在等待的情况下原子地检查状态变量；如果唤醒已经发生，这允许它完全避免睡眠。然而，我们不能在这里这样做——一旦唤醒成为可能，触摸共享内存是不安全的！

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

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

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

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

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

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

于 2011-09-24T03:32:23.493 回答
1

在与 bdonlan 在 SO chat 上进行了长时间讨论后，我想我有一个解决方案。基本上，我们将问题分解为两个自同步释放问题：销毁操作和取消映射。

处理破坏很容易：只需让pthread_barrier_destroy函数等待所有服务员停止检查屏障。这可以通过在屏障中设置使用计数，在进入/退出等待函数时原子地递增/递减，并让销毁函数旋转等待计数达到零来完成。（也可以在这里使用 futex，而不仅仅是旋转，如果您在使用计数的高位或类似位置粘贴一个服务员标志。）

处理取消映射也很容易，但不是本地的：通过向系统调用包装器添加锁定，确保在屏障服务员退出过程中不会发生munmap或mmap带有标志。MAP_FIXED这需要一种特殊的读写锁。最后一个到达屏障的服务员应该在munmaprw-lock 上获取一个读锁，当最后一个服务员退出时（当递减用户计数导致计数为 0 时），该读锁将被释放。munmap并且mmap可以通过使编写器锁递归来使其可重入（正如某些程序可能期望的那样，即使 POSIX 不需要它）。实际上，读者和作者完全对称的一种锁，并且每种类型的锁都排除了相反类型的锁但不是相同类型的锁，应该效果最好。

于 2011-09-27T04:56:03.193 回答
0

好吧，我想我可以用笨拙的方法来做到这一点......

让“障碍”成为它自己在套接字上侦听的进程。将 barrier_wait 实现为：

open connection to barrier process
send message telling barrier process I am waiting
block in read() waiting for reply

一旦 N 个线程正在等待，屏障进程就会告诉所有线程继续。然后每个服务员关闭它与屏障进程的连接并继续。

将 barrier_destroy 实现为：

open connection to barrier process
send message telling barrier process to go away
close connection

一旦所有连接都关闭并且屏障进程被告知离开，它就会退出。

[编辑：当然，这会分配和销毁套接字作为等待和释放操作的一部分。但我认为你可以不这样做就实现相同的协议；见下文。]

第一个问题：这个协议真的有效吗？我认为确实如此，但也许我不了解要求。

第二个问题：如果它确实有效，是否可以在没有额外过程开销的情况下进行模拟？

我相信答案是“是”。您可以让每个线程在适当的时候“扮演”屏障进程的角色。您只需要一个主互斥锁，由当前正在“扮演”屏障进程的任何线程持有。细节，细节......好的，所以barrier_wait可能看起来像：

lock(master_mutex);
++waiter_count;
if (waiter_count < N)
    cond_wait(master_condition_variable, master_mutex);
else
    cond_broadcast(master_condition_variable);
--waiter_count;
bool do_release = time_to_die && waiter_count == 0;
unlock(master_mutex);
if (do_release)
    release_resources();

这里master_mutex（一个互斥体）、master_condition_variable（一个条件变量）、waiter_count（一个无符号整数）、N（另一个无符号整数）和time_to_die（一个布尔值）都是由barrier_init分配和初始化的共享状态。 waiter_count被初始化为零、time_to_die假和N屏障正在等待的线程数。

然后 barrier_destroy 将是：

lock(master_mutex);
time_to_die = true;
bool do_release = waiter_count == 0;
unlock(master_mutex);
if (do_release)
    release_resources();

不确定有关信号处理等的所有细节......但我认为“最后一个关灯”的基本想法是可行的。

于 2011-08-04T04:37:16.260 回答