并发控制课件

7.5 并发控制并发控制第第第第7 7章章章章 数据库保护技术数据库保护技术数据库保护技术数据库保护技术1.403403教研室教研室 韦素媛韦素媛主要内容主要内容n nn数据库并发操作带来的数据不数据库并发操作带来的数据不数据库并发操作带来的数据不数据库并发操作带来的数据不一致问题一致问题一致问题一致问题n nn锁锁锁锁n nn锁协议锁协议锁协议锁协议n nn封锁带来的问题：活锁和死锁封锁带来的问题：活锁和死锁封锁带来的问题：活锁和死锁封锁带来的问题：活锁和死锁n nn并发操作的调度并发操作的调度并发操作的调度并发操作的调度2.403403教研室教研室 韦素媛韦素媛并发控制并发控制数据库是一个可以供多个用户共同使用的共享资数据库是一个可以供多个用户共同使用的共享资数据库是一个可以供多个用户共同使用的共享资数据库是一个可以供多个用户共同使用的共享资源。源。源。源。n n串行访问，每个时刻只能有一个用户应用程序对串行访问，每个时刻只能有一个用户应用程序对串行访问，每个时刻只能有一个用户应用程序对串行访问，每个时刻只能有一个用户应用程序对数据库进行存取，其它用户程序必须等待。数据库进行存取，其它用户程序必须等待。数据库进行存取，其它用户程序必须等待。数据库进行存取，其它用户程序必须等待。缺点：制约数据库访问效率的瓶颈，不利于数据缺点：制约数据库访问效率的瓶颈，不利于数据缺点：制约数据库访问效率的瓶颈，不利于数据缺点：制约数据库访问效率的瓶颈，不利于数据库资源的利用。库资源的利用。库资源的利用。库资源的利用。n n并行访问，通过并发控制机制允许多个用户并发并行访问，通过并发控制机制允许多个用户并发并行访问，通过并发控制机制允许多个用户并发并行访问，通过并发控制机制允许多个用户并发地访问数据库。地访问数据库。地访问数据库。地访问数据库。3.403403教研室教研室 韦素媛韦素媛并发控制并发控制当多个用户并发地访问数据库时就会产生多个事当多个用户并发地访问数据库时就会产生多个事当多个用户并发地访问数据库时就会产生多个事当多个用户并发地访问数据库时就会产生多个事务同时存取同一数据的情况。务同时存取同一数据的情况。务同时存取同一数据的情况。务同时存取同一数据的情况。若对并发操作不加以控制就会造成错误地存取数若对并发操作不加以控制就会造成错误地存取数若对并发操作不加以控制就会造成错误地存取数若对并发操作不加以控制就会造成错误地存取数据，破坏数据库的一致性。据，破坏数据库的一致性。据，破坏数据库的一致性。据，破坏数据库的一致性。数据库的并发控制机制是衡量数据库管理系统性数据库的并发控制机制是衡量数据库管理系统性数据库的并发控制机制是衡量数据库管理系统性数据库的并发控制机制是衡量数据库管理系统性能的重要技术标志。能的重要技术标志。能的重要技术标志。能的重要技术标志。4.403403教研室教研室 韦素媛韦素媛7.5.1 DB并发操作带来的数据不一致问题并发操作带来的数据不一致问题例例例例7.16 7.16 在一个飞机订票系统中，可能会出现的业务：在一个飞机订票系统中，可能会出现的业务：在一个飞机订票系统中，可能会出现的业务：在一个飞机订票系统中，可能会出现的业务：（1 1）甲售票点读航班）甲售票点读航班）甲售票点读航班）甲售票点读航班X X的机票余额数为的机票余额数为的机票余额数为的机票余额数为A=25A=25；（2 2）紧接着，乙售票点读同一航班）紧接着，乙售票点读同一航班）紧接着，乙售票点读同一航班）紧接着，乙售票点读同一航班X X的机票余额数的机票余额数的机票余额数的机票余额数A=25A=25；（3 3）甲售票点卖出一张机票，然后修改机票余额数）甲售票点卖出一张机票，然后修改机票余额数）甲售票点卖出一张机票，然后修改机票余额数）甲售票点卖出一张机票，然后修改机票余额数A=A-1A=A-1为为为为2424，并把，并把，并把，并把A A写回数据库；写回数据库；写回数据库；写回数据库；（4 4）乙售票点也卖出一张机票）乙售票点也卖出一张机票）乙售票点也卖出一张机票）乙售票点也卖出一张机票,同样接着修改机票余额同样接着修改机票余额同样接着修改机票余额同样接着修改机票余额数数数数A=A-1A=A-1为为为为2424，并把，并把，并把，并把A A写回数据库。写回数据库。写回数据库。写回数据库。设甲售票点对应于事务设甲售票点对应于事务设甲售票点对应于事务设甲售票点对应于事务T1T1，乙售票点对应于事务，乙售票点对应于事务，乙售票点对应于事务，乙售票点对应于事务T2T2，则上，则上，则上，则上述事务过程的描述如图述事务过程的描述如图述事务过程的描述如图述事务过程的描述如图 5.403403教研室教研室 韦素媛韦素媛时间时间时间时间T1T1T1T1T2T2T2T2DBDBDBDB中的中的中的中的A A A A值值值值t0t0t0t025252525t1t1t1t1read(A)read(A)read(A)read(A)t2t2t2t2read(A)read(A)read(A)read(A)t3t3t3t3A:=A-1A:=A-1A:=A-1A:=A-1t4t4t4t4write(A)write(A)write(A)write(A)t5t5t5t524242424t6t6t6t6A:=A-1A:=A-1A:=A-1A:=A-1t7t7t7t7write(A)write(A)write(A)write(A)t8t8t8t824242424丢失修改丢失修改丢失修改丢失修改（1）丢失修改）丢失修改6.403403教研室教研室 韦素媛韦素媛时间时间时间时间T1T1T1T1T2T2T2T2DBDBDBDB中的中的中的中的A A A A值值值值t0t0t0t025252525t1t1t1t1read(A)read(A)read(A)read(A)t2t2t2t2read(A)read(A)read(A)read(A)t3t3t3t3A:=A-10A:=A-10A:=A-10A:=A-10t4t4t4t4write(A)write(A)write(A)write(A)t5t5t5t515151515读过时数据读过时数据读过时数据读过时数据（2）读过时数据）读过时数据 7.403403教研室教研室 韦素媛韦素媛时间时间时间时间T1T1T1T1T2T2T2T2DBDBDBDB中的中的中的中的A A A A值值值值t0t0t0t025252525t1t1t1t1read(A)read(A)read(A)read(A)t2t2t2t2A:=A-10A:=A-10A:=A-10A:=A-10t3t3t3t3write(A)write(A)write(A)write(A)t4t4t4t4read(A)read(A)read(A)read(A)15151515t5t5t5t5ROLLBACKROLLBACKROLLBACKROLLBACKt6t6t6t625252525读读读读“脏脏脏脏”数据数据数据数据（3）读）读“脏脏”数据数据 8.403403教研室教研室 韦素媛韦素媛DB并发操作带来的三类数据不一致问题并发操作带来的三类数据不一致问题并发操作可能带来的数据不一致性情况有三种并发操作可能带来的数据不一致性情况有三种并发操作可能带来的数据不一致性情况有三种并发操作可能带来的数据不一致性情况有三种（1 1）丢失修改）丢失修改）丢失修改）丢失修改（2 2）读过时数据）读过时数据）读过时数据）读过时数据（3 3）读）读）读）读“脏脏脏脏”数据数据数据数据9.403403教研室教研室 韦素媛韦素媛产生原因：产生原因：产生原因：产生原因：并发操作破坏了事务的隔离性并发操作破坏了事务的隔离性并发操作破坏了事务的隔离性并发操作破坏了事务的隔离性并发控制并发控制并发控制并发控制就是要通过正确的调度方式，就是要通过正确的调度方式，就是要通过正确的调度方式，就是要通过正确的调度方式，使一个用户事务的执行不受其它事务的使一个用户事务的执行不受其它事务的使一个用户事务的执行不受其它事务的使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性。干扰，从而避免造成数据的不一致性。干扰，从而避免造成数据的不一致性。干扰，从而避免造成数据的不一致性。DB并发操作带来的三类数据不一致问题并发操作带来的三类数据不一致问题10.403403教研室教研室 韦素媛韦素媛7.5.2 锁锁定义定义定义定义锁是防止存取同一资源的用户之间出现不正确地锁是防止存取同一资源的用户之间出现不正确地锁是防止存取同一资源的用户之间出现不正确地锁是防止存取同一资源的用户之间出现不正确地修改数据或不正确地更改数据结构的一种机制。修改数据或不正确地更改数据结构的一种机制。修改数据或不正确地更改数据结构的一种机制。修改数据或不正确地更改数据结构的一种机制。基本的锁方式有二种：基本的锁方式有二种：基本的锁方式有二种：基本的锁方式有二种：n n排它锁排它锁排它锁排它锁(Exclusive Locks(Exclusive Locks，简记为，简记为，简记为，简记为X X锁锁锁锁)n n共享锁共享锁共享锁共享锁(Share Locks(Share Locks，简记为，简记为，简记为，简记为S S锁锁锁锁)11.403403教研室教研室 韦素媛韦素媛（1）排它锁）排它锁(X锁锁)当某个事务当某个事务当某个事务当某个事务T T为修改某个数据项为修改某个数据项为修改某个数据项为修改某个数据项A A且不允许其它事且不允许其它事且不允许其它事且不允许其它事务修改该数据项，或不允许其它事务对该数据项务修改该数据项，或不允许其它事务对该数据项务修改该数据项，或不允许其它事务对该数据项务修改该数据项，或不允许其它事务对该数据项加加加加S S锁时，则该事务可以对锁时，则该事务可以对锁时，则该事务可以对锁时，则该事务可以对A A加排它锁，排它锁加排它锁，排它锁加排它锁，排它锁加排它锁，排它锁又称为写锁。又称为写锁。又称为写锁。又称为写锁。本事务：读本事务：读本事务：读本事务：读A A，修改，修改，修改，修改A A其它事务：在其它事务：在其它事务：在其它事务：在T T释放释放释放释放A A上的上的上的上的X X锁之前不能读锁之前不能读锁之前不能读锁之前不能读A A和修改和修改和修改和修改A A12.403403教研室教研室 韦素媛韦素媛（2）共享锁）共享锁(S锁锁)当某个事务当某个事务当某个事务当某个事务T T希望阻止其它事务修改正为它读取的希望阻止其它事务修改正为它读取的希望阻止其它事务修改正为它读取的希望阻止其它事务修改正为它读取的某个数据项某个数据项某个数据项某个数据项A A时，则该事务可以对时，则该事务可以对时，则该事务可以对时，则该事务可以对A A加共享锁，加共享锁，加共享锁，加共享锁，共享锁又称为读锁。共享锁又称为读锁。共享锁又称为读锁。共享锁又称为读锁。本事务：读本事务：读本事务：读本事务：读A A，不能修改，不能修改，不能修改，不能修改A A 其它事务：加其它事务：加其它事务：加其它事务：加S S锁读锁读锁读锁读A A，在，在，在，在T T释放释放释放释放A A上上上上S S锁之前不能锁之前不能锁之前不能锁之前不能修改修改修改修改A A13.403403教研室教研室 韦素媛韦素媛S SX X-S S X X S锁和锁和X锁的共存相容矩阵锁的共存相容矩阵14.403403教研室教研室 韦素媛韦素媛7.5.3 锁协议锁协议当一个事务当一个事务当一个事务当一个事务T T要对某个项加锁时，还必须遵守某种要对某个项加锁时，还必须遵守某种要对某个项加锁时，还必须遵守某种要对某个项加锁时，还必须遵守某种规则，比如在什么条件下可以申请规则，比如在什么条件下可以申请规则，比如在什么条件下可以申请规则，比如在什么条件下可以申请S S锁或锁或锁或锁或X X锁，锁，锁，锁，持锁时间如何确定、何时释放锁等。一般称这些持锁时间如何确定、何时释放锁等。一般称这些持锁时间如何确定、何时释放锁等。一般称这些持锁时间如何确定、何时释放锁等。一般称这些规则为锁协议（规则为锁协议（规则为锁协议（规则为锁协议（Locking ProtocolLocking Protocol）。）。）。）。对加锁方式规定不同的规则，就形成了不同的锁对加锁方式规定不同的规则，就形成了不同的锁对加锁方式规定不同的规则，就形成了不同的锁对加锁方式规定不同的规则，就形成了不同的锁协议。协议。协议。协议。不正确的并发操作可能带来的丢失修改、读过时不正确的并发操作可能带来的丢失修改、读过时不正确的并发操作可能带来的丢失修改、读过时不正确的并发操作可能带来的丢失修改、读过时数据和读数据和读数据和读数据和读“脏脏脏脏”数据等不一致性问题，三级锁协议数据等不一致性问题，三级锁协议数据等不一致性问题，三级锁协议数据等不一致性问题，三级锁协议在不同程度上可以解决这些问题。在不同程度上可以解决这些问题。在不同程度上可以解决这些问题。在不同程度上可以解决这些问题。15.403403教研室教研室 韦素媛韦素媛（1）一级锁协议）一级锁协议事务事务事务事务T T在修改数据在修改数据在修改数据在修改数据R R之前必须先对数据之前必须先对数据之前必须先对数据之前必须先对数据R R所在的项所在的项所在的项所在的项申请加申请加申请加申请加X X锁，在获得了锁，在获得了锁，在获得了锁，在获得了X X加锁后，直到该事务加锁后，直到该事务加锁后，直到该事务加锁后，直到该事务T T结结结结束时才释放所加的束时才释放所加的束时才释放所加的束时才释放所加的X X锁。锁。锁。锁。如果未获准加如果未获准加如果未获准加如果未获准加X X锁，则该事务锁，则该事务锁，则该事务锁，则该事务T T进入等待状态，直进入等待状态，直进入等待状态，直进入等待状态，直到获准到获准到获准到获准X X加锁后该事务才继续执行。加锁后该事务才继续执行。加锁后该事务才继续执行。加锁后该事务才继续执行。16.403403教研室教研室 韦素媛韦素媛事务事务事务事务事务事务T T T T T T要修要修要修要修要修要修改数据改数据改数据改数据改数据改数据R R R R R R：申请加申请加申请加申请加X X锁？锁？锁？锁？等待等待等待等待加加加加X X锁锁锁锁Y Y YN NNT T结束结束结束结束释放释放释放释放X X锁锁锁锁（1）一级锁协议）一级锁协议 本事务：读本事务：读本事务：读本事务：读R R，修改，修改，修改，修改R R；用；用；用；用COMMITCOMMIT和和和和ROLLBACKROLLBACK释放释放释放释放X X锁锁锁锁 其它事务：在其它事务：在其它事务：在其它事务：在T T结束前不能读结束前不能读结束前不能读结束前不能读R R，也不能修改，也不能修改，也不能修改，也不能修改R R 作用：防止丢失修改作用：防止丢失修改作用：防止丢失修改作用：防止丢失修改17.403403教研室教研室 韦素媛韦素媛（2）二级锁协议）二级锁协议二级锁协议除包括一级锁协议的内容外，还包括二级锁协议除包括一级锁协议的内容外，还包括二级锁协议除包括一级锁协议的内容外，还包括二级锁协议除包括一级锁协议的内容外，还包括如下规则：如下规则：如下规则：如下规则：事务事务事务事务T T在读数据在读数据在读数据在读数据R R之前必须先对数据之前必须先对数据之前必须先对数据之前必须先对数据R R所在的项申所在的项申所在的项申所在的项申请加请加请加请加S S锁，在获得了锁，在获得了锁，在获得了锁，在获得了S S加锁后，读完数据加锁后，读完数据加锁后，读完数据加锁后，读完数据R R后即可后即可后即可后即可释放所加的释放所加的释放所加的释放所加的S S锁。锁。锁。锁。如果未获准加如果未获准加如果未获准加如果未获准加S S锁，则该事务锁，则该事务锁，则该事务锁，则该事务T T进入等待状态，直进入等待状态，直进入等待状态，直进入等待状态，直到获准到获准到获准到获准S S加锁后该事务才继续执行。加锁后该事务才继续执行。加锁后该事务才继续执行。加锁后该事务才继续执行。18.403403教研室教研室 韦素媛韦素媛事务事务事务事务事务事务T T T T T T要读要读要读要读要读要读数据数据数据数据数据数据R R R R R R：申请加申请加申请加申请加S S锁？锁？锁？锁？等待等待等待等待加加加加S S锁锁锁锁读数据读数据读数据读数据Y Y YN NN释放释放释放释放S S锁锁锁锁（2）二级锁协议）二级锁协议一级锁协议一级锁协议一级锁协议一级锁协议 本事务：读本事务：读本事务：读本事务：读R R，不能修改，不能修改，不能修改，不能修改R R；用；用；用；用UNLOCK UNLOCK 释放释放释放释放S S锁锁锁锁(不需不需不需不需 等等等等T T结束结束结束结束)其它事务：可加其它事务：可加其它事务：可加其它事务：可加S S锁读锁读锁读锁读R R，不能修改，不能修改，不能修改，不能修改R R 作用：防止丢失修改，防止读作用：防止丢失修改，防止读作用：防止丢失修改，防止读作用：防止丢失修改，防止读“脏脏脏脏”数据数据数据数据19.403403教研室教研室 韦素媛韦素媛（3）三级锁协议）三级锁协议三级锁协议除包括一级锁协议的内容外，还包括三级锁协议除包括一级锁协议的内容外，还包括三级锁协议除包括一级锁协议的内容外，还包括三级锁协议除包括一级锁协议的内容外，还包括如下规则如下规则如下规则如下规则 ：事务事务事务事务T T在读数据在读数据在读数据在读数据R R之前必须先对数据之前必须先对数据之前必须先对数据之前必须先对数据R R所在的项申所在的项申所在的项申所在的项申请加请加请加请加S S锁，在获得了锁，在获得了锁，在获得了锁，在获得了S S加锁后，直到该事务加锁后，直到该事务加锁后，直到该事务加锁后，直到该事务T T结束结束结束结束时才释放所加的时才释放所加的时才释放所加的时才释放所加的S S锁。锁。锁。锁。如果未获准加如果未获准加如果未获准加如果未获准加S S锁，则该事务锁，则该事务锁，则该事务锁，则该事务T T进入等待状态，直进入等待状态，直进入等待状态，直进入等待状态，直到获准到获准到获准到获准S S加锁后该事务才继续执行加锁后该事务才继续执行加锁后该事务才继续执行加锁后该事务才继续执行 。20.403403教研室教研室 韦素媛韦素媛事务事务事务事务T T T T要读要读要读要读数据数据数据数据R R R R：申请加申请加申请加申请加S S锁？锁？锁？锁？等待等待等待等待加加加加S S锁锁锁锁读数据读数据读数据读数据Y YN NT T结束结束结束结束释放释放释放释放S S锁锁锁锁（3）三级锁协议）三级锁协议一级锁协议一级锁协议一级锁协议一级锁协议 本事务：读本事务：读本事务：读本事务：读R R，不能修改，不能修改，不能修改，不能修改R R；用；用；用；用COMMITCOMMIT和和和和ROLLBACKROLLBACK释放其它事务：可加释放其它事务：可加释放其它事务：可加释放其它事务：可加S S锁读锁读锁读锁读R R，不能修改，不能修改，不能修改，不能修改R R 作用：防止丢失修改，防止读作用：防止丢失修改，防止读作用：防止丢失修改，防止读作用：防止丢失修改，防止读“脏脏脏脏”数据，防止读过时数据，防止读过时数据，防止读过时数据，防止读过时数据数据数据数据21.403403教研室教研室 韦素媛韦素媛7.5.4 封锁带来的问题（封锁带来的问题（1）活锁）活锁如果事务如果事务如果事务如果事务T1T1封锁了数据封锁了数据封锁了数据封锁了数据R R，事务，事务，事务，事务T2T2又请求封锁又请求封锁又请求封锁又请求封锁R R，于是于是于是于是T2T2等待，等待，等待，等待，T3T3也请求封锁也请求封锁也请求封锁也请求封锁R R，当，当，当，当T1T1释放了释放了释放了释放了R R上的封锁之后，系统首先批准了上的封锁之后，系统首先批准了上的封锁之后，系统首先批准了上的封锁之后，系统首先批准了T3T3的请求，的请求，的请求，的请求，T2T2仍然等待，然后仍然等待，然后仍然等待，然后仍然等待，然后T4T4又请求封锁又请求封锁又请求封锁又请求封锁R R，当，当，当，当T3T3释放了释放了释放了释放了R R上的封锁之后，系统又批准了上的封锁之后，系统又批准了上的封锁之后，系统又批准了上的封锁之后，系统又批准了T4T4的请求，的请求，的请求，的请求，T2T2继继继继续等待，续等待，续等待，续等待，如此下去，如此下去，如此下去，如此下去，T2T2有可能永远等待。有可能永远等待。有可能永远等待。有可能永远等待。这种可能存在某个事务永远处于等待状态、得不这种可能存在某个事务永远处于等待状态、得不这种可能存在某个事务永远处于等待状态、得不这种可能存在某个事务永远处于等待状态、得不到封锁的机会的现象，称为活锁。到封锁的机会的现象，称为活锁。到封锁的机会的现象，称为活锁。到封锁的机会的现象，称为活锁。解决方法：先来者先执行。解决方法：先来者先执行。解决方法：先来者先执行。解决方法：先来者先执行。22.403403教研室教研室 韦素媛韦素媛T1T2（2）死锁）死锁两个或两个以上的事务都处于等待状态，每个事两个或两个以上的事务都处于等待状态，每个事两个或两个以上的事务都处于等待状态，每个事两个或两个以上的事务都处于等待状态，每个事务都在等待其中另一个事务解除封锁，它才能继务都在等待其中另一个事务解除封锁，它才能继务都在等待其中另一个事务解除封锁，它才能继务都在等待其中另一个事务解除封锁，它才能继续执行下去，结果任何一个事务都无法继续执行续执行下去，结果任何一个事务都无法继续执行续执行下去，结果任何一个事务都无法继续执行续执行下去，结果任何一个事务都无法继续执行，这种现象称为死锁。，这种现象称为死锁。，这种现象称为死锁。，这种现象称为死锁。23.403403教研室教研室 韦素媛韦素媛（3）死锁的预防（）死锁的预防（OS）一次加锁法一次加锁法一次加锁法一次加锁法要求每个事务必须对所有要使用的数据项一次性要求每个事务必须对所有要使用的数据项一次性要求每个事务必须对所有要使用的数据项一次性要求每个事务必须对所有要使用的数据项一次性地全部加锁，否则就不能继续执行。地全部加锁，否则就不能继续执行。地全部加锁，否则就不能继续执行。地全部加锁，否则就不能继续执行。缺点：扩大了锁的范围，降低了系统的并发度。缺点：扩大了锁的范围，降低了系统的并发度。缺点：扩大了锁的范围，降低了系统的并发度。缺点：扩大了锁的范围，降低了系统的并发度。24.403403教研室教研室 韦素媛韦素媛（3）死锁的预防（）死锁的预防（OS）顺序加锁法顺序加锁法顺序加锁法顺序加锁法预先对数据项规定一个加锁顺序，所有事务都按预先对数据项规定一个加锁顺序，所有事务都按预先对数据项规定一个加锁顺序，所有事务都按预先对数据项规定一个加锁顺序，所有事务都按这个顺序进行加锁。这个顺序进行加锁。这个顺序进行加锁。这个顺序进行加锁。缺点：很难按规定的顺序进行加锁。缺点：很难按规定的顺序进行加锁。缺点：很难按规定的顺序进行加锁。缺点：很难按规定的顺序进行加锁。25.403403教研室教研室 韦素媛韦素媛（4）死锁的检测与解除）死锁的检测与解除1 1）超时法）超时法）超时法）超时法如果一个事务的等待时间超过了规定的时限，就如果一个事务的等待时间超过了规定的时限，就如果一个事务的等待时间超过了规定的时限，就如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。认为发生了死锁。认为发生了死锁。认为发生了死锁。优点：实现简单优点：实现简单优点：实现简单优点：实现简单缺点：缺点：缺点：缺点：n n有可能误判死锁有可能误判死锁有可能误判死锁有可能误判死锁n n若时限设置的太长，可能出现死锁发生后不能及若时限设置的太长，可能出现死锁发生后不能及若时限设置的太长，可能出现死锁发生后不能及若时限设置的太长，可能出现死锁发生后不能及时发现的情况。时发现的情况。时发现的情况。时发现的情况。26.403403教研室教研室 韦素媛韦素媛（4）死锁的检测与解除）死锁的检测与解除2 2）有向等待图法）有向等待图法）有向等待图法）有向等待图法检测死锁检测死锁检测死锁检测死锁n n画一个表示事务等待关系的有向等待图画一个表示事务等待关系的有向等待图画一个表示事务等待关系的有向等待图画一个表示事务等待关系的有向等待图G=(VG=(V，E)E)。V V为结点集合，结点表示一个正在运行的事为结点集合，结点表示一个正在运行的事为结点集合，结点表示一个正在运行的事为结点集合，结点表示一个正在运行的事务；务；务；务；E E为有向边集合，有向边表示事务的等待关为有向边集合，有向边表示事务的等待关为有向边集合，有向边表示事务的等待关为有向边集合，有向边表示事务的等待关系。系。系。系。n n若若若若T1T1正在等待给被正在等待给被正在等待给被正在等待给被T2T2锁住的数据项加锁，则在锁住的数据项加锁，则在锁住的数据项加锁，则在锁住的数据项加锁，则在T1T1和和和和T2T2之间划一条有向边，方向是之间划一条有向边，方向是之间划一条有向边，方向是之间划一条有向边，方向是T1T1指向指向指向指向T2T2。事务的有向等待图动态地反映了所有事务的等待事务的有向等待图动态地反映了所有事务的等待事务的有向等待图动态地反映了所有事务的等待事务的有向等待图动态地反映了所有事务的等待情况。情况。情况。情况。27.403403教研室教研室 韦素媛韦素媛（4）死锁的检测与解除）死锁的检测与解除n n有向等待图中的每个回路意味着死锁的存在；如有向等待图中的每个回路意味着死锁的存在；如有向等待图中的每个回路意味着死锁的存在；如有向等待图中的每个回路意味着死锁的存在；如果无任何回路，则表示无死锁产生。果无任何回路，则表示无死锁产生。果无任何回路，则表示无死锁产生。果无任何回路，则表示无死锁产生。n n并发控制子系统周期性地（比如每隔并发控制子系统周期性地（比如每隔并发控制子系统周期性地（比如每隔并发控制子系统周期性地（比如每隔0.50.5分钟）分钟）分钟）分钟）检测事务的有向等待图，如果发现有向等待图中检测事务的有向等待图，如果发现有向等待图中检测事务的有向等待图，如果发现有向等待图中检测事务的有向等待图，如果发现有向等待图中存在回路，就表示系统中出现了死锁。存在回路，就表示系统中出现了死锁。存在回路，就表示系统中出现了死锁。存在回路，就表示系统中出现了死锁。28.403403教研室教研室 韦素媛韦素媛（4）死锁的检测与解除）死锁的检测与解除2 2）有向等待图法）有向等待图法）有向等待图法）有向等待图法检测死锁检测死锁检测死锁检测死锁解除死锁解除死锁解除死锁解除死锁选择一个处理死锁代价最小的事务，将其撤消，选择一个处理死锁代价最小的事务，将其撤消，选择一个处理死锁代价最小的事务，将其撤消，选择一个处理死锁代价最小的事务，将其撤消，释放它持有的所有锁。释放它持有的所有锁。释放它持有的所有锁。释放它持有的所有锁。29.403403教研室教研室 韦素媛韦素媛7.5.5 并发调度的可串行性并发调度的可串行性通常情况下，如果一个事务在执行过程中没有与通常情况下，如果一个事务在执行过程中没有与通常情况下，如果一个事务在执行过程中没有与通常情况下，如果一个事务在执行过程中没有与其它事务并发运行，也就是说该事务的执行没有其它事务并发运行，也就是说该事务的执行没有其它事务并发运行，也就是说该事务的执行没有其它事务并发运行，也就是说该事务的执行没有受到其它事务干扰时，就认为该事务的运行结果受到其它事务干扰时，就认为该事务的运行结果受到其它事务干扰时，就认为该事务的运行结果受到其它事务干扰时，就认为该事务的运行结果是正常的或者是预想的。是正常的或者是预想的。是正常的或者是预想的。是正常的或者是预想的。也就是说，当多个事务串行执行时，各事务的运也就是说，当多个事务串行执行时，各事务的运也就是说，当多个事务串行执行时，各事务的运也就是说，当多个事务串行执行时，各事务的运行结果一定是正确的。行结果一定是正确的。行结果一定是正确的。行结果一定是正确的。因此，仅当几个事务的并发运行结果与这些事务因此，仅当几个事务的并发运行结果与这些事务因此，仅当几个事务的并发运行结果与这些事务因此，仅当几个事务的并发运行结果与这些事务按某一次序串行运行的结果相同时，这样的并发按某一次序串行运行的结果相同时，这样的并发按某一次序串行运行的结果相同时，这样的并发按某一次序串行运行的结果相同时，这样的并发操作才是正确的。操作才是正确的。操作才是正确的。操作才是正确的。30.403403教研室教研室 韦素媛韦素媛7.5.5 并发调度的可串行性并发调度的可串行性通常把按某一执行次序安排的事务执行的步骤称通常把按某一执行次序安排的事务执行的步骤称通常把按某一执行次序安排的事务执行的步骤称通常把按某一执行次序安排的事务执行的步骤称为调度为调度为调度为调度(Schedule)(Schedule)。多个事务的并发执行是正确的，当且仅当其结果多个事务的并发执行是正确的，当且仅当其结果多个事务的并发执行是正确的，当且仅当其结果多个事务的并发执行是正确的，当且仅当其结果与按某一顺序串行地执行它们时的结果相同。称与按某一顺序串行地执行它们时的结果相同。称与按某一顺序串行地执行它们时的结果相同。称与按某一顺序串行地执行它们时的结果相同。称这种调度称为可串行化（这种调度称为可串行化（这种调度称为可串行化（这种调度称为可串行化（SerializableSerializable）调度。）调度。）调度。）调度。可串行性（可串行性（可串行性（可串行性（SerializabilitySerializability）是并发事务正确性的）是并发事务正确性的）是并发事务正确性的）是并发事务正确性的判别准则。按照这个准则的规定，一个给定的并判别准则。按照这个准则的规定，一个给定的并判别准则。按照这个准则的规定，一个给定的并判别准则。按照这个准则的规定，一个给定的并发调度，当且仅当它可串行化时，才认为是正确发调度，当且仅当它可串行化时，才认为是正确发调度，当且仅当它可串行化时，才认为是正确发调度，当且仅当它可串行化时，才认为是正确的调度。的调度。的调度。的调度。31.403403教研室教研室 韦素媛韦素媛7.5.5 并发调度的可串行性并发调度的可串行性示例示例示例示例事务事务事务事务T1T1：从账号：从账号：从账号：从账号A A将数量为将数量为将数量为将数量为100100的款项转到账号的款项转到账号的款项转到账号的款项转到账号B B；事务事务事务事务T2T2：从账号：从账号：从账号：从账号B B将将将将2020的款项转到账号的款项转到账号的款项转到账号的款项转到账号C C。假设假设假设假设A A、B B和和和和C C的初值分别为的初值分别为的初值分别为的初值分别为600600、300300和和和和100100。32.403403教研室教研室 韦素媛韦素媛(a)(a)(a)(a)(b)(b)(b)(b)T2T2T2T2Read(A)Read(A)Read(A)Read(A)A:=A-100A:=A-100A:=A-100A:=A-100Write(A)Write(A)Write(A)Write(A)Read(B)Read(B)Read(B)Read(B)B:=B+100B:=B+100B:=B+100B:=B+100Write(B)Write(B)Write(B)Write(B)Read(B)Read(B)Read(B)Read(B)Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2B:=B-tempB:=B-tempB:=B-tempB:=B-tempWrite(B)Write(B)Write(B)Write(B)Read(C)Read(C)Read(C)Read(C)C:=C+tempC:=C+tempC:=C+tempC:=C+tempWrite(C)Write(C)Write(C)Write(C)Read(B)Read(B)Read(B)Read(B)Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2B:=B-tempB:=B-tempB:=B-tempB:=B-tempWrite(B)Write(B)Write(B)Write(B)Read(C)Read(C)Read(C)Read(C)C:=C+tempC:=C+tempC:=C+tempC:=C+tempWrite(C)Write(C)Write(C)Write(C)Read(A)Read(A)Read(A)Read(A)A:=A-100A:=A-100A:=A-100A:=A-100Write(A)Write(A)Write(A)Write(A)Read(B)Read(B)Read(B)Read(B)B:=B+100B:=B+100B:=B+100B:=B+100Write(B)Write(B)Write(B)Write(B)T2T2T2T2T1T1T1T1T1T1T1T1正确的并发调度正确的并发调度 33.403403教研室教研室 韦素媛韦素媛T1T1T1T1T2T2T2T2T1T1T1T1T2T2T2T2Read(A)Read(A)Read(A)Read(A)A:=A-100A:=A-100A:=A-100A:=A-100Write(A)Write(A)Write(A)Write(A)Read(B)Read(B)Read(B)Read(B)Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2B:=B-tempB:=B-tempB:=B-tempB:=B-tempWrite(B)Write(B)Write(B)Write(B)Read(B)Read(B)Read(B)Read(B)B:=B+100B:=B+100B:=B+100B:=B+100Write(B)Write(B)Write(B)Write(B)Read(C)Read(C)Read(C)Read(C)C:=C+tempC:=C+tempC:=C+tempC:=C+tempWrite(C)Write(C)Write(C)Write(C)Read(A)Read(A)Read(A)Read(A)A:=A-100A:=A-100A:=A-100A:=A-100Write(A)Write(A)Write(A)Write(A)Read(B)Read(B)Read(B)Read(B)B:=B+100B:=B+100B:=B+100B:=B+100Write(B)Write(B)Write(B)Write(B)Read(B)Read(B)Read(B)Read(B)Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2Temp:=B*0.2B:=B-tempB:=B-tempB:=B-tempB:=B-tempWrite(B)Write(B)Write(B)Write(B)Read(C)Read(C)Read(C)Read(C)C:=C+tempC:=C+tempC:=C+tempC:=C+tempWrite(C)Write(C)Write(C)Write(C)(c)(c)(c)(c)(d)(d)(d)(d)正确的正确的.vs.错误的并发调度错误的并发调度 34.403403教研室教研室 韦素媛韦素媛7.5.6 两段锁协议两段锁协议DBMSDBMS普遍采用加锁方法实现并发操作调度的可串普遍采用加锁方法实现并发操作调度的可串普遍采用加锁方法实现并发操作调度的可串普遍采用加锁方法实现并发操作调度的可串行性，从而保证调度的正确性。行性，从而保证调度的正确性。行性，从而保证调度的正确性。行性，从而保证调度的正确性。两段锁（两段锁（两段锁（两段锁（Two-Phase LockingTwo-Phase Locking，简称，简称，简称，简称2PL2PL）协议）协议）协议）协议就是保证并发调度可串行性的锁协议。就是保证并发调度可串行性的锁协议。就是保证并发调度可串行性的锁协议。就是保证并发调度可串行性的锁协议。规则规则规则规则在每一个事务中，所有的加锁语句都在解锁语句在每一个事务中，所有的加锁语句都在解锁语句在每一个事务中，所有的加锁语句都在解锁语句在每一个事务中，所有的加锁语句都在解锁语句之前。之前。之前。之前。35.403403教研室教研室 韦素媛韦素媛7.5.6 两段锁协议两段锁协议n n加锁段（扩展阶段）：事务可以申请获得任何数加锁段（扩展阶段）：事务可以申请获得任何数加锁段（扩展阶段）：事务可以申请获得任何数加锁段（扩展阶段）：事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。据项上的任何类型的锁，但是不能释放任何锁。据项上的任何类型的锁，但是不能释放任何锁。据项上的任何类型的锁，但是不能释放任何锁。n n解锁段（收缩阶段）：事务可以释放任何数据项解锁段（收缩阶段）：事务可以释放任何数据项解锁段（收缩阶段）：事务可以释放任何数据项解锁段（收缩阶段）：事务可以释放任何数据项上的任何类型的琐，但是不能再申请任何琐。上的任何类型的琐，但是不能再申请任何琐。上的任何类型的琐，但是不能再申请任何琐。上的任何类型的琐，但是不能再申请任何琐。36.403403教研室教研室 韦素媛韦素媛7.5.6 两段锁协议两段锁协议两段锁协议和可串行化调度两段锁协议和可串行化调度两段锁协议和可串行化调度两段锁协议和可串行化调度若并发执行的所有事务均遵守两段锁协议，则对若并发执行的所有事务均遵守两段锁协议，则对若并发执行的所有事务均遵守两段锁协议，则对若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的这些事务的任何并发调度策略都是可串行化的这些事务的任何并发调度策略都是可串行化的这些事务的任何并发调度策略都是可串行化的（充分条件，不是必要条件）（充分条件，不是必要条件）（充分条件，不是必要条件）（充分条件，不是必要条件）两段锁协议和一次加锁法两段锁协议和一次加锁法两段锁协议和一次加锁法两段锁协议和一次加锁法一次加锁法遵守两段锁协议；一次加锁法遵守两段锁协议；一次加锁法遵守两段锁协议；一次加锁法遵守两段锁协议；遵守两段锁协议的事务并不遵守一次加锁法。遵守两段锁协议的事务并不遵守一次加锁法。遵守两段锁协议的事务并不遵守一次加锁法。遵守两段锁协议的事务并不遵守一次加锁法。37.个人观点供参考，欢迎讨论！