在Linux上可以实现正确的故障安全stream程共享障碍吗?

在过去的一个问题中,我询问了如何在没有破坏的情况下实施pthread障碍

一旦pthread_barrier_wait返回,屏障如何被销毁?

并从迈克尔·伯尔(Michael Burr)那里得到了一个解决过程局部障碍的完美解决scheme,但是却无法解决过程共享障碍。 后来我们通过一些想法,但从来没有得出满意的结论,甚至没有开始陷入资源失败案件。

是否有可能在Linux上制造符合这些条件的障碍:

  • 进程共享(可以在任何共享内存中创build)。
  • 在屏障等待函数返回后,可立即取消映射或销毁任何线程的屏障。
  • 由于资源分配失败,不能失败。

迈克尔在解决过程共享案例中的尝试(见链接问题)具有不幸的属性,即在等待时间必须分配某种types的系统资源,这意味着等待可能失败。 目前还不清楚当一个障碍等待失败时呼叫者可以合理地做什么,因为整个障碍的关键是,直到其余的N-1线程到达它是不安全的。

一个内核空间解决scheme可能是唯一的方法,但即使这很困难,由于信号中断的可能性,没有可靠的方法来恢复它…

Solutions Collecting From Web of "在Linux上可以实现正确的故障安全stream程共享障碍吗?"

这对于Linux futex API来说是不可能的,我想这也可以被证明。

我们这里基本上是这样的一个场景,其中N个进程必须被最后一个进程可靠地唤醒,并且进一步的任何进程都不会在最终唤醒之后触及任何共享内存(因为它可能会被异步破坏或重用)。 虽然我们可以轻松地唤醒所有进程,但是根本的竞争状态是在唤醒和等待之间; 如果我们在等待之前发出唤醒声,那么失散者就不会醒来。

通常的解决办法就是让等待者自动检查等待的状态变量; 如果唤醒已经发生,这可以避免睡眠。 但是,我们不能这样做 – 只要唤醒成为可能,触摸共享内存是不安全的!

另一种方法是实际检查是否所有进程都已经进入睡眠状态。 但是,这对于Linux futex API来说是不可能的。 等待者数量的唯一指示是来自FUTEX_WAKE的返回值; 如果回报少于您预期的服务员人数,您知道有些人还没睡着。 然而,即使我们发现我们没有足够的服务员醒来,做任何事情都为时已晚 – 其中一个醒来的过程可能已经摧毁了这个障碍!

所以,不幸的是,这种可以立即破坏的原语不能用Linux futex API来构建。

请注意,在一个服务员,一个叫醒者的具体情况下,可以解决这个问题; 如果FUTEX_WAKE返回零,我们知道没有人真的被唤醒,所以你有机会恢复。 然而,把它变成一个高效的算法是相当棘手的。

向futex模型添加一个可以解决这个问题的可靠扩展是很棘手的。 基本的问题是,我们需要知道N个线程什么时候成功地进入了等待状态,并且原子地唤醒了他们。 然而,这些线程中的任何一个都可能随时等待运行一个信号处理程序 – 实际上,这个线程也可能会等待信号处理程序。

然而,一种可行的方法是对NT API中键控事件模型的扩展。 使用键控事件,线程从锁中成对释放; 如果你有一个没有“等待”的“释放”,那么“释放”呼叫阻止“等待”。

由于信号处理程序的问题,这本身是不够的; 然而,如果我们允许“释放”调用来指定一些线程被自动唤醒,这个工作。 您只需让屏障中的每个线程递减计数,然后在该地址上的键控事件上“等待”。 最后一个线程'释放'N – 1个线程。 内核不允许任何唤醒事件被处理,直到所有的N-1线程都进入这个键控事件状态; 如果有任何线程由于信号(包括释放线程)而离开futex调用,则在所有线程返回之前,这将防止任何唤醒。

经过与bdonlan长时间讨论SO聊天,我想我有一个解决方案。 基本上,我们把问题分解成两个自我同步的释放问题:销毁操作和解映射。

处理破坏很简单:只需使pthread_barrier_destroy函数等待所有服务员停止检查障碍。 这可以通过在屏障中使用计数来完成,在进入/退出等待函数时以原子方式递增/递减,并使销毁函数自旋等待计数达到零。 (也可以在这里使用futex,而不是仅仅在旋转,如果你把一个服务器标志放在使用次数或类似的高位上)。

处理解munmap也很容易,但是非本地的:通过向系统调用包装器添加锁定,确保当阻挡层等待者正在退出时,具有MAP_FIXED标志的munmapmmap不会发生。 这需要一个专门的读写器锁。 最后一个到达屏障的服务员应该抓住munmap rw-lock上的读锁,当最后的服务员退出时(当用户计数结果为0时)将释放该读锁。 munmapmmap可以通过使作者锁定递归来重入(如一些程序可能期望的,即使POSIX不需要它)。 实际上,读者和作者完全对称的一种锁,每种类型的锁都排除了相反类型的锁而不是相同的类型,应该是最好的。

那么我想我可以用笨拙的方法来做

让“障碍”成为它自己的进程在一个套接字上监听。 将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 (一个mutex), master_condition_variable (一个条件变量), waiter_count (一个无符号整数), N (另一个无符号整数)和time_to_die (一个布尔值)都是由barrier_init分配和初始化的共享状态。 waiter_count初始化为零, time_to_die为false, N为屏障正在等待的线程数。

那么barrier_destroy将是:

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

不了解所有关于信号处理的细节等等,但我认为,“最后一个熄灯”的基本思路是可行的。