用于创建锁层次结构的实用程序？

Question

根据在Threads and simple Dead lock cure和Herb Sutter中找到的答案，避免死锁的关键是使用锁定层次结构。

是否有任何优秀的C++库为此提供支持？我无法在Boost或Poco中找到任何内容。

理想情况下，它将是一个允许在编译时定义层次结构的系统。也许这应该是这样的：

template<class LowerLevelMutex> 
class RankedMutex { ... }; 

class BottomMutex { ... }; 

typedef RankedMutex<BottomMutex> L1Mutex; 
typedef RankedMutex<L1Mutex> L2Mutex; 
typedef RankedMutex<L2Mutex> L3Mutex; 
// ... 

Answer 1

是的，锁定层次结构可以有效地防止死锁;当然，你是否可以真正为你的程序定义一个层次结构（特别是在存在插件的情况下）完全是另一回事。

基本块是简单：

• 每个互斥应该有一个电平（或在编译时决定或运行时）
• 每个线程应该永远只获取以升序互斥或降序级别（决定一次）

我希望我能做正义的想法，请考虑一下草图下的例子实现;它从未被编译/测试过。

基本互斥：

template <typename Mutex, size_t Level> 
class HierarchicalMutex { 
public: 
    friend class LevelManager; 

    void lock() { 
     LevelManager::Lock(*this); 
    } 

    void unlock() { 
     LevelManager::Unlock(*this); 
    } 

private: 
    size_t previous; 
    Mutex mutex; 
}; // class HierarchicalMutex 

template <typename Mutex, size_t Level> 
size_t level(HierarchicalMutex<Mutex,Level> const&) { return Level; } 

的LevelManager的作用仅仅是为了确保电平转换以正确的顺序发生。

class LevelManager { 
public: 
    // 
    // Single Mutex locking 
    // 
    template <typename M> 
    static void Lock(M& m) { 
     m.previous = LevelUp(level(m)); 
     m.mutex.lock(); 
    } 

    template <typename M> 
    static void Unlock(M& m) { 
     m.mutex.unlock(); 
     LevelDown(level(m), m.previous); 
    } 

    // 
    // Multiple Mutexes Group Locking 
    // 
    // Note: those should expose a "size_t level(M const&)" function, 
    //  and calls to lock/unlock should appropriately call 
    //  this manager to raise/lower the current level. 
    // 
    // Note: mutexes acquired as a group 
    //  should be released with the same group. 
    // 
    template <typename M> 
    static void Lock(std::array_ref<M*> mutexes) { // I wish this type existed 
     using std::begin; using std::end; 

     auto begin = begin(mutexes); 
     auto end = end(mutexes); 

     end = std::remove_if(begin, end, [](M const* m) { return m == 0; }); 

     if (begin == end) { return; } 

     Sort(begin, end); 

     size_t const previous = LevelUp(level(*std::prev(end))); 

     for (; begin != end; ++begin) { 
      begin->previous = previous; 
      begin->mutex.lock(); 
     } 
    } 

    template <typename M> 
    static void Unlock(std::array_ref<M*> mutexes) { 
     using std::begin; using std::end; 

     auto begin = begin(mutexes); 
     auto end = end(mutexes); 

     end = std::remove_if(begin, end, [](M const* m) { return m == 0; }); 

     if (begin == end) { return; } 

     Sort(begin, end); 

     std::reverse(begin, end); 

     for (auto it = begin; it != end; ++it) { it->mutex.unlock(); } 

     LevelDown(level(*begin), begin->previous); 
    } 

private: 
    static __thread size_t CurrentLevel = 0; 

    template <typename It> 
    static void Sort(It begin, It end) { 
     using Ref = typename std::iterator_traits<It>::const_reference; 

     auto const sorter = [](Ref left, Ref right) { 
      return std::tie(level(left), left) < std::tie(level(right), right); 
     }; 

     std::sort(begin, end, sorter); 
    } 

    static size_t LevelUp(size_t const to) { 
     if (CurrentLevel >= to) { throw LockHierarchyViolation(); } 
     CurrentLevel = to; 
    } 

    static void LevelDown(size_t const from, size_t const to) { 
     if (CurrentLevel != from) { throw LockHierarchyViolation(); } 
     CurrentLevel = to; 
    } 
}; // class LevelManager 

踢，我实现锁定同一级别的倍数锁单杆的可能性。

Answer 2

你可以在这种情况下做的主要事情只是确保你的锁总是层次应用（意为嵌套）。这样，如果不拥有2级锁，则无法访问3级锁，如果没有1级锁，则无法访问2级锁。如果没有先到1和2，你甚至无法达到3，所以应该防止出现重大问题。

对于出现的某些死锁情况，您可以更具体一些吗？也许我们可以为一些特别复杂的事情找到解决方法，这些事情可能不像我上面所描述的那样容易操作。

Answer 3

不需要单独的类来管理层次结构。一个很好的解决方案可以在C++并发行动发现，由安东尼·威廉姆斯（ISBN 9781933988771）：

#include <mutex> 
#include <stdexcept> 

class hierarchical_mutex 
{ 
    std::mutex internal_mutex; 
    unsigned long const hierarchy_value; 
    unsigned long previous_hierarchy_value; 
    static thread_local unsigned long this_thread_hierarchy_value; 

    void check_for_hierarchy_violation() 
    { 
     if(this_thread_hierarchy_value <= hierarchy_value) 
     { 
      throw std::logic_error("mutex hierarchy violated"); 
     } 
    } 
    void update_hierarchy_value() 
    { 
     previous_hierarchy_value=this_thread_hierarchy_value; 
     this_thread_hierarchy_value=hierarchy_value; 
    } 
public: 
    explicit hierarchical_mutex(unsigned long value): 
     hierarchy_value(value), 
     previous_hierarchy_value(0) 
    {} 
    void lock() 
    { 
     check_for_hierarchy_violation(); 
     internal_mutex.lock(); 
     update_hierarchy_value(); 
    } 
    void unlock() 
    { 
     this_thread_hierarchy_value=previous_hierarchy_value; 
     internal_mutex.unlock(); 
    } 
    bool try_lock() 
    { 
     check_for_hierarchy_violation(); 
     if(!internal_mutex.try_lock()) 
      return false; 
     update_hierarchy_value(); 
     return true; 
    } 
}; 
thread_local unsigned long 
    hierarchical_mutex::this_thread_hierarchy_value(ULONG_MAX);  

int main() 
{ 
    hierarchical_mutex m1(42); 
    hierarchical_mutex m2(2000); 

}