Lab 7: Locking

Locking basics

Assume that a DBMS is using regular two-phase locking with three types of locks: shared, update and exclusive.

Consider the following partial schedule of three transactions:

Given the locks that the transactions would need to acquire, which of the following operations could happen next in the schedule? Explain each answer briefly.

1. r1(F)

   Could not occur next.

   T1 would need to lock item F, but it has already released its lock for item A. Under two-phase locking, a transaction cannot acquire any new locks after releasing a lock.

2. w2(A)

   Could occur next.

   T1 has released its lock for A and no one else has any locks for item A, so T2 would be able to acquire the exclusive lock for A and write it.

3. r2(E)

   Could occur next.

   T2 would need a shared lock for E. Since the only current lock on E is a shared lock, T2 can acquire a shared lock and read E.

4. w3(D)

   Could occur next.

   In order to write D, T3 would need to upgrade its update lock for D to an exclusive lock for D. And since there are no other locks on D, this upgrade can occur and T3 can write D.

5. w2(C)

   Could not occur next.

   T2 would need an exclusive lock for C. However, T2 already has a shared lock for C, and when a DBMS uses update locks, shared locks cannot be upgraded to exclusive locks. Instead, if T2 wanted to read and then write C, it should have acquired an update lock in order to read the item, and then it could upgrade that update lock to an exclusive lock in order to write the item.

6. r2(D) (followed sometime later by w2(D))

   r2(D) could not occur next.

   Because T2 wants to read and later write D, it would need to acquire an update lock for the read of D. However, it can’t do that because T3 already has an update lock for D. Once a transaction acquires an update lock for an item, other transactions cannot a new lock for that item until the update lock is released. T2 would need to wait for T3 to release its update lock for D.

7. r3(C) (followed sometime later by w3(C))

   r3(C) could occur next.

   Because T3 wants to read and later write C, it would need to acquire an update lock for the read of C. Since the only current lock on C is a shared lock, T3 can acquire an update lock for C and read it.

   Note: T3 won’t be able to write C until T2 releases its shared lock for C, since upgrading an update lock to an exclusive lock can’t happen until there are no locks being held for that item.

Locking and deadlock detection

Assume that:

• A DBMS is using rigorous two-phase locking.
• An exclusive lock for an item is requested just before writing that item.
• A shared lock for an item is requested (if needed) just before reading that item.
• Upgrades of shared locks are allowed.
• Update locks are not being used.
• The system performs deadlock detection using a waits-for graph.
• A transaction commits immediately after completing its final read or write.

Consider the following schedule involving the transactions T1, T2, and T3:

r1(X); r1(Z); w2(Y); w2(X); r3(Z); w3(Y); w1(Z)

1. Determine if this schedule would lead to deadlock.

   If deadlock occurs, show the partial schedule in table form (including lock operations and any commits) up to the point of deadlock, along with the waits-for graph at the point of deadlock.

   If deadlock does not occur, show the full schedule, including lock operations and commits. In that case, you do not need to include the waits-for graph.

   In either case, your schedule should include any changes to the sequence of operations that occur because a transaction is forced to wait for a lock.

   If two transactions wait for a lock held by the same other transaction, and that other transaction subsequently commits, you should assume that the waiting transaction with the smaller transaction number is granted its request first.

   The schedule would lead to deadlock.

   Here is the partial schedule in table form:

   T1	T2	T3
   sl(X); r(X) sl(Z); r(Z) xl(Z) denied wait for T3	xl(Y); w(Y) xl(X) denied wait for T1	sl(Z); r(Z) xl(Y) denied wait for T2

   Here is the waits-for graph at the point of deadlock:

   

   Explanation

   1. r1(X): T1 requests and acquires a shared lock for X and reads X.

   2. r1(Z): T1 requests and acquires a shared lock for Z and reads Z.

   3. w2(Y): T2 requests and acquires an exclusive lock for Y and writes Y.

   4. w2(X): T2 requests an exclusive lock for X, but T1 already holds a shared lock for X, so the request is denied and T2 is made to wait for T1. Add a directed edge from T2 to T1 in the waits-for graph.

   5. r3(Z): T3 requests a shared lock for Z. T1 already holds a shared lock for Z, but multiple transactions are allowed to hold shared locks for the same data element, and thus T3 acquires the lock and reads Z.

   6. w3(Y): T3 requests an exclusive lock for Y, but T2 already holds an exclusive lock for Y, so the request is denied and T3 is made to wait for T2. Add a directed edge from T3 to T2 in the waits-for graph.

   7. w1(Z): T1 attempts to upgrade its shared lock for Z to an exclusive lock, but T3 also holds a shared lock for Z, and thus the request is denied and T1 is made to wait for T3. Adding a directed edge from T1 to T3 in the waits-for graph creates a cycle: T1 → T3 → T2 → T1.

   The DBMS would detect the cycle in the waits-for graph and conclude that the three transactions are deadlocked. The DBMS would then abort and restart one of the transactions so that the others could make progress.

   Depending on the transaction chosen to be aborted and restarted and when it is restarted, it’s possible that additional conflicts could occur, and even that deadlock could occur once again.

2. Now imagine that we change the final action in the schedule to w1(X):

   r1(X); r1(Z); w2(Y); w2(X); r3(Z); w3(Y); w1(X)
   

   How would that change your answer?

   Deadlock would no longer occur.

   Here is the full schedule in table form:

   T1	T2	T3
   sl(X); r(X) sl(Z); r(Z) xl(X); w(X) commit u(X); u(Z)	xl(Y); w(Y) xl(X) denied wait for T1 xl(X); w(X) commit u(X); u(Y)	sl(Z); r(Z) xl(Y) denied wait for T2 xl(Y); w(Y) commit u(Y); u(Z)

   Explanation

   Steps a-f are the same as before.

   7. w1(X): T1 attempts to upgrade its shared lock for X to an exclusive lock. Since no one else has any locks for X, T1 is able to upgrade to an exclusive lock and write X.

   8. T1 is now done, so it commits. And because the DBMS is using rigorous locking, T1 releases all of its locks at commit, which we show by putting the unlock actions after the commit action.

   9. w2(X): Now that T1 has released its lock for X, T2 can try again to acquire an exclusive lock for X. Since no one has any locks on X, T2 can acquire the exclusive lock and write X.

   10. T2 is now done, so it commits and releases its locks.

   11. w3(Y): Now that T2 has released its lock for Y, T3 can try again to acquire an exclusive lock for Y. Since no one has any locks on Y, T3 can acquire the exclusive lock and write Y.

   12. T3 is now done, so it commits and releases its locks.

   Note that the need to wait for locks has modified the order of some of the actions. The final schedule is:

   r1(X); r1(Z); w2(Y); r3(Z); w1(X); w2(X); w3(Y)
   

Last updated on October 31, 2024.