标签：
无标签
实时数据库中并发控制理论
提纲
1. 与并发控制有关的概念
2. 并发控制的理论
3. 并发控制的实现
4. 锁的类别
5. 并发控制的原则
6. 实时数据库中并发控制的实现
7. 参考书目
1.与并发控制有关的概念
1.1. 事务的ACID特性
1.2. 事务分类
1.3. 平坦事务分类
1.4. 隔离性定义1
1.5. 隔离性的依赖模型
1.6. 三种有害的依赖关系
1.7. 隔离性原理
1.8. 隔离性定义2
1.9. 隔离性的级别
1.1. 事务的ACID特性
1.1.1. 一致性
1.1.2. 原子性
1.1.3. 执久性
1.1.4. 隔离性
1.1.1. 一致性
系统必须满足所有完整性约束
内部状态一致性
系统必须满足应用程序的完整性约束
系统异常时，能恢复到一致性的状态
1.1.2. 原子性
系统必须确保事务一直运行到完成，如果没有运行完成，将不产生任影响，就像没有运行一样。
原子性的执行表明事务要么成功提交，要么异常中址
1.1.3. 执久性
系统必须确保，一旦事务成功提交，不管后来计算机和存贮介质是否发生故障，其执行结果必须反映在系统中
1.1.4. 隔离性
尽管事务是并发执行的，但并发调度执行的结果就像事务按照某种顺序串行执行时所产生的结果一样
1.2. 事务分类
平坦事务
链式事务
嵌套事务
分布式事务
1.3. 平坦事务分类
只读事务
只写事务
更新事务
1.4. 隔离性定义1
事务处理系统可以并发地运行事务，但它的结果如同顺序执行一样，就应用程序而言，事务好像是在没有并行的情况下运行，事务的确切执行顺序是由系统控制的，系统行为等价于事务的某种串行执行，其造成的表面现象是一个事务执行完毕后，下一个事务才开始运行
1.5. 隔离性的依赖模型
事务的某次操作A的执行必须在另一个事务的某次操作B的操作结果，则称A依赖B
读-读 没有依赖关系
读-写 有依赖关系
写-写 有依赖关系
写-读 有依赖关系
1.6. 三种有害的依赖关系
丢失更新：事务T1的写被事务T2所忽略
T2读; T1写；T2写；
读脏数据：T1在读的是T2写的的中间数据
T2写；T1读；T2写；
不可重复读：事务T1读某对象两次，两次的结果不一致
T1读；T2写；T1读；
1.7. 隔离性原理
三种有害的依赖关系覆盖了事务处理的所有情况，如果可以防止它们发生，那么将不会有并发异常，事务将表现为隔离运行的状态
1.8. 隔离性定义2
如果满足下列条件，事务T与其它事务是隔离的：
0. T不会重写其它务的脏数据。
1. T所写的数据，在提交前，不会被其它事务读或写；
2. T不读其它务的脏数据；
3. T在提交之前，其它事务不会写T所要读的数据；
其中：
条件0和1排除了丢失更新；
条件2防止了读脏数据；
条件3防止了不可重复读；
1.9.隔离性的级别
0级： 0级事务不会重写高一级事务的脏数据
1级： 1级事务不会有丢失更新
2级： 2级事务既不会有丢失更新，也不会读脏数据；
3级： 3级事务不会有丢失更新，不会读脏数据，可重复读
SQL标准定义了这四种级别，每个关系数据库都实现了这四种级别
2.并发控制理论
2.1. 并发控制的原则
2.2. 并发控制的性能指标
2.3. 并行调度的等价性
2.4. 调度的可串行性
2.5. 调度可串行化的判断
2.6. 隔离性定理
2.1. 并发控制的原则
事务的并发执行不应导致程序的失效；
相比于串行执行，并发执行不应该有更低的平均吞吐量和更长的平均响应时间
2.2. 并发控制的性能指标
平均吞吐量
加权平均吞吐量
平均响应时间
加权平均响应时间
错失率
2.3. 并行调度的等价性
冲突等价
两个调度具有相同的事务集，相应的事务具有相同的操作；
两个调度中，任何两个相冲突的提交事务的操作的先后顺序一致；
视图等价
两个调度读出的数据是一样的；
两个调度留给系统的操作结果是一样的；
冲突等价实现容易，视图等价实现困难，现在的并发控制理论大多依据冲突等价
2.4. 调度的可串行化
如果一个调度等价于一个串行调度，则称该事务为可串行化的，该调度为可串行化调度；
可串行化调度分为冲突可串行化和视图可串行化
冲突可串行化实现容易，视图可串行化实现困难，现在的并发控制理论大多依据冲突可串行化
2.5. 可串行化调度的判断
如果某调度中，任意事务的的输出集与其余事务的输入集及输出集无交集，则该调度是可串行化的
构建事务调度的串行图，如果没有检测到环，则该调度是可串行化的；
可串行化判断有静态和动态两种
2.6. 隔离性定理
如果事务的读、写、解锁都有相应的锁覆盖，且所有的锁都会在事务结束前释放，则该事务是规范的；
如果某事务中所有的加锁操作都在解锁操作之前，则该事务是两阶事务；
如果同一时间内没发生两个不同事务的锁冲突，则该调度是合法的；
如果一个调度中，所有的事务都是规范的且是两阶段的，则任何合法的调度是隔离的
3.并发控制的实现
3.1. 基于锁的并发控制
3.2. 二段封锁协议的分类
3.3. 二段封锁协议的优缺点
3.4. 改进型二段封锁协议
3.5. 乐观并发控制
3.6. 乐观并发控制的优缺点
3.7. 改进型乐观并发控制
3.8. 其它并发控制算法
3.1. 基于锁的并发控制
锁类型：共享锁、排它锁
锁相容：读读相容，其它不相容
一个事务中，所有的加锁动作都在所有的解锁动作之前，称该事处是二段事务，相应的加锁封锁协议称为二段封锁协议（2PL）,2PL是调度可串行化的充分条件；
悲观协议
3.2. 二段封锁协议的分类
一般2PL
保守2PL
• 事务在访问对象之前，加锁全部完毕
• 避免死锁，降低并发性
严格2PL
• 所有排它锁必须在事务结束时才释放
• 避免读脏数据
强2PL
• 所有锁必须在事务结束时才释放
• 避免不可重复读
3.3. 二段封锁协议的优缺点
二段封锁协议是悲观协议，存在事务阻塞，降低了事处的并发度
如果对数据访问的竞争大，则二段封锁协议具有较高的性能，否则，会存在不必要的加锁和解锁操作
主要用在资源紧张的情况下
3.4. 改进型二段封锁协议
高优先级优先2PL
优先级继承2PL
条件优先级继承2PL
……
3.5. 乐观并发控制
乐观并发控制事先不进行冲突检查；
乐观并发控制将事务分为读、校验、提交三个阶段；
读操作从对象中取得副本并进行处理；校验阶段判断是否冲突；如果没有冲突，则提交更新，否则重启该事务；
同一时刻只一个事处处在验证阶段和写阶段
3.6. 乐观并发控制的优缺点
乐观并发处理中没有锁；
每个事务都有自己的私有缓存，空间浪费大；
如果冲突产生，事务重启的成本太高；
如果对象竞争小，乐观并发控制效率高，如果对象竞争频繁，则效率低，特别是有“热点”时
3.7. 改进型乐观并发控制
前验证乐观并发控制；
高优先级乐观并发控制；
半重启乐观并发控制；
……
3.8. 其它并行控制算法
字段调用*
契约封锁*
多版本并发控制
推测并发控制
基于动态调整串行化顺序的并发控制
4.锁的类别
采用不同类型的锁可以实现更精确的并发控制
4.1. 共享锁和排它锁
4.2.谓词锁
4.3. 粒度锁
4.4. 意向锁
4.5. 码区间封锁
4.6. 启发式封锁
4.1. 共享锁和排它锁
这是最常规的锁
4.2. 谓词锁
幻像
记录锁不能防止其它事务执行insert功能
Select * from emp where eye=“blue”
谓词锁
eye=“blue”
谓词锁能解决幻像的产生；
谓词锁能的执行成本太高；
4.3. 粒度锁
锁可以分为不同的级别：表锁、页锁、记录锁、字段锁、索引锁
根据需要对不同级的对象加锁
4.4. 意向锁
粒度锁的优化版本
锁可以分为不同的级别，这些分级就形成了一棵树
对树加锁，引入意向锁，在对某结点加锁前，必须先得到它的父结点的意向锁
意向锁是谓词锁的特例，效率比谓词锁高；
4.5. 码区间锁
意向锁的特殊版本
树标识可以通过区间码来标识，则可以只针对码区间加锁
4.6. 加锁的启发式算法
针对粒度锁、意向锁和码区间锁，可以在运行时动态升级和降级
5.并发控制实现时的原则
不同目标选择不同的并发控制方法；
不同执行环境选择不同的并发控制方法；
在明确具体应用需求的情况下，可以适当违反并行控制理论，以获得更高的性能；
选择了并发控制算法后，数据结构也应相应调整，以提高并发性能；
并发控制是有成本的，能不并行则不并行，能不锁就别锁，能短锁就别长锁，能简单则不复杂；
系统分类:
工控软件 | 用户分类:
无分类 | 来源:
无分类