数据库-第十一章并发控制

第1

页数据库系统原理第十一章 并发控制并发控制概述DBMS并发控制是为保证多用户并发操作数据库中信息时的正确性、一致性所采取的措施。事务调度事务的执行顺序称为一个调度，表示事务的指令在系统中执行的时间顺序。一组事务的调度必须保证：包含了所有事务的操作指令同一个事务中指令的顺序必须保持不变调度方式串行调度：属于同一事务的指令紧挨在一起并行调度：来自不同事务的指令可以交叉执行第2/35

页T2read(A);

temp:=

A0.1A

:=

A

temp;write(A);read(B);B:=B+

temp;write(B);事务执行示例从A过户50￥到BT1read(A);A

:=

A

50;write(A);read(B);B:=B+50;write(B);从A过户存款的10%到B开始状态：

A=1000￥B=2000￥A+B=3000￥第3/35

页read(A);A

:=

A

50;write(A);read(B);B

:=

B

+

50;write(B);read(A);

temp

:=

A0.1A

:=

A

temp;write(A);read(B);B

:=

B

+

temp;write(B);T1T2A=950￥B=2050￥结束状态：A=855￥B=2145￥A+B=3000￥串行调度1开始状态：A=1000￥B=2000￥A+B=3000￥第4/35

页read(A);A

:=

A

50;write(A);read(B);B

:=

B

+

50;write(B);T1T2read(A);

temp

:=

A0.1A

:=

A

temp;write(A);read(B);B

:=

B

+

temp;write(B);A=900￥B=2100￥结束状态：A=850￥B=2150￥A+B=3000￥串行调度2第5/35

页read(B);B

:=

B

+

temp;write(B);T1T2read(B);B

:=

B

+

50;write(B);结束状态：A=855￥B=2145￥A+B=3000￥A=950￥B=2000￥read(A);temp

:=

A0.1A

:=

A

temp;write(A);read(A);A

:=

A

50;write(A);A=855￥B=2000￥A=855￥B=2050￥并行调度3第6/35

页第7/35

页并行调度的问题丢失更新（lost

update)两个以上事务从DB中读入同一数据并修改，其中一事务（后提交的事务)的提交结果破坏了另一事务（先提交的事务)的提交结果，导致先前提交事务对DB的修改被丢失。不可重复读（read

non-repeatable)同一事务重复读同一数据，但获得结果不同。即从数据库中得到了不一致的数据。读“脏”数据（read

dirty)读未提交随后又被撤消(Rollback)的数据。即从数据库中得到了临时性数据。第8/35

页read(A);A

:=

A

50;T1T2A=1000￥结束状态：A=950￥B=2100￥A+B=3050￥write(A);read(B);B

:=

B

+

50;write(B);A=900￥B=2000￥B=2000￥read(A);

temp

:=

A0.1A

:=

A

temp;write(A);read(B);A=950￥B=2000￥A=950￥B=2050￥B

:=

B

+

temp;write(B);丢失更新丢失更新在数据库系统中是不可的错误，必须避免。。T1：查询酒吧Joe出售的啤酒的最高价和(max)

SELECT

MAX(price)

FROM

SellsWHERE

bar

=’Joe’;(min)SELECT

MIN(price)

FROM

SellsWHERE

bar

=’Joe’;T2：将酒吧Joe出售的啤酒改为Snow，售价3.5元。(del)(ins)DELETE

FROM

SellsWHERE

bar

=

’Joe’;INSERT

INTO

SellsVALUES(’Joe’,

’

Snow’,

3.50);SellsBarBeerPriceJoeBud2.50JoeMiller3.00第9/35

页不可重复读第10/35

页假设调度顺序为:(max)(del)(ins)(min)Price:{2.50,3.00}{2.50,3.00}{3.50}Statement:Result:(max)3.00(del)(ins)(min)3.50MAX<MIN!时间T1T2pricet1(del)t2(ins)t3(max){3.50}t4Rollbackt5(min){2.50,

3.00}读“脏”数据产生上述三类并发错误的原因：并发操作破坏了事务的 性。第11/35

页的粒度据

的

性 索引是DBMS实现事务

的一种常用方法。的定义事务T可对某个数据对象加锁（Lock)，加锁成功后，事务T

对这个数据对象就拥有一定的控制权，直到其释放锁（Unlock)。锁类型排它锁（X锁

/

写锁)：若事务T

对数据

R

加上

X

锁，则其它事务不能对

R

进行任何

。共享锁（S锁/读锁)：若事务T

对数据R

加上S

锁，则其它事务只能对R

加S锁，但不能加X锁。如果 务T1已经对元组t上了S锁，则以下答案错误的是

。A.

T1不能对t上X锁

B.

T2不能对t上X锁

C.

T2还能对t上S锁第12/35

页死锁1.含义两个或两个以上事务均处于等待状态，每个事务都在等待其中另一个事务的数据，导致任何事务都不能继续执行的现象称为死锁。时间TATBt1XLock

At2XLockBt3XLockB等待t4XLock

A等待t5等待等待第13/35

页产生条件①互斥（排它性控制)②不可

（ 前，其它事务不能

)③部分分配（每次申请一部分)④环路（每事务获得的数据同时又被另一事务请求)死锁的解决办法预防：

一次

法每个事务事先一次获得其需数据的全部锁。如：T

获得所有数据A、B锁，TA连续执行，TB等待；TA执行完后

A、B锁，TB继续执行，不会发生死锁。特征：简单，无死锁；粒度大，并发性低；难以确定 对象。第14/35

页顺序实行

。死锁的解决办法（续)预防：顺序

法事务按预先确定的数据上例中：设 顺序：A→B；T1、T2均按此顺序申请锁；若T1先获得A、B锁；T2则先申请A锁，等待；T1 A、B锁；T2获得锁运行；缺点：事务动态变化，很难按规定的顺序去施加

。第15/35

页3.死锁的解决办法（续)：超时法若事务的等待时间超过了规定的时限，就认为发生了死锁。缺点：若时限设置得太短，容易误判若时限设置得太长，死锁不易及时发现：等待图法①构造一事务等待图，图中每个节点表示正在运行的事务，每条边表示等待的情况；T1

T2②周期性检测该等待图；③判断存在回路否；④存在，则撤消某一事务：选择一个处理死锁代价最小的事务（NP难度问题），该有的锁，使其它事务得以继续运行。第16/35

页活锁1.含义事务因故

处于等待状态，也称

。T1T2T3T4TnLOCK(R)=TLOCK(R)=F等待LOCK(R)=FUNLOCK(R)等待等待LOCK(R)=T等待…LOCK(R)=F等待UNLOCK(R)等待LOCK(R)=T预防方法FCFS（

Come

Server)：先来先服务对于事务有优先级的系统，可设置一个最长等待时间，与优先级结合，调度事务的执行。第17/35

页两段锁协议（2PL：two-phase

locking)可串行化调度当且仅当多个事务并发执行的结果与该事务任一串行执行的结果相同时，则该并发执行是可串行化的。例：假设有两个事务T1、T2，数据库中A、B的初值均为2；T1：读B；A＝B＋1；写回A以上步骤可简写为：r1(B);w1(A)T2：读A；B＝A＋1；写回B以上步骤可简写为：r2(A);w2(B)如果是串行调度，只有两种可能的调度序列：r1(B);

w1(A);r2(A);w2(B)，结果为：A＝3，B＝4r2(A);

w2(B);

r1(B);

w1(A)两个事务并发执行，则可能的调r1(B);

r2(A);

w1(A);

w2(B)这个调度是不是可串行化的？第18/35

页可串行化——判断可串行化调度的充分条件。对于一个并发调度Sc，在保证操作次序不变的情况下，如果通过交换不操作可以得到一个串行调度，则Sc为冲突可串行化调度。操作——不同事务对同一个数据的读写操作或写写操作：Wi(x);

Rj(x)Ri(z);

Wi(z)Wi(y);

Wj(y)Wi(x);

Wj(y)交换（swap)原则——操作不能交换次序例2：r1(B);

r2(A);w1(A);w2(B)r1(A);

w1(B);

w1(C);

r2(B);

w2例1：r1(A);w1(B);r2(B);w1(C);w2(为什么不能冲突可串行化？第19/35

页可串行化调度。课堂练习：1.

一个可串行化调度一定是一个答案：错误。2.设有一个并发事务调度序列如下：r1(A);

w2(A);r2(B);

???;

w1(C);

w2(B)

……其中???表示某事务的一个读或者写操作（例如r1(B))，给出

???的所有可能实例，使得该调度序列是一个非 可串行化调度。答案：r1(A)w1(A)w1(B)r2(C)w2(C)第20/35

页2.两段锁含义事务分为两个阶段对数据加锁和

：第一阶段称为扩展阶段（获得锁)第二阶段称为收缩阶段（ 锁)3.策略①在对任何数据读、写之前，须先获得该数据的锁②

在 一个 之后，该事务不能再申请任何其它锁遵循两段锁协议的事务，其 序列可以为：SLOCK(A)

SLOCK(B)

XLOCK(C)

UNLOCK(B)

UNLOCK(A)

UNLOCK(C)扩展阶段收缩阶段不遵循两段锁协议的事务，其 序列可能为：SLOCK(A)

UNLOCK(A)

SLOCK(B)

XLOCK(C)

UNLOCK(B)

UNLOCK(C)第21/35

页时间TADB中的值TBt1S

Lock

BB=2

Y=BXLcok

AB=2A=2t2S

Lock

A等待t3A：=Y+1写回A=3UNLock

BUNLock

AB=2A=3t4B=2A=3S

Lock

AA=3

Y=At5B=4A=3X

Lock

BB=Y+1写回B=4UNLockBUNLockA4.两段锁协议目标实现并发操作调度的可串行化。若所有并发事务都遵守两段锁协议，则对这些事务的所有并行调度都是可串行化的。(why?)关于两段锁协议的两点说明：两段锁协议是可串行化调度的充分条件，但不是必要条件。两段锁协议不能防止死锁（注意区别于一次 法)。第23/35

页事务

级为了兼顾正确性和系统效率，SQL

定义了4种事务

级。设置事务 级的语法：SET

TRANSACTION

ISOLATION

LEVEL

XX

可以是：SERIALIZABLE（可串行化)REPEATABLE

READ（可重复读)READ

COMMITTED（读提交)READ

MITTED（读未提交)只有SERIALIZABLE

级能保证事务的ACID

特性。第24/35

页。T1：查询酒吧Joe出售的啤酒的最高价和(max)

SELECT

MAX(price)

FROM

SellsWHERE

bar

=’Joe’;(min)SELECT

MIN(price)

FROM

SellsWHERE

bar

=’Joe’;T2：将酒吧Joe出售的啤酒改为Snow，售价3.5元。(del)(ins)DELETE

FROM

SellsWHERE

bar

=

’Joe’;INSERT

INTO

SellsVALUES(’Joe’,

’

Snow’,

3.50);SellsBarBeerPriceJoeBud2.50JoeMiller3.00第25/35

页SERIALIZABLE（可串行化)如果事务T1的 级为

SERIALIZABLE，则T1只能看到T2执行前的数据库，或者T2执行后的数据库。时间T1T2pricet1t2t3t4时间T1T2pricet1(del)t2(ins)t3(max){3.50}t4(min){3.50}第26/35

页级的个性化级的设置只对当前事务有效。例如：如果事务T2的级为SERIALIZABLE，但事务T1的级不是SERIALIZABLE，则T1读到的数据可能为空集。时间T1T2pricet1(del)t2(max){}t3(min){}t4(ins)第27/35

页Readmited（读未提交)如果事务T1的 级是Read mited，则T1可能读到未提交的数据，但不会丢失更新。即：无法避免不可重复读和读脏数据。时间T1T2pricet1(del)t2(ins)t3(max){3.50}t4Rollbackt5(min){2.50,

3.00}第28/35

页Read

Commited（读提交)如果事务T1的 级是ReadCommited，则T1只能读到已提交数据，但是每次读到的数据不一定相同。即：无法避免不可重复读。时间T1T2pricet1(max){2.50,

3.00}t2(del)t3(ins)t4(min){3.50}第29/35

页Repeatable

Read（可重复读)第30/35

页Repeatable

Read在ReadCommited的基础上进一步要求：如果数据被重复读，则第一次读到的所有数据，第二次也应该被读到。但是，第二次可能读到新增的元组（幻象读）。时间T1T2pricet1(max){2.50,

3.00}t2(insert3.50)t3(min){2.50,

3.00,3.50}事务

级的实现1．一级 协议策略事务T在修改元组D之前须先对D加X锁，直到事务T结束（commit/rollback)才

。功能防止丢失更新；保证T可恢复（若意外终止，则回滚后才可 锁)。问题不能防止不可重复读和读“脏”数据（why?)可达到的事务 级：Read

mitted第31/35

页T1T2T1T2T1T21)Xlock(A)=

T读A=16A=50B=100Xlock(C)=TC=1002）Xlock(A)=FXlock(B)=TB:=B*2=200C:=2*C=2003)A:=A-1=15Xlock(S)=TS:=A+B=150C=2004)Xlock(A)=

FROLLBACK5）COMMITCOMMITUNLOCK(C)6)Xlock(A)=

FUnlock(B)7）Unlock（A）A=50B=2008）Xlock(A)=T读A＝15Xlock(S1)=TS1:=A+B=2509)

A:=A-1=1410）COMMITS!＝S1写丢失避免了！不可重复读读“脏”数据第33/35

页2．二级

协议1)策略一级协议+事务T

在D

之前必须对D

加S

锁，读完后即可 该

S锁。功能防止丢失更新；防止读脏。问题不能防止不可重复读（why?)。可达到的事务 级：Read

Committed第34/35

页T1T2T1T21)SLOCK(A)=T

A=50SLOCK(B)=T

B=100Xlock(C)=TC=100

C:=2*C=2002)Unlock(A)

Unlo