1并发控制的概念和理论 13分布式事务的可串行化调度测试 举例 考虑如下3个事务: T1: Read(x); Write(x); Commit T2: Write(x); Write(y) read(z); Commit T3: Read(x): Read(y) Read(z); Commit 这3个事务的一个调度: S={W2(x),W2(y),R2(z)C2R1(x)2W1(x)C1R3(x),R3(y),R3(z)C3} 优先图: T2—T1—T3 无环,S是串行调度
举例 • 考虑如下3个事务： T1: Read(x); Write(x); Commit; T2: Write(x); Write(y); Read(z); Commit; T3: Read(x); Read(y); Read(z); Commit; 这3个事务的一个调度： S={W2 (x),W2 (y),R2 (z),C2 ,R1 (x),W1 (x),C1 ,R3 (x),R3 (y),R3 (z),C3} 优先图： T2 T1 T3 无环， S是串行调度。 1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论
1并发控制的概念和理论 13分布式事务的可串行化调度测试 另外一个调度S S={W2(x),R1(x)2W1(x,C1,R3(x)2W2(y),R3(y),R2(z),C2R3(zC3} 先序图 T2→T1T3 无环,是可串调度
另外一个调度S’: S={W2 (x), R1 (x),W1 (x),C1 ,R3 (x), W2 (y), R3 (y), R2 (z), C2 ,R3 (z),C3} 先序图： T2 T1 T3 无环，是可串调度。 1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论
1并发控制的概念和理论 13分布式事务的可串行化调度测试 可串性理论扩展 可串性理论可以直接扩展到无重复副本的分布 式数据库中 事务在每个站点上的执行调度称作局部调度 如果数据库无重复副本的分布式数据库,并且每个 局部调度都是可串调度,只要这些局部调度的顺序 致,则它们的并(全局调度)也是可串调度 但是有副本的情况下,就比较复杂。可能局部调度 是可串行化的,而全局调度不是可串行化的
可串性理论扩展 • 可串性理论可以直接扩展到无重复副本的分布 式数据库中。 – 事务在每个站点上的执行调度称作局部调度 – 如果数据库无重复副本的分布式数据库，并且每个 局部调度都是可串调度，只要这些局部调度的顺序 一致，则它们的并（全局调度）也是可串调度 – 但是有副本的情况下，就比较复杂。可能局部调度 是可串行化的，而全局调度不是可串行化的。 1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论
1并发控制的概念和理论 14并发控制机制的常用方法及其分类 保证只产生可串行化调度的机制 并发控制机制分类 按分配模式(数据方式) 完全复制的DB 部分复制DB或分片的DB 按网络类型(通信方式) 广播能力的 星型网,环形网 同步化原则 建立在相互排斥地访问共享数据基础上的算法 通过一些准则(协议)对事务进行排序的算法 悲观并发控制法(事务是相互冲突的),乐观并发控制法 (没有太多的事务相互冲突)
• 保证只产生可串行化调度的机制 • 并发控制机制分类 – 按分配模式(数据方式) • 完全复制的DB • 部分复制DB或分片的DB – 按网络类型(通信方式) • 广播能力的 • 星型网, 环形网 – 同步化原则 • 建立在相互排斥地访问共享数据基础上的算法 • 通过一些准则(协议)对事务进行排序的算法 • 悲观并发控制法（事务是相互冲突的），乐观并发控制法 （没有太多的事务相互冲突） 1.4 并发控制机制的常用方法及其分类 1 并发控制的概念和理论
并发控制算法的分类 并发控制算法 悲观法 乐观法 加锁法 时标排序法 混合法 加锁法 时序排序法 集中式加锁 基本时标排序 主副本加锁 多版本时标排序 分布式加锁 保守时标排序
并发控制算法 悲观法 乐观法 加锁法 集中式加锁 分布式加锁 时标排序法 混合法 加锁法 时序排序法 主副本加锁 基本时标排序 保守时标排序 多版本时标排序 并发控制算法的分类