Ch14 事务
1. 并发控制
两种调度方式
| 串行 | 并行 |
|---|---|
串行(serial):同一事务的指令集中在一起执行 |
并发:可以间断的切换处理事务 |
2. 可串行化(serializable)
定义:将并发执行的调度等价为一种串行的调度(一组事务的调度包含该事务所有指令,不能中间插入)
2.1 冲突可串行化
对于read和write指令,调度S种分别属于事务i,j的指令,有以下组合
| i=read, j=read | i, j次序无关紧要 |
|---|---|
| i=read, j=write | write的先后决定了read的数据是否产生变化 |
| i=write, j=read | 同上 |
| i=write, j=write | 对于S的下一条read有影响,它只能read后write的值 |
因此,不同事务上对相同数据项的操作,其中至少有一个write指令时,i,j是冲突的
2.2 冲突等价
i,j是调度S的两条连续指令,从属于不同事务且不冲突,则可以交换i,j得到新的调度S’,S等价于S’,因为i,j的顺序改变不会影响事务处理,常见的交换:
| T1的read(A)<—>T2的read(B) |
|---|
| T1的read(A)<—>T2的write(B) |
| T1的write(A)<—>T2的read(B) |
| T1的read(A)<—>T2的read(A) |
2.3 可串行化判断
使用”优先图”,G(V,E),V作为点集,每个顶点就是一个事务Ti,边集由满足下列条件的边Ti->Tj组成:(恰好对应三种矛盾)
| Tj执行read(Q)前,Ti执行write(Q) |
|---|
| Tj执行write(Q)前,Ti执行read(Q)(Ti还未执行write(Q)) |
| Tj执行write(Q)前,Ti执行write(Q) |
举例
| 调度 | 优先图 |
|---|---|
 |
 |
| T1所有的命令都先于T2执行,因此优先图就是两点一线 |
|
| 
| 
|
| | T2的write(A)前执行了T1的read(A),产生T1->T2,T1的write(B)执行前,T2执行了read(B)因此有T2->T1,最终形成环
⭐结论:只有优先图中无环的调度才能冲突串行化 |
2.4 串行化顺序确定
使用拓扑排序生成串行化顺序(不唯一)
👇下图可能的串行化顺序:Ti->Tj->Tk->Tm或Ti->Tk->Tj->Tm
**
2.5 冲突等价与可串行化区别
- 可串行化是一组事务的调度包含该事务所有指令,不能中间插入,一般表示为
- 冲突等价是针对不同事务指令的交换,一般使用图示
Ch15 并行控制
1. 基于锁的协议
1.1 两种锁
| 共享锁lock-s | Ti获得Q上的共享锁—>Ti只能读Q,不能写 |
|---|---|
| 排他锁lock-x | Ti获得Q上的排他锁—>Ti可以读,写Q |
1.2 相容函数
如果T2请求Q上的锁B,但事先已有T1获得了Q上的锁A,如果此时T2能够立即获得锁,则称A,B锁是相容的,否则只能等T1解锁后T2才能获得,在此之前T2只能等待
-
1.3 两阶段锁协议
保证可串行性的一个协议是”两阶段封锁协议”,分为两个阶段提出加速和解锁申请:
(两个阶段都是针对一个事务来说) 增长阶段(growing phase):事务可获得锁,不能释放锁
- 缩减阶段(shrinking phase):事务可释放锁,但不能获得锁
两阶段封锁可以保证可串行性,但无法保证避免死锁
- 封锁点:对于任何事务,在调度中该事务获得其最后加锁的位置(增长阶段结束点)
1.4 三类二阶段锁协议
| 分类 | 特点 |
|---|---|
| 一般 | - 两阶段封锁 - 解锁不必非要再事务结束后,只需恪守两阶段定义,比如可以把unlock(B)放在lock-x(A)后,此时lock-x(A)恰好陈伟封锁点 |
| 严格(strict) | - 两阶段封锁 - 所有lock-x只能在事务提交后才能释放 |
| 严酷(rigorous) | - 两阶段封锁 - 任何锁在事务提交后才能释放 |
1.5 锁转换
| 定义 | 锁转换(lock conversion),提供一种lock-s和lock-x转化的方式,从而减少等待或饥饿,提高并发度 |
|---|---|
| 分类 | - 升级: lock-x lock-s,只能发生在增长阶段 - 降级: lock-s lock-x,只能发生在缩减阶段 |
| 两阶段操作 | - 增长:接收lock-s\接收lock-x\升级 - 缩减:释放lock-s\释放lock-x\降级 |
| 机制总结 | - 当T执行read(Q),系统产生lock-s(Q),read(Q)紧接 - 当T执行write(Q),系统检查T是否已经持有lock-s(Q),若有:执行升级,write(Q)紧接,否则直接lock-x(Q),write(Q)紧接 - 事务提交或中止,所有锁释放 |
举例
| 
| 对左侧调度采用普通两阶段协议:
T8在read(a1)前请求lock-x(a1),对其余ai请求lock-s(ai),但是实际上只用在write(a1)前请求lock-x(a1),使其余事务可以读取a1,提高并发度.
使用锁转换:
T8中先对所有ai请求lock-s,在write(a1)前,将lock-s(a1)lock-x(a1) | 忽略读写的调度:
|
| :—-: | —- | —- |
若有收获，就点个赞吧
0 人点赞
