1.为什么需要并发控制？

三种典型的不一致现象：1.丢失修改。2.不能重复读。3.脏读。

总体上讲并发控制的方法分为两种：封锁法和撤回法。（这两种衍生出来了许多协议）。

2.事务调度以及可串行性

什么是事务？：将一系列数据库操作组合在一起作为一个整体进行操作和控制，以便数据库管理系统能够提供一致性状态转换的保证。

事务的特性：ACID

（1）原子性Atomicity：DBMS能够保证事务的一组操作是原子不可分的，要么全做，要么全不做。

（2）一致性Consistency：DBMS要保证事务的操作状态是正确的，符合一致性的操作规则，不能出现典型的三种不一致现象，由隔离性来保证。

（3）隔离性Isolation：DBMS保证并发执行的多个事务之间互相不影响。例如两个事务T1和T2，并发执行相当于先执行T1在执行T2，或者先执行T2再执行T1.

（4）持久性Durability：DBMS保证已提交事务的影响是持久的，被撤销事务的影响是可恢复的。

所以具有ACID特性的数据操作（一组）就是事务。DBMS通常有事务管理器来管理事务。

事务调度的定义：一组事务的基本步（读，写，加锁，解锁等）的一种执行顺序称为对这组事务的一个调度。

并发调度：多个事务从宏观上看是并行执行的，但是其微观上的基本操作则是交叉执行的。当且仅当在这个并发调度下得到的结果和串行的执行事务得到的结果完全一致则这个并发调度是正确的。

可串行性：不管数据库的初始状态如何，一个调度对数据库状态的影响都和某个串行调度相同，则我们说这个调度室可串行化的或者说具有可串行性。

表达事务的一种模型：Rt（A）：事务T读A。 Wt（A）：事务T写A。 eg:T1:R1(A);W1(A);R1(B);W1(B).T2:R2(A);W2(A);R2(B);W2(B).

2.1冲突可串行化

冲突：调度中一对连续的动作**，他们满足：如果他们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变（不一致）。** 有冲突的两个操作是不能交换次序的，没有冲突的两个事务是可交换的。接下来介绍几种冲突的情况：

（1）同一事务的任意两个操作都是冲突的。（2）不同事务对同一个元素的两个写操作是冲突的。（3）不同事务对同一元素的一读一写操作是冲突的。

冲突可串行性：一个调度，如果通过交换相邻的两个无冲突的操作能够转换到某个串行的调度，则称此调度为冲突可串行化调度。

满足冲突可串行新一定满足可串行性，反之不然。

冲突可串行化的判别算法：构造一个优先图（前驱图），节点是每一个事务。如果Ti的一个操作和Tj的一个操作发生冲突，且Ti在Tj前执行，则绘制一条边由Ti指向Tj，表示Ti要在Tj之前执行。如果此图没有环则冲突是可串行化的。

3.基于封锁的并发控制方法

前面的内容解决了怎么样判断一个并发调度是正确的，接下来就是要解决怎样产生一个正确的并发调度（或者说产生一个冲突可串行化的调度）。基本上有两种方法：基于封锁（锁）的并发控制和基于撤回的并发控制。

基于锁的并发控制方法中，在数据库中维护了一个锁表来记录。调度器通过锁表来保证事务执行的正确性。锁可以延迟一些事物的执行，只有成功加锁之后才能执行。锁本身并不能保证冲突可串行性，锁为了调度提供了控制的手段，但是如何用锁仍然需要说明。对锁的不同运用方法就是不同的协议。

锁的类型（有的协议会针对某些特定的锁类型，但是有些协议不用）：

（1）排它锁X（exclusive locks）：只有一个事物能够读写，其他任何事物都不能读写。

（2）共享锁S（shared locks）：所有事务都可以读，但是任何事务都不能写。

（3）更新锁U（update locks）：初始读，以后可以升级为写

（4）增量锁I（incremental locks）

3.1封锁协议需要考虑的问题：

1.封锁协议的相容性矩阵：

（1）一个事务已经持有S锁：申请S锁允许，申请X锁不允许。

（2）一个事务已经持有X锁：申请S锁不允许，申请X锁不允许。

2.封锁协议的加锁/解锁时机：

（1）0级协议（0-LP）：有写要求的时候加一个排它锁，不在访问后就解锁。可以防止丢失修改，但是可能出现脏读和重复读错误。

（2）1级协议（1-LP）：有写要求的时候加一个排它锁，在事物提交之后解锁。可以防止丢失修改和脏读（由事物回滚造成的），但是允许重复读错误。

（3）2级协议（2-LP）：有写要求的时候加一个排它锁，在事物提交之后解锁，在有读要求的时候加一把共享锁，不在访问后立即解锁。可以防止丢失修改，脏读，不允许重复读错误。

（4）3级协议（3-LP）：有写要求的时候加一个排它锁，在事物提交之后解锁，在有读要求的时候加一把共享锁，在事务提交的时候解锁。防止所有的不一致性（如幻读）。

重点在于：加什么锁？什么时候解锁。所有的并发控制都不允许有丢失修改的错误。

3.封锁协议的封锁粒度：

封锁粒度是指封锁数据对象的大小。粒度单位：属性值--->元组--->元组集合--->整个关系--->整个DB索引项--->整个索引。 由前往后：并发度小，封锁开销小；由后往前：并发度大，封锁开销也大。

4.两段封锁协议

这是一种具体的基于锁的并发控制方法。

读写数据之前需要获得锁。每个事务中所有封锁请求咸鱼任何一个解锁请求。两阶段：加锁段，解锁段。加锁段中不能有解锁操作，解锁段中不能有加锁操作。

两段封锁协议是可以保证冲突可串行性的。但是可能产生死锁。

4.基于时间戳的并发控制方法

这是一种基于撤回的方法。时间戳具有唯一性，事物T启动的时候，系统将该时刻赋予T，为T的时间戳。时间戳可以表示一系列事务执行的先后次序，时间戳小的事务先执行，时间戳大的事务后执行。利用时间戳可以不用锁来进行并发控制。

借助时间戳，强制使一组并发事务的交叉执行等价于一个特定的顺序的串行执行。特定顺序：时间戳由小到大。如何强制：执行时判断冲突。如果没有冲突予以执行；如果有冲突，则撤销该事务，并且重启该事务，此时事务获得了一个更大的时间戳，表明该事务是后执行的事务。具体的冲突有：（1）读写/写读。（2）写写冲突。

一种简单的调度规则：对DB中每个数据元素x，系统保留其上的最大的时间戳。 RT（x），表示读数据元素x的最大时间戳；WT（x），表示写数据元素x的最大时间戳；TS（T）表示事务的时间戳。

（1）读写并发：若事务T读x，则将T的时间戳TS与WT（x）比较：若TS大，则允许T操作，并且更改RT(x)为max{RT(x),TS}；否则，有冲突撤回T，并重启。（先执行的先操作就是没有冲突）。对于事务些也是一样的。

（2）写写并发：若T事务写x，则将T的时间戳TS于WT(x)比较：若TS大，则允许T写，并且更改WT(x)为T的时间戳；否则有冲突，T撤回重做。

5.基于有效性确认的并发控制方法

这是另外一种基于撤回的方法。基于撤回的方法的基本思路就是：先检测冲突，有冲突就撤回。

基于有效性确认的并发控制希望能够批量的检测冲突。与时间戳不同的是，为每个活跃的事务保存其读写数据的集合，RS(T),WS(T)分别表示事务T读数据的集合，事务T写数据的集合。通过对多个事务的读写集合，判断是否有冲突，即有效性的确认，来完成事务的提交与回滚，增强事务以可串行化的方式执行。