CS 134

Key Points: Deadlock, Deadlock Avoidance, and Concurrency Bugs

Deadlock

  1. Definition: A situation where two or more processes are unable to proceed because each is waiting for the other to release a resource.
  2. Conditions for Deadlock:
    • Mutual Exclusion
    • Hold and Wait
    • No Preemption
    • Circular Wait
  3. Deadlock Prevention:
    • Eliminate one of the four conditions
    • Examples: Eliminate mutual exclusion; use timeouts for resource requests; prevent circular wait by requesting resources in a fixed order

Deadlock Avoidance

  1. Resource-Allocation Graph Algorithm:
    • Processes declare maximum resource needs in advance
    • System only grants requests if it won't lead to an unsafe state
    • Uses a graph to represent resource allocation and requests
  2. Banker's Algorithm (mentioned but not detailed):
    • More advanced algorithm for systems with multiple resources of each type

Atomicity Violations

  1. Definition: Bugs that occur when a program assumes an operation is atomic when it's not
  2. Causes:
    • Not even thinking about atomicity
    • Thinking things will be atomic when they're not
  3. Sequential Consistency:
    • Desired property where operations appear to execute in the order specified by the program
    • Only guaranteed when proper synchronization techniques are used

Order Violations

  1. Definition: Bugs that occur when the order of operations is not what the programmer expects
    • Compiler and hardware optimizations can reorder instructions!
  2. Example: Main thread assuming child threads have started before checking a condition
  3. Prevention: Use explicit synchronization to ensure required ordering

Concurrency Best Practices

  1. Use locks and other synchronization primitives carefully
  2. Be aware of compiler and hardware optimizations that can affect instruction ordering
  3. Don't assume operations are atomic unless explicitly guaranteed
  4. Use explicit synchronization to enforce required ordering between operations

Remember

  • Deadlock requires four conditions to occur simultaneously
  • Deadlock prevention and avoidance are two (very) different approaches to handling deadlock
  • The resource-allocation graph is a powerful tool for visualizing and reasoning about deadlock situations
  • Modern hardware and compilers can reorder instructions in ways that are surprising for concurrent programs
  • Atomicity violations and order violations are subtle bugs that can be hard to detect and reproduce
  • Always use proper synchronization techniques when writing concurrent code
  • Be prepared to draw resource allocation graphs on midterms—they're a classic exam question!

(When logged in, completion status appears here.)