《高级软件-王永利》第六章 并发控制.pptVIP

第六章 并发控制 6．1 基于锁的协议 6．1 基于锁的协议 相容琐：A类型的锁与B类型的锁相容 。 相容矩阵：(锁相容矩阵comp )如图： lock-s（Q） lock-x（Q） unlock（Q） 调度1是由于T1过早释放了B上的锁，而导致T2面对不一致的状态，若改为T3，T4，可以避免不一致，但可能会产生死锁，如图 ： *死锁：系统中有一个事务集合，该集合中 的事物均处于等待另一个事务的状 态，在此状态下，哪个事务都不能 继续执行，这种状态称为死锁。 操作系统中的死锁是多个进程互相等待。 解决死锁：必须回滚一个事务 。 2.授予锁： 当事务申请对一个数据项加某一类型的锁，且没有 其他事物在该数据项上已经加上与此类型相冲突的锁时，可 以授予锁。但是注意下面的情况： T2在数据项Q上持有共享锁，T1申请Q上的排他锁， T1 等待T2释放锁，同时T3申请Q上的共享锁，T3获得共享锁。T2可能释放锁，T4又申请共享锁，……。这样T1总无法在Q上获得排他锁，事务T1也就永远不能取得进展。 这种现象称为饿死。 为了避免事务饿死，当Ti申请对Q加M的锁时： 1）不存在在Q上持有与M冲突的锁的其他事务。 2）不存在等待对Q加锁且优先于Ti申请加锁的事务。 3.两阶段协议: 将事务分为增长阶段和缩减阶段 。 两阶段封锁协议保证冲突可串行化。 两阶段封锁协议不保证不会发生死锁。（如前面的T3,T4是两阶段的，但却发生死锁) 封锁点（lock point)： 对于任何事务，在调度中该事务获得其最后加锁的位置（增长阶段结束点）称为事务的封锁点。对多个事务的封锁点进行排序，这个序列就是事务的一个可串行化顺序。 在前一章中我们希望调度可串行化和无级联。 两阶段封锁协议下，可能发生级联回滚。 例如：下图如果T7的read(A)指令之后，T5发生 故障，导致T6、T7级联回滚。 在两阶段封锁下的部分调度如图： 例：T8，T9 锁的转换:提升upgrade，将共享锁提升为排他锁upgrade发生 在增长阶段；降级downgrade，将排他锁降级为共享锁。发生 在缩减阶段。 如图：是事务T8与T9在修改后的两阶段封锁协议下并发执行。 4.基于图的协议: 两阶段封锁协议保证可串行化是充分必要的,若 要开发非两阶段协议，最简单模型要求已知访问数 据项的顺序。 要求访问的数据项集合D={d1,d2,…,dn} 的所有数 据项满足偏序关系 。如果di-dj，则任何既访问di又 访问dj的事务，必须先访问di再访问dj。 偏序集合D为一有向无环图，称为数据库 图。为简化问题，我们只关心那些带根树， 给出一个称为树形协议的简单协议，该协议 只使用排他锁。 树形协议中，只有lock-x指令，每个事务Ti 对一个数据项只能加一次锁。并遵守以下规 则： Ti的首次加锁可以对任何数据项。 此后，Ti对数据项Q加锁的前提是Ti持有Q的双亲项上的锁。 对数据项解锁可以随时进行。 数据项Ti加锁并解锁后，Ti不能再对该数据项加锁。 满足树形协议的调度是冲突可串行化的。 例：具有树形结构的数据库图 ： 在树形协议下的可串行化调度 ： 树形协议：即保证冲突可串行化，又保证 不会死锁 。 6．2 基于时间戳的协议 实现方法： ①系统时钟 ②逻辑计数 W-timestamp(Q):成功执行write(Q)的所有事务的最大时间戳 R-timestamp(Q):成功执行read(Q)的所有事务的最大时间戳 3．Thomas写规则 (修改时间戳协议,比时间戳协议并发程度高) 忽略过时写操作 如图： 修改协议如下： 假设事务Ti发出write(Q)操作： a. 若TS(Ti)R-timestamp(Q),则Ti产生的Q值是先前所需要的，且系统假定该值不会被产生。因此，write(Q)操作被拒绝， Ti回滚。 b.若TS(Ti)W-timestamp(Q),则Ti想写入的Q值已过时。因此，write(Q)操作可被忽略。 c. 其他情况时执行write(Q)操作，将 W-timestamp(Q)设为TS(Ti)。 称为Thomas写规则。 6．3 基于有效性检查的协议 6．4 多粒度 1．多粒度树 2．加锁规则 1)必须遵守相容矩阵 2）根结点首先加锁，且可以加任意类型的锁 3）仅当Ti当前对Q的双亲结点持有IX或IS型的锁时， Ti对结点Q才可以加