第十章并发控制

1、12 事务处理系统通常允许多个事务并发执事务处理系统通常允许多个事务并发执行。行。 事务在并发的情况下必须保证一致性。事务在并发的情况下必须保证一致性。 考虑并发的原因：考虑并发的原因： 一个事务由多个步骤组成，即事务中的语句一个事务由多个步骤组成，即事务中的语句分为两类：分为两类：i/o活动和活动和cpu活动。活动。 系统中可能运行着各种各样的事务。一些较系统中可能运行着各种各样的事务。一些较长一些较短。长一些较短。3 单机系统：交叉并发执行单机系统：交叉并发执行 多处理系统：同时并发执行多处理系统：同时并发执行4 当数据库中有多个事务并发执行时，系当数据库中有多个事务并发执行时，系统必须对

2、并发事务之间的相互作用加以统必须对并发事务之间的相互作用加以控制，保证数据库的一致性，同时避免控制，保证数据库的一致性，同时避免用户得到不正确的数据。用户得到不正确的数据。5 所谓并发即多个事务轮流占用所谓并发即多个事务轮流占用cpu时间时间进行处理。进行处理。t1:read(a)a:=a-100write(a);t2:read(a);temp:=a*0.1;a:=a-temp;write(a);read(b);b:=b+100;write(b)read(b);b:=b+temp;write(b);67 数据库的并发操作带来的问题主要有以下三种：数据库的并发操作带来的问题主要有以下三种：1、丢

3、失更新、丢失更新.事务事务t12和和t13同时对同时对a操作，操作，t12对对a值值减减30，事务，事务t13对对a值加倍。值加倍。时时间间更新事务更新事务t12数据库中数据库中a的值的值更新事务更新事务t13t0100t1read(a)t2read(a)t3a=a-30t4a=a*2t5write(a)t670write(a)t72008时时间间更新事务更新事务t1更新事务更新事务t2t0read(a)=16t1read(a)=16t2a=a-1t3write(a)t4a=a-1t5write(a)t6t7均为15，假如飞机票的话，则会出现售出两张票，但显示只有一张票 9 2、不可重复读，（

4、读了过时的数据）、不可重复读，（读了过时的数据） 在在t5时刻，读的是过了时的数据时刻，读的是过了时的数据时时间间更新事务更新事务t12数据库中数据库中a的值的值更新事务更新事务t14t0100t1read(a)t2read(a)t3a=a-30t4write(a)t570read(a)10t1t2t0read(a)=50t1read(b)=100t2求和求和150t3read(b)=100t4b=b*2t5write(b)t6read(a)=50t7read(b)=200t8求和求和250t9验算不对验算不对11 3、读脏数据读脏数据,事务事务t12修改修改a值为值为70以后还未提交以后还未

5、提交（commit）,事务事务t15读取了读取了a值，随后事务值，随后事务t12执行执行回退，回退，a的值恢复为的值恢复为100,则则t15使用的是被撤销的使用的是被撤销的a值。值。时间时间更新事务更新事务t12 数据库中数据库中a的值的值读读t15t0100t1read(a)t2a=a-30t3write(a)t470read(a)t5rollbackt610012 在数据库中，把未提交随后又被撤销的在数据库中，把未提交随后又被撤销的数据称为数据称为“脏数据脏数据” 解决以上问题的方法有两种：封锁技术解决以上问题的方法有两种：封锁技术和时间戳技术。和时间戳技术。13 设有两个事务设有两个事务

6、t1、t2，其并发操作如下图所，其并发操作如下图所示示 - t1 t2-读读a=100a=a*2写回写回 读读a=200rollback恢复恢复a=100 -14 封锁、时间戳、乐观控制法封锁、时间戳、乐观控制法 确保并发控制正确即通过其他的方法保确保并发控制正确即通过其他的方法保证对数据项的访问以互斥的方式进行，证对数据项的访问以互斥的方式进行，通过加锁完成。通过加锁完成。15 所谓封锁就是事务所谓封锁就是事务t在对某个数据对象进行操在对某个数据对象进行操作之前，先向系统发出请求，对其加锁。此事作之前，先向系统发出请求，对其加锁。此事务对这个数据对象有一定控制，务对这个数据对象有一定控制，

7、而其他事务而其他事务则不能更新数据直到事务释放它的锁为止。则不能更新数据直到事务释放它的锁为止。 封锁类型主要有两种：封锁类型主要有两种： 共享锁。如果事务共享锁。如果事务ti获得了数据项获得了数据项q上的共享型锁，上的共享型锁，（记为（记为s），则），则ti可读取可读取q但不能写但不能写q。其他事务只。其他事务只能再对能再对q加加s锁。锁。 排他锁。若事务排他锁。若事务ti对对q加排他锁（记为加排他锁（记为x），则），则ti既既可以读可以读q又可以写又可以写q，其他事务都不能再加任何类，其他事务都不能再加任何类型的锁，不能再读取和修改型的锁，不能再读取和修改a16 a跟跟b代表任意类型锁，若

8、代表任意类型锁，若ti对数据项对数据项q加加a类类型锁，而事务型锁，而事务tj当前在当前在q上有上有b型锁，若型锁，若ti可以可以立即获得立即获得q，则，则a和和b相容。相容。 一个数据项上可以同时拥有多个一个数据项上可以同时拥有多个s锁，此后的锁，此后的x锁必须等到所有共享锁释放。锁必须等到所有共享锁释放。 _表示没加任何锁。表示没加任何锁。sx_struefalsetruexfalse falsetrue_truetruetrue17 事务通过执行事务通过执行lock_s(q)指令来申请指令来申请q上上的共享锁。的共享锁。 排他锁通过执行排他锁通过执行lock_ x(q)， unlock(

9、q)指令来释放锁。指令来释放锁。18 如果要访问一个数据项，事务如果要访问一个数据项，事务ti必须首必须首先给该数据项加锁，如果该数据项已经先给该数据项加锁，如果该数据项已经被另一事务加锁，则在所有不相容类型被另一事务加锁，则在所有不相容类型锁释放之前，不会授予事务锁释放之前，不会授予事务ti锁。锁。19共享锁共享锁共享共享 (s) 锁允许并发事务读取锁允许并发事务读取 (select) 一一个资源。个资源。20 资源上存在共享资源上存在共享 (s) 锁时，任何其它事锁时，任何其它事务都不能修改数据。一旦已经读取数据，务都不能修改数据。一旦已经读取数据，便立即释放资源上的共享便立即释放资源上的

10、共享 (s) 锁，除非锁，除非将事务隔离级别设置为可重复读或更高将事务隔离级别设置为可重复读或更高级别，或者在事务生存周期内用锁定提级别，或者在事务生存周期内用锁定提示保留共享示保留共享 (s) 锁。锁。21排它锁排它锁排它排它 (x) 锁用于数据修改操作，例如锁用于数据修改操作，例如 insert、update 或或 delete。确保。确保不会同时对同一资源进行多重更新。可不会同时对同一资源进行多重更新。可以防止并发事务对资源进行访问。其它以防止并发事务对资源进行访问。其它事务不能读取或修改排它事务不能读取或修改排它 (x) 锁锁定的锁锁定的数据。数据。22 对数据对象加锁时，需要约定一些

11、规则，例如对数据对象加锁时，需要约定一些规则，例如何时申请何时申请x锁或锁或s锁、持锁时间、何时释放等，锁、持锁时间、何时释放等，称这些规则为封锁协议称这些规则为封锁协议(locking protocol) 对封锁方式规定不同的规则，就形成了各种不对封锁方式规定不同的规则，就形成了各种不同的封锁协议同的封锁协议 不同级别的封锁协议达到的系统一致性是不同不同级别的封锁协议达到的系统一致性是不同的的 封锁协议只允许冲突可串行化调度。封锁协议只允许冲突可串行化调度。23 事务事务t在修改数据在修改数据r之前必须先对其加之前必须先对其加x锁，直到事务结束（锁，直到事务结束（commit或或rollba

12、ck）才释放才释放 一级封锁协议可防止丢失修改，并保证一级封锁协议可防止丢失修改，并保证事务事务t是可恢复的是可恢复的 在一级封锁协议中，不能保证可重复读在一级封锁协议中，不能保证可重复读和不读和不读“脏脏”数据，因为只有读的时候数据，因为只有读的时候是不用加锁的。是不用加锁的。24 任何更新任何更新q的事务必须先执行的事务必须先执行lock_x(q)操作，以获得操作，以获得q上的上的x锁，若未获准则事锁，若未获准则事务进入等待状态，直到获得务进入等待状态，直到获得x锁，事务才锁，事务才继续进行。继续进行。25时间时间更新事务更新事务t12数据库中数据库中a的值的值更新事务更新事务t13t01

13、00t1lock_x(a)t2read(a)t3lock_x(a)t4a=a-30waitt5write(a)t670t7unlock(a)t8lock_x(a)t9read(a)t10a=a*2t11write(a)t12140unlock(a)26 在一级封锁协议中，如果仅仅是读数据在一级封锁协议中，如果仅仅是读数据不对其修改，是不需要加锁的，所以不不对其修改，是不需要加锁的，所以不能保证可重复读和不读能保证可重复读和不读“脏脏”数据数据27 在一级封锁协议基础上加上事务在一级封锁协议基础上加上事务t在读取在读取数据数据q之前必须先对其加之前必须先对其加s锁，读完后即锁，读完后即释放释放s

14、锁。锁。 在二级封锁协议中，由于读完数据后即在二级封锁协议中，由于读完数据后即可释放可释放s锁，所以它不能保证可重复读锁，所以它不能保证可重复读28一级封锁协议加上事务一级封锁协议加上事务t在读取数据在读取数据r之之前必须先对其加前必须先对其加s锁，直到事务结束才释锁，直到事务结束才释放放三级封锁协议除防止了丢失修改和不读三级封锁协议除防止了丢失修改和不读“脏脏”数据外，还进一步防止了不可重复数据外，还进一步防止了不可重复读读293031 假设存款余额假设存款余额x=1000元，甲事务取走存元，甲事务取走存款款300元，乙事务取走存款元，乙事务取走存款200元，其执元，其执行时间如下：行时间如

15、下：3233 请分析该并发操作带来的数据不一致请分析该并发操作带来的数据不一致问题属于哪一类？如果按照该顺序执问题属于哪一类？如果按照该顺序执行，最终存款余额变成了多少？行，最终存款余额变成了多少？ 应采用几级封锁协议进行控制？应采用几级封锁协议进行控制？ 具体应如何实现这两个事务的并发控具体应如何实现这两个事务的并发控制？制？34一级封锁协议。一级封锁协议。while（x已建立排它锁）已建立排它锁） 等待等待对对x建立排它锁建立排它锁读读x更新更新x=x3释放排它锁释放排它锁将乙事务修改为：将乙事务修改为：while（x已建立排它锁）已建立排它锁） 等待等待对对x建立排它锁建立排它锁读读x更

16、新更新x=x200释放排它锁释放排它锁35 1 如何锁一个表的某一行如何锁一个表的某一行set transaction isolation level read uncommitted select * from table rowlock where id = 1362 锁定数据库的一个表锁定数据库的一个表select * from table with (holdlock) 加锁语句：加锁语句：sybase: update 表表 set col1=col1 where 1=0 ;mssql: select col1 from 表表 (tablockx) where 1=0 ;oracle:

17、 lock table 表表 in exclusive mode ；加锁后其它人不可操作，直到加锁用户解锁，用加锁后其它人不可操作，直到加锁用户解锁，用commit或或rollback解锁解锁37 1）排它锁）排它锁新建两个连接新建两个连接在第一个连接中执行以下语句在第一个连接中执行以下语句begin tran update table1 set a=aa where b=b2 waitfor delay 00:00:30 -等待等待30秒秒commit tran在第二个连接中执行以下语句在第二个连接中执行以下语句begin tran select * from table1 where b=

18、b2 commit tran若同时执行上述两个语句，则若同时执行上述两个语句，则select查询必须等待查询必须等待update执行完毕才能执行即要等待执行完毕才能执行即要等待30秒秒382）共享锁）共享锁在第一个连接中执行以下语句在第一个连接中执行以下语句begin tran select * from table1 holdlock -holdlock人为加锁人为加锁 where b=b2 waitfor delay 00:00:30 -等待等待30秒秒commit tran在第二个连接中执行以下语句在第二个连接中执行以下语句begin tran select a,c from table

19、1 where b=b2 update table1 set a=aa where b=b2 commit tran若同时执行上述两个语句，则第二个连接中的若同时执行上述两个语句，则第二个连接中的select查询可以执查询可以执行行而而update必须等待第一个事务释放共享锁转为排它锁后才能执行必须等待第一个事务释放共享锁转为排它锁后才能执行 即要等待即要等待30秒秒393）死锁）死锁增设增设table2(d,e)d ed1 e1d2 e2在第一个连接中执行以下语句在第一个连接中执行以下语句begin tran update table1 set a=aa where b=b2 waitfor

20、 delay 00:00:30 update table2 set d=d5 where e=e1 commit tran 在第二个连接中执行以下语句在第二个连接中执行以下语句begin tran update table2 set d=d5 where e=e1 waitfor delay 00:00:10 update table1 set a=aa where b=b2 commit tran同时执行，系统会检测出死锁，并中止进程同时执行，系统会检测出死锁，并中止进程 4041 当多个事务对同一数据封锁时，有一个当多个事务对同一数据封锁时，有一个事务处于永远等待的状态，此时称为活事务处于

21、永远等待的状态，此时称为活锁。锁。 避免活锁的方法是采用先来先服务的方避免活锁的方法是采用先来先服务的方法。法。42解决死锁主要有两种方法解决死锁主要有两种方法 采取一定措施来预防死采取一定措施来预防死锁的发生锁的发生 采用一定手段定期诊断采用一定手段定期诊断系统中有无死锁，若有系统中有无死锁，若有则解除之则解除之43 一次封锁法一次封锁法 要求每个事务必须一次将所有要使用的要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行数据全部加锁，否则就不能继续执行 顺序封锁法顺序封锁法 预先将数据对象规定一个封锁顺序，所预先将数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁有事务

22、都按这个顺序实行封锁44死锁的诊断与解除 超时法超时法 事务的等待时间超过了规定的时限，就认为发事务的等待时间超过了规定的时限，就认为发生了死锁生了死锁 可能误判死锁可能误判死锁 时限若设置得太长，死锁发生后不能及时发现时限若设置得太长，死锁发生后不能及时发现 等待图法等待图法 并发控制子系统周期性地检测事务等待图，如并发控制子系统周期性地检测事务等待图，如果发现图中存在回路，则表示系统中出现了死果发现图中存在回路，则表示系统中出现了死锁锁45 解除死锁的方法是选择一个处理死锁代解除死锁的方法是选择一个处理死锁代价最小的事务，将其撤消，释放此事务价最小的事务，将其撤消，释放此事务持有的所有的锁

23、，使其他事务得以继续持有的所有的锁，使其他事务得以继续运行下去运行下去46 不是所有的并发执行都能得到正确的结不是所有的并发执行都能得到正确的结果果 首先要研究的是如何保证事务的并发执首先要研究的是如何保证事务的并发执行是正确的。行是正确的。47 事务的执行次序称为调度，调度用于确事务的执行次序称为调度，调度用于确定那些可以保证一致性的执行序列。定那些可以保证一致性的执行序列。 如果多个事务依次执行，则称为事务的串行如果多个事务依次执行，则称为事务的串行调度。调度。 利用分时方法同时处理多个事务，称为事务利用分时方法同时处理多个事务，称为事务的并发调度。的并发调度。48 例如：银行中转帐业务。

24、设事务例如：银行中转帐业务。设事务t1从帐号从帐号a转转帐帐100到帐号到帐号b，事务，事务t2从帐号从帐号a转帐转帐10的的存款余额到帐户存款余额到帐户b。这两个事务分别定义为：。这两个事务分别定义为：t1:read(a)a:=a-100write(a);read(b);b:=b+100;write(b)t2:read(a);temp:=a*0.1;a:=a-temp;write(a);read(b);b:=b+temp;write(b);49 假设假设a和和b的初值为的初值为2000和和1000。如果。如果两个事务串行调度。如先执行两个事务串行调度。如先执行t1再执行再执行t2，a和和b的

25、值修改为的值修改为1710和和1290。 若先执行若先执行t2再执行再执行t1，则，则a和和b的值修的值修改为改为1700和和1300。但。但ab的值保持不的值保持不变。变。50t1:read(a)a:=a-100write(a);read(b);b:=b+100;write(b)t2:read(a);temp:=a*0.1;a:=a-temp;write(a);read(b);b:=b+temp;write(b);串行调度1t2:read(a);temp:=a*0.1;a:=a-temp;write(a);read(b);b:=b+temp;write(b);t1：read(a)a:=a-1

26、00write(a);read(b);b:=b+100;write(b)串行调度251 若两个事务并发执行，则操作系统可以若两个事务并发执行，则操作系统可以选其中一个事务执行一段时间，然后切选其中一个事务执行一段时间，然后切换上下文，执行第二个事务一段时间。换上下文，执行第二个事务一段时间。如此轮换所有事务共享如此轮换所有事务共享cpu时间。时间。52t1:read(a)a:=a-100write(a);t2:read(a);temp:=a*0.1;a:=a-temp;write(a);read(b);b:=b+100;write(b)read(b);b:=b+temp;write(b);并发

27、调度1t1：read(a)a:=a-100t2:read(a);temp:=a*0.1;a:=a-temp;write(a);read(b);write(a)read(b);b:=b+100;write(b)b:=b+temp;write(b);并发调度253 并发调度并发调度1等价于串行调度等价于串行调度1，但是并发，但是并发调度调度2的结果的结果a值和值和b值分别为值分别为1900和和1200，该调度是错误的。，该调度是错误的。54 如果有如果有n个事务串行调度，则可以有个事务串行调度，则可以有n!种种不同的有效调度。不同的有效调度。555657585960 串行调度是正确的。串行调度是正

28、确的。 并发调度的执行结果等于串行调度，则并发调度的执行结果等于串行调度，则该调度才是正确的。该调度才是正确的。 可串行化是并发事务正确调度的准则可串行化是并发事务正确调度的准则61 若多个事务并发调度的结果与按某次顺若多个事务并发调度的结果与按某次顺序串行地执行这些事务时的结果相同，序串行地执行这些事务时的结果相同，称这种调度为称这种调度为可串行化调度！可串行化调度！62 对数据库一致性有影响的操作主要是对数据库一致性有影响的操作主要是read和和write语句。语句。可将事务抽象成只有可将事务抽象成只有read和和write语句，则上例中并发语句，则上例中并发调度可抽象为：调度可抽象为：t

29、1: t2:read(a) write(a) read(a) write(a)read(b)write(b) read(b) write(b)63 对于不同形式的等价调度，分别称为对于不同形式的等价调度，分别称为冲冲突可串行化突可串行化和视图可串行化。和视图可串行化。64 一个调度一个调度s，其中分别含有属于，其中分别含有属于ti和和tj的的两条连续指令两条连续指令ii和和ij。如果。如果ii和和ij对不同的对不同的数据项进行操作，则交换二者不会影响数据项进行操作，则交换二者不会影响调度中任何指令的结果。调度中任何指令的结果。 如果如果ii和和ij对相同的数据项对相同的数据项q进行操作，进行操

30、作，则要考虑两者的顺序。则要考虑两者的顺序。65由于只考虑由于只考虑read和和write指令，因此只考虑以指令，因此只考虑以下情形：下情形：1. iiread(q),ij=read(q). ii 与与ij的次序无关的次序无关2. iiread(q),ij=write(q)。若。若ii先于先于ij，则，则ti不不会读取会读取tj的指令写入的的指令写入的q值；但值；但ij先于先于ii，则，则ti读到由读到由tj的指令的指令ij写入的写入的q值，因此次序重要值，因此次序重要3. ii write (q),ij= read(q)，情形同，情形同24. ii write (q),ij= write(q

31、)，由于两条指令均，由于两条指令均为为write，指令的顺序对，指令的顺序对ti和和tj没有影响，然没有影响，然而，调度的下一条而，调度的下一条read指令的读取将受到影指令的读取将受到影响。响。66当当ii与与ij是不同事务在相同数据项上的操是不同事务在相同数据项上的操作时，并且其中至少有一个是作时，并且其中至少有一个是write语语句时，句时，ii与与ij是是冲突冲突的。例如：的。例如：1. iiread(q),ij=write(q)2. ii write (q),ij= read(q) 3. ii write (q),ij= write(q)否则是否则是不冲突不冲突的。的。若调度若调度s

32、中，有一对非冲突语句，则其顺序中，有一对非冲突语句，则其顺序可以交换，交换后产生的新调度和可以交换，交换后产生的新调度和s等价。等价。67t1: t2:read(a) write(a) read(a) write(a)read(b)write(b) read(b) write(b)68 在该例中，在该例中，t2的的write（a）指令与）指令与read（b）指令不冲突，因而可以交换这两条指令得到一指令不冲突，因而可以交换这两条指令得到一个等价的调度。如图个等价的调度。如图t1: t2:read(a) write(a) read(a)read(b) write(a)write(b) read(b

33、) write(b)69 若继续交换非冲突指令：若继续交换非冲突指令：交换交换t1的的read（b）与）与t2的的read(a)交换交换t1的的write（b）与）与t2的的write（a）交换交换t1的的write（b）与）与t2的的read（a） 则可以得到如图所示的调度则可以得到如图所示的调度70t1: t2:read(a) write(a) read(b)write(b)read(a) write(a) read(b) write(b) 该调度等价于一个串行调度该调度等价于一个串行调度71 若一个调度在保证冲突操作的次序不变若一个调度在保证冲突操作的次序不变的情况下，通过交换两个事务不

34、冲突操的情况下，通过交换两个事务不冲突操作的次序得到另一个串行调度，则称该作的次序得到另一个串行调度，则称该调度是调度是冲突可串行化的调度冲突可串行化的调度。7273 如果一个调度是冲突可串行化的调度，如果一个调度是冲突可串行化的调度，则一定是串行调度。冲突可串行化调度则一定是串行调度。冲突可串行化调度是可串行化调度的充分条件是可串行化调度的充分条件但是不满足冲突可串行化的调度，也有可能但是不满足冲突可串行化的调度，也有可能是可串行化调度。是可串行化调度。74 调度调度l1= w1(y)w1(x)w2(y)w2(x)w3(x) 调度调度l2= w1(y)w2(y)w2(x)w1(x)w3(x) 调度调度l2和和l1的结果是一样的，的结果是一样的，l2是可串行化是可串行化的，但是的，但是l2的结果不是非冲突可串行化的。的结果不是非冲突可串行化的。75 例如：该例中的调度不是冲突可串行化的。例如：该例中的调度不是冲突可串行化的。t3 t4read(q) write(q)write(q)该调度既不等价于串行调度该调度既不等价于串行调度,也不等价于也不等价于串行调度串行调度有时两个调度可以产生同样的结果，但不是冲突有时两个调度可以产生同样的结果，但不是冲突可串行化的。可串行化的。76 若保证该调度有效的话要依赖于事务的若保证该调度有效的话要依赖于事务的调度：调度： 或者该调度是一个