C H A P T E R
15
Concurrency Control
Practice Exercises
15.1 Answer: Suppose two-phase locking does not ensure serializability. Then
there exists a set of transactions T
0
, T
1
... T
n−1
which obey 2PL and which
produce a nonserializable schedule. A non-serializable schedule implies a
cycle in the precedence graph, and we shall show that 2PL cannot produce
such cycles. Without loss of generality, assume the following cycle exists
in the precedence graph: T
0
→ T
1
→ T
2
→ ... → T
n−1
→ T
0
. Let a
i
be
the time at which T
i
obtains its last lock (i.e. T
i
’s lock point). Then for all
transactions such that T
i
→ T
j
, a
i
< a
j
. Then for the cycle we have
a
0
< a
1
< a
2
< ... < a
n−1
< a
0
Since a
0
< a
0
is a contradiction, no such cycle can exist. Hence 2PL
cannot produce non-serializable schedules. Because of the property that
for all transactions such that T
i
→ T
j
, a
i
< a
j
, the lock point ordering
of the transactions is also a topological sort ordering of the precedence
graph. Thus transactions can be serialized according to their lock points.
15.2
Answer:
a. Lock and unlock instructions:
T
34
: lock-S(A)
read(A)
lock-X(B)
read(B)
if A = 0
then B := B + 1
write(B)
unlock(A)
unlock(B)
1
剩余10页未读，继续阅读
评论0