Alex Rivera | Logout

Locking strategies and techniques for preventing deadlocks in code

Asked 2011-05-16T02:16:15.557
35

The common solution to preventing deadlock in code is to make sure the sequence of locking occur in a common manner regardless of which thread is accessing the resources.

For example given threads T1 and T2, where T1 accesses resource A and then B and T2 accesses resource B and then A. Locking the resources in the order they are needed causes a dead-lock. The simple solution is to lock A and then lock B, regardless of the order specific thread will use the resources.

Problematic situation:

Thread1                         Thread2
-------                         -------
Lock Resource A                 Lock Resource B
 Do Resource A thing...          Do Resource B thing...
Lock Resource B                 Lock Resource A
 Do Resource B thing...          Do Resource A thing...

Possible Solution:

Thread1                         Thread2
-------                         -------
Lock Resource A                 Lock Resource A
Lock Resource B                 Lock Resource B
 Do Resource A thing...          Do Resource B thing...
 Do Resource B thing...          Do Resource A thing...

My question is what other techniques, patterns or common practices are used in coding to guarantee dead lock prevention?

c++ design-patterns locking deadlock
Edit
Report

2 Answers

15

Consistent ordering of locking is pretty much the first and last word when it comes to deadlock avoidance.

There are related techniques, such as lockless programming (where no thread ever waits on a lock, and thus there is no possibility of a cycle), but that's really just a special case of the "avoid inconsistent locking order" rule -- i.e. they avoid inconsistent locking by avoiding all locking. Unfortunately, lockless programming has its own issues, so it's not a panacea either.

If you want to broaden the scope a bit, there are methods for detecting deadlocks when they do occur (if for some reason you can't design your program to avoid them), and ways for breaking deadlocks when they do occur (e.g. by always locking with a timeout, or by forcing one of the deadlocked threads to have their Lock() command fail, or even just by killing one of the deadlocked threads); but I think they are all pretty inferior to simply making sure deadlocks cannot happen in the first place.

(btw if you want an automated way to check whether your program has potential deadlocks in it, check out valgrind's helgrind tool. It will monitor your code's locking patterns and notify you of any inconsistencies -- very useful)

answered 2011-05-16T02:39:33.323
3

While not an alternative to the known-sequence solution you mention, Andrei Alexandrescu wrote about some techniques for compile time checks that acquisition of locks is done through the intended mechanisms. See http://www.informit.com/articles/article.aspx?p=25298

answered 2011-05-16T02:55:54.290

Your Answer