并发控制-课件

第十一章第十一章 并发控制并发控制 1ppt课件主要内容主要内容11.1 并发控制概述并发控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并发调度的可串行性并发调度的可串行性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度2ppt课件11.1 并发控制概述并发控制概述n多事务执行方式多事务执行方式(1)事务串行执行事务串行执行(2)交叉并发方式交叉并发方式(3)同时并发方式同时并发方式n并发并发 是指在单处理机上，利用分时方法实行多个事务同是指在单处理机上，利用分时方法实行多个事务同时做。时做。n事务并发执行带来的问题事务并发执行带来的问题 可可能能会会存存取取和和存存储储不不正正确确的的数数据据，破破坏坏事事务务的的隔隔离离性性和一致性和一致性3ppt课件nDBMS必须提供并发控制机制必须提供并发控制机制nDBMS的并发控制子系统的并发控制子系统保证事务的隔离性保证事务的隔离性保证事务的一致性保证事务的一致性n对并发操作进行正确调度对并发操作进行正确调度4ppt课件并发操作带来的问题并发操作带来的问题1-丢失更新丢失更新时间时间更新事务更新事务T1T1数据库中数据库中A A的值的值更新事务更新事务T2T2t0t0100100t1t1R R（A A）t2t2R R（A A）t3t3A:=A-1A:=A-1t4t4A:=A-1A:=A-1t5t5W W（A A）t6t69999W（A）t7t79999图图 在时间在时间t7t7丢失了事务丢失了事务T1T1的更新的更新5ppt课件时间时间更新事务更新事务T1T1数据库中数据库中A A的值的值更新事务更新事务T2T2t0t0100100t1t1R R（A A）t2t2t3t3t4t4t5t5COMMITCOMMITt6t6图图 事务事务T1T1两次读取两次读取A A的值，却得到了不同的结果的值，却得到了不同的结果R R（A A）200200R R（A A）A:=A*2A:=A*2W W（A A）并发操作带来的问题并发操作带来的问题2-不可重复读问题不可重复读问题6ppt课件并发操作带来的问题并发操作带来的问题3-读脏数据读脏数据时间时间更新事务更新事务T1T1数据库中数据库中A A的值的值读事务读事务T2T2t0t0100100t1t1R R（A A）t2t2A:=A-30A:=A-30t3t3W W（A A）t4t47070R R（A A）t5t5ROLLBACKROLLBACKt6t6100100图图 事务事务T2T2在时间在时间t4t4读了未提交的读了未提交的A A值（值（7070）7ppt课件 并发控制就是并发控制就是用正确的方式调度并发用正确的方式调度并发操作操作，使一个用户事务的执行不受其他，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一事务的干扰，从而避免造成数据的不一致性。致性。8ppt课件11.2 封锁封锁 n封锁是实现并发控制的一个主要技术。封锁是实现并发控制的一个主要技术。n锁（锁（Lock）是一个与数据项相关的变量，对可能应用是一个与数据项相关的变量，对可能应用于该数据项上的操作而言，于该数据项上的操作而言，锁描述了该数据项锁描述了该数据项的状态。的状态。n两种封锁：两种封锁：-排他型（排他型（Exclusive）封锁（简称：）封锁（简称：X锁）锁）-共享型（共享型（Share）封锁（简称：）封锁（简称：S锁）锁）9ppt课件X锁（排它锁）锁（排它锁）n排它锁又称为写锁排它锁又称为写锁 若事务若事务T对数据对象对数据对象A加上加上X锁，则只允许锁，则只允许T读取读取和修改和修改A，其它任何事务都不能再对，其它任何事务都不能再对A加任何类型的加任何类型的锁，直到锁，直到T释放释放A上的锁。上的锁。nX锁的操作锁的操作nXlock A：表示事务对数据：表示事务对数据A加加X锁，并读数据锁，并读数据Anunlock A：表示事务要解除对数据：表示事务要解除对数据A的的X锁锁10ppt课件X锁锁nPX协议协议:使用使用X X锁的规则称为锁的规则称为PXPX协议。协议。任何企图更新记录任何企图更新记录R的事务必须的事务必须先执行先执行“Xlock R”操操作，以获得对作，以获得对R的的X锁，才能读或写记录锁，才能读或写记录R；如果未获准；如果未获准X锁，那么这个事务进入等待队列，一直到获准锁，那么这个事务进入等待队列，一直到获准X锁，事锁，事务才能继续做下去。务才能继续做下去。nPXC协议协议 X锁的解除操作应该合并到事务的结束（锁的解除操作应该合并到事务的结束（COMMIT或或ROLLBACK）操作中）操作中。引入此规则，。引入此规则，PX协议成为协议成为PXC协议协议。11ppt课件S锁（共享锁）锁（共享锁）nS锁定义锁定义 若事务若事务T对数据对象对数据对象A加上加上S锁，则事务锁，则事务T可以读可以读A但不能修改但不能修改A。其它事务只能再对其它事务只能再对A加加S锁，而锁，而不能加不能加X锁，直到锁，直到T释放释放A上的上的S锁。锁。n操作操作nSlock A 表示事务对数据表示事务对数据A加加S锁，并读数据。锁，并读数据。nUnlock A 表示事务要解除对数据表示事务要解除对数据A的的S锁。锁。允许并发的读，又称为允许并发的读，又称为读锁读锁12ppt课件n封锁的相容矩阵封锁的相容矩阵注：注：N=NO，不不相相容容的的请请求求Y=YES，相容的请求，相容的请求X、S、：分分别别表表示示X锁，锁，S锁，无锁锁，无锁如如果果两两个个封封锁锁是是不不相相容容的的，则则后后提提出出封封锁锁的的事事务务要要等待。等待。X S X S X XS S N N YN N Y N Y Y N Y Y Y Y Y Y Y Y T2T1 13ppt课件例：使用例：使用X锁封锁解决数据丢失锁封锁解决数据丢失时间时间更新事务更新事务T1T1数据库中数据库中A A的值的值更新事务更新事务T2T2t0t0100100t1t1Xlock AXlock At2t2Xlock AXlock At t3R（A）waitwaitt4t4A:=A-1A:=A-1waitwaitt5t5waitwaitt6t6W（A）waitwaitt7t7COMMIT9999waitwaitt8t8Unlock AUnlock Awaitwaitt9t9获得获得Xlock AXlock At10t10 R R（A A）t11t11A A：=A-1=A-1t12t129898W W（A A）14ppt课件11.3 活锁和死锁活锁和死锁 封锁技术可以有效地解决并行操作的一封锁技术可以有效地解决并行操作的一致性问题，但也带来一些新的问题。致性问题，但也带来一些新的问题。n死锁死锁n活锁活锁 15ppt课件1.“活锁活锁”T2Xlock AT3Xlock AT4Xlock AAA已被封锁，已被封锁，不成功，等待不成功，等待A刚被释刚被释放，成功放，成功时间点时间点A刚被释放，刚被释放，成功成功T2永远等待永远等待活锁！活锁！解决方法：先来先服务解决方法：先来先服务系统可能使某个事务永远处于等系统可能使某个事务永远处于等待状态，得不到封锁的机会，这待状态，得不到封锁的机会，这种现象称为种现象称为“活锁活锁”。16ppt课件2.“死锁死锁”时间时间事务事务T1事务事务T2t0XlockAt1XlockBt2XlockBt3waitXlockAt4waitwait出现了出现了T1 在等待在等待T2，而，而T2又在等待又在等待T1的局面，的局面，T1和和T2两个事务永远不两个事务永远不能结束，形成了死锁。能结束，形成了死锁。17ppt课件n 解决死锁的方法解决死锁的方法两类方法两类方法1）预防死锁预防死锁2）死锁的诊断与解除）死锁的诊断与解除18ppt课件1）死锁的预防）死锁的预防n预防死锁的发生就是要破坏产生死锁的预防死锁的发生就是要破坏产生死锁的条件。条件。n预防死锁的方法预防死锁的方法 一次封锁法一次封锁法 顺序封锁法顺序封锁法19ppt课件一次封锁法一次封锁法n要求每个事务必须一次将所有要使用的数据全要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行部加锁，否则就不能继续执行n一次封锁法存在的问题一次封锁法存在的问题 扩大封锁范围扩大封锁范围难于事先精确确定封锁对象难于事先精确确定封锁对象20ppt课件顺序封锁法顺序封锁法n顺序封锁法是预先对数据对象规定一个封锁顺顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。序，所有事务都按这个顺序实行封锁。n顺序封锁法存在的问题顺序封锁法存在的问题n 维护成本高维护成本高n 难于实现难于实现21ppt课件2）死锁的诊断与解除死锁的诊断与解除n允许死锁发生允许死锁发生n解除死锁解除死锁由由DBMS的并发控制子系统定期检测系统中的并发控制子系统定期检测系统中是否存在死锁是否存在死锁一旦检测到死锁，就要设法解除一旦检测到死锁，就要设法解除22ppt课件“死锁的诊断死锁的诊断”若事务等待图若事务等待图有环，则表示有环，则表示出现死锁出现死锁图图 事务的有环依赖图事务的有环依赖图1）超时法超时法2）等待图法等待图法 图：图：结点表示正运行的事务。结点表示正运行的事务。边表示事务等待的情况。边表示事务等待的情况。T1 T223ppt课件“死锁的解除死锁的解除”n死锁测试程序：死锁测试程序：选择一个处理死锁代价最小的事务，将其撤选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务消，释放此事务持有的所有的锁，使其它事务能继续运行下去。能继续运行下去。24ppt课件11.4 并发调度的可串行性并发调度的可串行性一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的二、如何保证并发操作的调度是正确的二、如何保证并发操作的调度是正确的25ppt课件n事务的调度事务的调度 事务的执行次序称为事务的执行次序称为“调度调度”n串行调度串行调度 如果多个事务依次执行，则称为事务的串行调如果多个事务依次执行，则称为事务的串行调度（度（Serial Schedule）n并发调度并发调度 如果利用分时的方法，同时处理多个事务，则如果利用分时的方法，同时处理多个事务，则称为事务的并发调度（称为事务的并发调度（Concurrent Schedule）26ppt课件一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的n计算机系统对并行事务中并行操作的调度是的随机的，计算机系统对并行事务中并行操作的调度是的随机的，而不同的调度可能会产生不同的结果。而不同的调度可能会产生不同的结果。n将所有事务串行起来的调度策略一定是正确的调度策将所有事务串行起来的调度策略一定是正确的调度策略。略。以不同的顺序串行执行事务也有可能会产生以不同的顺序串行执行事务也有可能会产生不同的结果，但由于不会将数据库置于不一致状态，不同的结果，但由于不会将数据库置于不一致状态，所以都可以认为是正确的。所以都可以认为是正确的。n 几个事务的并行执行是正确的，当且仅当几个事务的并行执行是正确的，当且仅当其结果与按其结果与按某一次序串行地执行这些事务时的结果相同某一次序串行地执行这些事务时的结果相同。这种并。这种并行调度策略称为行调度策略称为可串行化（可串行化（SerializableSerializable）的调度）的调度。n可串行性是并行事务正确性的唯一准则可串行性是并行事务正确性的唯一准则27ppt课件例：现在有两个事务，分别包含下列操作：例：现在有两个事务，分别包含下列操作：事务事务1：读：读B；A=B+1；写回；写回A；事务事务2：读：读A；B=A+1；写回；写回B；假设假设A的初值为的初值为2，B的初值为的初值为2。n对这两个事务的不同调度策略对这两个事务的不同调度策略n串行执行串行执行n串行调度策略串行调度策略1n串行调度策略串行调度策略2n交错执行交错执行n不可串行化的调度不可串行化的调度n可串行化的调度可串行化的调度28ppt课件串行调度策略，正确的调度串行调度策略，正确的调度SlockBY=B=2UnlockBXlockAA=Y+1写回写回A(=3)UnlockA SlockAX=A=3UnlockAXlockBB=X+1写回写回B(=4)UnlockB T1T2SlockBY=B=3UnlockBXlockAA=Y+1写回写回A(=4)UnlockA SlockAX=A=2UnlockAXlockBB=X+1写回写回B(=3)UnlockBT1T229ppt课件并行调度策略并行调度策略T2SlockBY=B=2UnlockBXlockAA=Y+1写回写回A(=3)UnlockA SlockAX=A=2UnlockAXlockBB=X+1写回写回B(=3)UnlockBT1SlockBY=B=2UnlockBXlockAA=Y+1写回写回A(=3)UnlockASlockA等待等待等待等待等待等待X=A=3UnlockAXlockBB=X+1写回写回B(=4)UnlockBT1T2不不可可串串行行化化的的调调度度可可串串行行化化的的调调度度30ppt课件二、如何保证并发操作的调度是正确的二、如何保证并发操作的调度是正确的n保证并发操作调度正确性的方法保证并发操作调度正确性的方法n封锁方法：封锁方法：两段锁（两段锁（Two-Phase Locking，简称简称2PL）协议）协议n时标方法时标方法n乐观方法乐观方法31ppt课件n两段封锁协议是最常用的一种封锁协议。n封锁协议 在运用封锁方法时，对数据对象加锁时需要约定一些规则，例如何时申请封锁、持锁时间、何时释放封锁等。我们称这些规格为封锁协议。32ppt课件11.5 两段锁协议两段锁协议n两段锁协议两段锁协议 是指所有事务必须分两个阶段对数据项是指所有事务必须分两个阶段对数据项加锁和解锁。加锁和解锁。n内容内容1.1.在对任何数据进行读、写操作之前，事务在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁首先要获得对该数据的封锁2.2.在释放一个封锁之后，事务不再获得任何在释放一个封锁之后，事务不再获得任何其他封锁。其他封锁。33ppt课件n“两段两段”锁的含义锁的含义事务分为两个阶段事务分为两个阶段n 第一阶段是获得封锁，也称为扩展阶段；第一阶段是获得封锁，也称为扩展阶段；n 第二阶段是释放封锁，也称为收缩阶段。第二阶段是释放封锁，也称为收缩阶段。例：例：事务事务1的封锁序列：的封锁序列：Slock A.Slock B.Xlock C.Unlock B.Unlock A.Unlock C；事务事务2的封锁序列：的封锁序列：Slock A.Unlock A.Slock B.Xlock C.Unlock C.Unlock B；事务事务1遵守两段锁协议，而事务遵守两段锁协议，而事务2不遵守两段协议。不遵守两段协议。34ppt课件结论结论n并行执行的所有事务均遵守两段锁协议，则对这并行执行的所有事务均遵守两段锁协议，则对这些事务的所有并行调度策略都是可串行化的。些事务的所有并行调度策略都是可串行化的。所有遵守两段锁协议的事务，其并行执行的结果所有遵守两段锁协议的事务，其并行执行的结果一定是正确的一定是正确的n事务遵守两段锁协议是可串行化调度的事务遵守两段锁协议是可串行化调度的充分条件充分条件，而不是必要条件而不是必要条件n可串行化的调度中，不一定所有事务都必须符合可串行化的调度中，不一定所有事务都必须符合两段锁协议。两段锁协议。35ppt课件图图 遵守两段锁协议的事务可能发生死锁遵守两段锁协议的事务可能发生死锁T1SlockB读读B=2XlockA等待等待等待等待T2SlockA读读A=2XlockA等待等待36ppt课件11.6 封锁的粒度封锁的粒度一、什么是封锁粒度一、什么是封锁粒度二、选择封锁粒度的原则二、选择封锁粒度的原则37ppt课件一、什么是封锁粒度一、什么是封锁粒度nX锁和锁和S锁都是加在某一个数据对象上的锁都是加在某一个数据对象上的n封锁的对象封锁的对象:逻辑单元，物理单元逻辑单元，物理单元 例：在关系数据库中，封锁对象：例：在关系数据库中，封锁对象：n逻辑单元逻辑单元:属性值、属性值集合、元组、关属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等系、索引项、整个索引、整个数据库等n物理单元：页（数据页或索引页）、物理记物理单元：页（数据页或索引页）、物理记录等录等38ppt课件n封锁对象可以很大也可以很小封锁对象可以很大也可以很小 例：例：对整个数据库加锁对整个数据库加锁 对某个属性值加锁对某个属性值加锁n封锁对象的大小称为封锁对象的大小称为封锁的粒度封锁的粒度(Granularity)39ppt课件二、选择封锁粒度的原则n封锁的粒度越封锁的粒度越n系统被封锁的对象系统被封锁的对象n并发度并发度n系统开销系统开销大大少少小小小小小小多多高高大大多粒度封锁多粒度封锁(multiple granularity locking)在一个系统中同时支持多种封锁粒度在一个系统中同时支持多种封锁粒度供不同的事务选择供不同的事务选择40ppt课件