本章内容提要
保证数据一致性是对数据库的最基本的要求 。 数据库的重要特征是它能为多个用户提供数据共享 。 因此,
DBMS必须提供并发控制机制来保证数据库的一致性 。
数据库的并发控制以事务为单位,通常使用封锁技术实现并发控制 。
本章介绍两类最常用的封锁和三级封锁协议 。 不同的封锁和不同级别的封锁协议所提供的系统一致性保证是不同的,提供数据共享度也是不同的 。
对数据对象施加封锁,会带来活锁和死锁问题,并发控制机制必须提供适合数据库特点的解决方法 。
第八章 并发控制本章重点：
数据库并发控制的基本原理与技术封锁协议两段锁协议本章难点：
封锁协议两段锁协议第八章 并发控制
数据库是一个共享资源，可以供多个用户使用。允许多个用户同时使用的数据库系统称为多用户数据库系统。
为了充分利用系统资源，发挥数据库共享资源的特点，
应该允许多个事务 并行 的执行。
当多个用户并发地存取数据库时就会产生多个事务同时存取同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。
所以 DBMS必须提供并发控制机制。
并发控制机制是衡量一个数据库管理系统性能的重要标志之一。
第八章 并发控制
例 1：考虑飞机订票系统中的一个活动序列,
1.甲售票点（甲事务）读出某航班的机票余额 A,设 A=16,
2.乙售票点（乙事务）读出同一航班的机票余额 A,也为
16.
3.甲售票点卖出一张机票,修改余额 A← A-1.所以 A为 15,把 A
写回数据库,
4.乙售票点也卖出一张机票,修改余额 A← A-1.所以 A为 15,
把 A写回数据库,
结果明明卖出两张机票，数据库中机票余额只减少 1
。
第八章 并发控制
8.1 并发控制概述
并发操作带来的数据不一致性包括三类：
（ A）丢失修改 （ lost update）
（ B）不可重复读 （ non-repeatable read）
（ C）读“脏”数据 （ dirty read）
第八章 并发控制
8.1 并发控制概述第八章 并发控制
8.1 并发控制概述
(A)丢失修改两个事务 T1和 T2读入同一数据并修改,T2提交的结果破坏了 T1提交的结果，导致 T1的修改被丢失。
第八章 并发控制
8.1 并发控制概述
T1 T2
⑴ 读 A=16
⑵ 读 A=16
⑶ A?A-1
写回 A=15
⑷ A?A-1
写回 A=15（ A）丢失修改第八章 并发控制
8.1 并发控制概述
（ B）不可重复读
不可重复读是指事务 T1读取数据后，事务 T2执行更新操作，使 T1无法再现前一次读取结果。
第八章 并发控制
8.1 并发控制概述
T1 T2
⑴ 读 A=50
读 B=100
求和 =150
⑵
⑶ 读 A=50
读 B=200
求和 =250
读 B=100
B?B× 2
写回 B=200
第八章 并发控制
8.1 并发控制概述
（ C） 读“脏”数据 T1 T2
⑴ 读 C=100
C?C× 2
写回 C=200
⑵
⑶ ROLLBACK
C恢复为 100
读 C=200
产生上述三类数据不一致性的主要原因是并发操作破坏了事务的隔离性。
并发控制就是要用正确的方式 调度 并发操作，使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性 ——这就是 DBMS中并发控制机制的责任。
并发控制的主要技术 ——封锁（ Locking）。
第八章 并发控制
8.1 并发控制概述
1,封锁的定义封锁 就是事务 T在对某个数据对象操作之前，先向系统发出请求，对其加锁。加锁后事务 T就对该数据对象有了一定的控制，在事务 T释放它的锁之前，其它的事务不能更新此数据对象。
2,封锁类型基本的封锁类型有两种,
排它锁 (Exclusive locks 简记为 X锁 )
共享锁 (Share locks 简记为 S锁 ).
第八章 并发控制
8.2 封锁（ Locking）
第八章 并发控制
8.2 封锁（ Locking）
（ 1）排它锁（又称为写锁）
若事务 T对数据对象 A加上 X锁，则 只允许 T读取和修改 A，
其它任何事务都不能再对 A加任何类型的锁，直到 T释放 A上的锁。
这就保证了其它事务在 T释放 A上的锁之前不能再读取和修改 A。
第八章 并发控制
8.2 封锁（ Locking）
（ 2）共享锁（又称为读锁）
若事务 T对数据对象 A加上 S锁，则事务 可以读 A但不能修改 A，其它事务只能再对 A加 S锁，而不能加 X锁，直到 T释放 A上的 S锁。
这就保证了其它事务可以读 A，但在 T释放 A上的 S锁之前不能对 A做任何修改。
第八章 并发控制
8.2 封锁（ Locking）
排它锁和共享锁的控制方式相容矩阵：
T2
T1
X S —
X N N Y
S N Y Y
— Y Y Y
Y= Yes 相容的请求 N= No 相容的请求注意,X 锁和 S锁是互斥的第八章 并发控制
8.3 封锁协议
在运用 X锁和 S锁这两种基本封锁，对数据对象加锁时，还需要约定一些规则，例如应何时申请 X锁或 S锁、持锁时间、何时释放等。我们称这些规则为封锁协议（ Locking Protocol）。
对封锁方式规定不同的规则，就形成了各种不同的封锁协议。
不同级别的封锁协议达到的系统一致性级别是不同的。
第八章 并发控制
8.3 封锁协议一,1级封锁协议
1级封锁协议是：事务 T在 修改数据 R之前必须先对其加 X锁,直到事务结束才释放。事务结束包括正常结束（ COMMIT）和非正常结束（ ROLLBACK）。 例 1,P269
（ A）
1级封锁协议可防止：丢失修改，
并保证事务 T是可恢复的。
在 1级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。
第八章 并发控制
8.3 封锁协议二,2级封锁协议
2级封锁协议是,1级封锁协议加上事务 T在读取数据 R之前必须先对其加 S锁,读完 后即可释放 S锁。
例 1,P269（ C）
2级封锁协议可防止：丢失修改防止读“脏”数据。
第八章 并发控制
8.3 封锁协议三,3级封锁协议
3级封锁协议是,1级封锁协议加上事务 T在读取数据 R
之前必须先对其加 S锁，直到 事务结束 才释放。
例 1,P269（ B）
3级封锁协议可防止：丢失修改读‘脏’数据不可重复读。
第八章 并发控制
8.3 封锁协议第八章 并发控制
8.4 活锁和死锁
和操作系统一样,封锁的方法可能引起活锁和死锁第八章 并发控制
8.4 活锁和死锁一、活锁 __避免活锁的简单方法是采用 先来先服务 的策略
Lock R
…
Unlock
…
…
Lock R
等待等待等待等待等待
Lock R
Lock R
Unlock
…
Lock R
等待等待等待
Lock R
第八章 并发控制
8.4 活锁和死锁二、死锁 T1 T2
Lock R1
Lock R2
等待等待等待等待
Lock R2
Lock R1
等待等待等待第八章 并发控制
8.4 活锁和死锁解决死锁问题主要有两类方法：
（ 1）预防死锁
（ 2）死锁的诊断与解除第八章 并发控制
8.4 活锁和死锁
1,死锁的预防
防止死锁的发生其实就是要破坏产生死锁的条件。
预防死锁通常有两种方法：
① 一次封锁法
② 顺序封锁法第八章 并发控制
8.4 活锁和死锁
① 一次封锁法一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。
一次封锁法的问题：
扩大了封锁的范围降低了系统的并发度第八章 并发控制
8.4 活锁和死锁
② 顺序封锁法顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。
顺序封锁法的问题：
事务的封锁请求可以是动态决定的，
因此很难按规定的顺序去施加封锁。
第八章 并发控制
8.4 活锁和死锁在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点。
DBMS在解决死锁的问题上普遍采用的是诊断并解除死锁的方法。
第八章 并发控制
8.4 活锁和死锁
2,死锁的诊断与解除
（ A）死锁的诊断方法：
① 超时法
② 等待图法第八章 并发控制
8.4 活锁和死锁
① 超时法
如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。
超时法实现简单，但其不足也很明显：
（ 1）有可能误判死锁，事务因为其他原因使等待时间超过时限，系统会误认为发生了死锁。
（ 2）时限若设置得太长，死锁发生后不能及时发现。
第八章 并发控制
8.4 活锁和死锁
② 等待图法事务等待图是一个有向图 G=(T,U)。 T为结点的集合，
每个结点表示正运行的事务； U为边的集合，每条边表示事务等待的情况。若 T1等待 T2,则 T1,T2之间划一条有向边，从 T1指向 T2。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（比如每隔 1分钟）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。
第八章 并发控制
8.4 活锁和死锁
（ B）死锁的解除方法：
（ 1）选择一个处理死锁代价最小的事务 ——祭品,将其撤消，释放此事务持有的所有的锁，使其它事务得以继续运行下去。
（ 2）对撤消的事务所执行的数据修改操作必须加以恢复。
第八章 并发控制
8.5 并发调度的可串行性
计算机系统对并发事务中并发操作的调度是 随机 的，
而不同的调度可能会产生不同的结果，那么哪个结果是正确的，哪个是不正确的呢？
如果一个事务运行过程中没有其他事务同时运行，
那么就可以认为该事务的运行结果是正常的或者预想的。因此 将所有事务串行起来的调度策略一定是正确的调度策略 。虽然以不同的顺序串行执行事务可能会产生不同的结果，但由于不会将数据库置于不一致状态，所以都是正确的。
第八章 并发控制
8.5 并发调度的可串行性可串行化定义：
多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。我们称这种调度策略为可串行化
（ Serializable）的调度。
可串行性 （ Serializability）是并发事务正确性的准则。按这个准则规定，一个给定的并发调度，
当且仅当它是可串行化的，才认为是 正确调度 。
（例 P272-273）
第八章 并发控制
8.5 并发调度的可串行性
为了保证并发操作的正确性,DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。
目前 DBMS普遍采用封锁方法实现并发操作调度的可串行性，从而保证调度的正确性。
两段锁（ Two-Phase Locking，简称 2PL）协议就是保证并发调度可串行性的封锁协议。
除此之外还有其他一些方法，如时标方法、乐观方法等来保证调度的正确性。
第八章 并发控制
8.6 两段锁协议两段锁协议 —— 是指所有事务必须分两个阶段对数据项加锁和解锁：
1,在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁。
2,在释放一个封锁之后，事务不再申请和获得任何其他封锁。
第八章 并发控制
8.6 两段锁协议
“两段”锁的含义：
事务分为两个阶段。
第一阶段 ——获得封锁，也称为扩展阶段。在这一阶段，
事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。
第二阶段 ——释放封锁，也称为收缩阶段。在这阶段，
事务可以释放任何数据项上的任何类型的琐，但是不能再申请任何琐。
第八章 并发控制
8.6 两段锁协议
例如事务 T1遵守两段锁协议，其封锁序列是：
又如事务 T2不遵守两段锁协议，其封锁序列是
Slock A … Unlock A … Slock B … Xlock C …
Unlock C … Unlock B ；
第八章 并发控制
8.6 两段锁协议
可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。
事务遵守两段锁协议是可串行化的充分条件，
而不是必要条件。
第八章 并发控制
8.6 两段锁协议注意 ——两段锁协议和防止死锁的一次封锁法的异同之处。
（ A）一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议；
（ B）两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁，（例 P275）
第八章 并发控制
8.6 两段锁协议遵守 两段锁协议的事务发生死锁
T1 T2
Slock B
读 B=2
Xlock A
等待等待
Slock A
读 A=2
Xlock B
等待第八章 并发控制
8.7 封锁的粒度
封锁的对象的大小称为封锁粒度（ Granularity）。
封锁的对象可以是逻辑单元，也可以是物理单元。
以关系数据库为例，封锁对象可以是：
这样一些逻辑单元,
属性值、
属性值的集合、
元组、
关系、
索引项、
整个索引整个数据库；
这样一些物理单元,
页 (数据页或索引页 )、
块等第八章 并发控制
8.7 封锁的粒度
封锁粒度与系统的并发度和并发控制的开销密切相关。
直观地看，封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；反之，封锁的粒度越小，并发度较高，但系统开销也就越大。
如果在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁
（ multiple granularity locking）。
第八章 并发控制
8.7 封锁的粒度
选择封锁粒度时应该同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以求得最优的效果。
一般说来，需要处理大量元组的事务可以以关系为封锁粒度；需要处理多个关系的大量元组的事务可以以数据库为封锁粒度；而对于一个处理少量元组的用户事务，以元组为封锁粒度就比较合适了。
第八章 并发控制
8.7 封锁的粒度
8.7.1 多粒度封锁
1.多粒度树定义多粒度树的根结点是整个数据库，表示最大的数据粒度，叶结点表示最小的数据粒度。
第八章 并发控制
8.7 封锁的粒度
2,多粒度封锁的封锁协议多粒度封锁协议 允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。
因此，在多粒度封锁中一个数据对象可能以两种方式封锁,
(A) 显式封锁
(B) 隐式封锁第八章 并发控制
8.7 封锁的粒度
(A)显式封锁 ____是应事务的要求直接加到数据对象上的封锁；
(B)隐式封锁 ____是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。
多粒度封锁中 显式封锁和隐式封锁的效果是一样的，
因此系统检查封锁冲突时要检查显式封锁和隐式封锁。
第八章 并发控制
8.7 封锁的粒度
一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁（即由于上级结点已加的封锁造成的）冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突。显然，这样的检查方法效率很低。为此人们引进了一种新型锁，称为意向锁（ intention lock）。
第八章 并发控制
8.7 封锁的粒度
8.7.2 意向锁
意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。
例如，对任一元组加锁时，必须先对它所在的关系加意向锁
于是，事务 T要对关系 R1加 X锁时，系统只要检查根结点数据库和关系 R1是否已加了不相容的锁，而不再需要搜索和检查 R1中的每一个元组是否加了 X锁。
第八章 并发控制
8.7 封锁的粒度三种常用的意向锁：
(1) 意向共享锁 (intent share lock)，简记为 IS锁
(2) 意向排它锁 (intent exclusive lock)，简记为 IX锁，
(3) 共享意向排它锁 (share intent exclusive lock)，简记为
SIX锁。
第八章 并发控制
8.7 封锁的粒度
1,IS锁如果对一个数据对象加 IS锁，表示它的后裔结点拟（意向）
加 S锁。例如，要对某个元组加 S锁，则要首先对关系和数据库加 IS锁
2,IX锁如果对一个数据对象加 IX锁，表示它的后裔结点拟（意向）
加 X锁。例如，要对某个元组加 X锁，则要首先对关系和数据库加 IX锁
3,SIX锁如果对一个数据对象加 SIX锁，表示对它加 S锁，再加 IX锁，即
SIX = S + IX。例如对某个表加 SIX锁，则表示该事务要读整个表
（所以要对该表加 S锁），同时会更新个别元组（所以要对该表加 IX锁）。
第八章 并发控制
8.7 封锁的粒度
图 8.9（ a）给出了这些锁的相容矩阵，从中可以发现这五种锁的强度有图 8.9（ b）所示的偏序关系。
所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的，
反之则不然。
第八章 并发控制
8.7 封锁的粒度第八章 并发控制
8.7 封锁的粒度
具有意向锁的多粒度封锁方法中任意事务 T要对一个数据对象加锁，必须先对它的上层结点加意向锁。申请封锁时应该按自上而下的次序进行；释放封锁时则应该按自下而上的次序进行。
具有意向锁的多粒度封锁方法提高了系统的并发度，
减少了加锁和解锁的开销，它已经在实际的数据库管理系统产品中得到广泛应用。
第八章 并发控制
8.8 Oracle的并发控制参阅 P278-279
第八章 并发控制小结：
数据库的重要特征是它能为多个用户提供数据共享 。
DBMS必须提供并发控制机制来协调并发用户的并发操作以保证并发事务的隔离性,保证数据库的一致性 。
数据库的并发控制以事务为单位,通常使用封锁技术实现并发控制 。 不同的封锁和不同级别的封锁协议所提供的系统一致性保证是不同的,提供数据共享度也是不同的 。
对数据对象施加封锁,会带来活锁和死锁问题,并发控制机制必须提供适合数据库特点的解决方法 。
保证数据一致性是对数据库的最基本的要求 。 数据库的重要特征是它能为多个用户提供数据共享 。 因此,
DBMS必须提供并发控制机制来保证数据库的一致性 。
数据库的并发控制以事务为单位,通常使用封锁技术实现并发控制 。
本章介绍两类最常用的封锁和三级封锁协议 。 不同的封锁和不同级别的封锁协议所提供的系统一致性保证是不同的,提供数据共享度也是不同的 。
对数据对象施加封锁,会带来活锁和死锁问题,并发控制机制必须提供适合数据库特点的解决方法 。
第八章 并发控制本章重点：
数据库并发控制的基本原理与技术封锁协议两段锁协议本章难点：
封锁协议两段锁协议第八章 并发控制
数据库是一个共享资源，可以供多个用户使用。允许多个用户同时使用的数据库系统称为多用户数据库系统。
为了充分利用系统资源，发挥数据库共享资源的特点，
应该允许多个事务 并行 的执行。
当多个用户并发地存取数据库时就会产生多个事务同时存取同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。
所以 DBMS必须提供并发控制机制。
并发控制机制是衡量一个数据库管理系统性能的重要标志之一。
第八章 并发控制
例 1：考虑飞机订票系统中的一个活动序列,
1.甲售票点（甲事务）读出某航班的机票余额 A,设 A=16,
2.乙售票点（乙事务）读出同一航班的机票余额 A,也为
16.
3.甲售票点卖出一张机票,修改余额 A← A-1.所以 A为 15,把 A
写回数据库,
4.乙售票点也卖出一张机票,修改余额 A← A-1.所以 A为 15,
把 A写回数据库,
结果明明卖出两张机票，数据库中机票余额只减少 1
。
第八章 并发控制
8.1 并发控制概述
并发操作带来的数据不一致性包括三类：
（ A）丢失修改 （ lost update）
（ B）不可重复读 （ non-repeatable read）
（ C）读“脏”数据 （ dirty read）
第八章 并发控制
8.1 并发控制概述第八章 并发控制
8.1 并发控制概述
(A)丢失修改两个事务 T1和 T2读入同一数据并修改,T2提交的结果破坏了 T1提交的结果，导致 T1的修改被丢失。
第八章 并发控制
8.1 并发控制概述
T1 T2
⑴ 读 A=16
⑵ 读 A=16
⑶ A?A-1
写回 A=15
⑷ A?A-1
写回 A=15（ A）丢失修改第八章 并发控制
8.1 并发控制概述
（ B）不可重复读
不可重复读是指事务 T1读取数据后，事务 T2执行更新操作，使 T1无法再现前一次读取结果。
第八章 并发控制
8.1 并发控制概述
T1 T2
⑴ 读 A=50
读 B=100
求和 =150
⑵
⑶ 读 A=50
读 B=200
求和 =250
读 B=100
B?B× 2
写回 B=200
第八章 并发控制
8.1 并发控制概述
（ C） 读“脏”数据 T1 T2
⑴ 读 C=100
C?C× 2
写回 C=200
⑵
⑶ ROLLBACK
C恢复为 100
读 C=200
产生上述三类数据不一致性的主要原因是并发操作破坏了事务的隔离性。
并发控制就是要用正确的方式 调度 并发操作，使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性 ——这就是 DBMS中并发控制机制的责任。
并发控制的主要技术 ——封锁（ Locking）。
第八章 并发控制
8.1 并发控制概述
1,封锁的定义封锁 就是事务 T在对某个数据对象操作之前，先向系统发出请求，对其加锁。加锁后事务 T就对该数据对象有了一定的控制，在事务 T释放它的锁之前，其它的事务不能更新此数据对象。
2,封锁类型基本的封锁类型有两种,
排它锁 (Exclusive locks 简记为 X锁 )
共享锁 (Share locks 简记为 S锁 ).
第八章 并发控制
8.2 封锁（ Locking）
第八章 并发控制
8.2 封锁（ Locking）
（ 1）排它锁（又称为写锁）
若事务 T对数据对象 A加上 X锁，则 只允许 T读取和修改 A，
其它任何事务都不能再对 A加任何类型的锁，直到 T释放 A上的锁。
这就保证了其它事务在 T释放 A上的锁之前不能再读取和修改 A。
第八章 并发控制
8.2 封锁（ Locking）
（ 2）共享锁（又称为读锁）
若事务 T对数据对象 A加上 S锁，则事务 可以读 A但不能修改 A，其它事务只能再对 A加 S锁，而不能加 X锁，直到 T释放 A上的 S锁。
这就保证了其它事务可以读 A，但在 T释放 A上的 S锁之前不能对 A做任何修改。
第八章 并发控制
8.2 封锁（ Locking）
排它锁和共享锁的控制方式相容矩阵：
T2
T1
X S —
X N N Y
S N Y Y
— Y Y Y
Y= Yes 相容的请求 N= No 相容的请求注意,X 锁和 S锁是互斥的第八章 并发控制
8.3 封锁协议
在运用 X锁和 S锁这两种基本封锁，对数据对象加锁时，还需要约定一些规则，例如应何时申请 X锁或 S锁、持锁时间、何时释放等。我们称这些规则为封锁协议（ Locking Protocol）。
对封锁方式规定不同的规则，就形成了各种不同的封锁协议。
不同级别的封锁协议达到的系统一致性级别是不同的。
第八章 并发控制
8.3 封锁协议一,1级封锁协议
1级封锁协议是：事务 T在 修改数据 R之前必须先对其加 X锁,直到事务结束才释放。事务结束包括正常结束（ COMMIT）和非正常结束（ ROLLBACK）。 例 1,P269
（ A）
1级封锁协议可防止：丢失修改，
并保证事务 T是可恢复的。
在 1级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。
第八章 并发控制
8.3 封锁协议二,2级封锁协议
2级封锁协议是,1级封锁协议加上事务 T在读取数据 R之前必须先对其加 S锁,读完 后即可释放 S锁。
例 1,P269（ C）
2级封锁协议可防止：丢失修改防止读“脏”数据。
第八章 并发控制
8.3 封锁协议三,3级封锁协议
3级封锁协议是,1级封锁协议加上事务 T在读取数据 R
之前必须先对其加 S锁，直到 事务结束 才释放。
例 1,P269（ B）
3级封锁协议可防止：丢失修改读‘脏’数据不可重复读。
第八章 并发控制
8.3 封锁协议第八章 并发控制
8.4 活锁和死锁
和操作系统一样,封锁的方法可能引起活锁和死锁第八章 并发控制
8.4 活锁和死锁一、活锁 __避免活锁的简单方法是采用 先来先服务 的策略
Lock R
…
Unlock
…
…
Lock R
等待等待等待等待等待
Lock R
Lock R
Unlock
…
Lock R
等待等待等待
Lock R
第八章 并发控制
8.4 活锁和死锁二、死锁 T1 T2
Lock R1
Lock R2
等待等待等待等待
Lock R2
Lock R1
等待等待等待第八章 并发控制
8.4 活锁和死锁解决死锁问题主要有两类方法：
（ 1）预防死锁
（ 2）死锁的诊断与解除第八章 并发控制
8.4 活锁和死锁
1,死锁的预防
防止死锁的发生其实就是要破坏产生死锁的条件。
预防死锁通常有两种方法：
① 一次封锁法
② 顺序封锁法第八章 并发控制
8.4 活锁和死锁
① 一次封锁法一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。
一次封锁法的问题：
扩大了封锁的范围降低了系统的并发度第八章 并发控制
8.4 活锁和死锁
② 顺序封锁法顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。
顺序封锁法的问题：
事务的封锁请求可以是动态决定的，
因此很难按规定的顺序去施加封锁。
第八章 并发控制
8.4 活锁和死锁在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点。
DBMS在解决死锁的问题上普遍采用的是诊断并解除死锁的方法。
第八章 并发控制
8.4 活锁和死锁
2,死锁的诊断与解除
（ A）死锁的诊断方法：
① 超时法
② 等待图法第八章 并发控制
8.4 活锁和死锁
① 超时法
如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。
超时法实现简单，但其不足也很明显：
（ 1）有可能误判死锁，事务因为其他原因使等待时间超过时限，系统会误认为发生了死锁。
（ 2）时限若设置得太长，死锁发生后不能及时发现。
第八章 并发控制
8.4 活锁和死锁
② 等待图法事务等待图是一个有向图 G=(T,U)。 T为结点的集合，
每个结点表示正运行的事务； U为边的集合，每条边表示事务等待的情况。若 T1等待 T2,则 T1,T2之间划一条有向边，从 T1指向 T2。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（比如每隔 1分钟）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。
第八章 并发控制
8.4 活锁和死锁
（ B）死锁的解除方法：
（ 1）选择一个处理死锁代价最小的事务 ——祭品,将其撤消，释放此事务持有的所有的锁，使其它事务得以继续运行下去。
（ 2）对撤消的事务所执行的数据修改操作必须加以恢复。
第八章 并发控制
8.5 并发调度的可串行性
计算机系统对并发事务中并发操作的调度是 随机 的，
而不同的调度可能会产生不同的结果，那么哪个结果是正确的，哪个是不正确的呢？
如果一个事务运行过程中没有其他事务同时运行，
那么就可以认为该事务的运行结果是正常的或者预想的。因此 将所有事务串行起来的调度策略一定是正确的调度策略 。虽然以不同的顺序串行执行事务可能会产生不同的结果，但由于不会将数据库置于不一致状态，所以都是正确的。
第八章 并发控制
8.5 并发调度的可串行性可串行化定义：
多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。我们称这种调度策略为可串行化
（ Serializable）的调度。
可串行性 （ Serializability）是并发事务正确性的准则。按这个准则规定，一个给定的并发调度，
当且仅当它是可串行化的，才认为是 正确调度 。
（例 P272-273）
第八章 并发控制
8.5 并发调度的可串行性
为了保证并发操作的正确性,DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。
目前 DBMS普遍采用封锁方法实现并发操作调度的可串行性，从而保证调度的正确性。
两段锁（ Two-Phase Locking，简称 2PL）协议就是保证并发调度可串行性的封锁协议。
除此之外还有其他一些方法，如时标方法、乐观方法等来保证调度的正确性。
第八章 并发控制
8.6 两段锁协议两段锁协议 —— 是指所有事务必须分两个阶段对数据项加锁和解锁：
1,在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁。
2,在释放一个封锁之后，事务不再申请和获得任何其他封锁。
第八章 并发控制
8.6 两段锁协议
“两段”锁的含义：
事务分为两个阶段。
第一阶段 ——获得封锁，也称为扩展阶段。在这一阶段，
事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。
第二阶段 ——释放封锁，也称为收缩阶段。在这阶段，
事务可以释放任何数据项上的任何类型的琐，但是不能再申请任何琐。
第八章 并发控制
8.6 两段锁协议
例如事务 T1遵守两段锁协议，其封锁序列是：
又如事务 T2不遵守两段锁协议，其封锁序列是
Slock A … Unlock A … Slock B … Xlock C …
Unlock C … Unlock B ；
第八章 并发控制
8.6 两段锁协议
可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。
事务遵守两段锁协议是可串行化的充分条件，
而不是必要条件。
第八章 并发控制
8.6 两段锁协议注意 ——两段锁协议和防止死锁的一次封锁法的异同之处。
（ A）一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议；
（ B）两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁，（例 P275）
第八章 并发控制
8.6 两段锁协议遵守 两段锁协议的事务发生死锁
T1 T2
Slock B
读 B=2
Xlock A
等待等待
Slock A
读 A=2
Xlock B
等待第八章 并发控制
8.7 封锁的粒度
封锁的对象的大小称为封锁粒度（ Granularity）。
封锁的对象可以是逻辑单元，也可以是物理单元。
以关系数据库为例，封锁对象可以是：
这样一些逻辑单元,
属性值、
属性值的集合、
元组、
关系、
索引项、
整个索引整个数据库；
这样一些物理单元,
页 (数据页或索引页 )、
块等第八章 并发控制
8.7 封锁的粒度
封锁粒度与系统的并发度和并发控制的开销密切相关。
直观地看，封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；反之，封锁的粒度越小，并发度较高，但系统开销也就越大。
如果在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁
（ multiple granularity locking）。
第八章 并发控制
8.7 封锁的粒度
选择封锁粒度时应该同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以求得最优的效果。
一般说来，需要处理大量元组的事务可以以关系为封锁粒度；需要处理多个关系的大量元组的事务可以以数据库为封锁粒度；而对于一个处理少量元组的用户事务，以元组为封锁粒度就比较合适了。
第八章 并发控制
8.7 封锁的粒度
8.7.1 多粒度封锁
1.多粒度树定义多粒度树的根结点是整个数据库，表示最大的数据粒度，叶结点表示最小的数据粒度。
第八章 并发控制
8.7 封锁的粒度
2,多粒度封锁的封锁协议多粒度封锁协议 允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。
因此，在多粒度封锁中一个数据对象可能以两种方式封锁,
(A) 显式封锁
(B) 隐式封锁第八章 并发控制
8.7 封锁的粒度
(A)显式封锁 ____是应事务的要求直接加到数据对象上的封锁；
(B)隐式封锁 ____是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。
多粒度封锁中 显式封锁和隐式封锁的效果是一样的，
因此系统检查封锁冲突时要检查显式封锁和隐式封锁。
第八章 并发控制
8.7 封锁的粒度
一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁（即由于上级结点已加的封锁造成的）冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突。显然，这样的检查方法效率很低。为此人们引进了一种新型锁，称为意向锁（ intention lock）。
第八章 并发控制
8.7 封锁的粒度
8.7.2 意向锁
意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。
例如，对任一元组加锁时，必须先对它所在的关系加意向锁
于是，事务 T要对关系 R1加 X锁时，系统只要检查根结点数据库和关系 R1是否已加了不相容的锁，而不再需要搜索和检查 R1中的每一个元组是否加了 X锁。
第八章 并发控制
8.7 封锁的粒度三种常用的意向锁：
(1) 意向共享锁 (intent share lock)，简记为 IS锁
(2) 意向排它锁 (intent exclusive lock)，简记为 IX锁，
(3) 共享意向排它锁 (share intent exclusive lock)，简记为
SIX锁。
第八章 并发控制
8.7 封锁的粒度
1,IS锁如果对一个数据对象加 IS锁，表示它的后裔结点拟（意向）
加 S锁。例如，要对某个元组加 S锁，则要首先对关系和数据库加 IS锁
2,IX锁如果对一个数据对象加 IX锁，表示它的后裔结点拟（意向）
加 X锁。例如，要对某个元组加 X锁，则要首先对关系和数据库加 IX锁
3,SIX锁如果对一个数据对象加 SIX锁，表示对它加 S锁，再加 IX锁，即
SIX = S + IX。例如对某个表加 SIX锁，则表示该事务要读整个表
（所以要对该表加 S锁），同时会更新个别元组（所以要对该表加 IX锁）。
第八章 并发控制
8.7 封锁的粒度
图 8.9（ a）给出了这些锁的相容矩阵，从中可以发现这五种锁的强度有图 8.9（ b）所示的偏序关系。
所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的，
反之则不然。
第八章 并发控制
8.7 封锁的粒度第八章 并发控制
8.7 封锁的粒度
具有意向锁的多粒度封锁方法中任意事务 T要对一个数据对象加锁，必须先对它的上层结点加意向锁。申请封锁时应该按自上而下的次序进行；释放封锁时则应该按自下而上的次序进行。
具有意向锁的多粒度封锁方法提高了系统的并发度，
减少了加锁和解锁的开销，它已经在实际的数据库管理系统产品中得到广泛应用。
第八章 并发控制
8.8 Oracle的并发控制参阅 P278-279
第八章 并发控制小结：
数据库的重要特征是它能为多个用户提供数据共享 。
DBMS必须提供并发控制机制来协调并发用户的并发操作以保证并发事务的隔离性,保证数据库的一致性 。
数据库的并发控制以事务为单位,通常使用封锁技术实现并发控制 。 不同的封锁和不同级别的封锁协议所提供的系统一致性保证是不同的,提供数据共享度也是不同的 。
对数据对象施加封锁,会带来活锁和死锁问题,并发控制机制必须提供适合数据库特点的解决方法 。
