CS W186 Introduction to Database Systems
Spring 2020 Josh Hug, Michael Ball DIS 9
1 Conflict Serializability
(a) Draw the dependency graph (precedence graph) for the schedule.
Solution:
(b) Is this schedule conflict serializable? If so, what are all the conflict equivalent serial schedules? If not, why not?
Solution: Yes. T3, T1, T2 and T1, T3, T2. Topologically sorting the above graph gives these schedules.
(c) Draw the dependency graph (precedence graph) for the schedule.
Solution:
CS W186, Spring 2020, DIS 9 1
(d) Is this schedule conflict serializable? If so, what are all the conflict equivalent serial schedules? If not, why not?
Solution: No, there’s a cycle between T1 and T2: T1 must come before T2 and T2, before T1.
2 Deadlock
(a) Draw a “waits-for” graph and state whether or not there is a deadlock
Solution: Yes there is deadlock. There is a cycle between T1, T2, and T3.
CS W186, Spring 2020, DIS 9 2
3 Locking
(a) What is printed, assuming we initially have B = 3 and F = 300?
Solution: 3030
(b) Does the execution use 2PL, strict 2PL, or neither?
Solution: Neither – T2 unlocks S(F) before it acquires S(B)
(c) Would moving Unlock(F) in the second transaction to any point after Lock_S(B) change this (or keep it) in 2PL?
Solution: Yes – all locks would be acquired (for T2) before any are released.
(d) Would moving Unlock(F) in the first transaction and Unlock(F) in the second transaction to the end of their respective transactions change this (or keep it) in strict 2PL?
Solution: No – T1 still unlocks B before the end of the transaction
(e) Would moving Unlock(B) in the first transaction and Unlock(F) in the second transaction to the end of their respective transactions change this (or keep it) in strict 2PL?
Solution: Yes – all unlocks would only happen when the respective transactions end
CS W186, Spring 2020, DIS 9 3
4 Multigranularity Locking
(a) Suppose a transaction T1 wants to scan a table R and update a few of its tuples. What kinds of locks should T1 have on R, the pages of R, and the updated tuples?
Solution:
(a) Obtain SIX on R
(b) Obtain IX on Page [We don’t obtain a SIX because there is already an S lock on R (from the SIX). Obtaining another S on the Page is redundant.]
(c) Obtain X on Tuples being modified
(b) Is an S lock compatible with an IX lock?
(c)
Solution: Suppose T1 wants an S lock on an object, O, and T2 wants an IX lock on the same
object O. An S lock implies that T1 will read the entire object (all of its sub-objects). An IX lock implies that T2 will write some of the sub-objects of the object. This means that there is some sub-object of O that T1 will read and T2 will write. This is not valid, so the S and IX locks must be incompatible.
Consider a table which contains two pages with three tuples each, with Page 1 containing Tuples 1, 2, and 3, and Page 2 containing Tuples 4, 5, and 6.
(a) Given that a transaction T1 has an IX lock on the table, an IX lock on Page 1, and an X lock on Tuple 1, which locks could be granted to a second transaction T2 for Tuple 2? Solution: X, S
(b) Given that a transaction T1 has an IS lock on the table and an S lock on Page 1, what locks could be granted to a second transaction T2 for Page 1?
Solution: S, IS
Project Prep
5
The LockManager in the project will have the following 4 functions:
• acquire(transaction, resourceName, lockType): this method is the stan- dard acquire method of a lock manager. It allows a transaction to request one lock, and grants the request if there is no queue and the request is compatible with existing locks. Otherwise, it should queue the request (at the back) and block the transaction
• release(transaction, resourceName): this method is the standard release method of a lock manager. It allows a transaction to release one lock that it holds.
• acquireAndRelease(transaction, resourceName, lockType, releaseLocks): this method atomically acquires one lock and releases zero or more locks. This method has
priority over any queued requests (it should proceed even if there is a queue, and it is placed
in the front of the queue if it cannot proceed).
CS W186, Spring 2020, DIS 9 4
• promote(transaction, resourceName, lockType): this method allows a trans- action to explicitly promote/upgrade a held lock. This method has priority over any queued requests (it should proceed even if there is a queue, and it is placed in the front of the queue if it cannot proceed).
In this problem we will have 3 transactions (T1, T2, T3) and 2 resources that we will try to lock (A, B). After each lock request is processed, fill out the following two tables that store the information for what locks are held:
The following lock requests are made in this order:
• acquire(T1, A, X)
• acquire(T2, B, S)
• acquire(T3, B, X)
• acquireAndRelease(T2, A, S, releaseLocks=) • release(T1, A)
• acquire(T1, A, S) • acquire(T3, A, X) • promote(T2, A, X) • release(T1, A)
CS W186, Spring 2020, DIS 9 5
Solution:
acquire(T1, A, X)
There are no locks held, so this request will be immediately granted.
acquire(T2, B, S)
There are no locks held on B, so this request will be immediately granted.
CS W186, Spring 2020, DIS 9 6
acquire(T3, B, X)
Another transaction owns an S lock on B, so T3 cannot acquire an X lock on B yet and is therefore put on B’s queue.
acquireAndRelease(T2, A, S, releaseLocks=)
Another transaction owns an X lock on A, so T2 cannot acquire an S lock on A yet, so it is put on the front of A’s queue.
CS W186, Spring 2020, DIS 9 7
release(T1, A)
When T1 releases its lock on A, T2’s acquireAndRelease request on A’s queue can now be granted so T2 will acquire a shared lock on A. As part of the newly granted acquireAndRelease request, T2 will release the lock it holds on B. When this lock is released, it allows T3’s acquire request for an X lock on B (on the B queue) to be granted.
acquire(T1, A, S)
The only lock on resource A is a shared lock, so this request for a shared lock can be immediately granted.
CS W186, Spring 2020, DIS 9 8
acquire(T3, A, X)
This request cannot be granted because other transactions own S locks on A, so it must be added to A’s queue.
promote(T2, A, X)
This request cannot be granted because T1 also has a shared lock on A. This means the request will go to the front of A’s queue, because promote requests immediately go to the front of the queue.
CS W186, Spring 2020, DIS 9 9
release(T1, A) When T1 releases its lock on A, the queue for A is processed. The first request on the queue is to promote T2’s S lock to an X lock. Because T2’s lock is the only lock on A now, this promote request can be granted so T2 now gets an X lock on A. The next request on A’s queue is for an X lock on A, which obviously conflicts with T2’s newly granted X lock, so it must remain on the queue.
CS W186, Spring 2020, DIS 9 10