MX Challenges

(Usage hints for this presentation)

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

Chair of Data Science: Machine Learning and Data Engineering (Prof. Gieseke)
Dept. of Information Systems
University of Münster, Germany

1. Introduction

2. Deadlocks

2.1. Deadlock

Permanent blocking of thread set
“Gridlock” by Interiot~commonswiki and Jeanacoa under CC BY-SA 2.5 Generic; from Wikimedia Commons
- Reason
  - Cyclic waiting for resources/locks/messages of other threads
  - (Formal definition on later slide)
A deadlock is a programming bug, which leads to multiple threads being stuck: In essence, the threads mutually wait for something from other threads which never arrives.

To get a feeling for deadlocks, note that some traffic situations can be interpreted as deadlocks. First, the image here shows a traffic situation where no car can move because other cars (in particular, the red ones) block required street segments. In OS terms, the cars can be interpreted as threads, which are stuck, while street segments represent shared resources under MX that are exclusively owned by some threads while others also need them. This is an instance of cyclic waiting.

As a different example, consider priority to the right and a street crossing where four cars arrive from all four directions. Under “priority to the right”, each driver needs to wait for another car to move first. Thus, neither can move, all are stuck.

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
  - Properties of resources (e.g., linearly ordered ones)
  - Properties of threads (transactions?)

In programming, we aim to avoid problematic algorithms or rules such a “priority to the right” so that deadlocks do not occur. However, there is no generally accepted solution, and you need to be particularly careful when using MX mechanisms.

As you will see, OSs typically ignore deadlocks, which is justified by the reasoning that programmers should avoid this type of bug; thus, there is no need to add additional complexity and overhead to the OS. Moreover, solutions also depend on the type of resources, e.g., you will see a strategy for linearly ordered resources later on.

As a side note, database systems may involve deadlock detection for transactions, which can be aborted to undo their effects, while this is less simple for threads in OSs. Thus, thread properties also play a role in deadlock considerations.

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):

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

As stated on this slide, a deadlock exists precisely when four conditions hold:

First, resources are used under MX.

Second, the threads involved in the deadlock hold some resources while waiting for others.

Third, the OS does not forcibly remove allocated resources.

Fourth, the threads can be arranged in a circular chain such that each thread holds resources for which the next thread in the chain waits.

In the deadlock example about money transfers above, we have two threads and two accounts protected by locks. The four conditions hold as follows: First, accounts are locked exclusively.

Second, each thread holds one lock while waiting for a second lock.

Third, locks are never removed by the OS. Instead, threads may release them.

Fourth, both threads wait for each other.

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” 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.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

A strategy for deadlocks is called prevention strategy if it prevents deadlocks from happening by making sure that one of the four defining deadlock conditions can never become true. Although there are four conditions, only two of them are used for practical purposes, and they are explained in the subsequent bullet points.
- 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
  Some systems may prevent the “hold and wait” condition from becoming true. One example are database systems with variants of the two-phase locking protocol, where transactions either acquire all resources they need, or none at all. Clearly, such transactions either hold or wait, preventing cycles in resource allocation graphs.
- 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
  For programmers, preventing the “circular wait” condition is a usual choice. This is possible if resources can be numbered linearly. If a thread needs multiple resources, it acquires them according to their linear order.
  
  Then, edges in resource allocation graphs can never “go back”, which would be necessary to close cycles.

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

(See stackexchange for difference between prevent and avoid)

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
The typical approach is to analyze resource requests by threads. If some deadlock avoidance algorithm is able to rule out a deadlock for the resulting state, the request will be granted. If the algorithm is not able to rule out deadlocks, the request will not be granted. Note that such algorithms generally err on the safe side. Thus, some requests might not be granted, although they would not cause any deadlock; the OS might be unable to detect this, though.
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
A famous deadlock avoidance technique is Dijkstra’s banker’s algorithm, which has quite restrictive preconditions and is therefore not used in practice.

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)
The final strategy for dealing with deadlocks is deadlock detection. Here, the system does not take special precautions to avoid or prevent deadlocks but lets them happen. To deal with deadlocks, they are detected, for example based on cycle checks on resource allocation graphs, and then resolved. Detection may take place periodically or after waiting times or even immediately upon resource requests; the latter actually prevents cyclic wait conditions, moving from deadlock detection to deadlock prevention.

To resolve deadlocks, the OS typically terminates some threads until no cycle exists any longer, and various strategies exist to select victim threads, which is beyond our topics.

Prerequisite to build graph
- Mutex records by which thread it is locked (if any)
- OS records for what mutex a thread is waiting
Clearly, the OS needs to build suitable data structures for deadlock detection, in case of resource allocation graphs, each mutex can easily record by which thread it is locked, while the OS also keeps track of what threads are waiting for what mutexes.

4. Further Challenges

4.1. Starvation

A thread starves if its resource requests are repeatedly denied
Examples in previous presentations
- Interrupt livelock
- Thread with low priority in presence of high priority threads
- Thread which cannot enter CS
  - Famous illustration: Dining philosophers (next slide)
  - No simple solutions

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” 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” 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
- E.g.: (Lampson and Redell 1980)

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

Bibliography

Coffman, E. G., M. Elphick, and A. Shoshani. 1971. “System Deadlocks.” Acm Comput. Surv. 3 (2): 67–78. https://doi.org/10.1145/356586.356588.

Hailperin, Max. 2019. Operating Systems and Middleware – Supporting Controlled Interaction. revised edition 1.3.1. https://gustavus.edu/mcs/max/os-book/.

Lampson, Butler W., and David D. Redell. 1980. “Experience with Processes and Monitors in Mesa.” Commun. Acm 23 (2): 105–17. https://doi.org/10.1145/358818.358824.

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.