Wait-for graph

Wait-for graph

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 to P_j implies P_j is holding a resource that P_i needs and thus P_i is waiting for P_j to release its lock on that resource.

References

cite book
last = Silberschatz
first = Abraham
coauthors = Peter Galvin, Greg Gagne
title = Operating System Concepts
publisher = John Wiley & Sons, INC.
date = 2003
pages = 260
isbn = 0-471-25060-0


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Dominator (graph theory) — For Dominating set problem, see Dominating set. In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n (or sometimes d n). By… …   Wikipedia

  • Business Process Execution Language For Web Services — Die WS Business Process Execution Language (BPEL) ist eine XML basierte Sprache zur Beschreibung von Geschäftsprozessen, deren einzelne Aktivitäten durch Webservices implementiert sind. Die im Jahr 2002 von IBM, BEA Systems und Microsoft… …   Deutsch Wikipedia

  • Commitment ordering — In concurrency control of databases, transaction processing (transaction management), and related applications, Commitment ordering (or Commit ordering; CO; (Raz 1990, 1992, 1994, 2009)) is a class of interoperable Serializability techniques …   Wikipedia

  • Serializability — In concurrency control of databases,[1][2] transaction processing (transaction management), and various transactional applications (e.g., transactional memory[3] and software transactional memory), both centralized and distributed, a transaction… …   Wikipedia

  • Deadlock — This article is about the computer science concept. For other uses, see Deadlock (disambiguation). A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often… …   Wikipedia

  • Feedback vertex set — In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.… …   Wikipedia

  • Two-phase locking — This article is about concurrency control. For commit consensus within a distributed transaction, see Two phase commit protocol. In databases and transaction processing two phase locking, (2PL) is a concurrency control method that guarantees… …   Wikipedia

  • Edge chasing — In computer science, edge chasing is an algorithm for deadlock detection in distributed systems. Whenever a process A is blocked for some resource, a probe message is sent to all processes A may depend on. The probe message contains the process… …   Wikipedia

  • WFG — may refer to: *World Financial Group *Wait For Graph …   Wikipedia

  • Coffee preparation — For the agricultural and industrial processes for producing whole coffee beans, see Coffee processing. Coffee preparation is the process of turning coffee beans into a beverage. While the particular steps needed vary with the type of coffee… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”