Transactions - How to avoid deadlocks?

Question

I was asked this question in a .net/C# interview:

If we have two threads T1 and T2. T1 acquires a lock on obj1 and then does some processing and acquires a lock on obj2. T2 acquires a lock on obj2 and then does some processing and acquires a lock on obj1. So, we can have a deadlock. What is common technique that we use in multithreading to avoid this situation?

I answered saying that T1 and T2 should have some mechanism to communicate and we should do the coding in such a way that T2 starts doing its job only after T1 has signalled that it is done with its job. The interviewer asked me if I knew about transactions and how we can use it to encounter this deadlock situation. I have some amount of multithreading experience on the UI side in winforms. But, I have never used transactions. Can some one tell me more about this or point me to a url/book,

Answer 1

One general approach to avoid deadlocks is to ensure your threads/processes acquire locks on resources in the same order. eg, T2 should lock obj1 first and then obj2 (the same as T1).

That way you can't have both threads holding a resource that the other thread wants, ie a deadlock.

If the wording in your quote was the exact question, it is badly written. It should be:

T1 acquires a lock on obj1, does something and then tries to also lock obj2 without unlocking obj1. At the same time T2 acquires a lock on obj2, does something and then tries to also lock obj1 without unlocking obj2. A deadlock will occur.

I highly recommend reading Concurrent Programming on Windows by Joe Duffy. It's probably the most comprehensive book on threading theory and practice for Windows.

Answer 2

One approach is that all processes need to acquire all locks at the start of the transaction. If some is not available, the process releases all locks, and retries. Depending on the implementation this can still lead to livelocks though.

To see the problem from the other end, see Dijkstra's banker's algorithm.

Answer 3

I'm not entirely sure where transactions comes directly into this, other than the ability to rollback. The main thing IMO is to aquire the locks in a consistent order, and early; oh, and use a timeout when aquiring locks - don't sit there looking stuck forever.

The reference to transactions makes me think primarily of databases, in which case another consideration is to use tricks like UPDLOCK to ensure you get a write lock initially to avoid issues promoting a (contested) read-lock to a write-lock (changing from a deadlock to simple blocking). Of course, many databases also have better deadlock detection than most regular code.

Answer 4

See http://en.wikipedia.org/wiki/Deadlock

Answer 5

I think, that the thing the interviewer was referring to, is the ability to rollback a transaction. Rollback of the transaction will revert all changes made by the transaction as if the transaction never happened. It will also release all locks obtained by it.

Now let each thread from the example use its own transaction (in database, Vista file system or other interfaces which support transactions). If the deadlock happens (can be easily detected once it happens), you will select one from the threads which are part of the deadlock (victim) and rollback its transaction. This will release the locks so the remaining thread can continue. The victim thread might retry the transaction latter.

If the probability of the deadlock is low relative to the cost of retrying entire transaction, this might be usable solution.