Results 1 to 2 of 2
  1. #1
    Join Date
    Oct 2009
    Posts
    1

    Serializability graphs

    Hi guys,

    I'm new to the forum and was wondering if i could maybe get some help.

    I've just started back at uni after some time off and have run straight into my first wall. Precedence graphs.

    I was just wondering if someone could please help me understand them, i thought i'd learn it over the weekend and then i wouldn't feel behind when i went into lectures next week.

    1)
    read(T1, balx), read(T2, balx), wright(T3, balx), read(T2, balx), read(T1, baly), commit(T1), commit(T2)

    2)
    read(T1, balx), write(T2, balx), wright(T1, balx), read(T3, balx), commit(T1), commit(T2), commit(T3)

    I have the ansewrs for these as we went through them in the class but i just have absolutly no idea of how to read this information and draw the Precedence graphs for these schedules

    It's stressing me out big time and making me feel really thick.

    Any help would be greatly appreciated

    Danny

  2. #2
    Join Date
    Oct 2002
    Location
    Baghdad, Iraq
    Posts
    697
    Hmm, I did most of my concurrence stuff in Java. But the same general principles apply, and most of it is common sense in the end.

    What you're trying to do is reorder a set of actions so that the effects on the data are the same as if each transaction had executed one at a time, with each completing before the next began.

    read(T1, bollocks), read(T2, bollocks), write(T3, bollocks), read(T2, bollocks), read(T1, baly), commit(T1), commit(T2)

    Anyhow, in this case we've got three transactions contending for the table "bollocks." (I renamed it to differentiate from baly.)
    • First T1 reads from bollocks, then T2 reads from bollocks.
    • T3 next writes to bollocks, meaning that T1 and T2 are seeing a different view of bollocks than T3.
    • T2 again reads from bollocks. Okay, so do you think T2 sees the same data or what T3 has written?
    • T1 reads from baly and then T1 and T2 commit for no apparent reason.
    What if we express it like this:

    read(T1, bollocks), read(T1, baly), commit(T1), read(T2, bollocks), read(T2, bollocks), commit(T2), write(T3, bollocks)

    This is what would happen if each transaction were executed serially, and the aim of the graph is to figure out what needs to be locked down or rescheduled to simulate that happening. (This example doesn't help because it's kinda pointless; you don't generally commit transactions that only read.)

    Next question:

    read(T1, bollocks), write(T2, bollocks), write(T1, bollocks), read(T3, bollocks), commit(T1), commit(T2), commit(T3)

    Okay, now you can see that T3 must depend on T1 and T2 since they both wrote, and T1 also depends on T2 since it is writing. Again, to serialize it would look like so:

    read(T1, bollocks), write(T1, bollocks), commit(T1), write(T2, bollocks), commit(T2), read(T3, bollocks), commit(T3)

    If you get that, and you figure out just what they're talking about as far as conflicts it should be pretty straightforward to draw up the graph of which transaction is possibly conflicting with other transactions. It's really just a question of whether or not one transaction writing to a table will screw up another transaction, and from that you can figure out how to schedule the reads and writes properly.

    Again, it's been a while since I did stuff kinda sorta related to this, so I hope I haven't wound up confusing you more.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •