Chapter 16: Concurrency Control Lock- Based Protocols(基于锁的协议) Timestamp- Based protocols(基于肘间戳的协议 Validation- Based Protocols(基于有效性检查的协议) Multiple Granularity(多粒度 Multiversion schemes(多版本机制 Deadlock Handling(死锁处理) Insert and Delete Operations(插入与删除处理) 标 Database System Concepts 3rd Edition 16.1 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.1 ©Silberschatz, Korth and Sudarshan rd Edition Chapter 16: Concurrency Control Lock-Based Protocols（基于锁的协议） Timestamp-Based Protocols（基于时间戳的协议） Validation-Based Protocols（基于有效性检查的协议） Multiple Granularity（多粒度） Multiversion Schemes（多版本机制） Deadlock Handling（死锁处理） Insert and Delete Operations（插入与删除处理）
Lock-Based Protocols(基于锁的协议) A lock is a mechanism to control concurrent access to a data item Data items can be locked in two modes 1. exclusive排他锁(x) mode Data item can be both read as well as written. X-lock is requested using lock-X nstruction 2. shared共享锁(S)mode. Data item can only be read.S lock is requested using lock-s instruction. Lock requests are made to concurrency-control manager. Transaction can proceed only after request is granted. 标 Database System Concepts 3rd Edition 16.2 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.2 ©Silberschatz, Korth and Sudarshan rd Edition Lock-Based Protocols（基于锁的协议） A lock is a mechanism to control concurrent access to a data item Data items can be locked in two modes : 1. exclusive排他锁(X) mode. Data item can be both read as well as written. X-lock is requested using lock-X instruction. 2. shared共享锁(S) mode. Data item can only be read. Slock is requested using lock-S instruction. Lock requests are made to concurrency-control manager. Transaction can proceed only after request is granted
Lock-Based Protocols(Cont) 6 ck-compati bility matrix(锁相容性矩阵) s true false X false false A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions Any number of transactions can hold shared locks on an item, but if any transaction holds an exclusive on the item no other transaction may hold any lock on the item If a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transactions have been release ed. The lock is then granted d Database System Concepts 3rd Edition 16.3 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.3 ©Silberschatz, Korth and Sudarshan rd Edition Lock-Based Protocols (Cont.) Lock-compatibility matrix（锁相容性矩阵） A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions Any number of transactions can hold shared locks on an item, but if any transaction holds an exclusive on the item no other transaction may hold any lock on the item. If a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transactions have been released. The lock is then granted
Lock-Based Protocols(Cont) Example of a transaction performing locking: T1: lock-X(B) lock-S(A) read(B read(A) B:=B-50 unlock(A) write (B) lock-S(B) unlock(B) read(B) lock-X(A unlock( B); read(A) display(A+B) A:=A+50 write(A) unlock(B) Database System Concepts 3rd Edition 16.4 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.4 ©Silberschatz, Korth and Sudarshan rd Edition Lock-Based Protocols (Cont.) Example of a transaction performing locking: T1: lock-X(B) T2 : lock-S(A) read (B) read (A) B:=B-50 unlock(A) write(B) lock-S(B) unlock(B) read (B) lock-X(A) unlock(B); read(A) display(A+B) A:=A+50 write(A) unlock(B)
Lock-Based Protocols(Cont. concurrency-control manager lock-X(B) grant-x(B,T1) read (B) B:=B-50 write(B) unlock(B) lock-S(A grant-S A,T2) read(A) unlock(A lock-S(B) grant-s(B, T2) read(B) unlock(B display(A+B) lock-X(A) grant-X(A, T1) read (A A:=A+50 write(A) unlock(B) Database System Concepts 3rd Edition 16.5 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.5 ©Silberschatz, Korth and Sudarshan rd Edition Lock-Based Protocols (Cont.) T1 T2 concurrency-control manager lock-X(B) grant-X(B,T1) read (B) B:=B-50 write(B) unlock(B) lock-S(A) grant-S(A,T2) read (A) unlock(A) lock-S(B) grant-S(B,T2) read (B) unlock(B) display(A+B) lock-X(A) grant-X(A,T1) read(A) A:=A+50 write(A) unlock(B)
Pitfalls of lock-Based protocols Consider the partial schedule T lock-X (B) read(B) B:=B-50 write (B) ock-S(A) read(a) lock-S(B) lock-X(A) Such a situation is called a deadlock(死锁) To handle a deadlock one of T3 or Tg must be rolledback and its locks released Database System Concepts 3rd Edition 16.6 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.6 ©Silberschatz, Korth and Sudarshan rd Edition Pitfalls of Lock-Based Protocols Consider the partial schedule Such a situation is called a deadlock（死锁）. To handle a deadlock one of T3 or T4 must be rolledback and its locks released
Pitfalls of Lock-Based Protocols(Cont) he potential for deadlock exists in most locking protocols Deadlocks are a necessary evil Starvation(53t)is also possible if concurrency control manager is badly designed. For example T5 T6 T7 T8 lock-S(Q) Lock×(Q) lock-S(Q) unlock(Q) lock-S(Q) unlock(Q) unlock(Q) Database System Concepts 3rd Edition 16.7 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.7 ©Silberschatz, Korth and Sudarshan rd Edition Pitfalls of Lock-Based Protocols (Cont.) The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil. Starvation（饿死） is also possible if concurrency control manager is badly designed. For example: T5 T6 T7 T8 lock-S(Q) Lock-X(Q) lock-S(Q) unlock(Q) lock-S(Q) unlock(Q) unlock(Q)
The Two-Phase Locking Protocol 两段侦协议) This is a protocol which ensures conflict-serializable schedules Phase1: Growing Phase(增长阶段) x transaction may obtain locks x transaction may not release locks Phase2: Shrinking Phase(缩减阶段) x transaction may release locks x transaction may not obtain locks The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points封锁点(e. the point where a transaction acquired its final lock) Database System Concepts 3rd Edition 16.8 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.8 ©Silberschatz, Korth and Sudarshan rd Edition The Two-Phase Locking Protocol （两段锁协议） This is a protocol which ensures conflict-serializable schedules. Phase 1: Growing Phase（增长阶段） transaction may obtain locks transaction may not release locks Phase 2: Shrinking Phase（缩减阶段） transaction may release locks transaction may not obtain locks The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points 封锁点 (i.e. the point where a transaction acquired its final lock)
The Two-Phase Locking Protocol(Cont) TWO-phase locking does not ensure freedom from deadlocks Cascading roll-back is possible under two-phase locking To avoid this follow a modified protocol called strict two- phase locking(严格两段锁). Here a transaction must hold all its exclusive locks till it commits/aborts Rigorous two- phase locking(强两段锁) is even stricter: here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit 标 Database System Concepts 3rd Edition 16.9 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.9 ©Silberschatz, Korth and Sudarshan rd Edition The Two-Phase Locking Protocol (Cont.) Two-phase locking does not ensure freedom from deadlocks Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol called strict twophase locking（严格两段锁）. Here a transaction must hold all its exclusive locks till it commits/aborts. Rigorous two-phase locking（强两段锁） is even stricter: here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit
The Two-Phase Locking Protocol(Cont) T lock-X(A) read(a) lock-S(B) read ( B write(A) unlock(A) lock-X(A) read(A) write(A) unlock(A) lock-S(A) ead(A) 标 Database System Concepts 3rd Edition 16.10 OSilberschatz, Korth and Sudarshan
Database System Concepts 3 16.10 ©Silberschatz, Korth and Sudarshan rd Edition The Two-Phase Locking Protocol (Cont.)