I am reading C++ Concurrency in Action and it says that always locking mutexes in a certain order prevents deadlocks. However, this is not a computer science book and no proof is given for this claim. I would like to develop some (more) intuition for why this is, with ideally a proof to convince me.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The four necessity conditions for deadlock are:
- Mutual exclusion
- Hold and Wait
- No preemption
- Circular Wait
Let there be two processes/threads - P1 and P2 and two resources - R1 and R2. Now assume that both resouces must be acquired to perform a certain task T. Assume that requirements 1 to 3 are guaranteed. If you allow the processes to run concurrently to perform T such that P1 tries to acquire R1 first, followed by R2 while P2 acquires the resources in reverse order, then it can happen that P1 is holding R1 while P2 is holding R2. At this point the processes are waiting for the other to release the other resource. You now have circular wait and a deadlock occurs.
Now, if the processes follow the same order of acquisition, only one of then will be able to hold the first resource and the other cannot proceed, hence preventing circular wait and the deadlock.
-
$\begingroup$ Thanks for your answer! This only proves it for two processes. But there can be more than two processes involved in a deadlock. $\endgroup$ Commented Feb 12 at 9:21
-
$\begingroup$ You can extend this for more than 2 processes. If the number of required resources is at least the number of processes, you can arrange the order of acquisition such that each process will take one and wait for another held by some other process. $\endgroup$– RusselCommented Feb 12 at 10:21
$\begingroup$
$\endgroup$
How you get a deadlock: Thread 1 waits for lock A and grabs it. Thread 2 waits for lock B and grabs it. Then thread 1 waits for lock B which is already locked and thread 2 waits for lock A which is already locked. Now both threads are waiting and will not ever release the lock they are already holding, so both threads wait forever.
This is easily solved if both threads take their locks in the same order. Thread 1 and thread 2 both wait for lock A. One is quicker and grabs the lock. The other has to wait until the first thread has completely done its job and eventually releases lock A, but that will happen eventually and both threads finish eventually.
So the deadlock can be prevented by taking locks in the same order. A simple ordering: Assign a level 0, 1, 2 etc. to every lock. Then a thread must not wait for a lock at some level L if it is already holding a lock at the same or a higher level.
