3. (20 points) Sequence S1: T1 R(X), T2:WCX). T2:W(Y), T3:W(). T1:W(). T1:Commit

Question

3. (20 points) Sequence S1: T1 R(X), T2:WCX). T2:W(Y), T3:W(). T1:W(). T1:Commit, T2:Commit, T3:Commit Sequence S2: T1 R(X). T2:W(Y). T2:W(X), T3:W(Y). T1:W). T1:Commit, T2:Commit, T3:Commit For each sequence and for each of the following concuTency control mechanisms, describe how the concuTency control mechanism handles the sequence Assume that the timestamp of transaction Ti isi For lock-based concuTrency control mechanisms, add lock and unlock requests to the previous sequence of actions as per the locking protocol. The DBMS processes actios in the order shown Ifa transaction is blocked, assume that all its actions are queued until it is resumed, the DBMS continues with the next action (according to the listed sequence) of an unblocked transaction 1. Strict 2PL with timestamps used for deadlock prevention (using Wait-Die policy). 2. Strict 2PL with deadlock detcction. (Show tae waits-for graph in case of dcadlock) 3. Optimistic concurrency control. 4. Timestamp concurrency control with buffering of reads and writes (to ensure recoerability) and the Thomas Write Rule 5. Multiversion timestamp concurrency control

Explanation / Answer

1. Using Wait-Die policy.

Sequence S1: T1 acquires shared-lock on X;

For an exclusive-lock on X, since T2 has a lower priority, it will be aborted When T2 asks;

T3 now gets exclusive-lock on Y;

When T1 also asks for an exclusive-lock on Y, which is still held by T3, since T1 has higher priority, T1 will be blocked waiting;

T3 now finishes write, commits and releases all the lock;

T1 wakes up, acquires the lock, proceeds and finishes; T2 now can be restarted successfully.

Sequence S2: The sequence and consequence are the same with sequence S1, except T2 was able to advance a little more before it gets aborted.

2. In deadlock detection, transactions are allowed to wait, they are not aborted until a deadlock has been detected. (Compared to prevention schema, some transactions may have been aborted prematurely.)

Sequence S1: T1 gets a shared-lock on X;

T2 blocks waiting for an exclusive-lock on X;

T3 gets an exclusive-lock on Y;

T1 blocks waiting for an exclusive-lock on Y;

T3 finishes, commits and releases locks;

T1 wakes up, get an exclusive-lock on Y, finishes up and releases lock on X and Y;

T2 now gets both an exclusive-lock on X and Y, and proceeds to finish. No deadlock.

Sequence S2: There is a deadlock. T1 waits for T2, while T2 waits for T.

3. Optimistic concurrency control:
For both S1 and S2: each transaction will execute, read values from the database and write to a private workspace; they then acquire a timestamp to enter the validation phase. The timestamp of transaction Ti is i.
Sequence S1: Since T1 gets the earliest timestamp, it will commit without problem; but when validating T2 against T1, none of the three conditions hold, so T2 will be aborted and restarted later; so is T3 (same as T2).
Sequence S2: The fate is the same as in Sequence S1.

4. Timestamp concurrency control with buffering of reads and writes and TWR.
Sequence S1: This sequence will be allowed the way it is.
Sequence S2: Same as above.

5. Multiversion concurrency control
Sequence S1: T1 reads X, so RTS(X) = 1;
T2 is able to write X, since TS(T2) ; RTS(X); and RTS(X) and WTS(X) are set to 2;
T2 writes Y, RTS(Y) and WTS(Y) are set to 2;
T3 is able to write Y as well, so RTS(Y) and WTS(Y) are set to 3;
Now when T1 tries to write Y, since TS(T1) ¡ RTS(Y), T1 needs to be aborted and restarted later.
Sequence S2: The fate is similar to the one in Sequence S1.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.