Tip: Lock Leveling

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

Below is an example on how to use the Lock class.

// CritSectLock instances are declared elsewhere
CritSectLock a;
CritSectLock b;
CritSectLock c;

void foo()
{
	Lock lock(c,b,a); // The order of the arguments doesn't matter
	// as a, b and c will acquired in a ascending order.
	
	// Your code is here.
	//....
	
	// a, b and c will be released by the destructor of Lock calss
}

References



About the Author

Wong Shao Voon

I guess I'll write here what I does in my free time, than to write an accolade of skills which I currently possess. I believe the things I does in my free time, say more about me.

When I am not working, I like to watch Japanese anime. I am also writing some movie script, hoping to see my own movie on the big screen one day.

I like to jog because it makes me feel good, having done something meaningful in the morning before the day starts.

I also writes articles for CodeGuru; I have a few ideas to write about but never get around writing because of hectic schedule.

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: August 14, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT Data protection has long been considered "overhead" by many organizations in the past, many chalking it up to an insurance policy or an extended warranty you may never use. The realities of today makes data protection a must-have, as we live in a data-driven society -- the digital assets we create, share, and collaborate with others on must be managed and protected for many purposes. Check out this upcoming eSeminar and join Seagate Cloud …

  • Event Date: April 15, 2014 The ability to effectively set sales goals, assign quotas and territories, bring new people on board and quickly make adjustments to the sales force is often crucial to success--and to the field experience! But for sales operations leaders, managing the administrative processes, systems, data and various departments to get it all right can often be difficult, inefficient and manually intensive. Register for this webinar and learn how you can: Align sales goals, quotas and …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds