多个互斥锁定策略以及库不使用地址比较的原因

Question

存在一种众所周知的锁定多个锁的方法,其依赖于根据该排序选择固定的线性排序和获取锁.

例如,在"获取锁定两个互斥锁并避免死锁"的答案中提出了这一点.特别是,基于地址比较的解决方案似乎非常优雅和明显.

当我试图检查它是如何实际实现的时候,令我惊讶的是,我发现这个解决方案没有被广泛使用.

引用内核文档 - 锁定不可靠指南:

教科书会告诉你,如果你总是以相同的顺序锁定,你将永远不会遇到这种僵局.实践会告诉你这种方法不能扩展:当我创建一个新的锁时,我不太了解内核,无法确定它适合的5000锁定层次结构中的位置.

PThreads似乎根本没有内置这样的机制.

Boost.Thread提出了完全不同的解决方案,lock()因为多个(2到5个)互斥锁基于尝试并锁定尽可能多的互斥锁.

这是Boost.Thread源代码的片段(Boost 1.48.0,boost/thread/locks.hpp:1291):

template<typename MutexType1,typename MutexType2,typename MutexType3>
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3)
{    
    unsigned const lock_count=3;
    unsigned lock_first=0;
    for(;;)
    {    
        switch(lock_first)
        {    
        case 0:
            lock_first=detail::lock_helper(m1,m2,m3);
            if(!lock_first)
                return;
            break;
        case 1:
            lock_first=detail::lock_helper(m2,m3,m1);
            if(!lock_first)
                return;
            lock_first=(lock_first+1)%lock_count;
            break;
        case 2:
            lock_first=detail::lock_helper(m3,m1,m2);
            if(!lock_first)
                return;
            lock_first=(lock_first+2)%lock_count;
            break;
        }    
    }    
}    

其中成功lock_helper返回0和未成功锁定的互斥锁数量.

为什么这个解决方案比地址或任何其他类型的ID 更好？我没有看到指针比较有任何问题,使用这种"盲"锁定可以避免这种问题.

关于如何在库级别解决此问题还有其他想法吗？

Answer 1

从赏金文字:

我甚至不确定我是否可以证明所提出的Boost解决方案的正确性,这似乎比具有线性顺序的解决方案更棘手.

Boost解决方案不会死锁,因为它在持有锁时永远不会等待.除了第一个锁之外的所有锁都是通过try_lock获取的.如果任何try_lock调用无法获取其锁定,则释放所有先前获取的锁定.此外,在Boost实现中,新的尝试将从锁定失败以获取上一次开始,并将首先等待它可用; 这是一个聪明的设计决定.

作为一般规则,最好避免在持有锁定时阻止呼叫.因此,如果可能的话,使用try-lock的解决方案是首选(在我看来).特别是在锁定顺序的情况下,整个系统可能会卡住.想象一下,最后一个锁定(例如,具有最大地址的锁定)是由一个被阻塞的线程获得的.现在想象一些其他线程需要最后一个锁和另一个锁,并且由于订购它将首先获得另一个并且将等待最后一个锁.所有其他锁都会发生同样的情况,整个系统在释放最后一个锁之前不会有任何进展.当然,这是一个极端而且不太可能的情况,但它说明了锁定顺序的固有问题:锁定数越高,锁定获得时间接影响越大.

基于try-lock的解决方案的缺点是它可能导致活锁,并且在极端情况下整个系统可能也会卡住至少一段时间.因此,重要的是要有一些退避模式,使锁定尝试之间的暂停时间更长,并且可能是随机的.

Answer 2

有时,需要在锁定B之前获取锁定A. 锁B可能具有较低或较高的地址,因此在这种情况下您不能使用地址比较.

示例:如果您有树数据结构,并且线程尝试读取和更新节点,则可以使用每个节点的读写器锁来保护树.这仅在您的线程始终从上到下的root-to-leave获取锁时才有效.在这种情况下,锁的地址无关紧要.

如果首先获取哪个锁无关紧要,则只能使用地址比较.如果是这种情况,地址比较是一个很好的解决方案.但如果情况并非如此,你就无法做到.

我想Linux内核要求某些子系统在其他子系统之前被锁定.使用地址比较无法做到这一点.