用於創建鎖層次結構的實用程序？

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); 

}