第十一章 并发控制

.,第十一章并发控制,.,主要内容,11.1并发控制概述11.2封锁11.3活锁和死锁11.4并发调度的可串行性11.5两段锁协议11.6封锁的粒度,.,11.1并发控制概述,多事务执行方式(1)事务串行执行(2)交叉并发方式(3)同时并发方式并发是指在单处理机上，利用分时方法实行多个事务同时做。事务并发执行带来的问题可能会存取和存储不正确的数据，破坏事务的隔离性和一致性,.,DBMS必须提供并发控制机制DBMS的并发控制子系统保证事务的隔离性保证事务的一致性对并发操作进行正确调度,.,并发操作带来的问题1-丢失更新,图在时间t7丢失了事务T1的更新,.,图事务T1两次读取A的值，却得到了不同的结果,并发操作带来的问题2-不可重复读问题,.,并发操作带来的问题3-读脏数据,.,并发控制就是用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性。,.,11.2封锁,封锁是实现并发控制的一个主要技术。锁（Lock）是一个与数据项相关的变量，对可能应用于该数据项上的操作而言，锁描述了该数据项的状态。两种封锁：-排他型（Exclusive）封锁（简称：X锁）-共享型（Share）封锁（简称：S锁）,.,X锁（排它锁）,排它锁又称为写锁若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。X锁的操作XlockA：表示事务对数据A加X锁，并读数据AunlockA：表示事务要解除对数据A的X锁,.,X锁,PX协议:使用X锁的规则称为PX协议。任何企图更新记录R的事务必须先执行“XlockR”操作，以获得对R的X锁，才能读或写记录R；如果未获准X锁，那么这个事务进入等待队列，一直到获准X锁，事务才能继续做下去。PXC协议X锁的解除操作应该合并到事务的结束（COMMIT或ROLLBACK）操作中。引入此规则，PX协议成为PXC协议。,.,S锁（共享锁）,S锁定义若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A。其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。操作SlockA表示事务对数据A加S锁，并读数据。UnlockA表示事务要解除对数据A的S锁。,允许并发的读，又称为读锁,.,封锁的相容矩阵,注：N=NO，不相容的请求Y=YES，相容的请求X、S、：分别表示X锁，S锁，无锁如果两个封锁是不相容的，则后提出封锁的事务要等待。,XS,XS,NNYNYYYYY,T2T1,.,例：使用X锁封锁解决数据丢失,.,11.3活锁和死锁,封锁技术可以有效地解决并行操作的一致性问题，但也带来一些新的问题。死锁活锁,.,1.“活锁”,T2XlockA,T3XlockA,T4XlockA,A,A已被封锁，不成功，等待,A刚被释放，成功,时间点,A刚被释放，成功,T2永远等待活锁！,解决方法：先来先服务,系统可能使某个事务永远处于等待状态，得不到封锁的机会，这种现象称为“活锁”。,.,2.“死锁”,出现了T1在等待T2，而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成了死锁。,.,解决死锁的方法,两类方法1）预防死锁2）死锁的诊断与解除,.,1）死锁的预防,预防死锁的发生就是要破坏产生死锁的条件。预防死锁的方法一次封锁法顺序封锁法,.,一次封锁法,要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行一次封锁法存在的问题扩大封锁范围难于事先精确确定封锁对象,.,顺序封锁法,顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。顺序封锁法存在的问题维护成本高难于实现,.,2）死锁的诊断与解除,允许死锁发生解除死锁由DBMS的并发控制子系统定期检测系统中是否存在死锁一旦检测到死锁，就要设法解除,.,“死锁的诊断”,若事务等待图有环，则表示出现死锁,1）超时法2）等待图法图：结点表示正运行的事务。边表示事务等待的情况。,.,“死锁的解除”,死锁测试程序：选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务能继续运行下去。,.,11.4并发调度的可串行性,一、什么样的并发操作调度是正确的二、如何保证并发操作的调度是正确的,.,事务的调度事务的执行次序称为“调度”串行调度如果多个事务依次执行，则称为事务的串行调度（SerialSchedule）并发调度如果利用分时的方法，同时处理多个事务，则称为事务的并发调度（ConcurrentSchedule）,.,一、什么样的并发操作调度是正确的,计算机系统对并行事务中并行操作的调度是的随机的，而不同的调度可能会产生不同的结果。将所有事务串行起来的调度策略一定是正确的调度策略。以不同的顺序串行执行事务也有可能会产生不同的结果，但由于不会将数据库置于不一致状态，所以都可以认为是正确的。几个事务的并行执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。这种并行调度策略称为可串行化（Serializable）的调度。可串行性是并行事务正确性的唯一准则,.,例：现在有两个事务，分别包含下列操作：事务1：读B；A=B+1；写回A；事务2：读A；B=A+1；写回B；假设A的初值为2，B的初值为2。对这两个事务的不同调度策略串行执行串行调度策略1串行调度策略2交错执行不可串行化的调度可串行化的调度,.,串行调度策略，正确的调度,.,并行调度策略,不可串行化的调度,可串行化的调度,.,二、如何保证并发操作的调度是正确的,保证并发操作调度正确性的方法封锁方法：两段锁（Two-PhaseLocking，简称2PL）协议时标方法乐观方法,.,两段封锁协议是最常用的一种封锁协议。封锁协议在运用封锁方法时，对数据对象加锁时需要约定一些规则，例如何时申请封锁、持锁时间、何时释放封锁等。我们称这些规格为封锁协议。,.,11.5两段锁协议,两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁。内容1.在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁2.在释放一个封锁之后，事务不再获得任何其他封锁。,.,“两段”锁的含义事务分为两个阶段第一阶段是获得封锁，也称为扩展阶段；第二阶段是释放封锁，也称为收缩阶段。例：事务1的封锁序列：SlockA.SlockB.XlockC.UnlockB.UnlockA.UnlockC；事务2的封锁序列：SlockA.UnlockA.SlockB.XlockC.UnlockC.UnlockB；事务1遵守两段锁协议，而事务2不遵守两段协议。,.,结论,并行执行的所有事务均遵守两段锁协议，则对这些事务的所有并行调度策略都是可串行化的。所有遵守两段锁协议的事务，其并行执行的结果一定是正确的事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件可串行化的调度中，不一定所有事务都必须符合两段锁协议。,.,图遵守两段锁协议的事务可能发生死锁,.,11.6封锁的粒度,一、什么是封锁粒度二、选择封锁粒度的原则,.,一、什么是封锁粒度,X锁和S锁都是加在某一个数据对象上的封锁的对象:逻辑单元，物理单元例：在关系数据库中，封锁对象：逻辑单元:属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等物理单元：页（数据页或索引页）、物理记录等,.,封锁对象可以很大也可以很小例：对整个数据库加锁对某个属性值加锁封锁对象的大小称为封锁的粒度(Granularity),.,二、选择封锁粒度的原则,封锁的粒度越系统被封锁的对象并发度系统开销,大少小小,小多高大,多粒度封锁(multiplegran