Imprint | Privacy Policy

MX Challenges

(Usage hints for this presentation)

IT Systems, Summer Term 2024
Dr. Jens Lechtenbörger (License Information)

1. Introduction

2. Deadlocks

2.1. Deadlock

  • Permanent blocking of thread set

  • No generally accepted solution
    • Deadlocks can be perceived as programming bugs
      • Dealing with deadlocks causes overhead
        • Acceptable to deal with (hopefully rare) bugs?
    • Solutions depend on

2.2. Deadlock Example

  • Money transfers between bank accounts
    • Transfer from myAccount to yourAccount by thread 1; transfer in other direction by thread 2
  • Race conditions on account balances
  • Need mutex per account
    • Lock both accounts involved in transfer. What order?
  • “Natural” lock order: First, lock source account; then, lock destination account
    • Thread 1 locks myAccount, while thread 2 locks yourAccount
      • Each thread gets blocked once it attempts to acquire the second lock
        • Neither can continue
      • Deadlock

2.3. Defining Conditions for Deadlocks

Deadlock if and only if (1) – (4) hold (Coffman, Elphick, and Shoshani 1971):

  1. Mutual exclusion
    • Exclusive resource usage
  2. Hold and wait
    • Threads hold some resources while waiting for others
  3. No preemption
    • OS does not forcibly remove allocated resources
  4. Circular wait
    • Circular chain of threads such that each thread holds resources that are requested by next thread in chain

2.4. Resource Allocation Graphs

  • Representation and visualization of resource allocation as directed graph
    • (Necessary prior knowledge: directed graphs and cycles)
    • Nodes

      Figure 4.22 of cite:Hai17

      Figure 4.22 of cite:Hai17” by Max Hailperin under CC BY-SA 3.0; converted from GitHub

      • Threads (squares)
      • Resources (circles)
      • (Choice of shapes is arbitrary, just for visualization purposes)
    • Edges
      • From thread T to resource R if T is waiting for R
      • From resource R to thread T if R is allocated to T
    • Fact: System in deadlock if and only if graph contains cycle

3. Deadlock Strategies

3.1. Ostrich “Algorithm”

  • A joke about missing deadlock handling
    • “Implemented” in most systems
      • Pretend nothing special is happening
      • (E.g., Java acts like ostrich)
    • Reasoning
      • Proper deadlock handling is complex
      • Deadlocks are rare, result from buggy programs

(Refresh HTML presentation for other drawings)

3.2. Deadlock Prevention

  • Prevent a defining condition for deadlocks from becoming true
  • Practical options

    • Prevent condition (2), “hold and wait”: Request all necessary resources at once

      • Only possible in special cases, e.g., conservative/static 2PL in DBMS
      • Threads either have no incoming or no outgoing edges in resource allocation graph → Cycles cannot occur
    • Prevent condition (4), “circular wait”: Number resources, request resources according to linear resource ordering

      • Consider resources R_h and R_k with h < k
        • Threads that need both resources must lock R_h first
        • Threads that already requested R_k do not request R_h afterwards
      • Requests for resources in ascending order → Cycles cannot occur

3.2.1. Linear Resource Ordering Example

  • Money transfers between bank accounts revisited
  • Locks acquired in order of account numbers
    • A programming contract, not known by OS
    • Suppose myAccount has number 42, yourAccount is 4711
      • Both threads try to lock myAccount first (as 42 < 4711)
        • Only one succeeds, can also lock yourAccount
        • The other thread gets blocked
    • No deadlock
  • (See Fig 4.21 in (Hailperin 2019) for an example of linear ordering in the context of the Linux scheduler)

3.3. Deadlock Avoidance

  • Dynamic decision whether allocation may lead to deadlock

    • If a deadlock cannot be ruled out easily: Do not perform that allocation but block the requesting thread (or return error code or raise exception)
    • Consequently, deadlocks do never occur; they are avoided
  • Classical technique

    • Banker’s algorithm by Dijkstra
      • Deny incremental allocation if “unsafe” state would arise
      • Not used in practice
        • Resources and threads’ requirements need to be declared ahead of time

3.4. Deadlock Detection

  • Idea

    • Let deadlocks happen
    • Detect deadlocks, e.g., via cycle-check on resource allocation graph
      • Periodically or
      • After “unreasonably long” waiting time for lock or
      • Immediately when thread tries to acquire a locked mutex
    • Resolve deadlocks: typically, terminate some thread(s)
  • Prerequisite to build graph

    • Mutex records by which thread it is locked (if any)
    • OS records for what mutex a thread is waiting

4. Further Challenges

4.1. Starvation

4.1.1. Dining Philosophers

  • MX problem proposed by Dijkstra
  • Philosophers sit in circle; eat and think repeatedly
    • Two forks required for eating
      • MX for forks

Figure 4.20 of cite:Hai17

Dining Philosophers

Figure 4.20 of cite:Hai17” by Max Hailperin under CC BY-SA 3.0; converted from GitHub

4.1.2. Starving Philosophers

  • Starvation of P0

    Figure 4.20 of cite:Hai17

    Figure 4.20 of cite:Hai17” by Max Hailperin under CC BY-SA 3.0; converted from GitHub

    • P1 and P3 or P2 and P4 eat in parallel
    • Then they wake the other pair
      • P1 wakes P2; P3 wakes P4
      • P2 wakes P1; P4 wakes P3
    • Iterate
    • (Above sequence possible for algorithm in (Tanenbaum 2001); inspired by exercise in (Stallings 2001))

5. Conclusions

5.1. Priority Inversion Example

  • Mars Pathfinder, 1997; Wikipedia offers details
    • Robotic spacecraft named Pathfinder

      Sojourner Rover

      Sojourner Rover” by NASA under Public domain; from Wikimedia Commons

      • With rover named Sojourner (shown to right)
    • A “low-cost” mission at $280 million
  • Bug (priority inversion) caused repeated resets
    • “found in preflight testing but was deemed a glitch and therefore given a low priority as it only occurred in certain unanticipated heavy-load conditions”
  • Priority inversion had been known for a long time

5.2. Summary

  • Concurrent access to resources leads to races
  • Mutual exclusion for critical section prevents races
    • Locks, monitors
    • Keyword synchronized in Java
      • Cooperation via wait() and notify()
  • Challenges such as deadlocks, starvation, priority inversion


Coffman, E. G., M. Elphick, and A. Shoshani. 1971. “System Deadlocks.” Acm Comput. Surv. 3 (2): 67–78.
Hailperin, Max. 2019. Operating Systems and Middleware – Supporting Controlled Interaction. revised edition 1.3.1.
Lampson, Butler W., and David D. Redell. 1980. “Experience with Processes and Monitors in Mesa.” Commun. Acm 23 (2): 105–17.
Stallings, William. 2001. Operating Systems: Internals and Design Principles. 4th ed. Prentice Hall.
Tanenbaum, Andrew S. 2001. Modern Operating Systems. 2nd ed. Prentice-Hall.

License Information

Source files are available on GitLab (check out embedded submodules) under free licenses. Icons of custom controls are by @fontawesome, released under CC BY 4.0.

Except where otherwise noted, the work “MX Challenges”, © 2017-2024 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.