没有合适的资源?快使用搜索试试~ 我知道了~
chapter15 实践习题1
需积分: 0 0 下载量 147 浏览量
2022-08-03
15:04:44
上传
评论
收藏 538KB PDF 举报
温馨提示
试读
11页
chapter15 实践习题1
资源详情
资源评论
资源推荐
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
2 Chapter 15 Concurrency Control
T
35
: lock-S(B)
read(B)
lock-X(A)
read(A)
if B = 0
then A := A + 1
write(A)
unlock(B)
unlock(A)
b. Execution of these transactions can result in deadlock. For example,
consider the following partial schedule:
T
31
T
32
lock-S(A)
lock-S(B)
read(B)
read(A)
lock-X (B)
lock-X (A)
The transactions are now deadlocked.
15.3 Answer: Rigorous two-phase locking has the advantages of strict 2PL.
In addition it has the property that for two conflicting transactions, their
commit order is their serializability order. In some systems users might
expect this behavior.
15.4
Answer:
Consider two nodes A and B, where Ais a parent of B. Let dummy vertex
D be added between A and B. Consider a case where transaction T
2
has a
lock on B, and T
1
, which has a lock on A wishes to lock B, and T
3
wishes
to lock A. With the original tree, T
1
cannot release the lock on A until it
gets the lock on B. With the modified tree, T
1
can get a lock on D, and
release the lock on A, which allows T
3
to proceed while T
1
waits for T
2
.
Thus, the protocol allows locks on vertices to be released earlier to other
transactions, instead of holding them when waiting for a lock on a child.
A generalization of idea based on edge locks is described in Buckley
and Silberschatz, “Concurrency Control in Graph Protocols by Using
Edge Locks,” Proc. ACM SIGACT-SIGMOD Symposium on the Principles
of Database Systems, 1984.
15.5
Answer: Consider the tree-structured database graph given below.
Practice Exercises 3
c
A
c
B
c
C
Schedule possible under tree protocol but not under 2PL:
T
1
T
2
lock (A)
lock (B)
unlock (A)
lock (A)
lock (C)
unlock (B)
lock (B)
unlock (A)
unlock (B)
unlock (C)
Schedule possible under 2PL but not under tree protocol:
T
1
T
2
lock (A)
lock (B)
lock (C)
unlock (B)
unlock (A)
unlock (C)
15.6 Answer:
The proof is in Kedem and Silberschatz, “Locking Protocols: From Exclu-
sive to Shared Locks,” JACM Vol. 30, 4, 1983. (The proof of serializability
and deadlock freedom of the original tree protocol may be found in Sil-
berschatz and Kedem, “Consistency in Hierarchical Database Systems”,
JACM Vol. 27, 1, Jan 1980.)
It is worth noting that if the protocol were modified to allow update
transactions to lock any data item first, non-serializable executions can
occur. Intuitively, a long running readonly transaction T
0
may precede an
update transaction T
1
on node a , but continues to holds a lock on child
node b. After T
1
updates a and commits, readonly transaction T
2
reads a,
and thus T
1
precedes T
2
. However, T
2
now overtakes T
1
, share locking b
and its child c (not possible with only exclusive locks), and reads c and
剩余10页未读,继续阅读
以墨健康道
- 粉丝: 25
- 资源: 307
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0