In his book, C Concurrency in Action, A. Williams introduces the concept of a lock hierarchy as a deadlock-avoidance mechanism. Below, I report a stripped down version of a HierarchicalMutex implementation (taken from the book):

class HierarchicalMutex {
   private:
    std::mutex Mutex_;
    unsigned const Level_;
    unsigned PrevLevel_{0};
    static thread_local unsigned current_level;

   public:
    explicit HierarchicalMutex(unsigned level) : Level_{level} {}

    void lock() {
        if (current_level <= this->Level_) { // (1)
            // I can only lock a mutex with a lower level than the currently
            // locked one.
            throw std::logic_error("lock: Out of order");
        }

        this->Mutex_.lock();
        this->PrevLevel_ = std::exchange(current_level, this->Level_);
    }

    // try_lock implemented accordingly [...]

    void unlock() {
        if (current_level != this->Level_)
            throw std::logic_error("unlock: Out of order");

        current_level = this->PrevLevel_;
        this->Mutex_.unlock();
    }
};

// current_level initialized to UINT_MAX so that, in the beginning, any
// HierarchicalMutex may be locked.
thread_local unsigned HierarchicalMutex::current_level{
    std::numeric_limits<unsigned>::max()};

Les's imagine threads A and B competing to lock an instance of HierarchicalMutex, as shown in the following code:

int main() {
    HierarchicalMutex mutex{1};

    std::thread threadA{[&mutex] { std::scoped_lock sl{mutex}; }};
    std::thread threadB{[&mutex] { std::scoped_lock sl{mutex}; }};

    threadB.join();
    threadA.join();
}

Say that thread A:

• Calls mutex.lock();
• Successfully evaluates check (1) to false;
• Locks HierarchicalMutex::Mutex_;
• Updates HierarchicalMutex::current_level and sets it to 1.

At this point, thread B:

• Calls mutex.lock();
• Evaluates check (1) to true.

This means that thread B will throw; but I'd expect it to wait until thread A unlocks mutex.

My questions are:

1. Is the execution flow I pictured even possible?
2. If so, is it correct for thread B to throw or should it wait for thread A to unlock mutex (as I'd expect)?
3. If my expectation is correct, how should HierarchicalMutex be implemented in order for thread B to wait instead of throwing? Is it enough to replace <= in check (1) with <?

CodePudding user response：

At this point, thread B:

Calls mutex.lock();

Evaluates check (1) to true.

No it won't. current_level is declared as a thread_local object. If you are unfamiliar with what that means, see your C textbook for a more complete discussion, but it boils down that current_level is a separate, discrete object in each execution thread. In both execution threads it's 0, and check (1) evaluates to false.