Homework #1, Due Thursday, May 6th.

Locking -- The implementation of Isolation -- The topic of Chapter 6

There are two parts to this work.

• The first is to develop a technique to illustrate and analyze the relations between two or more transactions to discover whether or not they are serializable. That is, they behave as if their effects are equivalent to some serial order of the transactions. The transactions run as if isolated from one another.
  
  
• The second is to understand how locking, and two-phase locking in particular, guarantees an order of operation that assures serialization.

To determine whether or not a set of transactions is serializable, we must first understand potential lock conflicts. There is a simple rule for determining the possible conflicts between two operations attempting to access the same data item (Chap. 6, pg. 196): Both read locks and write locks conflict with write locks. Read locks do not conflict with one another. It is customary to illustrate this is a simple table:

What the Lock Manager will grant	Read lock held by Tm	Write lock held by Tm
Read lock requested by Tk	Yes	No
Write lock requested by Tk	No	No

Example of a serializable sequence of operations --

Fig. 1 below is an example of a pair of transactions, T1 and T2. Arrows are used to connect conflicting operations, ones that would conflict if locks were requested. In this case both arrows go down, forward in time, from T1 to T2. That is, both conflicting operations in T1 precede the associated ones in T2.

Fig. 1. T1 precedes T2 in equivalent serial execution.

Because all possible conflicting operations in T1 precede those in T2, the schedule above is equivalent to the simple serial schedule T1-T2, in which T1 precedes T2, as shown in Fig. 2.

Fig. 2. T1 entirely precedes T2 giving the same result as the execution in Fig. 1.

Another way to represent the precedence relation is to draw the transactions as objects connected by directed arcs, a serialization graph. Such a graph is constructed so that there is an arc from Tm to Tk if any operation in Tm precedes any potentially conflicting operation in Tm. This is shown in Fig. 3 for the T1, T2 example above.

Fig. 3. The precedence graph for the two transactions in Figs. 1 and 2.

Example of a non-serializable sequence of operations --

In Fig. 4 below, the conflicting operations on data item A place T1 as preceding T2, but for data item B, T2 precedes T1. This is the simplest possible example of a non-serializable sequence of operations.

Fig. 4. Neither T1 nor T2 entirely precedes the other.
The transactions are in conflict and not serializable.
That is, they are not equivalent to the transactions running in order T1-T2 or T2-T1.

The serialization graph for Fig. 4 is shown in Fig. 5 below. The point to note is that it contains a cycle. The Appendix of Chap. 6 uses the existence and nonexistence of cycles in the serialization graph to prove the two-phase locking theorem.

Fig. 5. The precedence graph for the two transactions in Fig. 4.
It contains a cycle and therefore the two transactions are not serializable.

The interrelations between processes can be more complex than this. In the serialization graph in Fig. 6, each pair of transactions is well-behaved, but the set shows a cycle and therefore is non-serializable.

Fig. 6. A precedence graph for three transactions which contain a cycle and are therefore not serializable.

YOUR HOMEWORK #1 - Due Thursday, May 6^th

After all this, you might be wondering what your homework is!

Here is homework problem 1A:

Assume that T1 executes the following operations, in order, but possibly interspersed with operations of T2:

T1: Read(A), Read(B), Write(A).

Assume that T2 executes the following operations, in order, but possibly interspersed with operations of T1:

T2: Read(B), Write(A), Write(B).

Do the following: Construct two different schedules, for T1 and T2, drawing them in the style of Figs. 1, 2, and 4. The first schedule should be conflict-serializable, and the second schedule should not be. Draw the serialization graph for each.

Here is homework problem 1B:

Create a schedule for three transactions, T1, T2, and T2, and illustrate it in the style of Figs. 1, 2, and 4, except you will use three columns instead of two. The transactions should do some reading and writing of A, B, and C, and lead to a serialization graph that has a cycle in it identical to Fig. 6. That is, the combined schedule of the three transactions is non-serializable.

The second part of the homework deals with using the two-phase locking protocol to create schedules that are serializable.

Here is homework problem 2A:

Starting with the schedule shown in Fig. 4, invoke two-phase locking. This will block one of the transactions until the other transaction finishes its operations and commits or aborts at that time. Show that the resulting schedule and its serialization graph indicate that you have succeeded.

Here is homework problem 2B:

Using your schedule from your answer to problem 1B, invoke two-phase locking and show that the result is a serializable schedule. This should be apparent from the schedule that results (draw it) and from the resulting serialization graph that you should draw also.