Chapter 21: Concurrency Control Techniques
1
CHAPTER 21: CONCURRENCY CONTROL TECHNIQUES
Answers to Selected Exercises
21.20 – Prove that the basic two-phase locking protocol guarantees conflict serializability of
schedules. (Hint: Show that, if a serializability graph for a schedule has a cycle, then at least
one of the transactions participating in the schedule does not obey the two-phase locking
protocol.)
Answer:
(This proof is by contradiction, and assumes binary locks for simplicity. A similar
proof can be made for shared/exclusive locks.)
Suppose we have n transactions T1, T2, ..., Tn such that they all obey the basic
two-phase locking rule (i.e. no transaction has an unlock operation followed by a lock
operation). Suppose that a non-(conflict)-serializable schedule S for T1, T2, ..., Tn
21.21 – Modify the data structures for multiple-mode locks and the algorithms for
read_lock(X), write_lock(X), and unlock(X) so that upgrading and downgrading
of locks are possible. (Hint: The lock needs to keep track of the transaction id(s)
that hold the lock, if any.)
Answer:
We assume that a List of transaction ids that have read-locked an item is maintained, as
well as the (single) transaction id that has write-locked an item. Only read_lock and
write_lock are shown below.
Chapter 21: Concurrency Control Techniques
2
else if lock (X) = “write_locked, Tn”
(* downgrade the lock if write_lock on X is held by Tn itself *)
goto B;
end;
write_lock (X,Tn);
B: if lock (X) = “unlocked”
then lock (X) <- “write_locked, Tn”
else
if ( (lock (X) = “read_locked, List”) and (no_of_reads (X) = 1)
the lock manager wakes up the transaction);
goto B;
end;
21.22 – Prove that strict two-phase locking guarantees strict schedules.
21.23 – No solution provided.
21.24 – Prove that cautious waiting avoids deadlock.
Answer:
In cautious waiting, a transaction Ti can wait on a transaction Tj (and hence Ti
becomes blocked) only if Tj is not blocked at that time, say time b(Ti), when Ti waits.
Chapter 21: Concurrency Control Techniques
5
TS(T3) = read_TS(Y) and TS(T3) > write_TS(Y)
Execute write_item(Y)
TS(T3) = read_TS(Z) and TS(T3) > write_TS(Z)
Execute write_item(Z)
TS(T2) > write_TS(Z)
Execute read_item(Z)
TS(T1) > write_TS(Y)
Execute read_item(Y)
TS(T1) = read_TS(Y) and TS(T1) > write_TS(Y)
Execute write_item(Y)
TS(T2) > write_TS(Y)
Execute read_item(Y)
TS(T2) = read_TS(Y) and TS(T2) > write_TS(Y)
Execute write_item(Y)
TS(T2) > write_TS(X)
Execute read_item(X)
TS(T2) = read_TS(X) and TS(T2) > write_TS(X)
Execute write_item(X)
Chapter 21: Concurrency Control Techniques
7
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
Execute read_item(X) by reading the value of the initial version X
read_TS(X) <- max(read_TS(X),TS(T3)) = 6
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=4,
read_TS(Z)=4,read_TS(Z1)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
write_TS(Y3) <- TS(T3) = 4,
read_TS(Y2) <- TS(T3) = 4
read_TS(X)=6,read_TS(X1)=6,read_TS(Y)=1,read_TS(Y1)=4,read_TS(Y2)=6,
read_TS(Y3)=6,read_TS(Z)=4,read_TS(Z1)=4,
write_TS(X)=0,write_TS(X1)=6,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=4,
TS(T1)=3, TS(T2)=7, TS(T3)=1 (These do not change)
T3: read_item(Y)
Execute read_item(Y)
Set read_TS(Y) <- max(read_TS(Y),TS(T3)) = 1
read_TS(X)=0,read_TS(Y)=1,read_TS(Z)=0,write_TS(X)=0,write_TS(Y)=0,write_TS(Z)=0
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
Execute write_item(X) by creating a new version X1 of X
write_TS(X1) <- TS(T1) = 3, read_TS(X1) <- TS(T1) = 3
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=1,read_TS(Z)=1,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Z)=0
T3: write_item(Y)
write_TS(Z1)=1
T2: read_item(Z)
Execute read_item(Z) by reading the value of version Z1
Set read_TS(Z1) <- max(read_TS(Z1),TS(T2)) = 7
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=1,read_TS(Y1)=1,read_TS(Z)=1,
T1: write_item(Y)
Execute write_item(Y) by creating a new version Y2 of Y
write_TS(Y2) <- TS(T1) = 3, read_TS(Y2) <- TS(T1) = 3
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Y2)=3,
read_TS(Z)=1,read_TS(Z1)=7,
Execute write_item(Y) by creating a new version Y3 of Y
write_TS(Y3) <- TS(T2) = 7, read_TS(Y3) <- TS(T2) = 7
read_TS(X)=3,read_TS(X1)=3,read_TS(Y)=3,read_TS(Y1)=1,read_TS(Y2)=7,
read_TS(Y3)=7,read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(Y)=0,write_TS(Y1)=1,write_TS(Y2)=3,
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
Execute write_item(X) by creating a new version X2 of X
write_TS(X2) <- TS(T2) = 7, read_TS(X2) <- TS(T2) = 7
read_TS(X)=3,read_TS(X1)=7,read_TS(X2)=7,read_TS(Y)=3,read_TS(Y1)=1,
read_TS(Y2)=7,read_TS(Y3)=7,read_TS(Z)=1,read_TS(Z1)=7,
write_TS(X)=0,write_TS(X1)=3,write_TS(X2)=7,write_TS(Y)=0,write_TS(Y1)=1,
21.27 – 21.29: No solutions provided.