Deadlock Modeling (See Fig. 3.2)

Figure 3.2: Resource Allocation Graphs, in the right one, either $P_2$ or $P_4$ could relinquish a resource allowing $P_1$ or $P_3$ (which are currently blocked) to continue.

• Cycle is a necessary condition for a deadlock
• But when dealing with multiple unit resources -not sufficient
• A knot must exist-a cycle with no non-cycle outgoing path from any involved node
• At the moment assume that:
  • a process halts as soon as it waits for one resource,
  • processes can wait for only one resource at a time
• In general, four strategies are used for dealing with deadlocks:
  • Ignore (The Ostrich Algorithm): stick your head in the sand and pretend there is no problem at all.
  • Prevention: design a system in such a way that the possibility of deadlock is excluded a priori (e.g., compile-time/statically, by design)
  • Avoidance: make a decision dynamically checking whether the request will, if granted, potentially lead to a deadlock or not (e.g., run-time/dynamically, before it happens)
  • Detection and Recovery: let the deadlock occur and detect when it happens, and take some action to recover after the fact (e.g., run-time/dynamically, after it happens)

Figure 3.3: An example of how deadlock occurs and how it can be avoided.