CSc 417 - Assignment 7, concurrency
Due Monday 10 April 2006
Timestamping, 18.8.1
(p. 978) Fot these sequences of events, tell what happens as each
executes. st indicates
start, timestamps will be allocated in the order of starts. You will
want to keep track of the read and write timestamps for each data
element.
(b) st1;
r1(A); st2 w2(B); r2(A); w1(B);
(c) st1;
st2;
st3; r1(A); r2(B); w1(C); r3(B);
r3(C); w2(B); w3(A);
Multiversion Timestamping, 18.8.2
Same idea, but each write creates a new version, with its own read and
write timestamps. (Don't consider "what if there weren't
multi-versions.")
(b) st1;
st2;
st3; st4; w1(A); w3(A); r4(A);
r2(A);
(c) st1;
st2; st3; st4; w1(A); w4(A);
r3(A); w2(A);
If it helps, give A initial value of 5, and assume T1
writes 10,
T2 writes 20, T3 writes 30 and T4
writes 40.
Validation, 18.9.1
(p. 985) In the following swquences of events, Ri(X) means
"transaction
Ti starts, ;and its read set is the list of database elements X." Vi
means Ti attempts to validate, and Wi(X) means the "Ti
finishes, and
its write set was X.
Tell what happens when each sequences is processed by a
validation-based scheduler. Please explain the reason why, should any
transaction need to be rolled back.
(b) R1(A,B);
R2(B,C); V1;
R3(C,D); V3;
W1(A); V2;
W2(A); W3(D);
(c) R1(A,B);
R2(B,C); V1;
R3(C,D); V3;
W1(C); V2;
W2(A); W3(D);