Dienstprogramme für die Erstellung einer Sperrhierarchie?

Question

Laut den Antworten in Gewinde und einfache Deadlock-Kur und auch Herb Sutter der Schlüssel zur Vermeidung von Deadlocks liegt in der Verwendung von Sperrhierarchien.

Gibt es gute C++-Bibliotheken, die Unterstützung für diese bieten? Ich kann keine in Boost oder Poco finden.

Idealerweise wäre es ein System, das es erlaubt, die Hierarchie zur Kompilierzeit zu definieren. Vielleicht würde es wie folgt aussehen:

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

class BottomMutex { ... };

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

Answer 1

Ja, Sperrhierarchien können Deadlocks wirksam verhindern; ob Sie tatsächlich eine Hierarchie für Ihr Programm definieren können (insbesondere bei Vorhandensein von Plugins), ist natürlich eine ganz andere Frage.

Die Grundbausteine sind einfach:

• Jede Mutex sollte einen Level haben (entweder zur Kompilier- oder zur Laufzeit bestimmt)
• Jeder Thread sollte immer nur einen Mutex in aufsteigender oder absteigender Reihenfolge erwerben (einmalige Entscheidung)

Ich hoffe, ich kann der Idee gerecht werden. Bitte betrachten Sie die Beispielimplementierung unten als Skizze; sie wurde nie kompiliert/getestet.

Ein einfacher Mutex:

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

Le site LevelManager hat lediglich die Aufgabe, dafür zu sorgen, dass die Ebenenübergänge in der richtigen Reihenfolge erfolgen.

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

Zum Spaß habe ich die Möglichkeit implementiert, mehrere Schlösser der gleichen Stufe mit einem einzigen Schuss zu sperren.

Answer 2

Eine separate Klasse zur Verwaltung der Hierarchie ist nicht erforderlich. Eine schöne Lösung findet sich in C++-Gleichzeitigkeit in Aktion , von Anthony Williams ( 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);
}

Answer 3

Das Wichtigste, was Sie in einem solchen Fall tun können, ist sicherzustellen, dass Ihre Sperren immer hierarchisch angewendet werden (d. h. verschachtelt). Auf diese Weise können Sie nicht auf die Sperre der Stufe 3 zugreifen, ohne im Besitz der Sperre der Stufe 2 zu sein, auf die Sie nicht zugreifen können, ohne zuerst die Sperre der Stufe 1 zu besitzen. Sie werden nicht einmal in der Lage sein, zu 3 zu gelangen, ohne zuerst zu 1 und 2 zu gelangen, was größere Probleme verhindern sollte.

Können Sie die Fälle, in denen es zu einer Blockade kommt, näher erläutern? Vielleicht können wir eine Lösung für einige der besonders komplizierten Dinge finden, die nicht so einfach zu manipulieren sind, wie ich es oben beschrieben habe.