Deadlocking Lectures: Refer to AOS Chapter 8 (or Tanenbaum's Chapter 3)

  • Dea01resallocgraph.png  Introduction to deadlock, what it involves, kinds of resources, what's bad about sharing or preempting non-sharable resources, Holt's resource allocation graph on process and resource nodes, meaning of its arrows.
  • Dea02safetyliveness.png  Safety and liveness oppose each other, here's why.  Think of crockadile management policies..
  • Dea03evolresallocgraph.png  Details of how a resource allocation graph evolves as resources are requested and released by processes. When a resource requested by one process is released by another, the arrow representing the request is reversed shortly afterward to represent the granting of that resource to the requestor.
  • Dea04histories.png  Explanation of Tanenbaum's figure 3-4 which demonstrates that some interleavings lead to deadlock and others do not.
  • Dea05condstrats.png  Coffman's (1971) 4 conditions for deadlock. Strategies for dealing with the deadlock problem.
  • Dea06detectrecover.png  Deadlock detection. Strategies for recovery after detection:
  • Dea07avoidance.png  Deadlock avoidance is a dynamic strategy. Safe state defined. Safe states explained in terms of a resource trajectory around conflict regions.
  • Dea08prevention.png  Deadlock prevention is done by design of system structure so that one (or more) of Coffman's conditions is falsified. More sophisticated locks such as read-write locks and other strategies like spooling reduce the requirements for mutual exclusion and so lead to more concurrency. The wait and hold condition is attacked by rollback when a lock is held typically combined with 2 phase locking in some database designs. The circular wait condition is attacked by programs that respect a predetermined hierarchy (or partial order) of locks.

    • Next Lecture:
  • Dea09deadlockDefIntSyscalls.png  Deadlock definition discussed. Remarks on modeling. Extending the definition to model situations where there are threads with or without processes too. Details of how you can program systems to break out of deadlocks by the use of Unix signals: If a signal is caught, a blocked syscall will return as an interrupted system call.
  • Review and coverage of the resource trajectory graph with its forbidden regions.. Dea07avoidance.png
  • Dea9.5TwoPhaseLock.png(under construction) Introduction to concurrency in database systems, the transaction model where each entire transaction is performed in a way that appears atomic or is aborted, so it is if none of its operations were performed at all. The the use of 2-phase locking in structuring transactions to avoid deadlock.

  • Dea10DetRecoverFlow.png  Role of the deadlock detection and recovery strategy in system operation explained with a flowchart.
  • Depth-first-search (For more coverage of this and similar topics take the Algorithms course CSI403.)
  • Let's now use AOS Slides for Chapter 8, begin with slide 15..
  • Deadlock Avoidance using the Resource Allocation Graph: Record the information that Pi might request resource Rj by a claim edge (dotted) from Pi to Rj. The RAG represents a safe state if and only if it (regular and claim edges together) has no directed cycle. EXAMPLE (I think OSCJ's example is wrong...)
  • Let's now use AOS Slides for Chapter 8, begin with slide 15..
  • Demo of the Banker's Algorithm--OSCJ section (8.5.3.3).
  • Dea14avoidanceFlow.png  Role of the dynamic deadlock avoidance in system operation explained with a flowchart. Safe state definition reviewed.
  • Dea15bankerDemo.png  Demonstration of Dijkstra's banker's algorithm and it's description from Tanenbaum.
  • Dea16bankerRemarkNoDefaulti.png   Remark on the banker's algorithm: The banker assumes no borrower will default.