Question: In case 2 is it possible to deadlock in the following scenario:
X0: Writes A, Reads B
X1: Writes B, Reads A
In this case, it looks like both X0 and X1 will stall. How is this resolved?
This comment was marked helpful 0 times.
fangyihua
Is case 4 an example of livelock?
This comment was marked helpful 0 times.
TeBoring
@Mayank: In conflict detection, stalling may lead to deadlock. T0 reads X, T1 reads Y, T0 tries to write Y, stalls on T1, while T1 tries to write X, and stalls on T0. To make stalling practical, deadlock avoidance techniques are needed. The Greedy algorithm uses two rules to avoid deadlock: First, if T1 has lower priority than T0, or if T1 is waiting for another transaction, then T1 aborts when conflicting with T0. Second, if T1 has higher priority than T0 and is not waiting, then T0 waits until T1 commits, aborts, or starts waiting (in which case the first rule is applied).
This comment was marked helpful 1 times.
kayvonf
@fanyihua: Yes it is an example of livelock!
This comment was marked helpful 0 times.
mschervi
Question In case 4, why do the processes only perform a "check" after 2 operations? The previous slide says that a check happens after every load and store.
This comment was marked helpful 0 times.
bottie
@mschervi Since the the operations "rdA, wrA" happened on the same processor, it will not incur conflicts, it only need to do one check when all load/store operations are done on one processor.
This comment was marked helpful 0 times.
placebo
In case 2, if X0 makes many more updates to A (before committing) while X1 is stalling, does X1 need to issue the "rd A" command again when it comes out of its stalled state? I think it does, otherwise it would be working with a very outdated copy of the A variable.
This comment was marked helpful 0 times.
lazyplus
Question: In case 4, why the read&write; operation on X1 will restart the transaction on X0?
If the conflict is detected by X1 and X1 is restarted, X0 will proceed and finally commit. No live lock will happen then.
I think it also sounds more reasonable to abort X1 because it comes later than X0.
This comment was marked helpful 0 times.
TeBoring
@lazyplus: Either aborting X1 or aborting X0 can work. Because it uses lazy versioning here, X1 cannot see X0's write. Thus, continue X0 can be correct. Besides, rd wr is atomic. Therefore, X1 didn't check after rd.
Question: In case 2 is it possible to deadlock in the following scenario:
X0: Writes A, Reads B
X1: Writes B, Reads A
In this case, it looks like both X0 and X1 will stall. How is this resolved?
This comment was marked helpful 0 times.
Is case 4 an example of livelock?
This comment was marked helpful 0 times.
@Mayank: In conflict detection, stalling may lead to deadlock. T0 reads X, T1 reads Y, T0 tries to write Y, stalls on T1, while T1 tries to write X, and stalls on T0. To make stalling practical, deadlock avoidance techniques are needed. The Greedy algorithm uses two rules to avoid deadlock: First, if T1 has lower priority than T0, or if T1 is waiting for another transaction, then T1 aborts when conflicting with T0. Second, if T1 has higher priority than T0 and is not waiting, then T0 waits until T1 commits, aborts, or starts waiting (in which case the first rule is applied).
This comment was marked helpful 1 times.
@fanyihua: Yes it is an example of livelock!
This comment was marked helpful 0 times.
Question In case 4, why do the processes only perform a "check" after 2 operations? The previous slide says that a check happens after every load and store.
This comment was marked helpful 0 times.
@mschervi Since the the operations "rdA, wrA" happened on the same processor, it will not incur conflicts, it only need to do one check when all load/store operations are done on one processor.
This comment was marked helpful 0 times.
In case 2, if X0 makes many more updates to A (before committing) while X1 is stalling, does X1 need to issue the "rd A" command again when it comes out of its stalled state? I think it does, otherwise it would be working with a very outdated copy of the A variable.
This comment was marked helpful 0 times.
Question: In case 4, why the read&write; operation on X1 will restart the transaction on X0?
If the conflict is detected by X1 and X1 is restarted, X0 will proceed and finally commit. No live lock will happen then.
I think it also sounds more reasonable to abort X1 because it comes later than X0.
This comment was marked helpful 0 times.
@lazyplus: Either aborting X1 or aborting X0 can work. Because it uses lazy versioning here, X1 cannot see X0's write. Thus, continue X0 can be correct. Besides, rd wr is atomic. Therefore, X1 didn't check after rd.
This comment was marked helpful 0 times.