数据库第4章并发控制.ppt

第4章 并发控制,本章要点,并发操作及影响 理解事务的概念 并发操作的可串行性 并发控制及实现技术,序言,事务并行地运行可充分利用系统资源 事务是构成单一逻辑工作单元的操作集合,是并发控制的基本单位. 多用户数据库系统中允许多个用户同时使用数据库，即在同一时刻可能有多个事务并行运行.,举例:并发控制,这种数据库的不一致是由并发操作引起的,机票数量A,A=16,A=15,A=15,售票点,售票点,A=16,A=16,出售1,出售1,事务T1,事务T2,4.1 事 务 事务 事务是构成单一逻辑工作单元的操作集合。它必须以原子的方式执行，即：所有的操作要么都做，要么都不做，是一个不可分割的工作单位。 事务的性质(ACID) 原子性（Atomicity） 一致性（Consistency） 隔离性（Isolation） 持久性（Durability）,事务的开始与结束,1.开始事务 用“BEGIN TRANSACTION” 定义事务的开始 2.结束事务 结束事务通常以下两种方式： （1）成功：COMMIT （2）不成功：ROLLBACK,事务的状态 事务的执行状态分为5种： 活动状态 部分提交状态 失败状态 中止状态 提交状态,图4.1 事务的状态转换图,4.2事务调度与并发控制,事务的调度 事务调度的概念： 调度（Schedule）：事务的执行次序。 串行调度（Serial Schedule）：多个事务依次串行执行，且只有当一个事务的所有操作都执行完后才执行另一个事务的所有操作。 并行调度（Concurrent Schedule）：利用分时的方法处理多个事务。,并发控制 当多个事务中的多个事务并发执行时，有可能无法保证事务之间的隔离性，并破坏数据库的一致性、正确性。因此，DBMS的一个重要任务就是要有一种机制去保证事务在并发的存取和修改数据的时候的完整性不被破坏。 并发控制机制就是一种在多用户环境下对数据库进行并发操作进行规范的机制，是衡量DBMS性能的重要标志之一。 并发控制能给数据库的操作带来很大好处，最明显的有以下两点： （1）改善系统的资源利用率 （2）改善短事务的响应时间,数据的不一致性,经过大量实例分析，发现并发操作的不正确调度可能会带来三种数据不一致性。 丢失修改 读“脏”数据 不可重复读,并发操作引起的丢失修改,丢失修改 事务T1对数据的修改被事务T2的修改覆盖,并发操作引起的读脏数据,读脏数据 事务T1 修改了某数据并写回磁盘，事务T2 读取了同一数据后，T1由于某种原因被撤销，被修改的值复原，此时T2读到的数据与数据库中的数据不一致,T1 读C=1 C=C*2 写回C=2 ROLLBACK C恢复为1,T2 读C=2,并发操作引起的不可重复读,不可重复读 事务T1读取某一数据后，事务T2对其做了修改，当T1按同样条件再读时得到不同的值 事务T1读取某些数据后，事务T2删除(或插入)了一些记录，当T1按同样条件再读时发现少(或多)了一些记录,T1 读A=1,B=2 求A+B=3 读A=1,B=4 求A+B=5,T2 读B=2 B=B*2 写回B=4,小结,产生上述三类不一致性的主要原因 并发操作破坏了事务的隔离性，事务间相互干扰 并发控制的主要技术 封锁技术 (Locking),可串行化准则 假设事务都是串行运行的，一个事务结束（提交或者退回）后，另一个事务才能开始运行，那么就可以认为所有事务的运行结果都是正确的。尽管这些事务假如以不同的顺序运行，可能会对数据库造成不同的影响。 以此为判断标准，我们将可串行化的并发调度当作判断事务并发操作的唯一正确性准则。 即：假如并发操作调度的结果与按照某种顺序串行执行这些操作的结果相同，就认为并发操作是正确的。,例 并发事务的不同调度策略:假设A,B初值均为2, T1: 读B; A=B+1; 写回A; T2: 读A; B=A+1; 写回B,T1,T2,T1,T2,T1,T2,Y = B = 2,A = Y + 1,X = A = 3,写回B(=4),B = X + 1,a 串行调度,c 不可串行化的调度,Y = B = 2,A = Y + 1,写回A(=3),X = A = 2,写回B(=3),B = X + 1,Y = B = 2,A = Y + 1,写回A(=3),Lock A, B,X = A = 3,写回B(=4),B = X + 1,等待,等待,等待,T1,T2,Y = B = 3,A = Y + 1,写回A(=4),X = A = 2,写回B(=3),B = X + 1,d 可串行化的调度,b 串行调度,写回A(=3),结果: A = 3, B=4,结果: A = 4, B=3,结果: A = 3, B=3,结果: A = 3, B=4,Lock A, B . . .,ULock A, B,ULock A, B,4.3 封锁管理,封锁机制 1.封锁的定义 所谓封锁指的是事务T对某个数据对象（如关系、记录等）进行操作以前，先请求系统对其加锁，成功加锁之后该事务就对该数据对象有了控制权，在事务T释放它的锁之前，其他的事务不能更新此数据对象，只有事务T对其解锁之后，其他的事务才能更新它。,封锁是实现并发控制的一个重要的技术。,有两种基本的封锁类型：,排它锁(X锁,写锁)： 若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁 共享锁(S锁,读锁)： 若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁,2.封锁的粒度,封锁的粒度即封锁对象的大小，如 逻辑单元：属性、元组、关系、索引、数据库等 物理单元：页、块等 封锁粒度对并发控制的影响 封锁粒度越大，并发度越小，系统封锁开销越小； 封锁粒度越小，并发度越高，系统封锁开销越大；,修改属性,修改关系,如何选择封锁粒度:综合考虑系统并发度和并发控制开销,活锁和死锁,活锁 举例说明： 事务T1封锁某数据后，事务T2请求封锁未获得并等待，而T1释放锁后，事务T3请求封锁并获得，T3释放锁后，事务T4请求封锁并获得T2可能永远等待 解决办法：采用先来先服务的策略,死锁 举例说明： 事务T1和T2各自封锁了数据R1和R2后，又各自请求封锁R2和R1，因都无法获得而等待对方释放的现象 解决的两类方法 预防死锁 允许发生死锁，采用一定手段定期诊断并解除死锁,死锁的预防,一次封锁法 办法：每个事务一次将所有要使用的数据全部加锁 顺序封锁法 办法：预先规定数据对象的封锁顺序，所有事务均按此顺序,超时法 办法：等待时间超过规定的时限 等待图法 办法：画等待图，发现回路,死锁的诊断,两段锁协议,概念：事务对数据项的加锁和解锁分为两个阶段完成 获得封锁：在对数据读写之前首先申请并获得封锁； 释放封锁：在释放一个封锁后不再申请和获得任何其他封锁 如遵守两段锁协议的事务 如不遵守两段锁协议的事务, Slock A Slock B Xlock C .,Unlock B Unlock A Unlock C , Slock A,Unlock B ,Slock B Xlock C .,Unlock C ,Slock D,三个级别的封锁协议,1级封锁协议 内容：写数据前加X锁直至事务结束 事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK） 评价：是否可解决 丢失修改？ 读脏数据？ 可重复读？,可防止, 不能保证, 不能防止,T1,T2,T1,T2,T1,T2,Xlock A,获得Xlock A,读A = 16,A = A -1,写回A = 15,Commit,Unlock A,Xlock A,等待,等待,获得Xlock A,读A = 15,Commit,Unlock A,等待,等待,A = A -1,写回A = 14,Slock A,Slock B,读A = 50,求和 = 150,读A = 50,Commit,Unlock A,Xlock B,等待,等待,获得Xlock B,读B = 100,Commit,Unlock B,等待,等待,B = B * 2,写回B = 200,读B = 100,读B = 100,求和 = 150,Unlock B,等待,等待,等待,等待,Xlock C,读C = 100,C= C * 2,写回C = 200,Rollback (C恢复为100),Unlock C,Slock C,等待,等待,获得Slock C,读C = 100,Commit,Unlock C,等待,1级 : 没有丢失修改,3级 :可重复读,2级 :不读脏数据,用封锁机制解决三种数据不一致性的示例,2级封锁协议 内容： 读数据前加S锁，读完即释放 写数据前加X锁直至事务结束 评价：是否可解决 丢失修改？ 读脏数据？ 可重复读？,可防止, 不能保证,可防止,3级封锁协议 内容： 读数据前加S锁直至事务结束 写数据前加X 锁直至事务结束 评价：是否可解决 丢失修改？ 读脏数据？ 可重复读？,可防止,能保证,可保证,小结 用封锁协议解决问题,用什么封锁协议解决以下问题？ 丢失修改？ 读脏数据？ 不能重复读？,1级封锁,2级封锁,3级封锁,4.4 查询优化的一般策略,对于一个较复杂的查询要求，通常都可以用几种不同的表达式来表达，它们的结果应该是相同的，但执行的过程可能有很大差别。,例 假设Student表200条学生记录，SC表有300条选课记录，查询学生李明选修的所有课程成绩，可以用多个关系代数表达式实现。试比较它们的区别。,E1=Score (Student.Sno=SC.Sno and Student.Sname=李明(Student SC),E2=Score (Student.Sname=李明(Student SC),E3=Score (Student.Sname=李明Student) SC),先做Student和 SC笛卡尔积,生成的临时表有200 300= 60000条记录,在其中查询符合条件(Student.Sno=SC.Sno and Student.Sname=李明)的记录,最后投影到属性Score上.,先做Student和 SC的自然连接,生成的临时表有不超过300条记录,在其中查询符合条件Student.Sname=李明的记录,最后投影到属性Score上.,先查询Student表中符合条件Student.Sname=李明的记录,只有1条,再和SC表进行自然连接, 李明选了多少门课,生成的临时表就有多少条记录, 最后投影到属性Score上., 选择运算尽早进行。 投影运算与选择运算同时进行。 将笛卡儿积与随后的选择运算合并为连接运算。 投影运算与其他运算同时进行。 寻找公共子表达式并将结果加以存储。 对文件进行预处理。,我们希望在系统开销尽量小的情况下对查询进行尽可能的优化，一般采用以下策略：,4.5 关系代数的等价变换,变换规则： 1.连接或笛卡儿积的交换律 E1 E2 E2 E1 E1 E2 E2 E1,2.连接或笛卡儿积的结合律 （E1 E2） E3 E1 （ E2 E3） （E1 E2） E3 E1 （ E2 E3）,. 以下略,参见教材P73,应用举例,B, D20010101, S.LN=L.LN and B.BN=L.BN,S L,图书管理系统关系模式如下: Book(BN ,Title, Author, Publisher) Student(LN,Name, Class) Loan(LN, BN, Date),要求：查询2001年元旦前借出的图书书名和借书的学生姓名。,语法树,Title,Name, Title,Name ( D20010101 ( S.LN=L.LN and B.BN=L.BN