创建锁层次结构的工具?

19
根据在线程和简单死锁解决方案Herb Sutter中找到的答案,避免死锁的关键是使用锁层次结构。
是否有任何好的C++库提供此支持? 我在Boost或Poco中找不到任何内容。
理想情况下,它将是一个允许在编译时定义层次结构的系统。也许它会像这样:
template<class LowerLevelMutex>
class RankedMutex { ... };

class BottomMutex { ... };

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

2
正如我在答案中所说,避免死锁没有一种万能的方法,而且一旦发生了,也没有简单的解决办法。最好在设计过程中就避免它。那么你的具体情况是什么? - Platinum Azure
@Platinum Azure:我正在寻找老旧且庞大代码库中死锁问题的解决方案。 - StackedCrooked
1
我什么也没有,很抱歉。 :-( - Platinum Azure
1
你有检查过 boost::recursive_mutex 吗? - Alexandre C.
1
@Alexandre,recursive_mutex仅防止一个线程两次锁定同一互斥量时出现自我死锁。它对于两个线程以相反的顺序锁定两个互斥量无济于事。 - Tim
3个回答

10
是的,锁层次可以有效地防止死锁;当然,能否为您的程序定义一个层次结构(特别是在插件存在的情况下)是完全另一回事。
基本块很简单:
- 每个互斥体都应该有一个级别(在编译时或运行时确定) - 每个线程只应按升序或降序获取互斥体(仅决定一次)
我希望我的想法能得到认可,请考虑下面的示例实现只是一个草图;它从未被编译/测试过。
一个基本的互斥体:
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
< p > < em > 为了好玩,我实现了一次锁定多个相同级别的锁的可能性。

看起来真的很酷。感谢回复。我曾经尝试过使用运行时检查器来检测不一致的锁定顺序,但从未使用过。这是一个我获得了从头开始重写的许可的遗留项目。我选择了无锁的方法。顺便说一句,我独立发明了你所写的这个passkey习惯用法 :) 我正在尝试将其用于线程访问控制。 - StackedCrooked

8

不需要一个单独的类来管理层级关系。一个好的解决方案可以在Anthony Williams的《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);
}

1
在这种情况下,您可以做的主要事情就是确保始终按层次结构应用锁(即嵌套)。这样,您无法在没有拥有第2级锁的情况下访问第3级锁,而要先拥有第1级锁才能访问第2级锁。您甚至无法先到达第3级而不先到达第1和2级,因此这应该可以防止主要问题。
您能否更具体地说明一些可能发生的死锁案例?也许我们可以找到一些特别复杂的事情的解决方法,这些事情可能不像我上面描述的那么容易操作。

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