《郭文明精品》PPT课件.ppt

软件学院 郭文明2004.08,数据库系统概论讲义,8. 并发控制,事务处理技术主要包括数据库恢复和并发控制。 当多个用户并发地存取数据库时可能产生多个事务同时存取同一数据的情况。如果对并发操作不加控制就可能破坏数据的一致性。 并发控制的核心问题 对并发操作进行正确调度，有效控制。 在保证一致性的前提下最大限度地提高并发度。,软件学院 郭文明2004.08,数据库系统概论讲义,8. 并发控制,不同事务中各个步骤的执行顺序必须以某种方式进行规范，控制这些步骤的功能由DBMS的调度器部件完成。保证并发执行的事务能保持一致性的整个过程称为并发控制。,事务管理器,调度器,缓冲区,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,DBMS在处理用户提交事务时的策略，即事务调度。调度是一个或多个事务的操作按时间排列的一个序列。表示事务的指令在系统中执行的时间顺序。 如果一个调度的动作是事务顺序排列，顺序执行，也即事务没有混合，那么称这一调度为串行调度。 如果一个调度的动作是事务之间可以混合，那么称这一调度为并行调度。,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,事务的调度 一组事务的调度必须保证 包含了所有事务的操作指令 一个事务中指令的顺序必须保持不变。 串行调度 在串行调度中，属于同一事务的指令紧挨在一起。 对于有n个事务的事务组，可以有n！个有效调度。 并行调度 在并行调度中，来自不同事务的指令可以交叉执行。 当并行调度等价于某个串行调度时，则称它是正确的。,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,并行 Vs 串行 基本比较 并行事务可能会破坏数据库的一致性。 串行事务效率低。 并行的优点 一个事务由不同的步骤组成，所涉及的系统资源也不同。这些步骤可以并发执行，以提高系统的吞吐量。 系统中存在着周期不等的各种事务，串行会导致难于预测的时延。如果各个事务所涉及的是数据库的不同部分，采用并发会减少平均响应时间。,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,事务执行示例,T1: read(A); A := A 50; write(A); read(B); B := B + 50; write(B);,T2: read(A); temp := A0.1 A := A temp; write(A); read(B); B := B + temp; write(B);,从A过户 50￥到B,从A过户存款 的10%到B,开始状态： A=1000￥ B=2000￥ A+B=3000￥,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,read(A); A := A 50; write(A); read(B); B := B + 50; write(B);,read(A); temp := A0.1 A := A temp; write(A); read(B); B := B + temp; write(B);,T1,T2,A=950￥ B=2050￥,结束状态： A=855￥ B=2145￥ A+B=3000￥,串 行 调 度 1,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,read(A); A := A 50; write(A); read(B); B := B + 50; write(B);,read(A); temp := A0.1 A := A temp; write(A); read(B); B := B + temp; write(B);,T1,T2,A=900￥ B=2100￥,结束状态： A=850￥ B=2150￥ A+B=3000￥,串 行 调 度 2,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,read(A); A := A 50; write(A);,read(B); B := B + temp; write(B);,T1,T2,A=950￥ B=2000￥,结束状态： A=855￥ B=2145￥ A+B=3000￥,read(B); B := B + 50; write(B);,read(A); temp := A0.1 A := A temp; write(A);,A=855￥ B=2000￥,A=855￥ B=2050￥,并 行 调 度 3,软件学院 郭文明2004.08,数据库系统概论讲义,8.1 并发操作,read(A); A := A 50;,B := B + temp; write(B);,T1,T2,A=1000￥ B=2000￥,结束状态： A=950￥ B=2100￥ A+B=3050￥,write(A); read(B); B := B + 50; write(B);,read(A); temp := A0.1 A := A temp; write(A); read(B);,A=900￥ B=2000￥,A=950￥ B=2000￥,A=950￥ B=2050￥,并 行 调 度 4,软件学院 郭文明2004.08,数据库系统概论讲义,8.2 并发操作事务一致性,并发操作带来的数据不一致性包括三类： 丢失修改：两个事务T1和T2读入同一数据并修改，一个事务T2的提交破坏了另一个事务T1提交的结果，导致T1的修改丢失。 不可重复读：事务T1读取数据后，事务T2执行更新操作，使T1无法再次显现前一次的读取结果。 事务T2执行update，T1两次读取值不一样； 事务T2执行delete，T1两次读取记录数不一样； 事务T2执行insert，T1两次读取记录不一样； 读脏数据：事务T2执行更新操作，事务T1读取数据后，事务T2撤消了原来的操作，使T1读取数据为脏数据。,软件学院 郭文明2004.08,数据库系统概论讲义,8.2 并发操作事务一致性,read(A); A1 := A; read(B); B1 := B; A1 + B1 = 2950;,read(B); B := B + 50; write(B);,T1,T2,A=1000￥ B=2000￥,read(A); A := A 50; write(A);,读 脏 数 据,软件学院 郭文明2004.08,数据库系统概论讲义,8.2 并发操作事务一致性,read(A); A1 := A,T1,T2,A=1000￥ B=2000￥,read(A); A := A 50; write(A); read(B); B := B + 50; write(B);,不 能 重 复 读,read(B); B1 := B A1+B1=3050,A=950￥ B=2050￥,软件学院 郭文明2004.08,数据库系统概论讲义,8.2 并发操作事务一致性,read(A); A := A 50;,T1,T2,A=1000￥ B=2000￥,read(A); temp := A0.1 A := A temp; write(A); read(B);,丢 失 修 改,write(A); read(B); B := B + 50; write(B);,B := B + temp; write(B);,结束状态： A=950￥ B=2100￥ A+B=3050￥,软件学院 郭文明2004.08,数据库系统概论讲义,8.2 并发操作事务一致性,产生三类数据不一致性的主要原因是并发操作破坏了事务的隔离性。 并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性。 并发控制的主要技术是封锁、时间戳和有效性确认。,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,封锁的定义 封锁就是一个事务对某个数据对象加锁，取得对它一定的控制，限制其它事务对该数据对象使用。 并发控制的基本方法就是封锁。 封锁的类型 排它锁（X锁，eXclusive lock，写锁）：事务T对数据对象R加上X锁，则其它事务对R的任何封锁请求都不能成功，直至T释放R上的X锁。 共享锁（S锁，Share lock，读锁）：事务T对数据对象R加上S锁，则其它事务对R的X锁请求不能成功，而对R的S锁请求可以成功。,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,排他锁和共享锁相容矩阵,相容请求,不相容请求,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,封锁粒度 封锁对象：属性值、属性值集合、元组、关系、某索引项、整个索引、整个数据库、物理页、块。 封锁粒度大，则并发度低，封锁机构简单，开销小。 封锁粒度小，则并发度高，封锁机构复杂，开销高。 在同一个系统中同时支持多种封锁粒度供不同的事务选择，这种封锁方法称为多粒度封锁。 理想的情况是只封锁与规定的操作有关的的数据对象，这些数据对象称作事务的完整性相关域。,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,封锁方法 直接封锁 事务对它要进行存取的数据对象直接申请加锁。,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,分层封锁 数据对象从大到小有一种层次关系，当封锁了外层数据对象时也就意味着同时封锁了它的所有内层数据对象。,数据库,段,关系,元组,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,意向（预约）封锁 在分层封锁中，封锁了上层节点就意味着封锁了所有内层节点。 隐式封锁是该数据对象没有显式加锁，是由于其上级节点加锁而使该数据对象加上了锁。 如果有事务T1对某元组加了S锁，而事务T2对该元组所在的关系准备加X锁，需依次判断该关系、该关系所在库、该关系中所有元组是否有S锁和X锁，否则隐含地X封锁了该元组，从而造成矛盾。 依次判断上下级对象是否有封锁冲突，效率低下。,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,意向（预约）封锁 引入意向锁I（Intend Lock）：当为某节点加上I锁，表明其某些内层节点已发生事实上的封锁；对某一对象加锁时，必须对它的上层节点加意向锁。 I锁的实施是从封锁层次的根开始，依次占据路径上的所有节点，直至要真正进行显式封锁的节点的父节点为止。 I锁的释放是按自下而上的次序进行。,软件学院 郭文明2004.08,数据库系统概论讲义,8.3 封锁,共享锁、排他锁、意向（预约）封锁相容矩阵,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,封锁协议：何时申请封锁、申请什么样的封锁、何时释放封锁的规则称为封锁协议。 保持到事务结束时才释放的锁称作长锁。在事务中途就可以释放的锁称作短锁。 封锁协议分为： 1级封锁协议：避免了丢失修改； 2级封锁协议：避免了丢失修改和读脏数据； 3级封锁协议：避免了丢失修改、读脏数据和不可重复读。,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,1级封锁协议 在更新中加长X锁。,1级封锁协议 BEGIN 长X锁 EOT,lock-X(A); read(A); A := A 1; write(A); commit； Unlock;,lock-X(A) Wait Wait Wait Wait read(A); A := A 1; write(A)； commit； Unlock;,T1,T2,保证不 丢失修改,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,1级封锁协议 BEGIN 长X锁 EOT,不能保证 读脏数据,read(A); A1 := A; read(B); B1 := B; A1 + B1 = 2950;,T2,A=1000￥ B=2000￥,Lock-X(A) Lock-X(B) read(A); A := A 50; write(A); read(B); B := B + 50; write(B); Unlock A Unlock B,T1,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,2级封锁协议 在更新中加长X锁，在查询中加短S锁。,保证不 读脏数据,2级封锁协议 BEGIN 短S锁 长X锁 EOT,Lock-S(A);Lock-S(B) Wait Wait Wait read(A); A1 := A; read(B); B1 := B; A1 + B1 = 3000;,T2,A=1000￥ B=2000￥,Lock-X(A);Lock-X(B) read(A); A := A 50; write(A); read(B); B := B + 50; write(B); Unlock A;Unlock B,T1,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,2级封锁协议 BEGIN 短S锁 长X锁 EOT,lock-S(A); read(A); A1 := A; unlock(A); lock-S(A); read(A); A1 := A; unlock(A); commit；,lock-X(A) read(A); A := A 1; write(A)； commit；,T1,T2,不能保证 可重复读,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,3级封锁协议 在更新中加长X锁，在查询中加长S锁。,3级封锁协议 BEGIN 长S锁 长X锁 EOT,软件学院 郭文明2004.08,数据库系统概论讲义,8.4 封锁协议,lock-S(A); read(A); A1 := A; read(A); A1 := A; commit； unlock(A);,lock-X(A) Wait Wait Wait Wait read(A); A := A 1; write(A)； commit；,T1,保证 可重复读,3级封锁协议 BEGIN 长S锁 长X锁 EOT,软件学院 郭文明2004.08,数据库系统概论讲义,8.5 死锁和活锁,死锁(Deadlock) 定义 两个事务都封锁了一些数据对象，并相互等待对方释放另一些数据对象以便对其封锁，结果两个事务都不能结束，则发生死锁。 死锁发生的条件 互斥条件：事务请求对资源的独占控制。 等待条件：事务已持有一定资源，又去申请并等待其它资源。 非抢占条件：直到资源被持有它的事务释放之前，不可能将该资源强制从持有它的事务夺去。,软件学院 郭文明2004.08,数据库系统概论讲义,8.5 死锁和活锁,循环等待条件：存在事务相互等待的等待圈。 定理：在条件成立的前提下，条件是死锁存在的充分必要条件。,R2,R1,R3,软件学院 郭文明2004.08,数据库系统概论讲义,8.5 死锁和活锁,解决死锁的方法 预防死锁 一次封锁法（预先占据所需的全部资源）。 顺序封锁法（所有资源预先排序）。 事务退出已占有资源。 死锁检测和恢复 超时法 等待图法 检测发现死锁后，撤消代价较小的事务，并对该事务做恢复处理。,软件学院 郭文明2004.08,数据库系统概论讲义,8.6 并发调度的可串行性,多个事务并发执行时，其结果与某一串行调度的结果相同，称这种调度为可串行化的。,read(A) A := A100 Write(A) read(B) B := B+100 write(B),read(A) A := A*2 write(A) read(B) B := B*2 write(B),T1,T2,A=1000￥ B=2000￥,A=2200￥ B=4200￥,并 行 的 可 串 行 化 调 度,软件学院 郭文明2004.08,数据库系统概论讲义,8.6 并发调度的可串行性,多个事务并发执行时，其结果与某一串行调度的结果相同，称这种调度为可串行化的。,read(A) A := A100 Write(A) read(B) B := B+100 write(B),read(A) A := A*2 write(A) read(B) B := B*2 write(B),T1,T2,A=1000￥ B=2000￥,A=2200￥ B=4100￥,不 可 串 行 化 调 度,软件学院 郭文明2004.08,数据库系统概论讲义,8.6 并发调度的可串行性,read(A) A := A100 Write(A) read(B) B := B+100 write(B),read(A) A := A*1 write(A) read(B) B := B*1 write(B),T1,T2,A=1000￥ B=2000￥,A=1100￥ B=2100￥,一个与事务语义有关的可串行化调度,软件学院 郭文明2004.08,数据库系统概论讲义,8.6 并发调度的可串行性,可串行化的技术采用封锁。,Lock-X(A) read(A); A := A100 Write(A); Unlock Wait Lock-X(B) read(B); B := B+100 write(B); Unlock,Wait Lock-X(A) read(A); A := A*2 write(A); Unlock Lock-X(B) read(B); B := B*2 write(B); Unlock,T1,T2,A=1000￥ B=2000￥,A=2200￥ B=4100￥,采用封锁的 不可串行化调度,软件学院 郭文明2004.08,数据库系统概论讲义,8.7 两段锁协议,一个惊人的条件下，可以保证事务调度的可串行化两段锁协议。在商用数据库系统中被广泛采用。 定理：若所有事务均遵从两段锁协议，则这些事务的所有并行调度都是可串行化的。,软件学院 郭文明2004.08,数据库系统概论讲义,8.7 两段锁协议,两段锁协议(Two-phase Locking，2PL) 内容： 在对任何数据进行读写之前，事务首先要获得对该数据的封锁。 在释放一个封锁之后，事务不再获得任何其它封锁。 即事务分为两个阶段： 生长阶段：获得封锁。 收缩阶段：释放封锁。,软件学院 郭文明2004.08,数据库系统概论讲义,8.7 两段锁协议示例,示例 lock-S(A)lock-S(B)lock-X(C) unlock(A) unlock(C)unlock(B) 遵从两段锁协议。 lock-S(A)unlock-S(A)lock-S(B) lock-X(C) unlock(C)unlock(B) 不遵从两段锁协议。,软件学院 郭文明2004.08,数据库系统概论讲义,8.7 两段锁协