Software Design & Engineering Chapter 19 The difference between strict and nonstrict

Chap 19 solutions

19.1.1

The difference between strict and nonstrict locking for this example is only in the matter

of whether the lock on A is released prior to the write of B. That is, the lock on A must be

19.1.2a)

T1 wrote only B, but that value was later read by T3. Thus, T3 must be rolled back. T3

19.1.2b)

T2 rolled back since it reads B written by T1.

19.1.2c)

T2 rolled back since it reads B written by T1.

19.1.2d)

T3 rolled back as it reads B written by T1.

19.1.3a)

Inserting commit actions we get the following schedule:

r1(A)r2(B)w1(B)c1w2(C)c2r3(B)r3(C)w3(D)c3

i) If the lost tail of log begins before c1, T1, T2 and T3 are considered

19.1.3b)

r1(A)w1(B)c1r2(B)w2(C)c2r3(C)w3(D)c3

19.1.3c)

r2(A)r3(A)r1(A)w1(B)c1r2(B)r3(B)w2(C)c2r3(C)c3

i) If lost tail begins before c1, T1, T2 and T3 considered uncommitted. If lost

19.1.3d)

r2(A)r3(A)r1(A)w1(B)c1r3(B)w2(C)c2r3(C)c3

i) If lost tail before c1, T1, T2 and T3 considered uncommitted. If lost tail

19.1.4a)

For Recoverable schedules, each transaction must commit only after the transaction it

read from commits. There is one read in each transaction.

Therefore the constraints are

(i) When r1(C) follows w2(C) , c1 must follow c2

There are 10 transactions that violate (i) viz.

w2(A) r2(B) w2(C) w1(A) w1(B) r1(C) c_1 c_2

w2(A) r2(B) w1(A) w2(C) w1(B) r1(C) c_1 c_2

There are 13 transactions that violate (ii) viz.

w2(A) w1(A) w1(B) r2(B) w2(C) c_2 r1(C) c_1

w2(A) w1(A) w1(B) r2(B) w2(C) r1(C) c_2 c_1

w2(A) w1(A) w1(B) r2(B) r1(C) w2(C) c_2 c_1

19.1.4b)

In an ACR schedule, transactions only read values written by committed transactions.

Again each transaction has one read.

Therefore the constraints are

(i) When r1(C) follows w2(c), r1(c) must also follow c2

18 schedules that violate (i) only are

w2(A) r2(B) w2(C) w1(A) w1(B) r1(C) c_2 c_1

w2(A) r2(B) w2(C) w1(A) w1(B) r1(C) c_1 c_2

w2(A) r2(B) w1(A) w2(C) w1(B) r1(C) c_2 c_1

w2(A) r2(B) w1(A) w2(C) w1(B) r1(C) c_1 c_2

w1(A) w1(B) w2(A) r2(B) w2(C) r1(C) c_1 c_2

9 schedules that violate only (ii) are

w2(A) w1(A) w1(B) r2(B) w2(C) c_2 r1(C) c_1

w2(A) w1(A) w1(B) r2(B) r1(C) w2(C) c_2 c_1

19.1.4c)

All corresponding actions of the two transactions on same element are possible comflicts

i.e. cannot be swapped without affcting the serializale nature.

Of the 47 recoverable schedules, below 19 are not serializable due to conflicts.

w2(A) r2(B) w1(A) w1(B) r1(C) w2(C) c_2 c_1

w2(A) r2(B) w1(A) w1(B) r1(C) w2(C) c_1 c_2

19.1.4d)

Of the 41 ACR schedules, following 13 are not conflict serializable.

w2(A) r2(B) w1(A) w1(B) r1(C) w2(C) c_2 c_1

w2(A) r2(B) w1(A) w1(B) r1(C) w2(C) c_1 c_2

19.1.5

Example of ACR schedule (tx reads values only written by committed trans):

w1(A)w1(B)w2(A)c1r2(B)c2

19.2.1a)

After inserting the appropriate lock and unlock requests, the schedule becomes(assuming

no delays):

sl1(A)r1(A)sl2(B)r2(B)xl1(C)w1(C)sl3(D)r3(D)sl4(E)r4(E)xl3(B)w3(B)ul3(B,D)xl2(C)w2(C)u

3

2

1

4

3

2

1

4

1

2

3

1

2

– xl4(A) is denied since T1 is holding a lock to A

19.2.1b)

sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C)xl1(B)w1(B)ul1(B,A)xl2(C)w2(C)ul2(C,B)xl3(D)w3(D)ul3(

D,C)

– sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C) proceed fine

– xl1(B) is denied since T2 is holding lock to B

19.2.1c)

sl1(A)r1(A)sl2(B)r2(B)sl3(C)r3(C)xl1(B)w1(B)ul1(A,B)xl2(C)w2(C)ul2(C,B)xl3(A)w3(A)ul3(

A,C)

3

2

1

3

1

2

4

3

1

2

3

1

– xl2(C) is denied since T3 holds a lock on C

19.2.1d)

sl1(A)r1(A)sl2(B)r2(B)xl1(C)w1(C)xl2(D)w2(D)sl3(C)r3(C)ul3(C)xl1(B)w1(B)ul1(B,A,C)xl4(

D)ul4(D)xl2(A)w2(A)ul2(A,B,D)

– sl1(A)r1(A)sl2(B)r2(B)xl1(C)w1(C)xl2(D)w2(D) proceed fine.

– sl3(C) is denied since T1 is holding a lock on C.

1

2

1

2

3

1

2

3

19.2.2a)

T1

T2

T3

T4

sl1(A)r1(A)

sl2(B)r2(B)

xl1(C)w1(C)

sl3(D)r3(D)

sl4(E)r4(E)

older

T1 is older.

since T1 is older.

19.2.2b)

T1

T2

T3

sl1(A)r1(A)

sl(B)r2(B)

sl3(C)r3(C)

older than T2. Completes.

xl3(D)w3(D). Completes.

T2 restarts and completes.

19.2.2c)

T1

T2

T3

sl1(A)r1(A)

sl2(B)r2(B)

sl3(C)r3(C)

older than T2. w1(B).

19.2.2d)

T1

T2

T3

T4

sl1(A)r1(A)

sl2(B)r2(B)

xl1(C)w1(C)

xl2(D)w2(D)

since T1 is older.

w1(B). Completes.

Completes.

xl4(D). Completes.

completes.

19.2.3a)

T1

T2

T3

T4

sl1(A)r1(A)

sl2(B)r2(B)

xl1(C)w1(C)

sl3(D)r3(D)

sl4(E)r4(E)

is older.

T1 is older.

Completes.

sl3(D)r3(D)

sl4(E)r4(E)

Completes

xl3(A)w3(A). Completes.

T2 restarts and completes.

19.2.3b)

T1

T2

T3

sl1(A)r1(A)

sl2(B)r2(B)

sl3(C)r3(C)

older than T2.

older than T3.

xl3(D)w3(D). Completes.

T2 resumes and completes.

T1 resumes and completes.

19.2.3c)

T1

T2

T3

sl1(A)r1(A)

sl2(B)r2(B)

sl3(C)r3(C)

older than T2.

older than T3.

older.

T2 resumes and completes.

T1 resumes and completes.

T3 restarts and finishes.

19.2.3d)

T1

T2

T3

T4

sl1(A)r1(A)

sl2(B)r2(B)

xl1(C)w1(C)

xl2(D)w2(D)

T1 is older.

since T1 is older

Completes

Completes.

than T2.

xl4(D). Dies since

T2 is older.

xl2(A). Dies since T1 is

older.

19.2.4

There exists a {T1, T2, …, Tn} of waiting transaction such as T1 is waiting for an item

19.2.5

Yes this approach would avoid deadlocks since a transaction would never start until all

19.2.6

To construct a waits-for graph for an intention-locking system, the arcs need to be drawn

such that:

– the arc goes from transaction waiting for a lock on a node to the transaction holding the

lock on the node or its child node that causes the first transaction to wait. For eg., In the

T2 dies.

Completes.

Completes

19.2.7)

Suppose T1 is a transaction that tries to lock elements A and B in that order. There are

also an indefinitely long sequence of transactions T2, T3,… that lock B and then A.

The above graph is just like the first, except T4 and T3 have replaced T3 and T2,

respectively. As long as there is a supply of transactions like T2, T3, and T4, they can

prevent T1 from finishing ever.

Notice that the transactions in the example above request locks on A and B in different

orders. Perhaps forcing transactions to request locks in a fixed order will solve the

However, if the scheduler is able to give locks to any transaction it wishes, then it is easy

to make a transaction starve. Suppose T1 wants a lock on A when some other transaction

has that lock. As long as there is always another transaction besides T1 waiting for a lock

on A, and the scheduler always chooses to give the lock to some transaction other than T1

when the lock becomes available, T1 never makes any progress.

A

B

C

T1, if we allow that T1 might timeout first, then the sequence of events described above

could also occur with timeout-based deadlock prevention.

If timeouts occur for any transaction at exactly t seconds from when it first started to wait,

19.3.5

The task of the compensating transaction is first to determine whether the file f is still the

present one with that name, or whether it has been replaced with a later version.

1. If f is still in place, then the compensating transaction must

To see that this compensation works, we can consider all the possible cases above, and

check that the file system, after compensation, is the same as would be the case had f

never been written. If f was overwritten before compensation, then we surely leave the

There are two interesting issues. First, in order for there to be a compensating transaction,

it seems we must both remember the time at which the installation occurred (so we can

tell whether the file f has been overwritten when the uninstallation occurs), and we must

19.3.2

List of compensating actions:

– A1– : Remove desired itinerary details from database (if saved)

Cancel

Look for

Book a

Enter

Confirm

Start

A1

A2

A3

A4