11.并发控制

并发控制

多用户数据库系统

• 多事务执行方式

  • 事务串行执行

    

  • 交叉并发方式

    • 单处理机系统
    

  • 同时并发方式

    • 多处理机系统

并发控制概述

• 数据不一致性

  • 丢失修改
  • 不可重复读
  • 读"脏"数据

• 并发控制的主要技术

  • 封锁
  • 时间戳
  • 乐观控制法
  • 多版本并发控制

封锁

• 基本封锁类型

  • 排它锁(X锁)
    • 写锁
    • 不可读不可改
  • 共享锁(S锁)
    • 读锁
    • 可读不能改

• 锁的相容矩阵

  T1\T2	X	S	_
  X	N	N	Y
  S	N	Y	Y
  _	Y	Y	Y

封锁协议

• 何时申请X锁或S锁

• 封锁时间

• 何时释放

• 一级封锁协议

  • 事务T在修改之前必须先对其加X锁, 直到事务结束才释放; 事务结束包括正常结束(COMMIT)和非正常结束(POLLBACK)
  • 作用
    • 一级封锁协议可防止丢失修改, 并保证事务T可恢复
    • 在一级封锁协议中, 如果仅仅是读数据不对其进行修改是不需要加锁的, 所以它不能保证可重复读和不读"脏数据"

• 二级封锁协议

  • 一级封锁协议加上事务T在读取数据之前必须先对其加S锁, 读完后即可释放S锁
  • 作用
    • 可以防止丢失修改和读"脏"数据
    • 不能保证可重复读

• 三级封锁协议

  • 一级封锁协议加上事务T在读取数据R之前必须先对其加S锁, 直到事务结束才释放
  • 作用
    • 可防止丢失修改, 读"脏"数据和不可重复读

活锁和死锁

活锁

• 饥饿

死锁

• 解决方法

  • 预防
    • 破坏死锁产生条件
    • 一次封锁法 : 一次将所有要使用的数据全部加锁
    • 顺序封锁法 : 预先对数据对象规定一个封锁顺序
  • 诊断
    • 超时法 : 如果事务的等待时间超过了规定的时候, 就认为发生了死锁
    • 等待图法 : 用事务等待图动态反映所有事物的等待情况, 等待图是一个有向图G=(T, U)
      • 选择一个处理死锁代价最小的事务将其撤销, 释放锁

并发调度的可串行性

可串行化调度

• 可串行化调度 : 多个事务并发执行是正确的, 当且仅当其结果与按某一次序串行地执行这些事务时的结果相同

• 可串行性 : 是并发事务正确调度的准则

冲突可串行化调度

• 冲突操作 : 不同事务对同一数据的读写操作和写写操作

• 当不同事物的不冲突操作交换后等价于串行调度, 则原操作序列是冲突可串行化调度

  

• 冲突可串行化调度 -> 可串行化调度 (逆向不一定)

两段锁协议

• 实现并发调度的可串行性, 从而保证调度的正确性

• 两段锁含义 : 事务分为两个阶段

  • 扩展阶段 : 获得封锁
    • 可以申请获得任何数据项上的任何类型的锁, 但不能释放任何锁
  • 收缩阶段 : 释放封锁
    • 可以释放任何数据项上的任何类型的锁, 但是不能再申请任何锁

• 遵守两段锁协议一定是一个可串行化调度

• 两段锁协议的可能发生死锁

封锁的粒度

• 封锁对象的大小称为封锁粒度

• 封锁对象

  • 逻辑单元
  • 物理单元

多粒度封锁

• 在一个系统中同时支持多种封锁粒度供不同的事务选择

• 考虑封锁开销和并发度

  • 处理多个关系的大量元组的用户事务 : 以数据库为封锁单元
  • 处理大量元组的用户事务 : 以关系为封锁单元
  • 只处理少量元组的用户事务 : 以元组为封锁单位

• 多粒度树

  

• 多粒度封锁协议

  • 允许对多粒度树中的每个结点被独立加锁, 对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
    • 显示封锁
    • 隐式封锁
  • 系统检查封锁冲突时要检查 显式封锁 还要检查 隐式封锁
  • 对某个对象加锁, 要检查
    • 该数据对象
    • 所有上级结点
    • 所有下级结点

意向锁

• 提高对某个数据对象加锁时系统的检查效率

• 如果对一个结点加意向锁, 则说明该结点的下层结点正在被加锁. 对任一结点加基本锁, 必须先对它的上层结点加意向锁

• 意向共享锁 (IS)

• 意向排它锁 (IX)

• 共享意向排它锁 (SIX) : S + IX

• 强锁代替弱锁是安全的

• 具有意向锁的多粒度封锁方法

  • 申请封锁时自上而下, 释放封锁时自下而上