《并发控制技术》PPT课件.ppt

第八章并发控制技术,单用户和多用户系统,数据库系统一般可以分为单用户系统和多用户系统。单用户系统在任何时刻只允许一个用户使用的数据库系统。多用户系统允许多个用户同时使用数据库的系统。,事务的并发执行,并行 Vs 串行基本比较并行事务会破坏数据库的一致性。串行事务效率低。并行的优点一个事务由不同的步骤组成，所涉及的系统资源也不同。这些步骤可以并发执行，以提高系统的吞吐量。系统中存在着周期不等的各种事务，串行会导致难于预测的时延。如果各个事务所涉及的是数据库的不同部分，采用并发会减少平均响应时间。,并发控制的必要性,对数据库的并发操作可能导致下列问题：丢失修改(Lost Update)两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。,并发控制的必要性,不可重复读(Non-Repeatable Read)指事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取的结果。具体的讲，不可重复读包括三种情况：事务T1读取某一数据后，事务T2对其作了修改，当事务T1再次读取该数据时，得到与前一次不同的值。事务T1按照一定条件从数据库中读取了某些数据记录后，事务T2删除了其中部分记录，当T1再次按照相同条件读取数据时，发现某些记录神秘的消失了。事务T1按照一定条件从数据库中读取了某些数据记录后，事务T2插入了一些记录，当T1再次按照相同条件读取数据时，发现多了一些记录。后两种不可重复读有时也称作幻影（Phantom Row）现象。,并发控制的必要性,并发控制的必要性,并发控制的必要性,并发控制的必要性,读“脏”数据(Dirty Read)是指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，这时T1已修改过的数据恢复为原值，T2读到的数据就与数据库中的不一致，则T2读到的数据就为“脏”数据。,并发控制,封锁的定义封锁就是事务T在对某个数据对象如表、记录等操作之前，先向系统发出请求，对其加锁，从而对该数据对象有了一定的控制，在事务T释放它的锁之前，其他事务不能更新此数据对象。封锁是并发控制的一个非常重要的技术。,并发控制,封锁的类型排它锁（X锁，eXclusive lock）：事务T对数据对象A加上X锁，则只允许T读取和修改A，其它事务对A的任何封锁请求都不能成功（因而不能读取和修改R），直至T释放A上的X锁。共享锁（S锁，Share lock）：事务T对数据对象A加上S锁，则事务T可以读取但不能修改A，其它事务只能对A加S锁（因而可以读取A），而不能对A的加X锁（因而不能修改A），直到T释放A上的S锁。,并发控制,相容矩阵,不相容请求,相容请求,并发控制,一级封锁协议事务T在修改数据R之前必须对其加X锁，直到事务结束才释放。事务结束包括正常结束(COMMIT)和非正常结束(ROLLBACK)。一级封锁协议可以防止丢失修改，并保证事务T是可恢复的。在一级封锁协议中，如果仅仅是读数据而不对其进行修改，是不需要对其加锁的，因此它不能保证可重复读和不读“脏”数据。,并发控制,没有丢失修改,并发控制,二级锁协议二级锁协议是：一级锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。二级锁除了防止丢失修改，还可以进一步防止读“脏”数据。但由于读完后即可释放S锁，所以不能保证可重复读。,并发控制,不读脏数据,并发控制,三级锁协议三级锁协议是：一级锁协议加上事务T在读取R之前必须对其加S锁，直到事务结束才释放。三级封锁协议除了防止丢失修改和读“脏”数据以外，还进一步防止了不可重复读。,并发控制,可重复读,并发控制,并发控制,活锁,并发控制,死锁(Deadlock)定义在数据库运行期间，如果存在一个事务集合=T0，T1，Tn，使得T0等待T1持有的数据项锁，Tn-1等待Tn持有的数据项锁，Tn等待T1持有的数据项锁，则称系统处于死锁状态，称为死锁事务集合。,并发控制,死锁的例子如果事务T1封锁了数据R1，T2封锁了数据R2，然后T1又请求封锁R2，因T2已封锁了R2，于是T1等待T2释放R2上的锁。接着，T2又申请封锁R1，因T1已经封锁了R1，T2也只能等待T1释放R1上的锁。这样就出现了T1在等待T2，而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成死锁。,并发控制,解决死锁的方法预防死锁死锁检测和恢复,并发控制,预防死锁一次封锁法一次封锁法要求每个事务必须一次将其所有要使用的数据全部加锁，否则就不能执行。一次加锁法可以有效地防止死锁的发生，但由于需要扩大加锁的范围，因此降低了系统的并发度。顺序封锁法顺序封锁法是预先对数据对象规定一个封锁顺序，所有的事务都要按照这个顺序实行封锁。顺序封锁法可以有效地防止死锁，但其实施由于数据库中数据的不断变化和事务封锁要求的动态提出而难度很大。,并发控制,死锁检测超时法如果一个事务的等待时间超过了规定的期限，就认为发生了死锁。等待图法事务等待图是一个有向回路G=(T,U)。T为结点的集合，每个结点表示正在运行的事务；U为边的集合，每条边表示事务等待的情况。若T1等待T2，则T1，T2之间画一条有向边，从T1指向T2。事务等待图动态地反映了所有事务的等待情况。并发控制子系统周期性的检测事务等待图，如果发现图中存在回路，则表示系统出现死锁。,并发控制,T2,T1,T3,并发控制,死锁恢复DBMS的并发控制子系统一旦检测到系统中存在死锁，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事务得以继续运行下去。对于所撤销的事务所作的操作必须加以恢复。,事务的调度与可串行性,串行调度在串行调度中，属于同一事务的指令紧挨在一起。对于有n个事务的事务组，可以有n！个有效调度。并行调度在并行调度中，来自不同事务的指令可以交叉执行。,事务的调度与可串行性,问题：计算机系统对并发事务中并发操作的调度是随机的，而不同的调度可能产生不同的结果，那么哪个结果是正确的呢？定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行的执行它们时的结果相同，我们称这种调度策略为可串行化调度。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。,并发控制,两段锁协议(Two-phase Locking)内容在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁。在释放一个封锁之后，事务不再获得任何其它封锁。,并发控制,所谓两阶段锁协议的含义是指所有事务必须分两个阶段对数据项加锁和解锁。第一阶段是获得封锁也称扩展阶段。在这一阶段，事务可以申请获得任何数据项上的任何类型的封锁，但不能释放任何锁。第二阶段是释放阶段，也称收缩阶段。在这阶段，事务可以释放任何数据项上的任何类型的封锁，但是不能够再申请任何锁。定理：若所有事务均遵从两段锁协议，则这些事务的所有并行调度都是可串行化的。,并发控制,并发控制,封锁粒度 封锁对象的大小称为封锁粒度封锁对象：包括逻辑单元，如:属性值、属性值集合、元组、关系、某索引项、整个索引、整个数据库；和物理单元如：物理页、块。封锁粒度大，则并发度低，封锁机构简单，开销小。封锁粒度小，则并发度高，封锁机构复杂，开销高。如果在一个系统中同时支持多种封锁粒度供不同的事务选择是比较理想的，这种封锁方法称为多粒度封锁（Multiple Granularity Locking）。选择封锁粒度时应同时考虑封锁开销和并发度两个因素，适当选择封锁粒度以达到最优效果。,并发控制,多粒度树多粒度树的根结点是整个数据库，表示最大的粒度。叶结点表示最小的粒度。,数据库,关系Rn,关系R1,元组,元组,元组,元组,并发控制,多粒度封锁协议多粒度封锁协议允许多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以两种方式封锁，即：显式封锁是应事务的要求直接加到数据对象上的封锁。隐式封锁是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁。,并发控制,意向锁一般的，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；还要检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁冲突；还要检查其所有下级结点，看上面的显式封锁是否与本事务的隐式封锁冲突。效率很低，因此引入了意向锁。意向锁的含义是如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。,并发控制,三种常用的意向锁意向共享锁（Intent Share Lock，简称IS锁）如果要对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。意向排它锁（Intent Exclusive Lock，简称IX锁）如果要对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。意向共享排它锁（Share Intent Exclusive Lock，简称SIX锁）如果要对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S+IX。,并发控制,