how to guarantee no deadlock

I was stuck at one question in an interview.

Given two threads, and each one has a lock, how to guarantee no deadlock.

My knowledge is that it is not easy to avoid开发者_StackOverflow中文版 deadlock, that's why I got stuck. Can anybody give a hint.

Thanks!

The description is a bit lacking, but if you impose a locking order (e.g, if the locks are A and B, never lock B unless you already locked A, and never release A while B is locked), then deadlock won't occur.

There are known deadlock avoidance algorithms that can detect if a deadlock is about to occur and avoid the system getting into that state. For example, the Banker's Algorithm.

With a single lock it's not possible to get deadlocked unless one refuses to release their lock -- in which case the waiting thread is called starved. For multiple locks, they must be released in the reverse order that they were acquired, and both threads must agree on the order.

What you are trying to avoid here is this situation:

A has lock 1 waiting on lock 2

B has lock 2 waiting on lock 1

Lock ordering is preferable to timeouts/deadlock detection, but sometimes timeouts are necessary, particularly if you don't control all of the components in the system: hence deadlock timeout/detection in databases. If all of the callers were clever enough, deadlocks would never happen, but commonly not all of the callers are clever enough.

The answer your interviewers were going for is probably WaitForMultipleObjects(). That's a Windows API that locks both (or more) resources simultaneously.

A lot of work on concurrent/parallel programming is focused on lock-free designs. Not an exact answer to your question, but as Andrew already mentioned on this thread, the best way to avoid deadlocks is to not lock at all. A lot of very smart people working on concurrency issues are of that opinion.

These are two standard reasons for Deadlock:

1. Lock-Ordering deadlocks:
   It happens when two threads attempt to acquire the same locks in different order. Sequence will be something like this:
   i) Thread A acquires Lock LEFT
   ii) Thread B acquires Lock RIGHT
   iii) Thread A attempts Lock RIGHT
   iv) Thread B attempts Lock LEFT
   ---> Both will wait forever

   SOLUTION: Review code and make sure there is no cyclic locking dependency. If threads will ask locks in same order deadlock will never happened.

2. Dynamic Lock Order deadlocks: When locks defined at run time and you have no control, scenario like above may still occur causing deadlocks. For example -

   void transferFund( Account A, Account B, Amount x)
   {
       synchronized(A)
       { 
           synchronized(B)
           {
             // do transfer update balance
           }
       }
   }                                                                                  
   

   Sequence for deadlock will be: Thread 1 - transferFund ( A1, B1, 10); Thread 2 - transferFund ( B1, A1, 20);

   Solution: to fix avoid these deadlocks, induce some logic to make sure threads always use same order for acquiring locks. For example -

   if( A1.hashCode()  < B1.hashCode())
     { Lock A1 then Lock B1 }
   else
     { Lock B1 then Lock A1 }
   

NOTE: You can not avoid deadlocks when you are calling alien methods and you have no control how these alien methods are calling locks :(