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 deadlock, that's why I got stuck. Can anybody give a hint.
Thanks!
+11
A:
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.
Ofir
2010-02-17 21:51:13
Or better still, design for fewer locks.
Andrew
2010-02-17 21:52:03
+1 this is effectively what a lot of modern systems like Linux Kernel's lockdep do. They check to make sure that the locks are always used in the same order. If they aren't, then the system can deadline.
Broam
2010-02-17 21:52:42
+1
A:
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
Joel
2010-02-17 21:53:52
a thread that refuses to release a lock does not trigger a deadlock. The thread in question is still running.
Bahbar
2010-02-17 21:55:21
Bahbar, I believe Joel is saying that with a single lock, a thread that forget to release the lock can prevent another thread from ever making progress. You're right that this is technically not called deadlock, but it's probably still part of the things that the interviewer would care to prevent.
redtuna
2010-02-21 21:08:49
A:
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.
Kevin Won
2010-02-17 21:54:56
A:
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.
phlip
2010-02-17 22:00:45
A:
The answer your interviewers were going for is probably WaitForMultipleObjects(). That's a Windows API that locks both (or more) resources simultaneously.
Seva Alekseyev
2010-02-17 22:01:40
+1
A:
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.
Mike Daniels
2010-02-17 22:03:41