19-1 Why is the provision of lock and unlock operations not sufficient to ensure serialisability of composite operation invocations?

It depends how they are used. Lock, do operation, unlock just makes each component operation atomic (which we assume anyway). There must be an additional policy on the use of locks to ensure that an object is not unlocked "too early".

Once a transaction has locked an object it does not unlock it until it has locked all the objects required by all its operations. This ensures that two transactions must access any objects they have in common in the same order.

Two transactions may have objects in common. One may lock some of the common objects. The other may lock others. When the transactions request the objects held by the other we have deadlock. The four conditions hold.

Suppose a transaction locks all its objects then proceeds to invoke them. If it unlocks each object as soon as its invocation is done then that object’s state may be seen by other transactions before this one completes. If this one aborts we must abort all such transactions.

In strict 2PL the transaction does not unlock its objects until it completes with commit or abort. This ensures isolation.

19-2 Why might the start-time of a transaction not be the best time to use for its timestamp in TSO?

The transaction may spend some time processing before it starts to invoke persistent objects, or it may invoke operations which cannot conflict before potentially conflicting ones. It is then likely to be deemed "too late" at the objects it invokes ( if transactions with later timestamps have now invoked the potentially conflicting operations). (Contrast with OCC where all transactions prepare the state they wish to commit in shadow objects then request commit. In this case the order is first to commit, first served.)

Yes, the directed arc is from the transaction with the earlier timestamp to that with the later one.

We are concerned only with operations that are potentially conflicting. Let us assume, for the purpose of this comparison, that we do not enforce isolation by a strict execution schedule. (Strictness is for avoiding cascading aborts.)

In a system which employs 2PL for concurrency control, a transaction must wait if an object it requires is locked. We avoid non-serialisable schedules by allowing a number of objects to be held locked. Deadlock may arise and deadlock detection must be carried out. In a system which employs TSO the decision on whether an invocation can go ahead is made immediately and at a single object. This makes a higher degree of concurrency possible. An object is available except when being invoked, yet we have avoided non-serialisable histories and the possibility of deadlock. However, some transaction may have to be restarted with a later timestamp and the response time to that application may be no better than in the locking system. We allow equivalence to only one serial order of execution, that of the timestamps of the transactions.

2PL requires centralised information on the locks held and requested so that deadlock detection can be carried out. In TSO each object decides whether an invocation can go ahead. Overhead in TSO comes from having to abort and restart transactions.

19-3 Why are cascading aborts possible in a system with timestamp-based concurrency control? What extra mechanism could prevent it?

An object is available except when being invoked. A transaction may go on to abort after invoking an object and another transaction may have seen its state in the meantime. We can prevent this if an object only considers accepting an invocation if the transaction which carried out the previous one commits.

19-4 Is concurrency control based on timestamp ordering, or strict timestamp ordering, subject to deadlock?

In TSO no objects are held so deadlock cannot happen. In strict TSO an invocation can be rejected while an object awaits the commitment of the transaction which last invoked it. The method is defined so that cycles are avoided so deadlock cannot happen.

19-5 Why is optimistic concurrency control (OCC) potentially appropriate for use in real-time systems?

A transaction does not have to wait for an object to become available. The only possibility of delay in taking a shadow is if the current state is being updated. Objects are not locked for invocation or for atomic commitment.

The overhead is associated with restarting a transaction with new shadow objects if conflict is detected on validation.

19-6 What is involved in aborting a transaction in a system which uses OCC?

Restarting it with new shadow objects.

First, a check is made that the object states represent a consistent system state (objects are not locked for atomic commitment in OCC). If this is OK:

Suppose that changes have been committed at an object invoked by a transaction since its shadow was taken. If these result from operations which do not conflict with that of our transaction, its operation can be applied to the current system state. The validation phase must ensure this over all the objects invoked by a transaction. If conflicting operations have been committed at any object then the transaction is aborted and restarted.

A given object must participate in only one validation at once and must apply updates in the order specified by the validator.

19-7 Suppose that two transactions use copies of the same objects under an OCC scheme. Suppose that both transactions generate output and both are committed. Does the output reflect a serial ordering of the transactions? Does it matter?

The fact that they are committed means that they operated on a consistent system state. The output does not reflect a serial ordering and it does not matter - it is the nature of OCC that several transactions can operate on the same (consistent) system state.

19-8 Consider the example shown in Figure 19.11.

What happens when T3 requests commit?

mult(2) conflicts with add(3). T3 is restarted with a shadow object A=4.

add(2) does not conflict with add(3). T1 is committed and its operation is applied to the persistent object A=6.

If T3 requests commit it will be rejected again and restarted with A=6. It may then go on to request commit giving A=12.

19-9 A particular application is known to comprise almost entirely read-only transactions. Discuss the three approaches to concurrency control for such a system.

If we use 2PL we would achieve better performance if the system supports shared read locks. If a transaction requests to convert a read lock into a write lock it may be delayed until other transactions have finished reading. Deadlock can occur over lock conversion. In TSO most invocations will go ahead as read does not conflict with read. In OCC most transactions will succeed in committing as object states are not changed by read-only transactions (read operations commute). Presumably we are using a transaction system because updates are made from time to time, even if they are infrequent.

19-10 For a particular application, transactions are either read-only or have a phase in which they read and compute followed by a phase in which they write their results back to the database. Discuss the three approaches to concurrency control for this application.

The question is under-specified. It does not give us enough information about the type of application area. It may be that the transactions are long, such as in CAD applications. Does the read and compute followed by write comprise a single operation?

Strict 2PL ensures that transactions see only committed system state. It is desirable that read-only transactions should be able to take out shared read locks on objects. Read-write transactions would require to be able to convert a read lock into a write lock; that is, acquire a write lock without releasing the read lock on an object. Deadlock can then arise.

TSO would allow read operations to go ahead since they do not conflict.

The question does not say whether conflict is expected to be rare. If this is the case then OCC is suitable for this style of use. Read-only transactions may take shadows without delay. A check is carried out when the transaction requests commit that the shadows are consistent. If conflict is rare, this is likely to be the case.

19-11 In OCC we defined the version number of an object as the timestamp of the transaction whose validated invocations were most recently applied to the object. The transaction’s timestamp is therefore that of its commit time instead of its start time. Contrast TSO and OCC with respect to the timestamps allocated to transactions and the schedules that are allowed to execute.

In OCC and TSO a timestamp is associated with each recorded state (or version) of an object. In OCC the timestamp is issued by the validator of the transaction which invoked the object when it guarantees that the transaction will commit. Updates must be applied at objects in timestamp order. Shadow objects may be taken at any time. Updates made at an object are those of committed transactions. Transaction abort does not affect the persistent object; shadow objects are discarded.

In TSO a timestamp is associated with a transaction, possibly its start time or when it first invokes a potentially conflicting operation. Each object makes an individual decision on whether an invocation can be carried out on the basis of the transaction timestamp. The transaction co-ordinator (scheduler) will abort the transaction if any invocation is rejected at the object. There is therefore the possibility that invocations must be undone.

Strict TSO keeps the object unavailable until the decision to commit or abort the transaction has been taken. The updates can be applied at all objects on commit with the timestamp of the transaction as version-id.