Lock Leveling

• Download TestLock.zip-4.9KB

Introduction

This article introduces the use of lock leveling to prevent deadlocks. Lock leveling is also known as lock ordering, lock ranking and lock hierarchies. Lock leveling always acquire the locks in relative order to prevent deadlocks. Let us look at a simple deadlock example.

void Thread1() { lock lock1(A); { lock lock2(B); {...} } } void Thread2() { lock lock1(B); { lock lock2(A); {...} } }

If Thread1 holds lock A while waiting to hold lock B and at the same time Thread2 holds lock B while waiting to hold lock A, both threads fail to get the locks they want, thus a deadlock occurs.

void Thread1() { lock lock1(A,B); { ... } } void Thread2() { lock lock1(B,A); { ... } }

If we could acquire all the locks at the same time in a atomic operation as shown above, we could solve the problem. However that is not possible. One obvious way to solve this is to always take locks in relative order. One way is to encapsulate the mutex or critical section in a class and add a unique relative number as member to this class. Then lock these mutex or critical section class using a RAII lock class which will always sort the instances of mutex or critical section class before acquiring the lock, so they will always be acquired in the same order. This RAII lock class will release the locks in its destructor. The order of releasing the locks does not matter as releasing the locks does not result in a deadlock. Below is an example of the RAII lock leveling class.

// A RAII lock leveling class class Lock { public: explicit Lock(CritSectLock& a); explicit Lock(CritSectLock& a, CritSectLock& b); explicit Lock(CritSectLock& a, CritSectLock& b, CritSectLock& c); explicit Lock(CritSectLock& a, CritSectLock& b, CritSectLock& c, CritSectLock& d); explicit Lock(CritSectLock& a, CritSectLock& b, CritSectLock& c, CritSectLock& d, CritSectLock& e); ~Lock(void); private: void LockAll(); std::vector<CritSectLock*> m_vec; }; Lock::Lock(CritSectLock& a) { m_vec.push_back(&a); LockAll(); } Lock::Lock(CritSectLock& a, CritSectLock& b) { m_vec.push_back(&a); m_vec.push_back(&b); LockAll(); } Lock::Lock(CritSectLock& a, CritSectLock& b, CritSectLock& c) { m_vec.push_back(&a); m_vec.push_back(&b); m_vec.push_back(&c); LockAll(); } Lock::Lock(CritSectLock& a, CritSectLock& b, CritSectLock& c, CritSectLock& d) { m_vec.push_back(&a); m_vec.push_back(&b); m_vec.push_back(&c); m_vec.push_back(&d); LockAll(); } Lock::Lock(CritSectLock& a, CritSectLock& b, CritSectLock& c, CritSectLock& d, CritSectLock& e) { m_vec.push_back(&a); m_vec.push_back(&b); m_vec.push_back(&c); m_vec.push_back(&d); m_vec.push_back(&e); LockAll(); } struct CritSectLockComp : public std::binary_function<CritSectLock*, CritSectLock*, bool> { bool operator()(CritSectLock* a, CritSectLock*b ) { return ( a->GetIndex() < b->GetIndex() ); } }; void Lock::LockAll() { std::sort(m_vec.begin(),m_vec.end(), CritSectLockComp()); for(size_t i=0; i<m_vec.size(); ++i) { m_vec[i]->Enter(); } } Lock::~Lock(void) { for(size_t i=0; i<m_vec.size(); ++i) { m_vec[i]->Leave(); } }

This is an example on how to use this class.

// Critical section declared elsewhere. CritSectLock a; CritSectLock b; CritSectLock c; .... void foo() { Lock lock(c,b,a); //The order of arguments does not matter // as locks will be acquired in ascending order // your code is below // ...... // a, b and c will be released by lock when its Lock's destructor is called }

References

• Concurrent Programming on Windows by Joe Duffy
• C++ Coding Standards by Herb Sutter and Andrei Alexandrescu

License

This article, along with any associated source code and files, is licensed under The Intelliproject Open License (IPOL)

About the author