What are wait-for-graphs, Database Management System

Assignment Help:

What are wait-for-graphs?Give the algorithm to construct a wait-for-graph from a given schedule of transactions? How can deadlocks be detected from wait-for-graphs? 

 Ans:  The wait-for-graph is a directed graph and consists of nodes and directed arcs; the nodes of the graph are active transactions. An arc of the graph is inserted among two nodes if there is a data-item is needed by the node at the tail of the arc that is being held by the node at the head of the arc. 

  Algorithm to construct wait-for-graph is as follows:

1.  For every transaction Ti active at the time of deadlock detection, make a node labeled Ti in the wait-for-graph.

2.  For every case, if there is a transaction Ti, waiting for a data-item that is at present allocated and held by transaction Tj, then there is a directed arc from the node for transaction Ti, to the node for transaction Tj.

3.  For every case, if there is a directed arc from the node for transaction Ti, to the node for transaction Tj and transaction Tj released the lock, after that remove the arc between them.

4.  There no deadlock if the wait-for-graph is acyclic.  

The wait-for-graph is employed for detection of deadlock in the system. If there is any cycle exits in the wait-for-graph, all the active transaction (denoted as nodes) are in deadlock that are in the cycle.


Related Discussions:- What are wait-for-graphs

What is a recursive relationship, Question: (a) Can a set of data requi...

Question: (a) Can a set of data requirements be correctly modelled by two or more different ER diagrams? Explain your answer. You may use a small example, if you think it will

Relational schema for person, Example: RELATIONAL SCHEMA for PERSON: ...

Example: RELATIONAL SCHEMA for PERSON: PERSON (PERSON_ID: integer, NAME: string, AGE: integer, ADDRESS: String) RELATION INSTANCE In this instance, m = 3 and n = 4

How the one-to-one associations have to be implemented, Discuss how the one...

Discuss how the one-to-one associations have to be implemented. Some of properties of associations can be implemented directly by providing suitable declarations of the data me

CMIS 420 Homework Assignment 2, describe all the tables you have created. ...

describe all the tables you have created. ?get table_name, status, num_rows, user_stats in user_tables system view ?get table_name, constraint_name, constraint_type in user_constr

State the technique for converting a state diagram to code, Q. State the Te...

Q. State the Technique for converting a state diagram to code. i) Identify the major control path. Starting with first state, find the path from diagram that corresponds

Abstract data structures, The C_Artist  application will be developed using...

The C_Artist  application will be developed using the C language (C99 standards) and will be able to compile without warnings and link and run in the Swinburne computer laboratorie

Write a short note on participation role, write a short note on participati...

write a short note on participation role? Participation role: roles are indicating in E-R diagram by labelling the lines that connect diamonds to rectangles.

Mysql, he SQL query that will return the order number, quantity ordered, pr...

he SQL query that will return the order number, quantity ordered, price each and total cost of an order (quantity * price each) from the order details table. Label the calculated c

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd