不同的多事务执行方式：

并发控制：多用户数据库系统允许多个事务同时访问数据库。

特点：同一时刻可能有数百个事务并发运行。

典型场景包括飞机订票系统、银行系统。

串行调度

串行调度：一个调度如果先包含某个事务的全部操作，再包含另一个事务的全部操作，以此类推，就是串行调度。

串行调度不允许不同事务的操作混在一起。

调度 $A$ 为串行调度，顺序为 $T1 \rightarrow T2$。$T1$ 的读写 $A$、$B$ 全部完成后，$T2$ 才开始执行。

可串行化调度

正确性原则告诉我们，每个串行调度都能保持数据库一致性。

进一步的问题是：有没有非串行调度也能保证一致性？

如果调度 $S$ 对任意初始数据库状态的效果，都等价于某个串行调度 $S’$，则 $S$ 是可串行化调度。

调度 $C$ 是交叉并发，但效果等价于串行执行 $T1 \rightarrow T2$。因此调度 $C$ 是可串行化调度。

事务和调度

为了避免偶然数值影响，只关注读操作和写操作的顺序：

• $r_T(X)$：事务 $T$ 读取数据库元素 $X$。
• $w_T(X)$：事务 $T$ 写入数据库元素 $X$。
• $r_i(X)$、$w_i(X)$ 是事务 $T_i$ 的简写。

则

调度

调度 $S$：由一组事务的动作组成的序列。要求每个事务 $T_i$ 在调度 $S$ 中出现的动作顺序，必须与 $T_i$ 自身定义中的顺序相同。

例如上表中的调度可表示为：$Sc = r_1(A) w_1(A) r_2(A) w_2(A) r_1(B) w_1(B) r_2(B) w_2(B)$。

目标：找出对任意初始状态和事务语义都“好”的调度。分析时只看读写顺序。

结论：串行调度是好的。可串行化调度也是好的。

事务

事务：由 $ri(X)$、$wi(X)$ 等读写动作组成的序列。

冲突

冲突：调度中一对相邻动作，如果交换它们的顺序可能改变某个事务的行为，就称这两个动作冲突。

不会冲突的情况：

• 两个读永不冲突；
• 不同数据项上的读写或写写也不冲突。

冲突的情况：

• 同一事务内部的动作不能随意交换。
• 不同事务对同一数据元素的两个写操作冲突。
• 不同事务对同一数据元素的读写操作冲突。

核心判断：同一数据项 + 至少一个写。

冲突动作：不同事务的两个动作通常可以交换，除非同时满足：

1. 它们涉及同一个数据库元素；
2. 至少有一个动作是写。

典型冲突：$r_1(A)$ 与 $w_2(A)$，$w_1(A)$ 与 $r_2(A)$，$w_1(A)$ 与 $w_2(A)$。

冲突等价：如果调度 $S_1$ 可以通过一系列“不冲突的相邻动作交换”变成 $S_2$，那么 $S_1$ 与 $S_2$ 冲突等价。

冲突可串行化：如果调度 $S$ 与某个串行调度冲突等价，那么 $S$ 是冲突可串行化调度。

冲突可串行化调度是安全的调度。

冲突可串行化是可串行化的充分条件。也就是说：如果一个调度是冲突可串行化的，那么它一定是可串行化的。

冲突可串行化是可串行化的充分条件，但不是必要条件。有些调度虽然不是冲突可串行化，但仍可能是可串行化的。

判断冲突可串行化时，要保持冲突操作的先后顺序不变，只交换不冲突操作。

优先图

优先图 $P(S)$ 可用于判断调度 $S$ 是否冲突可串行化。

• 节点：调度中的事务。
• 边 $T_i \rightarrow T_j$：表示 $T_i$ 必须排在 $T_j$ 前面。
• 加边条件：$T_i$ 的动作 $A_1$ 在 $S$ 中先于 $T_j$ 的动作 $A_2$；二者访问同一数据库元素；且至少一个是写操作。

例如，对于调度

，它的优先图为：

如果图中没有环，就可以找到一个等价的串行顺序。

锁

调度器的职责是接收事务请求。调度器可以允许事务访问数据库，也可以阻塞事务，直到继续执行是安全的。锁表用来辅助调度器做出这个决定。锁调度器可以强制实现冲突可串行化。

冲突可串行化比一般可串行化要求更强。事务必须请求锁并释放锁。需要规定事务结构和调度结构。

加锁与解锁

• $l_i(X)$：事务 $T_i$ 请求数据库元素 $X$ 上的锁。
• $u_i(X)$：事务 $T_i$ 释放它在 $X$ 上的锁。

锁调度器需要满足两个方面：

1. 事务本身的一致性：事务只能在已经对某元素加锁且尚未释放该锁时，读写这个元素。如果事务 $T_i$ 有 $r_i(X)$ 或 $w_i(X)$，则之前必须有 $l_i(X)$，中间不能有 $u_i(X)$，之后还必须释放锁 $u_i(X)$。满足这种要求的事务称为良事务。
2. 调度的合法性：锁必须真的起作用。两个事务不能同时锁住同一个元素，除非前一个事务已经释放。如果调度中 $l_i(X)$ 后面出现 $l_j(X)$，那么二者之间必须有 $u_i(X)$。

两段锁协议（2PL）：在每个事务中，所有加锁请求必须出现在所有解锁动作之前。一旦事务开始释放锁，就不能再请求新的锁。

2PL 能保证一致事务的合法调度是冲突可串行化的。

• 第一阶段：增长阶段，事务不断获得锁。
• 第二阶段：收缩阶段，事务逐步释放锁。

两段锁不能完全消除死锁。

简单 2PL 的主要问题是，即使事务只想读 $X$，也必须对 $X$ 加锁。如果多个事务都只是读 $X$，而没有事务写 $X$，它们本来可以同时读取。

共享锁与排他锁

写操作需要的锁比读操作更强：

• 共享锁：读锁。
• 排他锁：写锁。

对于数据库元素 $X$：要么有一个排他锁；要么没有排他锁，但可以有多个共享锁。

• $sl_i(X)$：事务 $T_i$ 请求 $X$ 上的共享锁。
• $xl_i(X)$：事务 $T_i$ 请求 $X$ 上的排他锁。
• $u_i(X)$：事务 $T_i$ 释放 $X$ 上已有的锁。

规则1：事务一致性。没有排他锁不能写；没有任何锁不能读。读 $r_i(X)$ 之前必须有 $sl_i(X)$ 或 $xl_i(X)$，中间不能释放。写 $w_i(X)$ 之前必须有 $xl_i(X)$，中间不能释放。所有锁最后都必须释放。

如果事务既读又写同一个对象，可以选择:

• 方案1：一开始就请求排他锁。这样事务可以先读后写，但会降低并发度。
• 方案2：锁升级。事务先请求共享锁读取数据；如果之后需要写，再升级为排他锁。可以理解为获得第二个锁，或者释放共享锁后获得排他锁。

$ul_i(X)$：事务 $T_i$ 在 $X$ 上请求更新锁。更新锁只允许读，不允许写。但只有更新锁可以在之后升级为写锁；普通读锁不能升级。

规则2：两段锁事务。所有加锁动作必须在所有解锁动作之前。锁升级是例外情况：如果升级被视为获得更强的锁，可以发生在增长阶段。如果升级需要释放共享锁再获得排他锁，则必须谨慎处理。

规则3：调度合法性。同一个元素要么被一个事务排他锁定，要么被多个事务共享锁定，不能二者同时存在。如果已有共享锁，就不能再给其他事务排他锁。如果已有排他锁，就不能再给其他事务任何锁。

结论：合法调度 + 一致事务 + 2PL，在共享锁/排他锁系统中同样可以保证冲突可串行化。

消除死锁

解决死锁的方法有两类：

1. 预防死锁。
2. 诊断并解除死锁。

死锁的预防

• 一次封锁法：事务必须一次性加锁所有要用的数据，否则不能继续。问题：降低并发度，并且很难提前精确知道所有封锁对象。
• 顺序封锁法：预先规定数据对象的封锁顺序，所有事务都按顺序加锁。问题：维护成本高，实际实现困难。

操作系统中常用的死锁预防策略，不太适合数据库系统特点。数据库管理系统更常用的方法是：诊断并解除死锁。

死锁诊断与解除

诊断方法主要有两种：超时法、事务等待图法。

超时法：如果一个事务等待时间超过规定时限，就认为发生了死锁。

• 优点：实现简单。
• 缺点：可能误判；如果时限过长，死锁不能及时发现。

等待图法：用事务等待图动态反映所有事务的等待情况。

事务等待图是有向图 $G = (T, U)$。

• $T$：结点集合，每个结点表示一个正在运行的事务。
• $U$：边集合，每条边表示等待关系。若 $T_1$ 等待 $T_2$，则画边 $T_1 \rightarrow T_2$。

并发控制子系统会周期性生成事务等待图。如果发现图中存在回路，就表示系统中出现了死锁。

解除死锁：选择一个处理代价最小的事务，将其撤销。撤销后释放该事务持有的所有锁，使其他事务能够继续运行。