Test 3 Review B: Questions
In general locking, a transaction can acquire or release a lock on a transaction at any time. However, locking does not ensure serializability, which leads to the use of two-phase locking. Give a specific example of an unserializable schedule. Your schedule should include the times at which transactions lock and unlock elements, and of course it should following the basic locking rules.
What distinguishes two-phase locking from a basic locking scheme?
Explain what a shared lock is, and explain why shared locks are important to improving performance in database systems that use locking for ensuring serializability.
Suppose we have a DBMS that uses locks to allow concurrent transactions. Explain what the term starvation means, and describe a technique the DBMS can use to prevent starvation from occurring.
We saw that database systems support both shared and exclusive locks. This could conceivably lead to starvation: A transaction may stall indefinitely when it needs an exclusive lock on some element X, while there is a constant stream of other transactions acquiring and releasing a shared lock on X.
What can be done to prevent starvation of this type?
Describe the timeout technique for handling deadlocks.
One way of addressing deadlock is to create an ordering on database elements and to require that each transaction acquire all its locks in increasing order according to this ordering. Explain how this handles deadlock and why it works.
We saw in class two deadlock detection techniques — maintaining a wait-for graph, and timeouts. Explain the relative efficiency advantages of each.
In class we studied the wait-for graph
in the context of
locking. Explain what the graph is and what locking problem it
is meant to address.
For a locking system, a wait-for graph has a vertex for each transaction and an edge whenever one transaction has requested a lock held by another transaction. Explain how we can use this graph to take care of deadlock.
Recall the timestamp approach for ensuring serializability. Suppose that under the system, a transaction requests to read a database element X.
What should the scheduler do if the transaction's timestamp is older than WT(X)?
What should it do if the transaction's timestamp is newer than WT(X)?
Explain what multiversion timestamping is, and explain how it improves DBMS performance.
Test 3 Review B: Solutions
The following schedule is an example.
l1(A), w1(A), u1(A), l2(B), w2(B), u2(B), l2(A), w2(A), u2(A), l1(B), w1(B), u1(B)
General locking would allow this schedule, although the write sequence is not serializable.
In two-phase locking, each transaction must acquire all locks it requires before any locks are released: That is, once the transaction releases a lock, it can acquire no further locks.
A shared lock allows other transactions to obtain a shared lock at the same time, while preventing any transaction from obtaining an exclusive lock. This permits two transactions that are reading the value (but not modifying it) to access the same database element concurrently, so that a database system that frequently involves transactions that only read values will be able to achieve a higher degree of concurrency.
Starvation is the potential phenomenon where a
transaction T wants
to acquire a lock, but other transactions somehow always edge in
before T whenever the lock becomes available. One
starvation-avoidance technique (called first come, first serve
)
is that whenever a lock becomes released, the lock is awarded to
the transaction that has been waiting longest for the lock.
[Another technique is always to award a lock to the oldest
transaction that wants it.]
In the most elementary technique, the scheduler refuses to grant any shared locks when some transaction has requested an exclusive lock for a data element.
When a transaction's request for a lock cannot be granted within some fixed amount of time (say, 5 seconds), then transaction is canceled on the supposition that a deadlock is the most likely explanation for such a delay.
In this scheme, deadlocks can never arise. In a deadlock situation, you have a cycle of transactions, each requesting a lock on an element that the next one holds. Considering the data elements in the cycle, one must come furthest in the ordering. Our cycle would indicate that some transaction holds a lock on this element but is requesting a lock on some other element in the cycle — in other words, that a transaction is requesting locks out of order. If all transactions request locks in order, then, no cycles can arise.
With a wait-for graph, deadlock situations are resolved as soon as they occur. However, this comes at the expense of updating and checking the wait-for graph repeatedly. By contrast, timeouts require almost no computation as locks are acquired; but the system will take longer to detect deadlock once they occur. (The timeout technique is also less efficient because it can result in aborting transactions that are not leading to deadlock.)
The wait-for graph includes a vertex for each currently executing transaction, with a directed edge from any transaction waiting for a lock to the transaction holding that lock. It is meant for detecting deadlock and deciding how to resolve such situations.
When an edge is being added that leads to a cycle, this implies that deadlock is occurring, and the DBMS must cancel one of the transactions involved in the cycle before the rest can proceed.
We abort the transaction, restarting it with a new timestamp.
If C(X) is false (and so the transaction whose value is in X), then we wait until C(X) is true, or until transaction WT(X) aborts. Then we read the data element for the transaction and update RT(X).
In multiversion timestamping, the DBMS retains previous values of any database element that is modified. When a transaction comes along that reads the element, it determines which of the retained values to use based on the transaction's timestamp. This avoids the possibility of needing to abort the transaction due to the value it would read being unavailable, which means that transactions do not need to be reissued as often as they would be otherwise.