Mutexes are used to prevent multiple threads from causing a data race by accessing the same shared resource at the same time. Sometimes, when locking mutexes, multiple threads hold each other's lock, and the program consequently deadlocks. Four conditions are required for deadlock to occur:
- mutual exclusion (At least one nonshareable resource must be held.),
- hold and wait (A thread must hold a resource while awaiting availability of another resource.),
- no preemption (Resources cannot be taken away from a thread while they are in-use.), and
- circular wait (A thread must await a resource held by another thread which is, in turn, awaiting a resource held by the first thread.).
Deadlock needs all four conditions, so preventing deadlock requires preventing any one of the four conditions. One simple solution is to lock the mutexes in a predefined order, which prevents circular wait.
Noncompliant Code Example
The behavior of this noncompliant code example depends on the runtime environment and the platform's scheduler. The program is susceptible to deadlock if thread
thr1 attempts to lock
ba2's mutex at the same time thread
thr2 attempts to lock
ba1's mutex in the
Compliant Solution (Manual Ordering)
This compliant solution eliminates the circular wait condition by establishing a predefined order for locking in the
deposit() function. Each thread will lock on the basis of the
BankAccount ID, which is set when the
BankAccount object is initialized.
Compliant Solution (
This compliant solution uses Standard Template Library facilities to ensure that deadlock does not occur due to circular wait conditions. The
std::lock() function takes a variable number of lockable objects and attempts to lock them such that deadlock does not occur [ISO/IEC 14882-2014]. In typical implementations, this is done by using a combination of
unlock() to attempt to lock the object and backing off if the lock is not acquired, which may have worse performance than a solution that locks in predefined order explicitly.
Deadlock prevents multiple threads from progressing, halting program execution. A denial-of-service attack is possible if the attacker can create the conditions for deadlock.
|CONCURRENCY.LOCK.ORDER||Conflicting lock order|
Do not acquire locks in different order
|Polyspace Bug Finder|
|CERT C++: CON53-CPP||Checks for deadlocks|
|1772, 1773||Enforced by MTA|
|CERT Oracle Secure Coding Standard for Java||LCK07-J. Avoid deadlock by requesting and releasing locks in the same order|
|MITRE CWE||CWE-764, Multiple Locks of a Critical Resource|
Subclause 30.4, "Mutual Exclusion"