Threads and simple Dead lock cure

Question

When dealing with threads (specifically in C++) using mutex locks and semaphores is there a simple rule of thumb to avoid Dead Locks and have nice clean Synchronization?

Answer 1

Try to avoid acquiring one lock and trying to acquire another. This can result into circular dependency and cause for deadlock. If it is un-avoidable then at least the order of acquire locks should be predictable.

Use RAII ( to make sure lock is release properly in case of exception as well)

Answer 2

There is no simple deadlock cure.

Acquire locks in agreed order: If all calls acquire A->B->C then no deadlock can occur. Deadlocks can occur only if the locking order differs between the two threads (one acquires A->B the second B->A).

In practice is hard to choose an order between arbitrary objects in memory. On a simple trivial project is possible, but on large projects with many individual contributors is very hard. A partial solution is to create hierarchies, by ranking the locks. All locks in module A have rank 1, all locks in module B have rank 2. One can acquire a lock of rank 2 when helding locks of rank 1, but not vice-versa. Of course you need a framework around the locking primitives that tracks and validates the ranking.

Answer 3

1. If at all possible, design your code so that you never have to lock more then a single mutex/semaphore at a time.
2. If that's not possible, make sure to always lock multiple mutex/semaphores in the same order. So if one part of the code locks mutex A and then takes semaphore B, make sure that no other part of the code takes semaphore B and then locks mutex A.

Answer 4

A good simple rule of thumb is to always obtain your locks in a consistent predictable order from everywhere in your application. For example, if your resources have names, always lock them in alphabetical order. If they have numeric ids, always lock from lowest to highest. The exact order or criteria is arbitrary. The key is to be consistent. That way you'll never have a deadlock situation. eg.

1. Thread 1 locks resource A
2. Thread 2 locks resource B
3. Thread 1 waits to obtain a lock on B
4. Thread 2 waits to obtain a lock on A
5. Deadlock

The above can never happen if you follow the rule of thumb outlined above. For a more detailed discussion, see the Wikipedia entry on the Dining Philosophers problem.

Answer 5

There's no practical cure. Specifically, there's no way to simply test code for being synchronizationally correct, or to have your programmers obey the rules of the gentleman with the green V.

There's no way to properly test the multithreaded code, because the program logic may depend on timing of locks acquisition, and therefore, be different from execution to execution, somehow invalidating the concept of QA.

I would say

• prefer using threads only as a performance optimization for multi-core machines
• only optimize performance when you are sure you need this performance
• you may use threads to simplify program logic, but only when you are absolutely sure what you are doing. Be extra careful and all locks are confined to a very small piece of code. Do not let any newbies near such code.
• never use threads in a mission-critical system, such as flying an aircraft or operating dangerous machinery
• in all cases, threads are seldom cost-effective, due to higher debug and QA costs

If you determined to do threads or maintaining existing codebase:

• confine all locks to small and simple pieces of code, which operate on primitives
• avoid function calls or getting the program flow away to where the fact of being executed under lock is not immediately visible. This function will change by future authors, widening your lock span without your control.
• get locks inside objects to reduce locking scope, wrap non-thread-safe 3rd-party objects with your own thread-safe interfaces.
• never send synchronous notifications (callbacks) when executing under lock
• use only RAII locks, to reduce the cognitive load when thinking "how else can we exit from here", as in exceptions, etc.

A few words on how to avoid multi-threading.

A single-threaded design usually involves some heart-beat function provided by program components, and called in a loop (called heartbeat cycle) which, when called, gives a chance to all components to do the next piece of work and to surrender control back again. What algorithmists like to think of as "loops" inside the components, will turn into state machines, to identify what is the next thing that should be done when called. State is best maintained as member data of respective objects.

Answer 6

There are plenty of simple "deadlock cures". But none that are easy to apply and work universally.

The simplest of all, of course, is "never have more than one thread".

Assuming you have a multithreaded application though, there are still a number of solutions:

You can try to minimize shared state and synchronization. Two threads that just run in parallel and never interact can never deadlock. Deadlocks only occur when multiple threads try to access the same resource. Why do they do that? Can that be avoided? Can the resource be restructured or divided so that for example, one thread can write to it, and other threads are asynchronously passed the data they need?

Perhaps the resource can be copied, giving each thread its own private copy to work with?

And as already mentioned by every other answer, if and when you try to acquire locks, do so in a global consistent order. To simplify this, you should try to ensure that all the locks a thread is going to need are acquired as a single operation. If a thread needs to acquire locks A, B and C, it should not make three lock() calls at different times and from different places. You'll get confused, and you won't be able to keep track of which locks are held by the thread, and which ones it has yet to acquire, and then you'll mess up the order. If you can acquire all the lock you need once, then you can factor it out into a separate function call which acquires N locks, and does so in the correct order to avoid deadlocks.

Then there are the more ambitious approaches: Techniques like CSP make threading extremely simple and easy to prove correct, even with thousands of concurrent threads. But it requires you to structure your program very differently from what you're used to.

Transactional Memory is another promising option, and one that may be easier to integrate into conventional programs. But production-quality implementations are still very rare.