A deadlock in a resource allocation graph can be detected by executing a graph reduction algorithm by repeating this process:

  1. Select an unblocked process p.
  2. Remove p, including all request and allocation edges connected to p.

Anything left is blocked, and risks deadlock. However, it is considered completely reducible if there are no processes left on the graph after they have been removed.

Testing for deadlock can be accomplished more efficiently if done on a continuous basis. If the current state is not deadlocked, then the next state can be a deadlock state only if

  • the operation that caused the transition was a request for a resource and
  • the process that issued the request is deadlocked in the next state.

A wait-for graph is a resource allocation graph containing only processes that can have multiple incoming resource allocation edges but only one outgoing resource request edge.

Deadlock Detection was originally found on Access 2 Learn

Assistant Professor

Walter Wimberly is an Assistant Professor at a regional college in Tennessee, teaching Computer Science in the Software Engineering track. He works as a student advisor, oversees curriculum changes, develops new courses, and manages the advisory panel.
Walter taught full time for about 7 years, before going back into “industry” as a full stack Software Developer for a dozen years. There he focused on web based projects coding in JavaScript/jQuery and utilizing the Bootstrap CSS Framework on the front-end, and coding in PHP, ASP/ASP.Net, SQL on the back-end.

Since he loves teaching, he taught as an adjunct web and digital media classes for eight (8) years, while working in industry, and has since returned to teaching full time.

He has been married for over 25 years, and is father to several special needs boys. As such, he is working on some projects to help others who have special needs to be self-sufficient, and support the care givers of those with special needs. Check out his Autism blog for more info.

Similar Posts

Page Replacement with Fixed # of Frames

ByWalter Wimberly

A reference string is the sequence of page numbers referenced by an executing program during a given time interval. Reference strings are used to compare different page replacement algorithms by counting the number of page faults generated. Since page faults are time consuming, the optimal page replacement algorithm selects the page that will not be referenced for the longest…

Memory Paging

ByWalter Wimberly

The main disadvantage of dividing memory into variable partitions is external fragmentation, which requires the searching of memory for holes large enough to satisfy each request. As we’ve mentioned previously, swapping or compaction is necessary when no hole large enough is available. A page is a fixed-size contiguous block of a logical address space identified by the…

Classic Synchronization Problems

ByWalter Wimberly

The Readers-Writers Problem The readers-writers problem is an extension of the critical section problem where two types of processes, readers and writers. However, it involves an interesting issue when the processes compete for access to a common resource. Multiple readers are allowed to enter the critical section concurrently but only one writer is allowed to…