Basic TO Algorithm question
Two transactions T1 and T2. Initially RTS = 0 and WTS = 0 for data items X, Y
Timestamps are as follows: TS (T1)=10 and TS (T2)=20
T1
1. A * 1 = Read(X)
2. A1=A1-k
3. Write(X, A1)
T2
1. A * 1 = Read(X)
2. A 1=A1^ * 1.01
3. Write(X, A1)
T1
4. A^ 2 =R aad (V)
5. A 2=A2+k
6. Write(Y, A2)
T2
4. A * 2 = Read(Y)
5. A 2=A2^ * 1.01
6. Write(Y, A2)
Discuss whether the following schedule is serializable or not? Justify your answer using Basic TO Algorithm.
The Basic Two-Phase Locking (TO) algorithm can be used to check if a schedule is serializable.
In the given schedule, the transactions T1 and T2 are executed in an interleaved manner. Let's analyze the schedule step by step using the Basic TO Algorithm:
1. T1: Read(X) - T1 acquires a shared (S) lock on X.
T2: Read(X) - T2 requests an S lock on X, but it cannot be granted as T1 already holds an S lock on X. T2 waits.
2. T1: A1 = A1 - k - This operation does not involve any data items.
T2: T2 is still waiting.
3. T1: Write(X, A1) - T1 upgrades its shared (S) lock on X to an exclusive (X) lock. The value of X is modified to A1.
T2: T2 is still waiting.
4. T1: A2 = Read(V) - This operation does not involve X or Y.
T2: T2 is still waiting.
5. T1: A2 = A2 + k - This operation does not involve X or Y.
T2: T2 is still waiting.
6. T1: Write(Y, A2) - This operation involves a new data item Y. T1 requests a shared (S) lock on Y, which is granted as there are no conflicting locks on Y.
T2: T2 is still waiting.
7. T2: Read(Y) - T2 requests a shared (S) lock on Y, but it cannot be granted as T1 already holds a shared (S) lock on Y. T2 waits.
8. T2: A2 = A2^ * 1.01 - This operation does not involve Y.
9. T2: Write(Y, A2) - This operation involves Y. T2 requests an exclusive (X) lock on Y, but it cannot be granted as T1 still holds a shared (S) lock on Y. T2 waits.
In the given schedule, T1 holds shared (S) locks on both X and Y, whereas T2 is waiting to acquire shared (S) and exclusive (X) locks on X and Y, respectively. This violates the Basic TO Algorithm, which states that no transaction can request a lock that is incompatible with a lock held by another transaction.
Therefore, the given schedule is not serializable according to the Basic TO Algorithm.