第10章 并发控制技术 10.1 并发控制概述 10.2 并发控制的正确性准则 10.3 加锁协议 10.4 死锁的检测、处理和预防

Presentation on theme: "第10章 并发控制技术 10.1 并发控制概述 10.2 并发控制的正确性准则 10.3 加锁协议 10.4 死锁的检测、处理和预防"— Presentation transcript:

1 第10章 并发控制技术 10.1 并发控制概述 10.2 并发控制的正确性准则 10.3 加锁协议 10.4 死锁的检测、处理和预防
10.5 多粒度封锁

2 10.1 并发控制概述 引言 数据库是一种共享资源，可以供多个用户使用。允许多个用户同时使用的数据库系统称为多用户数据库系统。
当多个用户并发地存取数据库时就会产生多个事务同时存取同一数据的情况。 若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。(例子说明：下一页） 所以数据库管理系统必须提供并发控制机制。 并发控制机制是衡量一个数据库管理系统性能的重要标志之一。

3 10.1 并发控制概述 例1： 丢失修改 T1 T2 写-写冲突 1）读A=16 （机票预订典型例子） 2) 读A=16 3) AA-1
例1： 丢失修改 T T 写-写冲突 1）读A= （机票预订典型例子） 2) 读A=16 3) AA-1 写回A=15 4) AA-1

4 10.1 并发控制概述 例2： 不能重复读 T1 T2 1) 读A=50 读—写冲突 读B=100 求和=150 2） 读B=100
例2： 不能重复读 T T2 1) 读A= 读—写冲突 读B=100 求和=150 2） 读B=100 BB*2 写回B 3)读A=50 读B=200 求和=250 (验算不对）

5 10.1 并发控制概述 例3: 读脏数据 T1 T2 1) 读C=100 读—写冲突 CC*2 写回C 2) 读C=200
例3: 读脏数据 T T2 1) 读C= 读—写冲突 CC*2 写回C 2) 读C=200 3) Rollback C恢复为100

6 10.1 并发控制概述 数据库系统中的并发 从上面例子看，数据库管理系统必须提供并发控制机制。
如果数据库中的事务顺序执行，即一个事务完全结束后，另一个事务才开始，则称这种执行方式为串行访问(serial access)。 如果DBMS可以同时接受多个事务，事务在时间上重叠执行，则称这种执行方式为并发访问(concurrent access)。 在单CPU系统中，同一时间只能有一个事务占用CPU，即各个事务需要交叉使用CPU，我们称这种执行方式为交叉并发(interleaved concurrency)。 在多CPU系统中，可以允许多个事务同时占用CPU，我们称这种执行方式为同时并发(simultaneous concurrency)。

7 10.1 并发控制概述 事务并发执行可能引起的问题（对例子的解释）） 下面我们先来看一个例子，说明并发操作可能带来的数据的不一致性问题。
考虑飞机订票系统中的一个活动序列: 1).甲售票点（甲事务）读出某航班的机票余额A,设A=16. 2).乙售票点（乙事务）读出同一航班的机票余额A,也为16. 3).甲售票点卖出一张机票,修改余额A←A-1.所以A为15,把A写回数据库. 4).乙售票点也卖出一张机票,修改余额A←A-1.所以A为15,把A写回数据库. 问题是，结果明明卖出两张机票，数据库中机票余额却只减少1张。

8 10.1 并发控制概述 仔细分析并发操作带来的数据不一致性包括三类： 丢失修改（lost update）
两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。上面飞机订票例子就属此类。 不可重复读（non-repeatable read） 不可重复读是指事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果。具体地讲，不可重复读包括三种情况: 事务T1读取某一数据后，事务T2对其做了修改，当事务1再次读该数据时，得到与前一次不同的值。例如T1读取B=100进行运算，T2读取同一数据B，对其进行修改后将B=200写回数据库。T1为了对读取值校对重读B，B已为200，与第一次读取值不一致。

9 10.1 并发控制概述 读“脏”数据（dirty read）
事务T1按一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按相同条件读取数据时，发现某些记录神密地消失了。 事务T1按一定条件从数据库中读取某些数据记录后，事务T2插入了一些记录，当T1再次按相同条件读取数据时，发现多了一些记录。 读“脏”数据（dirty read） 读“脏”数据是指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤消，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就为"脏"数据,即不正确的数据。

10 10.1 并发控制概述 并发控制的目标 产生上述三类数据不一致性的主要原因是并发操作破坏了事务的隔离性。
并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性。 此外，并发控制还应能提高系统资源利用率并改善短事务的响应时间。

11 10.1 并发控制概述 5。加锁法 T1 T2 1) 请求xLock A 读A=16 2) 请求xLock A 等待 3）AA—1 等待
Commit 等待 Unlock 等待 4） 获得 xLock A 读A=15 AA—1 写回A=14 Commit Unlock 得到正确结果：没有丢失修改

12 10.1 并发控制概述 封锁法的定义： 事务T向系统请求，对某个数据对象（最常用的是元组）加锁，其它事务不能更新此数据，直到T释放它的锁为止。 （Lock , Unlock) 类型：排它锁X锁（Exclusive Lock)----其它事务不能读取、更新此数据。 共享锁S锁（Share Lock) 其它事务可以读取，但不能更新此数据。 处理：加锁以后，结果正确。 但是，还需讨论如何调度的问题。

13 10.2 并发控制的正确性准则 基本定义 计算机系统对并发事务中并发操作的调度是随机的，而不同的调度可能会产生不同的结果，那么哪个结果是正确的，哪个是不正确的呢？（例子说明，不同的调度有不同的结果---下一页） 如果一个事务运行过程中没有其他事务同时运行，也就是说它没有受到其他事务的干扰，那么就可以认为该事务的运行结果是正常的或者预想的。 因此将所有事务串行起来的调度策略一定是正确的调度策略。虽然以不同的顺序串行执行事务可能会产生不同的结果，但由于不会将数据库置于不一致状态，所以都是正确的。 定义1：设数据库系统中参与并发 执行的事务集为{T1,T2,…,Tn},一个调度(schedule)S就是对n个事务中的所有操作执行次序的一个安排。 在一个调度中，不同事务的操作可以交叉执行，但必须保持同一个事务中各个操作的次序。

14 10.2 并发控制的正确性准则 不同调度有不同结果的例子： T1 T2 读B 读A A=B+1 B=A+1 写回A 写回B
A,B初值为 T1T A=3, B=4 T2T A=4, B=3 以下列出三种不同的调度方法，得到三种不同的结果：

15 10.2 并发控制的正确性准则 串行调度 不可串行化的调度 可串行化的调度 T1 T2 T1 T2 T1 T2
串行调度 不可串行化的调度 可串行化的调度 T T T T T T2 SLock B SLock B SLock B Y=B= Y=B Y=B=2 Unlock B SLock A UnLock B XLock A X=A= Xlock A A=Y UnLock B 写回A(=3) UnLock A Slock A Unlock A XLock A A=Y 等待 写回A(=3) 等待 SLock A A=Y UnLock A 等待 X=A= 写回A(=3) X=A=3 UnLock A XLock B UnLock A XLock B B=X Xlock A B=X 写回B(=3) B=X+1 写回B(=4) UnLock A 写回B(=4) UnLock B UnLock B UnLock B 结果：A=3, B= 结果：A=3,B=3(与T1T2,T2T1不同） 结果：A=3, B=4

16 10.2 并发控制的正确性准则 由上面的例子，我们必须讨论如何避免不可串行化的调度，提出有关可串行化调度的问题。 1）可串行化调度的定义
2）两段锁协议（2PL） 3）可串行化调度的定理

17 10.2 并发控制的正确性准则 定义2：设数据库系统中参与并发 执行的事务集为{T1,T2,…,Tn}，如果其中2个调度S1和S2，在数据库的任何初始状态下，所有读出的数据都是一样的，留给数据库的最终状态也是一样的，则称S1和S2是目标等价(view equivalence)的。 定义3：设数据库系统中参与并发 执行的事务集为{T1,T2,…,Tn}，如果其中的两个操作op1和op2满足下列条件： (1) 它们属于不同的事务； (2) 其中至少有一个写(Write)操作； 则称op1和op2是冲突操作。 冲突操作包括读-写冲突和写-写冲突两种。 定义4：设数据库系统中参与并发 执行的事务集为{T1,T2,…,Tn}，S为一个调度，我们将那些通过调换S中不冲突的操作所得到的新的调度称为S的冲突等价(conflict equivalence)调度。 显然，如果两个调度是冲突等价，一定是目标等价的；反之，未必正确。

18 10.2 并发控制的正确性准则 可串行化调度的定义： 多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。我们称这种调度策略为可串行化（Serializable）的调度。 定义5：设数据库系统中参与并发 执行的事务集为{T1,T2,…,Tn}， S为一个调度，如果S能与一个串行调度冲突(目标)等价，则称S是冲突(目标)可串行的。 可串行性（Serializability）是并发事务正确性的准则。 按这个准则规定，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确的调度。 一个调度S是否可串行，可用其前趋图(precedence graph)来判定。

19 10.2 并发控制的正确性准则 可串行性的判定方法 一个调度S是否可串行，可用其前趋图(precedence graph)来判定。
前趋图是一个有向图G=(V,E)，其中V是顶点的集合，E是边的集合。V包含所有参与调度事务。边可以通过分析事务之间的冲突操作获得。其规则如下： 如果2个事务Ti和Tj之间有一对冲突操作op1和op2，在S中op1被安排在op2之前，则在E中加入边：Ti → Tj。 可以证明: (1)如果前趋图中存在回路，则S不可能冲突等价于任何串行调度； (2)如果前趋图中不存在回路，则可以用拓扑排序得到S的一个等价的串行调度。 例1(见讲义P149例7-1)

20 10.2 并发控制的正确性准则 例2，现在有两个事务，分别包含下列操作： 事务T1：R1(B)；A=B+1；W1(A)；
事务T2：R2(A)；B=A+1；R2(B)； 假设A、B的初值均为2。 按T1?T2次序执行结果为A=3,B=4； 按T2?T1次序执行结果为B=3,A=4。 下面给出对这两个事务的4种不同的调度策略。 (a) R1(B);A=B+1;W1(A); R2(A);B=A+1;R2(B)； (b) R2(A);B=A+1;R2(B); R1(B);A=B+1;W1(A); (c) R1(B);A=B+1; R2(A); W1(A); B=A+1;R2(B)； (d) R2(A);B=A+1; R1(B); R2(B); A=B+1;W1(A);

21 10.2 并发控制的正确性准则 (a)和(b)为两种不同的串行调度策略，虽然执行结果不同，但它们都是正确的调度。
(c)中两个事务是交错执行的，由于其执行结果与(a)、(b)的结果都不同，所以是错误的调度。 (d)中两个事务也是交错执行的，其执行结果与串行调度(b)的执行结果相同，所以是正确的调度。 为了保证并发操作的正确性，DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。 目前DBMS普遍采用加锁方法实现并发操作调度的可串行性，从而保证调度的正确性。 两段锁（Two-Phase Locking，简称2PL）协议就是保证并发调度可串行性的加锁协议。 除此之外还有其他一些方法，如时标方法、乐观方法等来保证调度的正确性。

22 10.3 加锁协议(##) 概述 加锁是实现并发控制的一个非常重要的技术。
所谓加锁就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。 基本的加锁类型有3种: 排它锁(Exclusive locks 简记为X锁)和共享锁(Share locks 简记为S锁)及U锁。

23 10.3 加锁协议 排它锁(X锁) 排它锁(X锁)又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其它事务在T释放A上的锁之前不能再读取和修改A。 X锁相容矩阵见讲义P150图7-19 。 共享锁(S锁) 共享锁(S锁)又称为读锁。若事务T对数据对象A加上S锁，则事务可以T读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这就保证了其它事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。(S,X)锁的相容矩阵见讲义P153图7-24 。

24 10.3 加锁协议 U锁 除X锁、S锁两种所之外，又增加了U锁。事务在进行更新时，一般都需要先读出旧的内容，在内存中修改后，再将修改后的内容写回。在此过程中，除了最后写回阶段，被更新的数据对象仍然可被其他事务访问。U锁就是为此目的设置的。 事务在需要(或有可能)更新一个数据对象时，首先申请对它的U锁，数据对象加了U锁后，仍允许其他事务对其加S锁。 待最后需要写入时，事务再申请将U锁升级为X锁。由于不必在事务执行的全过程中加X锁，所以进一步提高了系统的并发度。(S,U,X)锁的相容矩阵见讲义P153图7-25。

25 10.3 加锁协议 加锁协议 在运用X锁、S锁和U锁这3种基本加锁，对数据对象加锁时，还需要约定一些规则，例如应何时申请X锁或S锁、持锁时间、何时释放等。 我们称这些规则为加锁协议（Locking Protocol）。对加锁方式规定不同的规则，就形成了各种不同的加锁协议。 下面介绍三级加锁协议。对并发操作的不正确调度可能会带来丢失修改、不可重复读和读“脏”数据等不一致性问题，三级加锁协议分别在不同程度上解决了这一问题。为并发操作的正确调度提供一定的保证。 应注意，不同级别的加锁协议达到的系统一致性级别是不同的。

26 10.3 加锁协议 1级加锁协议 1级加锁协议是：事务T在修改数据R之前必须先对其加X锁，直到事务结束(EOT)才释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。 1级加锁协议可防止丢失修改，并保证事务T是可恢复的。 在1级加锁协议中，如果仅仅是读数据而不对其进行修改，则不需要加锁，所以它不能保证可重复读及不读“脏”数据。

27 10.3 加锁协议 2级加锁协议 3级加锁协议 2级加锁协议是：1级加锁协议加上事务T在读取数据A之前必须先对其加S锁，读完后即可释放S锁。
2级加锁协议除了可以防止了丢失修改，还可进一步防止读“脏”数据。 3级加锁协议 3级加锁协议是：1级加锁协议加上事务T在读取数据A之前必须先对其加S锁，直到事务结束才释放。 3级加锁协议除防止了丢失修改和不读‘脏’数据外，还进一步防止了不可重复读。

28 10.3 加锁协议 3级加锁协议的比较

29 10.3 加锁协议 两段锁协议(2PL) 所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁：
1). 在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁，而且 2.) 在释放一个封锁之后，事务不再申请和获得任何其他封锁。 所谓“两段”锁的含义是，事务分为两个阶段，第一阶段是获得封锁，也称为扩展阶段。这在阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。 第二阶段是释放封锁，也称为收缩阶段。在这阶段，事务可以释放任何数据项上的任何类型的琐，但是不能再申请任何琐。

30 10.3 加锁协议 例如事务T1遵守两段锁协议，其封锁序列是： 例如事务T1遵守两段锁协议，其封锁序列是：
又如事务T2不遵守两段锁协议，其封锁序列是： Slock A … Unlock A … Slock B … Xlock C … Unlock C … Unlock B； 可串行化调度的定理： 若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。（具体见 p 定理7.8-1）

31 10.3 加锁协议 两段锁协议与一次封锁法的异同 8。 活锁 另外要注意两段锁协议和防止死锁的一次封锁法的异同之处。
一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议； 但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁。 8。 活锁 如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，当T1释放了R上的封锁之后系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁R，当T3释放了R上的封锁之后系统又批准了T4的请求，...，T2有可能永远等待，这就是活锁。 避免活锁的简单方法是采用“先来先服务”的策略。

32 10.4 死锁的检测、处理和预防 什么是死锁？ 和操作系统一样，基于封锁的并发控制方法可能引起死锁。
一个事务如果申请锁而没有获准，则其必须等待其他事务释放锁。这就形成事务间的等待关系。 当事务中出现循环等待时，如果不加干涉，则会一直等待下去，这就是死锁(dead lock)。讲义图7-26(P154)给出了一个死锁的例子。 对于死锁有两种方法：一是防止死锁的出现；二是由系统检测死锁，一旦发现则对其处理。

33 10.4 死锁的检测处理和预防 死锁的预防 一次封锁法
在数据库中，产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。 防止死锁的发生其实就是要破坏产生死锁的条件。预防死锁通常有以下几种方法： 一次封锁法 一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。 一次封锁法虽然可以有效地防止死锁的发生，但也存在问题，一次就将以后要用到的全部数据加锁，势必扩大了封锁的范围，从而降低了系统的并发度。

34 10.4 死锁的检测处理和预防 顺序封锁法 顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。
顺序封锁法可以有效地防止死锁，但也同样存在问题。 事务的封锁请求往往随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的顺序对数据对象加封。

35 10.4 死锁的检测处理和预防 一种比较实用的死锁预防方法
不难看出，在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点，因此下面介绍一种在DBMS中比较实用的死锁的预防方法。 在这种方法中，当事务申请锁而未获准时，不是一律等待，而是让某些事务卷回重执(retry)，以避免循环等待。 为区别事务开始执行的先后，每个事务开始时被赋予一个唯一的并随时间递增的整数，称为时间标记(time stamp,ts)。 设有2个事务TA和TB，如ts(TA)<ts(TB)，则TA表示早于TB 。也称TA比TB”年老“，或者说TB 比TA”年轻“ 。

36 10.4 死锁的检测处理和预防 事务重执一般有2种策略： 等待-死亡(wait-die)策略
在这种策略中，设TB已持有某数据对象R的锁， TA申请同一数据对象的锁而发生冲突时，则按如下规则处理 if ts(TA)<ts(TB) then TA waits; else{ rollback TA; /* Die */ restart TA with the same ts(TA); } 在这种策略中，总是年老的事务等待年轻的事务。 击伤-等待(wound-wait)策略 这种策略按另一规则处理冲突： if ts(TA) > ts(TB) then TA waits; else{ rollback TB; /* Die */ restart TB with the same ts(TB); 在这种策略中，总是年轻的事务等待年老的事务。

37 10.4 死锁的检测处理和预防 死锁的检测与解除 超时法 如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。
超时法实现简单，但其不足也很明显。 一是有可能误判死锁，事务因为其他原因使等待时间超过时限，系统会误认为发生了死锁。 二是时限若设置得太长，死锁发生后不能及时发现。

38 10.4 死锁的检测处理和预防 等待图法 死锁的解除 事务等待图是一个有向图G=(T,U)。 T为结点的集合，每个结点表示正运行的事务；
U为边的集合，每条边表示事务等待的情况。若T1等待T2,则T1、T2之间划一条有向边，从T1指向T2。 事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性地（比如每隔1分钟）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。 死锁的解除 死锁发生后，靠事务自身无法解除，必须由DBMS干预。 通常采用的方法是选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务得以继续运行下去。 当然，对撤消的事务所执行的数据修改操作必须加以恢复。

39 10.5 多粒度封锁 多粒度锁 多粒度封锁协议允许多粒度树中的每个结点被独立地加锁。
对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以两种方式封锁： 显式封锁 隐式封锁

40 10.5 多粒度封锁 意向锁 一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁（即由于上级结点已加的封锁造成的）冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突。 显然，这样的检查方法效率很低。为此人们引进了一种新型锁，称为意向锁（intention lock）。 意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点将要被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。 例如，对任一元组加锁时，必须先对它所在的关系加意向锁。 事务T要对关系R1加X锁时，系统只要检查根结点数据库和关系R1是否已加了不相容的锁，而不再需要搜索和检查R1中的每一个元组是否加了X锁。

41 10.6 多粒度封锁 下面介绍三种常用的意向锁：意向共享锁(intent share lock)，简记为IS锁，意向排它锁(intent exclusive lock)，简记为IX锁，共享意向排它锁(share intent exclusive lock)，简记为SIX锁。 IS锁 如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。例如，要对某个元组加S锁，则要首先对关系和数据库加IS锁。 IX锁 如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。例如，要对某个元组加X锁，则要首先对关系和数据库加IX锁。 SIX锁 如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX = S + IX。例如对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）。

42 10.6 多粒度封锁 图8.9(a）给出了这些锁的相容矩阵，从中可以发现这五种锁的强度有图8.9(B)所示的偏序关系。
所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的，反之则不然。 具有意向锁的多粒度封锁方法中任意事务T要对一个数据对象加锁，必须先对它的上层结点加意向锁。 申请封锁时应该按自上而下的次序进行； 释放封锁时则应该按自下而上的次序进行。 具有意向锁的多粒度封锁方法提高了系统的并发度，减少了加锁和解锁的开销，它已经在实际的数据库管理系统产品中得到广泛应用，例如IBM DB2 UDB DBMS中就采用了这种封锁方法。

43 10.6 多粒度封锁