数据库：并发控制
1，并发控制概述
1.1，并发控制
并发带来的问题：
- 会产生多个事务同时存取同一数据的情况
- 可能会存取和存储不正确的数据，破坏事务隔离性和数据库的一致性
并发控制机制的任务：
- 对并发操作进行正确调度
- 保证事务的隔离性
- 保证数据库的一致性
★事务是并发控制的基本单位
| 方式 | 事务串行执行 | 交叉并发方式 | 同时并发方式 |
| 概念 | 每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行 |
单机系统中，事务的并行操作轮流交叉运行 |
多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行 |
| 优点 | 可以保证数据的正确性 | 能够减少处理机的空闲时间，提高系统的效率 | 最理想的并发方式 |
| 缺点 | 不能充分利用系统资源，发挥数据库共享资源的特点 | 不是真正的并发操作，可能会产生数据不一致 | 受制于硬件环境，同样可能会产生数据不一致 |
1.2，并发带来的数据不一致性
https://shao12138.blog.csdn.net/article/details/101061329#t2
2，*和*协议
2.1，*
*：事务在修改某个对象前，先锁住该对象，不允许其它事务读取或修改该对象，修改完毕或事务完成后再将锁打开。
基本*类型：排它锁、共享锁。
排他锁（X锁）：又称为写锁，若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁；
共享锁（S锁）：又称为读锁，若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。
2.2，*协议
*协议在运用X锁和S锁对数据对象加锁时，对何时申请X锁或S锁、持锁时间、何时释放等的一些约定。
一级*协议：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。 作用 一级*协议可防止丢失修改，并保证事务T是可恢复的 说明 在一级*协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。 二级*协议：一级*协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。 作用 二级*协议可以防止丢失修改和读“脏”数据 说明 在二级*协议中，由于读完数据后即可释放S锁，所以它不能保证可重复读 三级*协议：一级*协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。 作用 三级*协议可防止丢失修改、读脏数据和不可重复读 三级协议的主要区别：什么操作需要申请*以及何时释放锁（即持锁时间）
3，活锁和死锁
3.1，活锁
活锁：数据对象不断处于上锁、开锁的交替状态，某个事务有可能需要为该对象上锁，但始终没有得到上锁机会而永久等待下去的情形。
避免活锁：采用先来先服务的策略；当多个事务请求*同一数据对象时，按请求*的先后次序对这些事务排队，该数据对象上的锁一旦释放，首先批准申请队列中第一个事务获得锁。
3.2，活锁
死锁：多个事务因*冲突（竞争资源）而永远等待下去的情形。
解决死锁方法： 预防死锁（一次性*法和顺序*法）、诊断死锁并解除（超时法和等待图法）。
一次性*法：每个事务必须将所要求的数据对象全部上锁后才能执行读写操作，否则释放占用的资源。
存在的问题
- 使数据的上锁时间增长，降低了系统的并发度。
- 很难确定事务执行期间需*的数据对象。有些一开始不需要*的对象，随着数据库数据的变化，可能变成*对象，为避免此种情况发生，只能扩大*范围。
解决方法：将事务在执行过程中可能要*的数据对象全部加锁，这就进一步降低了并发度。
顺序*法：对所有数据对象规定一个*顺序，所有事务均按这个顺序实行*。
存在的问题
- 维护成本很高，数据库系统中*的数据对象极多，并且随数据的插入、删除等操作而不断地变化，要维护这样的资源的*顺序非常困难
- 难以实现，事务的*请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要*哪些对象，因此也就很难按规定的顺序去施加*
上述两种方法虽然都可以有效地预防死锁，但都存在一些问题，因此真正实施起来并不方便。所以预防死锁的策略不很适合数据库的特点，DBMS普遍采用诊断死锁并解除的方法。
等待图法：用一个有向图G=(T，U)表示事务等待的情况，T为结点的集合，每个结点表示正运行的事务，U为边的集合，每条边表示事务等待的情况；若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2。并发控制子系统周期性地（比如每隔数秒）生成事务等待图，检测事务。如果发现图中存在回路，则表示系统中出现了死锁。
解除死锁
- 选择一个处理死锁代价最小的事务，将其撤消
- 释放此事务持有的所有的锁，使其它事务能继续运行下去
4，并发调度的可串行性
4.1，可串行化调度
多事务并发执行，对并发操作的调度是随机的，数据库管理系统对并发事务不同的调度可能会产生不同的结果，如何保证正确性？
可串行化调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。
可串行性是并发事务正确调度的准则，一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度。对若干个事务，不同的并发调度策略其最终的执行结果不一定完全相同。但只要它们的调度是可串行化的，则都是正确调度。
4.2，冲突可串行化调度
冲突操作：是指不同的事务对同一数据的读写操作和写写操作。
Ri(x)与Wj(x) /*事务Ti读x，Tj写x，其中i≠j*/
Wi(x)与Wj(x) /*事务Ti写x，Tj写x，其中i≠j*/
★不能交换的动作包括同一事务的两个操作和不同事务的冲突操作。
一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’，如果Sc’是串行的，称调度Sc是冲突可串行化的调度。
冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度。
5，两端锁协议
数据库管理系统普遍采用两段锁协议的方法实现并发调度的可串行性，从而保证调度的正确性
两段*协议（也称两相上锁协议，简写2PL）指所有事务必须分两个阶段对数据项加锁和解锁。
（1）在对任何数据进行读、写操作之前，事务首先要申请并获得对该数据的*（读时S锁，写时X锁）；
（2）在释放一个*之后，事务不再申请和获得新的*。
“两段”锁的含义是事务分为两个阶段
- 第一阶段是获得*，也称为扩展阶段事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
- 第二阶段是释放*，也称为收缩阶段事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁
若所有事务都遵守两段*协议，则对这些事务的任何并发调度策略都是可串行化的。
2PL是并发控制正确性的充分条件，但不是必要条件。
两段锁协议与防止死锁的一次*法
- 一次*法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次*法遵守两段锁协议。
- 但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁。
6，*的粒度
6.1，*粒度
*的粒度：*对象的大小。可以是数据库、表、记录、字段等。
*粒度与系统的并发度和并发控制的开销密切相关。*的粒度越大，数据库所能够*的数据单元就越少，并发度就越小，系统开销也越小；*的粒度越小，并发度较高，但系统开销也就越大。
6.2，多*粒度
多粒度*：同时支持多种*粒度供不同事务选择的*方法。
多粒度*方法依赖的数据结构----多粒度树：将数据库中的数据对象按相互关系和粒度大小组织成的树型结构，其中根结点表示最大数据粒度，通常为整个数据库，叶结点表示最小数据粒度。
多粒度*协议：允许对多粒度树中的每个结点独立地加锁，并且对每一个结点加锁隐含着对其后裔结点也加以同样的锁。
在多粒度*中一个数据对象可能以两种方式*：显式*和隐式*
- 由事务直接加到数据对象上的*称为显式*
- 因上级结点加锁而引起下级对象被*，称为隐式*
- 显式*和隐式*的效果是一样的
★系统检查*冲突时要检查显式*还要检查隐式*
多粒度*方法:
为对某数据对象加锁，系统要检查：
（1）该对象有无显式*与之冲突；
（2）该对象的上级结点有无显式*与之冲突；
（3）该对象的下级结点有无显式*与之冲突；
当无任何冲突时方能加锁成功。
6.3，意向锁
用来指示下级结点正在被加锁的锁。对任一结点加锁时，必须先对其上级结点加意向锁。
引进意向锁目的：提高对某个数据对象加锁时系统的检查效率
意向锁的作用：减少加锁时的*冲突检查工作量。只需检查上级结点与本结点是否已加了不相容的锁，并通过本结点的意向锁了解下级结点是否有不相容的锁，从而不必再检查下级结点。
三种意向锁：意向共享锁（IS锁）、意向排它锁（IX锁）、共享意向排它锁(SIX锁)
意向共享锁（IS锁）：如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。
【例】:事务T1要对R1中某个元组加S锁，则要首先对关系R1和数据库加IS锁
IX锁：如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。
【例】:事务T1要对R1中某个元组加X锁，则要首先对关系R1和数据库加IX锁
SIX锁：如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX = S + IX。
【例】:对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）
意向锁的相容性
锁的强度：指它对其他锁的排斥程度，一个事务在申请*时以强锁代替弱锁是安全的，反之则不然。
意向锁的*和释放顺序：（1）申请*时应该按自上而下的次序进行；（2）释放*时则应该按自下而上的次序进行；
【例】:事务T1要对关系R1加S锁
- 要首先对数据库加IS锁
- 检查数据库和R1是否已加了不相容的锁(X或IX)
- 不再需要搜索和检查R1中的元组是否加了不相容的锁(X锁)