Deadlock - graph/edge/cycle - help with terminology

This is a discussion on Deadlock - graph/edge/cycle - help with terminology within the C++ Programming forums, part of the General Programming Boards category; Hi all! I'm just wondering about some terminology here. This week the book has been all theory, not providing any ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    121

    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

  2. #2
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Thanks, Crazy, now I have a plan of attack.

    -Patrick

  4. #4
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Sorry, I guess I glanced at 'Crazyfool' and thought that that was your name.

    -Patrick

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    No prob Registered.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Deadlock prevention in C
    By simpatico_qa in forum C Programming
    Replies: 12
    Last Post: 05-04-2009, 01:35 PM
  2. terminology
    By h_howee in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 05-04-2007, 10:36 PM
  3. Can i get a deadlock?
    By johny145 in forum Windows Programming
    Replies: 2
    Last Post: 09-18-2005, 07:43 PM
  4. Deadlock
    By Claudigirl in forum C Programming
    Replies: 2
    Last Post: 11-06-2003, 03:11 PM
  5. Guys, need help RE: deadlock avoidance
    By tribal in forum C++ Programming
    Replies: 2
    Last Post: 11-20-2001, 03:31 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21