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

11

在之前的一个问题中,我问了如何在没有销毁竞争的情况下实现pthread屏障:

如何让屏障在pthread_barrier_wait返回后立即可销毁?

我从Michael Burr那里得到了对于进程本地屏障的完美解决方案,但该方案对于进程共享的屏障会失败。我们后来一起探讨了一些想法,但从未达成令人满意的结论,也没有开始研究资源故障的情况。

在Linux上是否可能创建一个符合以下条件的屏障:

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

Michael尝试解决进程共享的情况(请参见链接的问题),但具有不幸的性质,即在等待时间必须分配某种系统资源,这意味着等待可能会失败。当屏障等待失败时,调用者应该做什么是不清楚的,因为屏障的整个作用在于,在剩余的N-1线程到达之前,不安全继续执行操作。

可能只有内核空间的解决方案,但由于存在信号中断等情况,即使是这样也很困难,且没有可靠的方法来恢复它...


1
我不确定我真正理解你的问题,从我所知道的来看,NPTL实现是故障安全的。屏障本身是在外部分配的,它的pthread_barrier_destroy函数只与最后一个等待者同步。那么问题是什么呢? - Hasturkun
尽管附件缺失,但它似乎描述了一种在销毁屏障之前取消映射内存的情况。如果我理解正确,在销毁屏障之前取消映射是不安全的(除非您可以保证没有您使用的线程使用该屏障,假设您不是最后一个用户)。NPTL实现永远不会在没有锁的情况下访问任何内容,pthread_barrier_destroy获取锁,确保销毁成功时没有人访问屏障内部(如果有任何线程正在等待,则不会成功)。 - Hasturkun
你正在阅读规范时,选择了一种懒惰实现者的方式来阅读它,而不是按字面意思(以及想要编写应用程序的人会阅读它的方式)。 - R.. GitHub STOP HELPING ICE
我认为这个问题可以通过在返回之前,让等待的线程重新排队到一个进程本地的屏障(或等效物)上,并且最后一个离开的线程唤醒其他线程来解决。这将确保当等待返回时,你的进程不再访问屏障对象,从而使得解除映射操作变得安全。 - Hasturkun
问题在于存储必要的数据,以便它们可以协商进程本地屏障并等待。屏障内部不起作用,因为可能有任意多个进程在使用它。在进程中使用全局数据不起作用,除非使用>O(1)搜索结构。 - R.. GitHub STOP HELPING ICE
显示剩余4条评论
3个回答

2
这是Linux futex API无法实现的,我认为这也可以被证明。

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

像这样的问题通常的解决方案是让落伍者在等待时原子地检查状态变量;如果唤醒已经发生,它可以完全避免睡眠。然而,在这里我们无法这样做——一旦唤醒变得可能,触摸共享内存就不安全了!

另一种方法是实际检查所有进程是否已经进入睡眠状态。然而,这在Linux futex API中是不可能的;等待者数量的唯一指示是FUTEX_WAKE的返回值;如果它返回少于您预期的等待者数量,则知道一些人还没有入睡。但是,即使我们发现我们没有唤醒足够的等待者,也为时已晚——已经醒来的进程中可能已经有一个销毁了屏障!

很遗憾,使用Linux futex API无法构建此类可立即销毁的原始对象。
需要注意的是,在仅有一个等待者和唤醒者的特定情况下,可能可以解决这个问题;如果FUTEX_WAKE返回零,则说明没有人被唤醒,因此您有机会进行恢复。然而,将其转化为高效算法相当棘手。
向futex模型添加强大的扩展以解决这个问题也很困难。基本问题是我们需要知道N个线程何时成功进入等待状态,并原子地唤醒它们。但是,任何一个线程都可能随时离开等待状态去运行信号处理程序 - 实际上,唤醒线程也可能离开等待状态去运行信号处理程序。
然而,可能有效的一种方式是对NT API中的keyed event模型进行扩展。使用键控事件,线程成对从锁中释放;如果您有一个“释放”而没有“等待”,则“释放”调用会阻塞“等待”。
这本身还不够,因为存在信号处理程序的问题;然而,如果我们允许“release”调用指定原子地唤醒一定数量的线程,那么这就可以解决。你只需要让屏障中的每个线程递减一个计数器,然后在该地址上等待一个键控事件。最后一个线程会“释放” N - 1 个线程。内核不会处理任何唤醒事件,直到所有 N-1 个线程都进入此键控事件状态;如果任何线程由于信号(包括释放线程)离开 futex 调用,则这会阻止任何唤醒,直到所有线程都回来。

这里有一个想法:FUTEX_REQUEUE 操作可以用于查询一个 futex 有多少个等待者(它返回唤醒的数量和重新排队的数量之和),使用时源地址和目标地址相同,唤醒数为0。它也可以(大概)用于将等待者重新排队到在等待者地址空间中甚至看不到的 futex 上。也许这些操作足以实现类似键控事件的东西?我认为唯一的大问题是当等待者被信号中断时会发生什么。即使你阻塞了所有信号(不太合法...),仍然有 SIGSTOP... - R.. GitHub STOP HELPING ICE
查询服务员数量本质上是有竞争条件的 - 值可能会在系统调用返回的瞬间发生变化,因此它只能作为性能优化而无用。即使您开始逐个将服务员移动到唤醒者端的堆栈本地futex变量中,服务员仍然可能被信号唤醒,然后返回其原始等待状态。不,我认为这确实需要一个新的内核操作。 - bdonlan
你确定如果被信号中断,他们会重新开始等待原始队列吗?也许是这样的;我得检查一下。我更倾向于认为,如果在重新排队后被中断,futex wait系统调用会失败并返回EAGAIN或返回0(唤醒),类似于readwrite在读/写一些数据后被中断时返回部分传输。当然,要确保我应该真正测试一下... - R.. GitHub STOP HELPING ICE
我另一个想法是对于pthread_barrier_init操作,为了创建一个进程共享的屏障,可以创建一个新进程作为永久的屏障管理器,并通过futex进行通信。最终的唤醒可以通过查询一些文件系统对象来控制,这些对象在管理进程的控制下,可以在不必分配资源的情况下进行查询,例如access。当然,由于似乎没有办法阻塞等待这样的事件,因此希望通过futex操作(上述想法)来优化等待,并仅在“最终检查”时使用fs。 - R.. GitHub STOP HELPING ICE
@R..,是的,它会失败并返回EAGAIN。此时屏障代码必须回到等待原始队列上。毕竟还有哪里可以等待呢?然后考虑这种情况:就在唤醒者在私有队列上发出FUTEX_WAKE并从屏障函数返回时,休眠者被信号唤醒并返回到原始队列上等待 - 即使访问该内存不再安全。 - bdonlan
显示剩余3条评论

1
经过与SO聊天中的bdonlan长时间讨论,我认为我有了一个解决方案。基本上,我们将问题分解为两个自同步释放问题:销毁操作和取消映射。
处理销毁很容易:只需使pthread_barrier_destroy函数等待所有等待者停止检查屏障即可。这可以通过在屏障中具有使用计数来完成,该计数在进入/退出等待函数时原子地递增/递减,并且使销毁函数旋转等待计数达到零。(如果将等待器标志放置在使用计数或类似计数的高位中,则还可以在此处使用futex,而不仅仅是旋转。)

处理取消映射也很容易,但是非本地:通过向系统调用包装器添加锁定,确保在屏障等待者正在退出的过程中不能发生带有MAP_FIXED标志的munmapmmap,这需要一种专门的读写锁。到达屏障的最后一个等待者应该在munmap读写锁上获取读锁,在最终等待者退出时(当减少用户计数结果为0时)将释放该锁。通过使写入锁递归,可以使munmapmmap可重入(正如某些程序可能期望的那样,尽管POSIX不要求)。实际上,一种读者和写者完全对称的锁,每种类型的锁都排除相反类型的锁而不是同一类型的锁,应该效果最好。


一个用于长期保存的聊天记录链接:http://chat.stackoverflow.com/rooms/3811/discussion-between-bdonlan-and-r - bdonlan
我已经实现了我们讨论的设计,看起来它正在工作。它通过了我的基本测试,包括unmap/destroy竞争条件和NPTL屏障测试,但我还没有对其进行重负载测试。性能有点下降,因为所有等待者实际上都必须等待两次(一旦他们都到达屏障,以便他们可以在退出之前全部获取munmap锁),但是对于非pshared屏障,我仍然使用旧的设计(由Michael Burr提供)。 - R.. GitHub STOP HELPING ICE

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初始化为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();

关于信号处理等所有细节,我不是很确定……但“最后一个离开的人熄灯”这个基本想法是可行的,我认为。


我的回答的后半部分在初始化期间除外,不会分配任何资源...这样可以工作吗? - Nemo
你的方法可以防止竞争出现在从屏障返回和销毁之间,但我认为当调用者取消映射屏障而不销毁它时,这并没有什么帮助。当然,这是进程共享屏障的典型用法,您可能希望将其保留供其他进程使用。 - R.. GitHub STOP HELPING ICE
@R..:为什么调用者要在未先销毁屏障的情况下取消映射它? - Hasturkun
1
因为有许多进程正在使用这个屏障。它可能属于一个服务器进程,你已经完成了与它的通信,但是它仍然需要屏障以便与其他进程进行后续的通信。 - R.. GitHub STOP HELPING ICE
使用我的解决方案,映射/取消映射是一个正交问题...你所要做的就是弄清楚如何管理_任何_共享内存的创建/销毁,然后你就完成了。这并不一定是微不足道的,但与障碍本身无关。 - Nemo
显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接