《事务调度与并发控制.docx》由会员分享，可在线阅读，更多相关《事务调度与并发控制.docx（17页珍藏版）》请在三一文库上搜索。
1、四级数据库第八章-事务调度与并发控制8.1 并发控制概述在第七章中己经讲到，事务是并发控制的基本单位，保证事务ACID特性是事务处理的重要任务，而事务ACID特性可能遭到 破坏的原因之一是多个事务对数据库的并发操作造成的。为了保证事务的隔离性更般，为了保证数据库的一致性，DBMS需要对并 发操作进行正确调度。这些就是数据库管理系统中并发控制机制的责任。下面先来看一个例子，说明并发操作带来的数据的不一致性问题。考虑飞机订票系统中的一个活动序列： 甲售票点(甲事务)读出某航班的机票余额A，设A=16 ； 乙售票点(乙事务)读出同一航班的机票余额A，也为16 ； 甲售票点卖出一机票，修改余额 AAI
2、,所以A为15,把A写回数据库； 乙售票点也卖出一机票，修改余额 AAI，所以A为15,把A写回数据库。结果明明卖出两机票，数据库中机票余额只减少1。这种情况称为数据库的不一致性。这种不一致性是由并发操作引起的。在并发操作情况下，对甲、乙两个事务的操作序列的调度是随 机的。若按上面的调度序列执行，甲事务的修改就被丢失。这是由于第步中乙事务修改 A并写回后覆盖了甲事务的修改。仔细分析并发操作带来的数据不一致性包括三类：丢失修改、不可重复读和读“脏”数据*如图8.1 所示。1 丢失修改( Lost Update)两个事务T1和T2。读入同一数据并修改，T2提交的结果破坏了 T1提交的结果，导致T1
3、的修改被丢失，如图8.1 (a)所示。上面飞机订票例子就属此类。图8.1T:02 4 14）:A-15（）Tj A-50金 &-1W 电fl*flmaNBC-63*It:it B-100 fi9fl cm% LOOiB W 不 qrasa二神商攵期命Mt（C） ItM2 .不可重复读(Non-Repeatable Read)不可重复读是指事务T1读取数据后，重复T2执行更新操作，使T1无法再现前一次读取结果。具体地讲，不可重复读包括三种情况：(1) 事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不同的值。例如在图8.1 (b)中，T1读取B=100进行运算
4、，T2读取同一数据B对其进行修改后将B=200写回数据库。T1为了对读取值校对重读B，B己为200，与第1次读取值不一致。(2)事务T1按一定条件从数据库中读取了某些数据记录后，事务当T1再次按T2删除了其中部分记录，相同条件读取数据时，发现某些记录神秘地消失了。(3)事务T1按一定条件从数据库中读取某些数据记录后，事务再次按相同条件T2插入了一些记录，当T1读取数据时，发现多了一些记录。后两种不可重复读有时也称为幻影(Phantom Row)现象。3 .读脏”数据(Dirty Read)读脏”数据是指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，这时T
5、1己修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就为脏”数据，即不正确的数据。例如在图8.1(C)中T1将C值修改为200，T2读到C为200，而T1由于 某种原因撤销，其修改作废，C恢复原值100，这时T2读到的C为200，与数据库容不一致就是脏”数据。产生上述三类数据不一致性的主要原因是并发操作破坏了事务的隔离性。并发控制就是要用正确的方式调度并发操作，使一个用户事 务的执行不受其他事务的干扰，从而避免造成数据的不一致性。另一方面，对数据库的应用有时允许某些不一致性，例如有些统计工作涉及数据量很大，读到一些脏”数据对统计精度没什么影响， 这时可以降低对一致
6、性的要求以减少系统开销。并发控制的主要技术是封锁(Locking)。例如在飞机订票例子中，甲事务要修改A，若在读出A前先锁住A，其他事务就不能再读取和修改A了，直到甲修改并写回A后解除了对A的封锁为止。这样，就不会丢失甲的修改。8.2 封锁（Locking ）封锁是实现并发控制的一个非常重要的技术。所谓封锁就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其他的事务不能更新此数据对象。确切的控制由封锁的类型决定。基本的封锁类型有两种：排它锁(Exclusive Locks，简称X锁)和共享锁(Share
7、 Locks，简称S锁)。排它锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。共享锁又称为读锁。若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能 加X锁，直到T释放A上的S锁。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。排它锁与共享锁的控制方式可以用图8.2的相容矩阵来表示。图8.2X曲sflYVvY-YH.YffiH摇愤夬那的棚那曲阳在图8.2的封锁类型相容矩阵中，最左边一列表示事务T
8、1已经获得的数据对象 上的锁的类型，其中横线表示没有加锁。最上面一行表示另一事务T2对同一数据对象发出 的封锁请求。T2的封锁请求能否被满足用矩阵中的Y和N表示，其中Y表示事务T2的封 锁要求与T1已持有的锁相容，封锁请求可以满足。N表示T2的封锁请求与T1己持有的锁 冲突，T2的请求被拒绝。8.3封锁协议在运用X锁和S锁这两种基本封锁，对数据对象加锁时，还需要约定一些规则，例如何时申请X锁或S锁、持锁时间、何时释放等。称这些规则为封锁协议(Locking Protocol )。对封锁方式规定不同的规则，就形成了各种不同的封锁协议。下面介绍三级封锁协议。对并发操作的不正确调度可能会带来丢失修改
9、、不可重复读和读脏”数据等不一致性问题，三级封锁协议分别在不同程度上解决了这一问题。为并发操作的正确调度提供一定的保证。不同级别的封锁协议达到的系统一致性级别是不同的。一、一级封锁协议一级封锁协议是：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束(COMMIT )和非正常结束(ROLLBACK )。一级封锁协议可防止丢失修改，并保证事务T是可恢复的。例如图8.3 ( a )使用一级封锁协议解决了图8.1 (a)中的丢失修改问题。图8.3 (a )事务T1在读A进行修改之前先对A加X锁，当T2再请求对A加X锁时被拒绝，T2只能等待T1释放A上的 锁后T2获得对A
10、的X锁，这时它读到的A己经是T1更新过的值15，再按此新的A值进行运算，并将结果值A= 14送回到磁盘。这样就避免了丢失T1的更新。在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。二、二级封锁协议二级封锁协议是：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。二级封锁协议除防止了丢失修改，还可进一步防止读脏”数据。例如图8.3 ( C)使用二级封锁协议解决了图8.1 ( c)中的读脏”数据问题。图8.3 ( c)中，事务T1在对C进行修改之前，先对C加X锁，修改其值后写回磁盘。这时T2请求在C上加S锁，因T1
11、己在C上加了 X锁，T2只能等待。T1因某种原因被撤销，C恢复为原值100，T1释放 C上的X锁后T2获得C上的S锁，读C=100。这就避免了 T2读“脏”数据。在二级封锁协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读。三、三级封锁协议三级封锁协议是：一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。三级封锁协议除防止了丢失修改和不读“脏”数据外，还进一步防止了不可重复读。例如图8?3(b)使用三级封锁协议解决了图8.1 (b)不可重复读问题。图8.3 ( b)中，事务T1在读A，B之前，先对A，B力pi S锁，这样其它事务只能再对A，B加S锁，而不能加X
12、锁，即其他事务只能读A，B，而不能修改它们。所以当T2为修改B而申请对B的X锁时被拒绝只能等待T1 释放B上的锁。T1为验算再读A，B，这时读出的B仍是100，求和结果仍为150，即可重复读。T1结束才释放A，B上的S 锁。T2才获得对B的X锁。上述三级协议的主要区别在于什么操作需要申请封锁，以及何时释放锁(即持锁时间)。三个级别的封锁协议可以总结为表8.1。图8.3 XtaiA .0 a-i*：.:KWhAlA4 A* Al 幡dStaMA3il 3410-190Xtochb啤凫疔障？oia aMM C-MaHftOLLSATKWWVW() AnjLStOi-t) , w :Uihkvk A
13、 Xkxkti1 nltxhU为了保证并发操作的正确性，DBMS的并发控制机制必须提供一定的手段来保证调度是可串行化的。从理论上讲，在某一事务执行时禁止其他事务执行的调度策略一定是可串行化的调度，这也是最简单的调度策略，但这种方法实际上是不可取的，这使用户不能充分共享数据库资源。目前DBMS普遍采用封锁方法实现并发操作调度的可串行性，从而保证调度的正确性。两段锁（Two-Phase Locking ，简称2PL ）协议就是保证并发调度可串行性的封锁协议除此之外还有其他一些方法，如时标方法、乐观方法等来保证调度的正确性。8.6 两段锁协议所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁
14、。在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁；在释放一个封锁之后，事务不再申请和获得任何其他封锁。所谓两段”锁的含义是，事务分为两个阶段，第一阶段是获得封锁，也称为扩展阶段。在这阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。第二阶段是释放封锁，也称为收缩阶段。在这阶段，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁。例如事务T1遵守两段锁协议，其圭寸锁序列是：Slock A Stock R Xlock CUnlock I) Unlock A UnlockH扩展阶。1* 收毁H可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的
15、任何并发调度策略都是可串行化的。 需要说明的是，事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。也就是说；若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的：若对并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议。在图8.6中，（a）和（b）都是可串行化的调度，但（a）中T1和T2都遵守两段锁协议，（b）中T1和T2不遵守两段锁协议。又如图8.5中（d）是可串行化的调度，但T1和T2也不遵守两段锁协议。另外要注意两段锁协议和防止死锁的一次封锁法的异同之处。一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵
16、守两段锁协议；但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁，如图8.7所示。 图 8.6、8.7T. ： T3Slock B:渎 B=2;Y=B；Xlock A；Slock A:等待T,LSlock B读B=2Y=BUn lock BXiockASlock AA-Y+l写回A3Unlock BUnlock A:轴1:Slock A:读AT:Y=A:XIockB 1:B=Y+I:写回B -4:Unlock &:Unlock AA=Y*I写回A -3Unlock ASlock A 读A=3X=AUnlock AXlock BB-X+l 写回B=
17、4 UnlxkB(b)不遵守。月段碱协议(a)蹲守两的榛协议图8.6可串行化调度Slock BiAB-2Slock AiS A=2XlockAXhckB等待S&7遵守两段锁协议的事务发先死锁8.7.1多粒度封锁多粒度树。多粒度树的根结点是整个数据库，表示最大的数8.8给出了一个三级粒度树。根结点为数据库，数据库下面讨论多粒度封锁，首先定义 据粒度。叶结点表示最小的数据粒度。图 的子结点为关系，关系的子结点为元组。图8.8数据库关系R元组 元组元组元组8.8三级粒度树然后，来讨论多粒度封锁的封锁协议。多粒度封锁协议允许多粒度树中的每个结点被独立地在多粒度加锁。对一个结点加锁意味着这个结点的所有后
18、裔结点也被加以同样类型的锁封锁中一个数据对象可能因此以两种方式封锁，显式封锁和隐式封锁 显式封锁 是应事务的要求直接加到数据对象上的封锁：隐式封 锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。多粒度封锁方法中，显式封锁和隐式封锁的效果是一,样的，因此系统检查封锁冲突时不仅要检查显式封锁还要检查隐式封锁。 例如事务T要对关系R1加X锁。系统必须搜索其上级结点数据库、关系R1以及R1中的每一个元组，如果其中某一个数 据对象己经加了不相容锁，则T必须等待。一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显 式封锁是否
19、与该数据对象上的隐式封锁（即由于上级结点已加的封锁造成的）冲突；还要检查其所有下级结点，看上面的显式封 锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突。显然，这样的检查方法效率很低。为此人们引进了一种新型锁，称 为意向锁（Intention Lock ）。8.7.2意向锁意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它 的上层结点加意向锁。例如，对任一元组加锁时，必须先对它所在的关系加意向锁。于是，事务T要对关系R1加X锁时，系统只要检查根结点数据库和关系R1是否己加了不相容的锁，而不再需要搜索和 检查尺中的每一个元组是否加了 X锁。下
20、面介绍三种常用的意向锁：意向共享锁（Intent Share Lock，简称IS锁）；苣向排它锁（Intent Exclusive Lock，简称 IX 锁）；共享意向排它锁（Share Intent Exclusive Lock，简称 SIX 锁）。1 IS 锁如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。例如，要对某个元组加S锁，则要首先对关系和数据库 加is锁。2IX锁如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。例如，要对某个元组加X锁，则要首先对关系和数据 库加IX锁。3SIX锁如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S +
21、IX。例如对某个表加SIX锁，则表示该事务要 读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）。图8.9 （a）给出了这些锁的相容矩阵，从中可以发现这5种锁的强度如图 8.9 （ b）所示的偏序关系。所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的，反之则不然。具有意向锁的多粒度封锁方法中任意事务T要对一个数据对象加锁，必须先对它的上层结点加意向锁。申请封锁时应该按自上而下的次序进行；释放封锁时则应该按自下而上的次序进行。具有意向锁的多粒度封锁方法提高了系统的并发度，减少了加锁和解锁的开销，它己经在实际的数据库管理系统产品中得到广 泛应
22、用，例如新版的Oracle数据库系统就采用了这种封锁方法。图8.9tb）MRMt 的“序 X:鼻8.8 Oracle的并发控制前面讨论了并发控制的一般原则与方法，下面简单介绍Oracle数据库系统中的并发控制机制。Oracle采用封锁技术保证并发操作的可串行性。Oracle的锁分为两大类：数据锁（亦称DML锁）和字典锁。字典锁是Oracle DBMS部用于对字典表的封锁。字典锁包括语法分析锁和DDL锁，由DBMS在必要的时候自动加锁和释放锁，用户无权控制。Oracle主要提供了 5种数据锁：共享锁（S锁）、排它锁（X锁）、行级共享锁（RS锁）、行级排它锁（RX锁）和共享 行级排它锁（SRX锁）
23、。其封锁粒度包括行级和表级。数据锁的相容矩阵如图8.10所示。图 8.10sX11,r弹rNYXN强KWYuYYuYfcxNNYYKYSRXNYNNY! YvffiKJO OrnekLOCK TABLE可以看出Oracle的RS锁、RX锁、SRX锁实际上就是上面介绍的IS锁、IX锁、SIX锁。在通常情况F，数据封锁由系统控制，对用户是透明的。但Oracle也允许用户用语句显式对封锁对象加锁。Oracle数据锁的一个显著特点是，在缺省情况下，读数据不加锁。也就是说，当一个用户更新数据时，另一个用户可以同时读取相应数据，反之亦然。Oracle通过回滚段(Rollback Segnent)的存结构来保证用户不读脏”数据和可重复读。这样做的好处是提高了数据的并发度。Oracle提供了有效的死锁检测机制，周期性诊断系统中有无死锁，若存在死锁，则撤销执行更新操作次数最少的事务。