Software Design & Engineering Chapter 18 Think of the interleaving as having 10 positions

18.1.1)

r1(A); r1(B); w1(B); r1(C); w1(C); r1(D); w1(D); r1(E); w1(E)

18.1.2)

18.2.1a)

Assume A=1, B=2

(T1,T2)

T1

Read (A,t) t=1

T=t+2 t=3

W(A,t) A=3

(T2,T1)

T2

R(B,s) s=2

s=s*2 s=4

W(B,s) B=4

R(A,s) s=1

s=s+3 s=4

18.2.1b)

Serializable schedule

T1

R(A,t)

t=t*2

T2

Non- serializable schedule

T1

R(A,t)

t=t*2

W(A,t)

T2

18.2.1c)

(T1,T2)

(T2,T1)

18.2.1d)

The key observation is that in order for an interleaving to be serializable, whichever

transaction reads A first, must write it before the second reads A, and likewise for B.

There are four possibilities:

4. T1 reads A first but T2 reads B first. Now, the first three steps of each transaction

may interleave in any way, and the last three of each may interleave in any way,

400.

The total number of serial orders is thus 402.

18.2.2a)

If a swap of two adjacent actions is legal, then the two actions can also be swapped back

18.2.2b)

18.2.2c)

Similar to 18.2.1 (d), for interleaving schedules to be serializable, a variable must be read

and written by one transaction before another transaction reads it.

For serial schedule (T1,T2), the four possibilities are:

18.2.2d)

Number of actions are different.

18.2.3a)

2) r1(A)w1(A)r1(B)r2(A) w1(B)w2(A)r2(B)w2(B) (2 swaps possible)

3) r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B) (first swap from 2)

18.2.3b)

In addition to the twelve schedules above, interleaving using transaction behavior like

18.2.1 allows for two more possibilities:

18.2.4a)

i)

The precedence graph is:

T3 —–> T2 —–> T1

ii)

18.2.4b)

i)

r1(A)w3(A) T1<T3

T1 —–> T2 —–> T3

ii)

18.2.4c)

i)

w3(A)r1(A) T3<T1

ii)

No, schedule is not conflict-serializable

iii)

18.2.4d)

i)

r1(A)r2(A) T1<T2

w1(D)

ii)

No, schedule is not conflict-serializable.

iii)

NA, since schedule has conflict.

18.2.4e)

i)

ii)

Yes, the schedule is conflict-serializable. The conflict-equivalent serial schedules are:

T3T1T4T2

iii)

NA, since schedule has conflict.

18.2.5)

In order that the three conditions are satisfied, one approach can be

:T1 and T2 are not in conflict (better yet, not operating on same variables)

The Precedence Graph of schedule S:

T2 -> T3 -> T1

18.2.6)

Consider the precedence graph of the serial schedule of transactions (T1,T2,T3,…) such

that T1 has reads for all variables and all other transactions write two of the variables

18.3.1a)

18.3.1b)

In legal schedules locks on a particular element are only held by one transaction at a

given time. Since locks are being acquired by T1 and T2 just before reads and bring

released just after writes; we can restate the legality requirement here as:

Between the read and write of an element by one transaction, No other transaction should

act on the element. Thus below 32 transactions are illegal:

r2(B);w2(B);r2(A);r1(A);w2(A);w1(A);r1(B);w1(B);

r2(B);w2(B);r2(A);r1(A);w1(A);w2(A);r1(B);w1(B);

r2(B);r1(A);w1(A);r1(B);w2(B);r2(A);w2(A);w1(B);

r2(B);r1(A);w1(A);r1(B);w2(B);r2(A);w1(B);w2(A);

r2(B);r1(A);w1(A);r1(B);w2(B);w1(B);r2(A);w2(A);

r2(B);r1(A);w1(A);r1(B);w1(B);w2(B);r2(A);w2(A);

r1(A);w1(A);r2(B);r1(B);w2(B);r2(A);w2(A);w1(B);

r1(A);w1(A);r2(B);r1(B);w2(B);r2(A);w1(B);w2(A);

r1(A);w1(A);r2(B);r1(B);w2(B);w1(B);r2(A);w2(A);

While below 38 transactions are legal:

r2(B);w2(B);r2(A);w2(A);r1(A);w1(A);r1(B);w1(B);

r2(B);w2(B);r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);

r2(B);w2(B);r1(A);w1(A);r2(A);r1(B);w2(A);w1(B);

r2(B);w2(B);r1(A);w1(A);r2(A);r1(B);w1(B);w2(A);

r2(B);w2(B);r1(A);w1(A);r1(B);r2(A);w2(A);w1(B);

r2(B);w2(B);r1(A);w1(A);r1(B);r2(A);w1(B);w2(A);

r2(B);r1(A);w1(A);w2(B);r1(B);w1(B);r2(A);w2(A);

r1(A);r2(B);w2(B);w1(A);r2(A);w2(A);r1(B);w1(B);

r1(A);r2(B);w2(B);w1(A);r2(A);r1(B);w2(A);w1(B);

r1(A);r2(B);w2(B);w1(A);r2(A);r1(B);w1(B);w2(A);

r1(A);r2(B);w2(B);w1(A);r1(B);r2(A);w2(A);w1(B);

r1(A);r2(B);w2(B);w1(A);r1(B);r2(A);w1(B);w2(A);

r1(A);r2(B);w2(B);w1(A);r1(B);w1(B);r2(A);w2(A);

r1(A);r2(B);w1(A);w2(B);r2(A);w2(A);r1(B);w1(B);

18.3.1c)

According to semantics of transactions, four possibilities for serializable schedules are:

(i) Serial order (T1,T2) = 1 transaction

(ii) Serial order (T2,T1) = 1 transaction

18.3.1d)

Only two schedules are conflict serializable:the serial orders (T1,T2) and (T2,T1). Both

18.3.1e)

No, there are none. Due to the semantics of the transactions, and the placement of lock

18.3.2)

Suppose the schedule starts with T1 locking and reading A. If T2 locks B before T1

18.3.3a)

Note that this question refers to the solved Exercise 18.2.4(a). For the sequence of the

18.3.3b)

18.3.3c)

w3(A)r1(A)w1(B)r2(B)w2(C)r3(C)

No delays necessary.

18.3.3d)

r1(A)r2(A)w1(B)w2(B)r1(B)r2(B)w2(C)w1(D)

18.3.3.e)

r1(A)r2(A)r1(B)r2(B)r3(A)r4(B)w1(A)w2(B)

18.3.4)a)

The consistent sequences(i+ii) are interleavings of the sequences

A sequence is not two-phase locked if the unlock of 1 occurs before lock of 2 or vice

versa. Only 2 such interleavings are possible i.e. all of 1 followed by all of 2 or vice versa.

Thus number of consistent but not two-phase orders = 2. (ii)

Thus the number of two-phase locked orders are = 20 – 2 = 18. (i)

Next consider number of two-phased locked orders(i+iii). The two locks must occur

before the two locks; there are four such permutations:

Action r1(A) can be placed in any of 5 positions combining with above lock-unlock

actions i.e. before,after, or in between above lock-unlock actions.

Similarly w1(B) can be placed in any of 6 positions combining above lock-unlock-r1(A)

Thus the answers are

(i) 18

18.3.4(b)

The consistent sequences(i+ii) are interleavings of the sequences

1. l2(A);r2(A);w2(A);u2(A)

2. l2(B);w2(B);u2(B)

The number of such interleaving are (7 choose 3) = 35. Since in 1 r2(A) and w2(A) can

Next consider number of two-phased locked orders(i+iii). The two locks must occur

before the two locks; there are four such permutations:

l2(A);l2(B);u2(A);u2(B)

Action r2(A) can be placed in any of 5 positions combining with above lock-unlock

actions i.e. before,after, or in between above lock-unlock actions.

Thus number of inconsistent non-two phase locked orders = 5040 – 774 – 66 – 4 = 4196

(iv)

Thus the answers are

(i) 66

18.4.1a)

i)

sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C)xl1(B)w1(B)u1(B)u1(A)xl2(C)w2(C)u2(C)u2(B)

ii)

T1 is delayed. 4th lock request xl1(B) waits since T2 is holding shared lock on B.

iii)

Same as i)

iv)

Same as ii)

18.4.1b)

i)

sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C)xl1(B)w1(B)u1(B)u1(A)xl2(C)w2(C)u2(C)u2(B)

ii)

T1 delayed. 4th lock request xl1(B) waits since T2 holds shared lock on B.

iii)

Same as i)

iv)

Same as ii)

i)

sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C)sl1(B)r1(B)sl2(C)r2(C)sl3(D)r3(D)xl1(C)w1(C)u1(C)

1 2 3 4 5 6 7

T2 is delayed. 8th lock request xl2(D) waits since T3 holds shared lock on D.

iii)

Same as i)

iv)

Same as ii)

18.4.1d)

i): xl1(A); r1(A); xl2(B); r2(B); xl3(C); r3(C); sl1(B); r1(B); sl2(C); r2(C); sl3(D); r3(D);

As soon as C is unlocked, T2 can get its shared lock on C. Thus, T2 completes and

releases its locks. As soon as its lock on B is released, T1 can get its lock on A, so it

completes.

(iii): sl1(A); r1(A); sl2(B); r2(B); sl3(C); r3(C); sl1(B); r1(B); sl2(C); r2(C); sl3(D); r3(D);

(v): ul1(A); r1(A); ul2(B); r2(B); ul3(C); r3(C); sl1(B); r1(B); sl2(C); r2(C); sl3(D); r3(D);

xl1(A); w1(A); u1(A); u1(B); xl2(B); w2(B); u2(B); u2(C); xl3(C); w3(C); u3(C); u3(D)

(vi): The update locks prevent the fourth and fifth shared-lock requests, sl1(B) and sl2(C),

18.4.1e)

i)

xl1(A)r1(A)xl2(B)r2(B)xl3(C)r3(C)sl1(B)r1(B)sl2(C)r2(C)sl3(A)r3(A)w1(A)u1(A)u1(B)w2(B)

1 2 3 4 5 6

u2(B)u2(C)w3(C)u3(C)u3(A)

ii)

T1 is delayed. 4th lock request sl1(B) waits since T2 has exclusive lock on B.

iii)

sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C)sl1(B)r1(B)sl2(C)r2(C)sl3(A)r3(A)xl1(A)w1(A)u1(A)u1(B)

iv)

T1 is delayed. 7th lock request xl1(A) waits since T3 has shared lock on A.

v)

ul1(A)r1(A)ul2(B)r2(B)ul3(C)r3(C)sl1(B)r1(B)sl2(C)r2(C)sl3(A)r3(A)xl1(A)w1(A)u1(A)

1 2 3 4 5 6 7

u1(B)xl2(B)w2(B)u2(B)u2(C)xl3(C)w3(C)u3(C)u3(A)

8 9

vi)

T1 is delayed. 4th lock request sl1(B) waits since T2 has update lock on B.

18.4.2b)

Possible serializable schedules are

(i) serial order (T1,T2)

(ii)serial order (T2,T1)

18.4.3a)

sl1(A)r1(A)sl2(B)r2(B)il1(B)inc1(B)il2(C)inc2(C)xl1(C)w1(C)u1(A)u1(B)u1(C)xl2(D)

18.4.3b)

sl1(A)r1(A)sl2(B)r2(B)il1(B)inc1(B)il2(A)inc2(A)xl1(C)w1(C)u1(C)u1(A)u1(B)xl2(D)w2(D)

18.4.3c)

il1(A)inc1(A)il2(B)inc2(B)il1(B)inc1(B)il2(C)inc2(C)xl1(C)w1(C)u1(C)u1(B)u1(A)xl2(D)