c++ - 多个互斥锁策略以及为什么库不使用地址比较

Question

有一种广为人知的锁定多个锁的方法，它依赖于选择固定的线性顺序并根据该顺序获取锁。

例如，在 "Acquire a lock on two mutexes and avoid deadlock" 的答案中提出了这一点。 .尤其是基于地址比较的解决方案似乎相当优雅和明显。

当我尝试检查它的实际实现方式时，令我惊讶的是，我发现这种解决方案并未得到广泛使用。

引用 Kernel Docs - Unreliable Guide To Locking :

Textbooks will tell you that if you always lock in the same order, you will never get this kind of deadlock. Practice will tell you that this approach doesn't scale: when I create a new lock, I don't understand enough of the kernel to figure out where in the 5000 lock hierarchy it will fit.

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

来自赏金文字:

I'm not even sure if I can prove correctness of the presented Boost solution, which seems more tricky than the one with linear order.

Boost 解决方案不能死锁，因为它在已经持有锁的情况下从不等待。除了第一个之外的所有锁都是用 try_lock 获取的。如果任何 try_lock 调用未能获取其锁，则释放所有先前获取的锁。此外，在 Boost 实现中，新的尝试将从上一次获取锁失败开始，并且会先等待直到它可用；这是一个明智的设计决策。

作为一般规则，最好避免在持有锁时阻塞调用。因此，如果可能，最好使用 try-lock 的解决方案(在我看来)。作为一个特殊的结果，在锁定排序的情况下，整个系统可能会卡住。想象一下最后一个锁(例如地址最大的锁)被一个线程获取，然后被阻塞。现在想象一些其他线程需要最后一个锁和另一个锁，并且由于排序，它将首先获得另一个并等待最后一个锁。所有其他锁也可能发生同样的情况，整个系统在最后一个锁被释放之前没有任何进展。当然，这是一种极端且不太可能发生的情况，但它说明了锁排序的内在问题:锁编号越高，获得锁时的间接影响就越大。

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