# Deadlock - graph/edge/cycle - help with terminology

• 11-23-2006
patricio2626
Deadlock - graph/edge/cycle - help with terminology
Hi all! I'm just wondering about some terminology here. This week the book has been all theory, not providing any real-life examples, so I need some clarification. We are studying graphs, and I do know what graphs, edges, cycles, the different types of graphs are, but it does me no good if I can't apply this knowledge to a C++ program. I understand that certain transactions (read or write, for example) can put locks on data, but not sure where edges and cycles come in. I'll give the wording of a question in the book, and write what I suspect it may mean:

To detect a deadlock, a wait-for-graph is constructed to show which transaction waits for which. Use a binary locking mechanism to implement a wait-for graph. In this mechanism, if a record R is accessed by a transaction T, the T puts a lock on R and this record cannot be processed by any other transaction before T is finished. Release all locks put on by a transaction T when T finishes. The input is composed of the following commands: read(T, A), write(T, A), end(T)). For example, if input is read(T1, A1), read(T2, A2), read(T1, A2), write(T1, A2), end(T1)... then T1 is suspended when attempting to execute the step read(T1, A2), and edge(T1, T2) is created, because T1 waits for T1 to finish. If T1 does not have to wait, resumed its execution. After each graph update, check for a cycle in the graph. If a cycle is detected, interrupt execution of the youngest transation T and put its steps at the end of the input.

My questions:
1) why is the edge(T1, T2) created? Is it because T1 is waiting for T2 to release the lock on A2, which read(T1, A2) is trying to access?
2) when it talks about 'graph update', does this mean the edges that you add up depending on the wait list?
3) would an example of a cycle as they have it here be: T1 is waiting on T2, T2 is waiting on T3, T3 is waiting on T1?

As usual, thanks a ton! I appreciate all of your input.

-Patrick
• 11-23-2006
Perspective
1. Yes.
2. A graph update is everytime you modify the graph (add or remove an edge)
3. Yes, that is a cycle. Anytime you can start at one node and get back to the same node by following the directed edges, you have a cycle.
• 11-24-2006
patricio2626
Thanks, Crazy, now I have a plan of attack.

-Patrick
• 11-24-2006
patricio2626
Sorry, I guess I glanced at 'Crazyfool' and thought that that was your name.

-Patrick
• 11-24-2006
Perspective
No prob Registered.