1、12/26/2022数据库系统1本章要求：本章要求：1、了解并发操作可能产生的数据不一致性、了解并发操作可能产生的数据不一致性2、掌握并发控制的技术：封锁机制、三级封锁协议、掌握并发控制的技术：封锁机制、三级封锁协议、活锁的避免、死锁的预防、诊断及解除活锁的避免、死锁的预防、诊断及解除3、掌握并发调度的正确性标准和技术（可串行性、掌握并发调度的正确性标准和技术（可串行性、两段锁协议）两段锁协议）12/26/2022数据库系统21 并发控制概述并发控制概述 在多用户数据库系统中，当多个用户并发存取数据在多用户数据库系统中，当多个用户并发存取数据库时就会产生多个事务同时存取同一数据的情形。若不库时
2、就会产生多个事务同时存取同一数据的情形。若不加控制，可能会存取和存储不正确的数据，造成数据库加控制，可能会存取和存储不正确的数据，造成数据库的不一致性。的不一致性。在并发操作情况下，对事务的操作序列的调度是随在并发操作情况下，对事务的操作序列的调度是随机的，考虑飞机订票系统，若按下面的序列调度：机的，考虑飞机订票系统，若按下面的序列调度：考虑飞机订票系统中的一个活动序列：考虑飞机订票系统中的一个活动序列：甲售票点读出某航班的机票余额甲售票点读出某航班的机票余额A，设，设 A=16，乙售票点读出同一航班的机票余额乙售票点读出同一航班的机票余额A，也为，也为16，12/26/2022数据库系统3
3、甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额 AA1，A变为变为15，把，把A 写回数据库写回数据库 乙售票点也卖出一张机票，修改余额乙售票点也卖出一张机票，修改余额 AA1，A也为也为15，把，把A写回数据库。写回数据库。卖出两张机票，而余额只减少卖出两张机票，而余额只减少1。错误！。错误！这种情况就造成数据库的不一致性，这种不一致这种情况就造成数据库的不一致性，这种不一致性是由并发操作引起的。性是由并发操作引起的。并发操作带来的数据不一致性包括三类：并发操作带来的数据不一致性包括三类：12/26/2022数据库系统4一、并发操作可能造成的不一致性一、并发操作可能造成的不一致
4、性 1、丢失修改、丢失修改：两事务读出同一数据并修改，先写回的数据修改丢失两事务读出同一数据并修改，先写回的数据修改丢失时间时间 事务事务T1 事务事务 T2A16 读出读出A=读出读出A=AA1 写回写回A=AA1 写回写回A=15AT1的修改丢失的修改丢失1615151615A 我的数据呢？我的数据呢？12/26/2022数据库系统52、不可重复读、不可重复读 事务事务T1读取某一数据，事务读取某一数据，事务T2读取并修改了同一数据；读取并修改了同一数据；事务事务T1为了对读取值进行校对再读此数据，得到了不同的结果。为了对读取值进行校对再读此数据，得到了不同的结果。时间时间 事务事务T1
5、事务事务 T2 读出读出A=50，B=100 求和求和=150 读出读出B=100 计算计算 B B 2，写回，写回B 读出读出A=50，B=求和求和=200250T1读出读出B的值与原来的不符，验算结果不对的值与原来的不符，验算结果不对12/26/2022数据库系统6有三种情况可造成不可重复读有三种情况可造成不可重复读（1）事务事务T1读取某一数据后，事务读取某一数据后，事务T2对其做了修改对其做了修改，事务事务T1再次读取该数据时，发现与前次不同；再次读取该数据时，发现与前次不同；（2）事务事务T1按一定条件读取了某些数据记录后，事务按一定条件读取了某些数据记录后，事务T2删除删除了其中的
6、部分记录，事务了其中的部分记录，事务T1再次按相同条件读再次按相同条件读取记录时，发现有些记录不存在；取记录时，发现有些记录不存在；（3）事务事务T1按一定条件读取了某些数据记录后，事务按一定条件读取了某些数据记录后，事务T2插入了一些记录插入了一些记录，事务，事务T1再次按相同条件读取记录再次按相同条件读取记录时，发现多了一些记录。时，发现多了一些记录。12/26/2022数据库系统73、读出、读出“脏脏”数据数据 事务事务T1修改某一数据，事务修改某一数据，事务T2读取同一数据；读取同一数据；事务事务T1由于某种原因被撤消，则由于某种原因被撤消，则T2读到的就是读到的就是“脏脏”数据。数据
7、。时间时间 事务事务T1 事务事务 T2 读出读出C=100 计算计算 CC 2，写回，写回C ROLLBACK C恢复为恢复为100“脏脏”数据数据 读出读出 C=200T2读出的数据无效读出的数据无效C=20012/26/2022数据库系统8 产生上述三类不一致性的主要原因就是产生上述三类不一致性的主要原因就是并发操作破并发操作破坏了事务的隔离性。坏了事务的隔离性。并发控制并发控制就是要用正确的方式调度就是要用正确的方式调度并发操作，使某个事务的执行不受其它事务的干扰。并发操作，使某个事务的执行不受其它事务的干扰。并发控制的技术是封锁，即事务在修改某个对象并发控制的技术是封锁，即事务在修改
8、某个对象前，先锁住该对象，不允许其它事务读取或修改该对前，先锁住该对象，不允许其它事务读取或修改该对象，修改完毕或事务完成后再将锁打开。象，修改完毕或事务完成后再将锁打开。12/26/2022数据库系统92 封锁（封锁（Locking）封锁的类型：封锁的类型：排它锁排它锁（Exclusive Lock，简称，简称X锁锁，又称，又称互斥锁互斥锁）：）：若事务若事务T对数据对象对数据对象R加上加上X锁，则只允许锁，则只允许T读、写读、写R，禁止其禁止其它事务对它事务对R加任何锁，相应地其它事务就无法读、写对象加任何锁，相应地其它事务就无法读、写对象R。共享锁共享锁（Shared Lock，简称，简
9、称S锁锁）：）：若事务若事务T对数据对象对数据对象R加上加上S锁，则锁，则T可以读可以读R，但不可以写，但不可以写R，且其它事务可以对且其它事务可以对R加加S锁、但禁止加锁、但禁止加X锁。这保证了事务锁。这保证了事务T在释在释放放R的的S锁之前，其它事务只可以读锁之前，其它事务只可以读R，不可以修改，不可以修改R。12/26/2022数据库系统10附加知识点附加知识点（参见参见P295例例2图图11.4）：）：1、封锁协议（、封锁协议（Locking Protocol）在运用在运用X锁和锁和S锁对数据对象加锁时，对何时申请锁对数据对象加锁时，对何时申请X锁或锁或S锁、锁、持锁时间、何时释放等的
10、一些约定。持锁时间、何时释放等的一些约定。2、三级封锁协议、三级封锁协议 基本方法：基本方法：事务在读数据对象事务在读数据对象R时先上时先上S锁，封锁后才能读锁，封锁后才能读R，否则需，否则需等待；等待；事务在写数据对象事务在写数据对象R时先上时先上X锁，封锁后才能写锁，封锁后才能写R，否则需，否则需等待；等待；何时何时释放锁释放锁（Unlock）？）？12/26/2022数据库系统11根据上锁的类型和释放锁的时机，分为三种情况。根据上锁的类型和释放锁的时机，分为三种情况。1级封锁协议级封锁协议:事务事务T在修改数据对象在修改数据对象R之前必须先对其加之前必须先对其加X锁，直到事务锁，直到事务
11、结束才释放。结束才释放。2级封锁协议级封锁协议:1级封锁协议级封锁协议+事务事务T在读取数据对象在读取数据对象R之前必须先对其加之前必须先对其加S锁，锁，读完即释放读完即释放S锁锁。3级封锁协议级封锁协议:1级封锁协议级封锁协议+事务事务T在读取数据对象在读取数据对象R之前必须先对其加之前必须先对其加S锁，锁，S锁也是直到事务结束才释放锁也是直到事务结束才释放。12/26/2022数据库系统121级封锁协议级封锁协议:事务事务T在修改数据对象在修改数据对象R之前必须先对其加之前必须先对其加X锁，锁，直到直到事务结束事务结束才释放。才释放。分析：分析：时间时间 事务事务T1 事务事务 T2 请求
12、请求X锁锁 对对A加加X锁锁 读出读出A=16 请求请求X锁锁 等待等待 AA1 写回写回A=15 Commit 释放释放X锁锁 对对A加加X锁锁 读出读出A=15 AA1 写回写回A=14 Commit 释放释放X锁锁作用：作用：防止丢失修改防止丢失修改 保证事务是可恢复的保证事务是可恢复的12/26/2022数据库系统132级封锁协议级封锁协议:1级封锁协议级封锁协议+事务事务T在读取数据对象在读取数据对象R之前必须先对其之前必须先对其加加S锁，读完即释放锁，读完即释放S锁。锁。分析：分析：作用：作用：防止丢失修改防止丢失修改时间时间 事务事务T1 事务事务 T2 请求请求X锁锁 对对C加
13、加X锁锁 读出读出C=100 计算计算 CC 2,写回写回C ROLLBACK （C恢复为恢复为100）释放释放X锁锁 请求请求S锁锁 等待等待 防止读防止读“脏脏”数据数据 对对C加加S锁锁 读出读出C=100 释放释放S锁锁 保证事务是可恢复的保证事务是可恢复的12/26/2022数据库系统143级封锁协议级封锁协议:1级封锁协议级封锁协议+事务事务T在读取数据对象在读取数据对象R之前必之前必须先对其加须先对其加S锁，锁，S锁也锁也是直到事务结束才释放。是直到事务结束才释放。分析：分析：作用：作用：防止丢失修改防止丢失修改 对对A加加S锁锁 对对B加加S锁锁 读出读出A=50，B=100
14、求和求和=150 对对B请求请求X锁锁 等待等待 读出读出A=50，B=100 求和求和=150 Commit 释放释放A、B上的上的S锁锁时间时间 事务事务T1 事务事务 T2 对对B加加X锁锁 读出读出B=100 计算计算 B B 2，写回，写回B Commit 释放释放X锁锁 防止读防止读“脏脏”数据数据 保证可重复保证可重复读读 保证事务是可恢复的保证事务是可恢复的12/26/2022数据库系统15 对对R1上上X锁锁 对对R2上上X锁锁 对对R2请求请求X锁锁 等待等待 对对R1请求请求X锁锁 等待等待3 活锁和死锁活锁和死锁 使用封锁机制，得不到锁的事务就要等待，这可能使用封锁机制
15、，得不到锁的事务就要等待，这可能出现下述局面：出现下述局面：T1 T2 T1和和T2将将永远等待下去永远等待下去12/26/2022数据库系统161、活锁（、活锁（Livelock）：）：数据对象不断处于上锁、开锁的交替状态，某个事务有可能数据对象不断处于上锁、开锁的交替状态，某个事务有可能为该对象上锁，但始终没有得到上锁机会而永久等待下去的情形。为该对象上锁，但始终没有得到上锁机会而永久等待下去的情形。例如：例如：T1 T2 T3 T4 .封锁封锁R请求封锁请求封锁R 请求封锁请求封锁R等待等待 请求封锁请求封锁R 等待等待释放锁释放锁封锁封锁R等待等待释放锁释放锁封锁封锁R 如此下去，如此
16、下去，T2可能永可能永远不能封远不能封锁锁R。12/26/2022数据库系统17避免活锁避免活锁：如采用先来先服务策略。如采用先来先服务策略。2、死锁（、死锁（Deadlock）：）：多个事务因封锁冲突（竞争资源）而永远等待下去的情形。多个事务因封锁冲突（竞争资源）而永远等待下去的情形。如如（课件（课件p15例子）例子）死锁问题的死锁问题的解决方法解决方法预防死锁预防死锁诊断死锁诊断死锁并解除并解除一次封锁法一次封锁法顺序封锁法顺序封锁法超时法超时法等待图法等待图法（1）一次封锁法）一次封锁法 每个事务必须将所要求的数据对象全部上锁后才能执行读每个事务必须将所要求的数据对象全部上锁后才能执行读
17、写操作，否则释放占用的资源。写操作，否则释放占用的资源。存在的问题存在的问题 使数据的上锁时间增长，降低了系统的并发度。使数据的上锁时间增长，降低了系统的并发度。12/26/2022数据库系统18 很难确定事务执行期间需封锁的数据对象。有些一开始不需很难确定事务执行期间需封锁的数据对象。有些一开始不需要封锁的对象，随着数据库数据的变化，可能变成封锁对象，为要封锁的对象，随着数据库数据的变化，可能变成封锁对象，为避免此种情况发生，只能扩大封锁范围。避免此种情况发生，只能扩大封锁范围。（2）顺序封锁法）顺序封锁法 对所有数据对象规定一个封锁顺序，所有事务均按这个顺对所有数据对象规定一个封锁顺序，所
18、有事务均按这个顺序实行封锁。序实行封锁。存在的问题存在的问题：很难维护数据对象的封锁顺序，因为数据对象很多并在不断很难维护数据对象的封锁顺序，因为数据对象很多并在不断地增加、减少。地增加、减少。很难确定事务需封锁那些对象，从而很难按规定的顺序封锁。很难确定事务需封锁那些对象，从而很难按规定的顺序封锁。预防死锁的策略不很适合数据库的特点，预防死锁的策略不很适合数据库的特点，DBMS普遍采用普遍采用诊断诊断死锁并解除的方法。死锁并解除的方法。12/26/2022数据库系统19（3）超时法）超时法 当一个事务的等待时间超过了规定的时限，就认为发生了死当一个事务的等待时间超过了规定的时限，就认为发生了
19、死锁。锁。存在的问题：存在的问题：时限规定的太短，可能误判死锁，规定的太长，又不能及时时限规定的太短，可能误判死锁，规定的太长，又不能及时发现死锁。因此很难确定一个合理的时限。发现死锁。因此很难确定一个合理的时限。（4）等待图法）等待图法 用一个有向图表示事务等待的情况。图用一个有向图表示事务等待的情况。图中节点表示事务，边表示事务间的等待关系。中节点表示事务，边表示事务间的等待关系。并发控制子系统定时检查此图，若发现有回并发控制子系统定时检查此图，若发现有回路，则产生死锁。路，则产生死锁。发生死锁时，解除死锁的方法：发生死锁时，解除死锁的方法：选择一个处理代价最小的事务，将其撤消。选择一个处
20、理代价最小的事务，将其撤消。ROLLBACK12/26/2022数据库系统204 并发调度的可串行性并发调度的可串行性 多事务并发执行，对并发操作的调度是随机的，如何保证正多事务并发执行，对并发操作的调度是随机的，如何保证正确性？确性？1、调度（、调度（Schedule）：）：若干个事务的操作构成的序列。若干个事务的操作构成的序列。2、串行与并发、串行与并发 对调度对调度S中的两个事务中的两个事务Ti和和Tj，若，若S中中Ti的操作都在的操作都在Tj的操作的操作之前（或反之），则称之前（或反之），则称Ti、Tj是是串行执行串行执行的；否则称作是的；否则称作是并发执并发执行行的。的。若调度若调度
21、S中的所有事务都是串行执行的，则称中的所有事务都是串行执行的，则称S是是串行串行的的（Serial）。）。12/26/2022数据库系统213、可串行化（、可串行化（Serializable）多个事务的并发执行是正确的，当且仅当其结果与按某一多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度为可串行化次序串行地执行它们时的结果相同，称这种调度为可串行化的调度。的调度。调度调度可串行化的可串行化的不可串行化的不可串行化的串行的串行的并发的并发的并发的并发的 所有事务串行起来的调度策略一定是正确的调度策略。尽所有事务串行起来的调度策略一定是正确的调度策略。
22、尽管一组事务可能有多个串行调度序列，且产生的执行结果不一管一组事务可能有多个串行调度序列，且产生的执行结果不一定相同，但每个序列都不会将数据库置于不一致状态。定相同，但每个序列都不会将数据库置于不一致状态。12/26/2022数据库系统224、一点说明、一点说明：对若干个事务，不同的并发调度策略其最终的执行结对若干个事务，不同的并发调度策略其最终的执行结果不一定完全相同。但只要它们的调度是可串行化的，则果不一定完全相同。但只要它们的调度是可串行化的，则都是正确调度。都是正确调度。如：事务如：事务T1：读：读B；AB+1；写回；写回A。事务事务T2：读：读A；BA+1；写回；写回B。T1 T2
23、读读BAB+1写写A 读读A BA+1 写写B T1 T2 读读A BA+1 写写B读读BAB+1写写A T1 T2 读读B 读读AAB+1写写A BA+1 写写B结果结果A=3B=4假设假设T1、T2执行前执行前 A=2，B=2A=4B=3A=3B=312/26/2022数据库系统23 T1 T2 读读B 读读AAB+1写写A BA+1 写写B T1 T2 读读B 读读AAB+1写写A BA+1 写写B 分析右边的调度：分析右边的调度：若采用若采用2级封锁协议，级封锁协议，则可能得到这样的调度则可能得到这样的调度仍是不可串行化的调度仍是不可串行化的调度若采用若采用3级封锁协议，级封锁协议，则
24、可能得到这样的调度则可能得到这样的调度永久等待，造成死锁永久等待，造成死锁Slock BUnlock B Slock A Unlock AXlock AUnlock A Xlock B Unlock BSlock B读读B Slock A 读读AXlock AAB+1 Xlock B写写AUnlock AUnlock B BA+1 写写B Unlock A Unlock B因此，三级封锁协议不能因此，三级封锁协议不能保证得到可串行化的调度，保证得到可串行化的调度，也会造成死锁。也会造成死锁。12/26/2022数据库系统245 两段锁协议两段锁协议1、两段封锁协议、两段封锁协议（也称（也称两相
25、上锁协议两相上锁协议）（2-Phase-Locking Protocol，简写，简写2PL）（1）在对任何数据进行读、写操作之前，事务首先要申请并获）在对任何数据进行读、写操作之前，事务首先要申请并获得对该数据的封锁（读时得对该数据的封锁（读时S锁，写时锁，写时X锁）；锁）；（2）在释放一个封锁之后，事务不再申请和获得新的封锁。）在释放一个封锁之后，事务不再申请和获得新的封锁。例：例：Lock A Lock B Lock C Unlock B Unlock A Unlock CLock A Lock B Unlock B Lock C Unlock A Unlock C含义含义：事务封锁分两个
26、阶段：事务封锁分两个阶段 第一阶段是第一阶段是扩展阶段扩展阶段（Growing Phase），只进行上锁），只进行上锁 第二阶段是第二阶段是收缩阶段收缩阶段（Shrinking Phase）,只进行解锁只进行解锁12/26/2022数据库系统252、2PL的正确性的正确性 定理定理：若所有事务都遵守两段封锁协议，则对这些事务的任：若所有事务都遵守两段封锁协议，则对这些事务的任何并发调度策略都是可串行化的。何并发调度策略都是可串行化的。3、说明、说明 2PL是并发控制正确性的充分条件，但不是必要条件。是并发控制正确性的充分条件，但不是必要条件。即若所有事务都遵守即若所有事务都遵守2PL，则这些事
27、务的任何并发调度都是可，则这些事务的任何并发调度都是可串行化的，反之，一个并发调度是可串行化的，不一定所有事串行化的，反之，一个并发调度是可串行化的，不一定所有事务都遵守务都遵守2PL。（参见（参见P299图图11.7（d）12/26/2022数据库系统26Lock A Lock B Lock C Unlock B Unlock A Unlock C允许读写允许读写不允许读写不允许读写此时才允许读写此时才允许读写预防死锁的预防死锁的一次封锁法一次封锁法2PL 2PL会产生死锁（参见会产生死锁（参见P302图图11.9）。）。2PL不隐含预防死锁的一次封锁法，但一次封锁法肯不隐含预防死锁的一次封
28、锁法，但一次封锁法肯定遵守定遵守2PL。12/26/2022数据库系统276 封锁的粒度封锁的粒度1、封锁的粒度（、封锁的粒度（Granularity）封锁对象的大小。可以是数据库、表、记录、字段等。封锁对象的大小。可以是数据库、表、记录、字段等。粒度大，封锁开销小，但影响共享粒度大，封锁开销小，但影响共享粒度小，封锁开销大，但共享性好粒度小，封锁开销大，但共享性好2、多粒度封锁（、多粒度封锁（Multiple Granularity Locking)同时支持多种封锁粒度供不同事务选择的封锁方法。同时支持多种封锁粒度供不同事务选择的封锁方法。多粒度封锁方法依赖的数据结构多粒度封锁方法依赖的数据
29、结构-多粒度树多粒度树 将数据库中的数据对象按相互关系和粒度大小组织成的树型将数据库中的数据对象按相互关系和粒度大小组织成的树型结构，其中根结点表示最大数据粒度，通常为整个数据库，叶结构，其中根结点表示最大数据粒度，通常为整个数据库，叶结点表示最小数据粒度。结点表示最小数据粒度。12/26/2022数据库系统28多粒度封锁协议多粒度封锁协议 允许对多粒度树中的每个结点独立地加锁，并且对每一个结允许对多粒度树中的每个结点独立地加锁，并且对每一个结点加锁隐含着对其后裔结点也加以同样的锁。点加锁隐含着对其后裔结点也加以同样的锁。由事务直接加到数据对象上的封锁称为由事务直接加到数据对象上的封锁称为显式
30、封锁显式封锁，因上级结，因上级结点加锁而引起下级对象被封锁，称为点加锁而引起下级对象被封锁，称为隐式封锁隐式封锁。显式封锁与隐式封锁的效果是一样的。显式封锁与隐式封锁的效果是一样的。多粒度封锁方法多粒度封锁方法 为对某数据对象加锁，系统要检查：为对某数据对象加锁，系统要检查：该对象有无显式封锁与之冲突；该对象有无显式封锁与之冲突；该对象的上级结点有无显式封锁与之冲突；该对象的上级结点有无显式封锁与之冲突；该对象的下级结点有无显式封锁与之冲突；该对象的下级结点有无显式封锁与之冲突；当无任何冲当无任何冲突时方能加突时方能加锁成功。锁成功。3、意向锁、意向锁 用来指示下级结点正在被加锁的锁。对任一结
31、点加锁时，必用来指示下级结点正在被加锁的锁。对任一结点加锁时，必须先对其上级结点加意向锁。须先对其上级结点加意向锁。12/26/2022数据库系统29作用作用：减少加锁时的封锁冲突检查工作量。只需检查上级结点与减少加锁时的封锁冲突检查工作量。只需检查上级结点与 本结点是否已加了不相容的锁，并通过本结点的意向锁了解下级本结点是否已加了不相容的锁，并通过本结点的意向锁了解下级结点是否有不相容的锁，从而不必再检查下级结点。结点是否有不相容的锁，从而不必再检查下级结点。三种意向锁三种意向锁 意向共享锁（意向共享锁（IS锁）锁）如果要对某个对象加如果要对某个对象加S锁，需先对其上级对象加锁，需先对其上级对象加IS锁。锁。意向排它锁（意向排它锁（IX锁）锁）如果要对某个对象加如果要对某个对象加X锁，需先对其上级对象加锁，需先对其上级对象加IX锁。锁。共享意向排它锁（共享意向排它锁（SIX锁）锁）如果要对某对象加如果要对某对象加S锁，并对其下级对象加锁，并对其下级对象加X锁，则应对该对锁，则应对该对象加象加SIX锁。锁。意向锁的封锁和释放顺序意向锁的封锁和释放顺序封锁：自上而下封锁：自上而下 释放：自下而上释放：自下而上
