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.