This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Wait-for graph" – news · newspapers · books · scholar · JSTOR(May 2023)
In computer science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or prevent deadlock must support a mechanism to detect deadlocks and an algorithm for recovering from them.
One such deadlock detection algorithm makes use of a wait-for graph to track which other processes a process is currently blocking on. In a wait-for graph, processes are represented as nodes, and an edge from process to implies is holding a resource that needs and thus is waiting for to release its lock on that resource. If the process is waiting for more than a single resource to become available (the trivial case), multiple edges may represent a conjunctive (and) or disjunctive (or) set of different resources or a certain number of equivalent resources from a collection. The possibility of a deadlock is implied by graph cycles in the conjunctive case, and by knots in the disjunctive case. There is no simple algorithm for detecting the possibility of deadlock in the final case.[1]
The wait-for-graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.
Referencesedit
^Srinivasan, Selvaraj; Rajaram, Rajeev (January 2011). "A decentralized deadlock detection and resolution algorithm for generalized model in distributed systems". Distributed and Parallel Databases. Tamil Nadu: RMD Engineering College. 29 (4): 261–276. doi:10.1007/s10619-011-7078-7. S2CID 15749022. Retrieved October 21, 2020.
wait, graph, this, article, multiple, issues, please, help, improve, discuss, these, issues, talk, page, learn, when, remove, these, template, messages, this, article, relies, largely, entirely, single, source, relevant, discussion, found, talk, page, please, . This article has multiple issues Please help improve it or discuss these issues on the talk page Learn how and when to remove these template messages This article relies largely or entirely on a single source Relevant discussion may be found on the talk page Please help improve this article by introducing citations to additional sources Find sources Wait for graph news newspapers books scholar JSTOR May 2023 Some of this article s listed sources may not be reliable Please help this article by looking for better more reliable sources Unreliable citations may be challenged or deleted May 2023 Learn how and when to remove this template message Learn how and when to remove this template message A wait for graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems In computer science a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or prevent deadlock must support a mechanism to detect deadlocks and an algorithm for recovering from them One such deadlock detection algorithm makes use of a wait for graph to track which other processes a process is currently blocking on In a wait for graph processes are represented as nodes and an edge from process P i displaystyle P i to P j displaystyle P j implies P j displaystyle P j is holding a resource that P i displaystyle P i needs and thus P i displaystyle P i is waiting for P j displaystyle P j to release its lock on that resource If the process is waiting for more than a single resource to become available the trivial case multiple edges may represent a conjunctive and or disjunctive or set of different resources or a certain number of equivalent resources from a collection The possibility of a deadlock is implied by graph cycles in the conjunctive case and by knots in the disjunctive case There is no simple algorithm for detecting the possibility of deadlock in the final case 1 The wait for graph scheme is not applicable to a resource allocation system with multiple instances of each resource type References edit Srinivasan Selvaraj Rajaram Rajeev January 2011 A decentralized deadlock detection and resolution algorithm for generalized model in distributed systems Distributed and Parallel Databases Tamil Nadu RMD Engineering College 29 4 261 276 doi 10 1007 s10619 011 7078 7 S2CID 15749022 Retrieved October 21 2020 Silberschatz Abraham Galvin Peter Gagne Greg 2003 Operating System Concepts John Wiley amp Sons Inc pp 260 ISBN 0 471 25060 0 nbsp This computer science article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Wait for graph amp oldid 1153050193, wikipedia, wiki, book, books, library,
