Skip to main content

Conditions For Deadlock

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives​

  • Explain the main ideas and vocabulary in Conditions For Deadlock.
  • Work through the source examples for Conditions For Deadlock without depending on raw chunk order.
  • Use Conditions For Deadlock as selective reference when learner modules point back to Ostep.

Prerequisites​

  • None curated yet.

Module targets​

  • module-03-concurrency-synchronization

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This unit is anchored to Ostep and the source chapter "Conditions For Deadlock". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment​

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance​

  • Primary source: Ostep
  • Source chapter: Conditions For Deadlock
  • Raw source file: 156-conditions-for-deadlock.md

Merged source​

Conditions For Deadlock​

Conditions for Deadlock

Four conditions need to hold for a deadlock to occur [C+71]:

  • Mutual exclusion:Threads claim exclusive control of resources that they require (e.g., a thread grabs a lock).
  • Hold-and-wait:Threads hold resources allocated to them (e.g., locks that they have already acquired) while waiting for additional resources (e.g., locks that they wish to acquire).
  • No preemption:Resources (e.g., locks) cannot be forcibly removed from threads that are holding them.
  • Circular wait:There exists a circular chain of threads such that each thread holds one or more resources (e.g., locks) that are being requested by the next thread in the chain. If any of these four conditions are not met, deadlock cannot occur.

Thus, we first explore techniques topreventdeadlock; each of these strategies seeks to prevent one of the above conditions from arising and thus is one approach to handling the deadlock problem.

Prevention

Circular Wait

Probably the most practical prevention technique (and certainly one that is frequently employed) is to write your locking code such that you never induce a circular wait. The most straightforward way to do that is to provide atotal orderingon lock acquisition. For example, if there are only two locks in the system (L1andL2), you can prevent deadlock by always acquiringL1beforeL2. Such strict ordering ensures that no cyclical wait arises; hence, no deadlock.

Of course, in more complex systems, more than two locks will exist, and thus total lock ordering may be difficult to achieve (and perhaps is unnecessary anyhow). Thus, apartial orderingcan be a useful way to structure lock acquisition so as to avoid deadlock. An excellent real example of partial lock ordering can be seen in the memory mapping code in Linux [T+94]; the comment at the top of the source code reveals ten different groups of lock acquisition orders, including simple ones such as "imutexbeforeimmapmutex" and more complex orders such as "immapmutexbeforeprivatelockbeforeswaplockbefore

mapping->treelock".

As you can imagine, both total and partial ordering require careful design of locking strategies and must be constructed with great care. Further, ordering is just a convention, and a sloppy programmer can easily ignore the locking protocol and potentially cause deadlock. Finally, lock

TIP: ENFORCELOCKORDERINGBYLOCKADDRESS

In some cases, a function must grab two (or more) locks; thus, we know we must be careful or deadlock could arise. Imagine a function that is called as follows: dosomething(mutext *m1, mutext *m2). If the code always grabsm1beforem2(or alwaysm2beforem1), it could deadlock, because one thread could calldosomething(L1, L2)while another thread could calldosomething(L2, L1).

To avoid this particular issue, the clever programmer can use theaddress of each lock as a way of ordering lock acquisition. By acquiring locks in either high-to-low or low-to-high address order, dosomething()can guarantee that it always acquires locks in the same order, regardless of which order they are passed in. The code would look something like this:

if (m1 > m2) { // grab locks in high-to-low address order
pthread_mutex_lock(m1);
pthread_mutex_lock(m2);
} else {
pthread_mutex_lock(m2);
pthread_mutex_lock(m1);
}
// Code assumes that m1 != m2 (it is not the same lock)

By using this simple technique, a programmer can ensure a simple and efficient deadlock-free implementation of multi-lock acquisition.

ordering requires a deep understanding of the code base, and how various routines are called; just one mistake could result in the "D" word1.

Hold-and-wait

The hold-and-wait requirement for deadlock can be avoided by acquiring all locks at once, atomically. In practice, this could be achieved as follows:

lock(prevention);
lock(L1);
lock(L2);
...
unlock(prevention);

By first grabbing the lockprevention, this code guarantees that no untimely thread switch can occur in the midst of lock acquisition and thus deadlock can once again be avoided. Of course, it requires that any time any thread grabs a lock, it first acquires the global prevention lock. For

example, if another thread was trying to grab locksL1andL2in a different order, it would be OK, because it would be holding the prevention lock while doing so.

1Hint: "D" stands for "Deadlock".

Note that the solution is problematic for a number of reasons. As​

before, encapsulation works against us: when calling a routine, this approach requires us to know exactly which locks must be held and to acquire them ahead of time. This technique also is likely to decrease concurrency as all locks must be acquired early on (at once) instead of when they are truly needed.