lec11-并发控制

并发控制

参考了bj老师PPT，以及下面两位学长的博客，在此表示感谢
eaglebear2002, spricoder

事务的ACID特性

• 事务并发执行带来的问题
  • 会产生多个事务同时存取同一数据的情况
  • 可能会存取和存储不正确的数据，破坏事务隔离性和数据库的一致性
• 数据库管理系统必须提供 并发控制机制，并发控制机制是衡量一个数据库管理系统性能的重要标志

多事务执行方式

1. 事务串行执行

   • 每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后运行
   • 不能充分利用系统资源
   • 

2. 交叉并发方式

   • 单处理机系统中，事务的并行执行是这些并行事务的操作轮流交叉运行
   • 并行事务并没有真正的并行运行, 但是可以减少处理机的空闲时间, 提高系统的效率(类比操作系统)
   • 

3. 同时并发方式

   • 多处理机系统中, 每个处理机可以运行一个事务, 多个处理机可以同时运行多个事务, 实现多个事务真正的并行运行
   • 需要更复杂的并发方式控制

并发控制

• 事务是并发控制的基本单位

• 并发控制机制的任务:

  • 对并发操作进行正确调度
  • 保证事务的隔离性
  • 保证数据库的一致性

不一致性:

• 这个例子, T1 事务的修改相当于丢失, T2 的事务修改覆盖了 T1

并发操作带来3种不一致性

记号:

• R(x) 读数据 x
• W(x) 写数据 x

丢失修改

• 两个事务 T1 和 T2 读入同一个数据并且修改, 后面的就会导致前面的修改丢失

不可重复读

• T1 读取数据后, T2 执行更新操作, 使得 T1 无法再现前一次读取结果
• 一般包括三种情况:(读后改, 读后插, 读后删, 后两种称为幻影现象)
  1. T1 读取之后, T2 做了修改, 导致得不到与前一次一样的值
  2. T1 读取之后, T2 删除了部分记录
  3. T1 读取之后, T2 插入了部分记录

读“脏”数据

• 读脏数据是指:
  • 事务 T1 修改某一数据, 并将其写回磁盘
  • 事务 T2 读取同一数据后, T1 由于某种原因被撤销(比如发生了ROLLBACK)
  • 此时 T1 被已经修改过的数据恢复原值, T2 读到的数据就与数据库中的数据不一致
  • T2 读到的数据就是“脏”数据
• 

并发控制的主要技术:

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

封锁

• 封锁, 就是事务 T 在对某个数据对象(可大可小, 元组, 记录, 到数据库) 操作之前, 先向系统发出请求, 对他加锁
• 加锁之后, 事务 T 对这个数据对象有了一定的控制, 也就是说后面的事务会受到影响和限制

S锁 与 X锁

• 排他锁(exclusive lock, 写锁):

  • 加上 X 锁之后, T 可以读取以及修改, 别的事务不允许加 X 或者 S 锁

• 共享锁(shared lock, 读锁):

  • 加上 S 锁之后, T 可以读取, 别的事务也可以再加 S 锁

三级封锁协议(对应前面的3种不一致性)

• 在运用 X 锁 和 S 锁对数据对象加锁的时候, 需要约定一些规则:
  • 什么时候申请 X 或 S
  • 什么时候释放

一级封锁协议

• 事务 T 在修改数据 R 之前必须先加上 X 锁, 直到事务结束才释放: (正常结束 / 非正常结束)

• 可以避免 丢失修改

二级封锁协议

• 一级封锁协议 + 事务T在读取数据 R 之前必须加上 S 锁, 读完就可以释放
• 可以避免 丢失修改 + 读脏数据

三级封锁协议

• 一级封锁协议 + 事务T在读取数据 R 之前必须加上 S 锁, 事务结束可以释放
• 可以避免 丢失修改 + 读脏数据 + 不可重复读

活锁 与 死锁

活锁

死锁

产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。

死锁的预防:

• 一次封锁法:9
  每个事务必须一次性将所有数据加锁
• 顺序封锁法
  预先对数据对象规定一个封锁顺序, 所有事务按照这个顺序进行封锁

死锁诊断与消除:

• 超时法:
  等待事件超限, 就认为发生了死锁
• 等待图法:
  并发控制子系统每隔一段时间就, 生成 事务等待图, 出现环就说明出现死锁
  • 解除的方法: 选择一个代价最小的事务, 进行撤销, 释放所有的锁

事务调度

并发调度的可串行性 = 正确性

• 可串行化调度 = 正确的调度

冲突可串行化:

冲突可串行化 是 可串行化调度的充分条件, 也就是说, 即使不满足冲突可串行化, 也有可能满足可串行性调度;

冲突操作:

读写 或者 写写,

• 题目, 给出冲突可串行化调度
  • 只需要保证 1每个事务内部顺序不变, 2冲突操作相对位置顺序不变

两段锁协议

• 只加锁(扩展) + 只释放(收缩)

• 提示我们, 要 X 锁就一步到位就好

封锁粒度

封锁粒度(封锁对象大小)

显式封锁 与 隐式封锁

关于意向锁

• X , S

• IS: 子节点想要加 S 锁
  事务 T1 要对 R1 中某个元组加 S 锁，则要首先对关系 R1 和数据库加IS锁

• IX: 子节点想要加 X 锁
  事务 T1 要对 R1 中某个元组加 X 锁，则要首先对关系 R1 和数据库加IX锁

• SIX(S+IX):
  对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁)，同时会更新个别元组（所以要对该表加IX锁）。

  这里是同一个事务的要求, 所以可以 SIX ?

相容矩阵: