Test 3 Review B

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Problem R3b.1.

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.

The following schedule is an example.

l₁(A), w₁(A), u₁(A), l₂(B), w₂(B), u₂(B), l₂(A), w₂(A), u₂(A), l₁(B), w₁(B), u₁(B)

General locking would allow this schedule, although the write sequence is not serializable.

Problem R3b.2.

What distinguishes two-phase locking from a basic locking scheme?

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.

Problem R3b.3.

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.

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.

Problem R3b.4.

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.

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.]

Problem R3b.5.

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?

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.

Problem R3b.6.

Describe the timeout technique for handling deadlocks.

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.

Problem R3b.7.

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.

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.

Problem R3b.8.

We saw in class two deadlock detection techniques — maintaining a wait-for graph, and timeouts. Explain the relative efficiency advantages of each.

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.)

Problem R3b.9.

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.

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.

Problem R3b.10.

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.

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.

Problem R3b.11.

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)?

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).

Problem R3b.12.

Explain what multiversion timestamping is, and explain how it improves DBMS performance.

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.