事务的并发控制

《事务的并发控制》由会员分享，可在线阅读，更多相关《事务的并发控制（17页珍藏版）》请在金锄头文库上搜索。

1、第 9 章 事务的并发控制 第 9 章 事务的并发控制 主要内容：单服务器中的并发问题，包括，事务、严格两段锁协议及其实现、锁协议的修改、乐观并发控制中的事务验证、时间戳定序方法主要内容：单服务器中的并发问题，包括，事务、严格两段锁协议及其实现、锁协议的修改、乐观并发控制中的事务验证、时间戳定序方法 学时：学时：45*5 重点：两段锁协议、时间戳定序方法重点：两段锁协议、时间戳定序方法 难点：事务验证及时间戳定序方法的理解难点：事务验证及时间戳定序方法的理解 9-1 概述 9-1 概述 事务（事务（Transaction）是一个操作系列，含在该系列中的操作要么都被完成，要么都未被完成。）是一个

2、操作系列，含在该系列中的操作要么都被完成，要么都未被完成。 例如，事务例如，事务T1: 取款取款(A,4),存款（存款（B,4） 事务事务T2: 取款取款(B,3),存款（存款（C,3） 为了保证正确的存取款，系统必须做到：当一个事务没有完成对一个数据项的使用之前，系统不允许其它事务使用，以保证事务对数据操作的原子性。为了保证正确的存取款，系统必须做到：当一个事务没有完成对一个数据项的使用之前，系统不允许其它事务使用，以保证事务对数据操作的原子性。 保证“原子性”的方法是对数据项加锁，被锁数据只允许加锁者操作。从而保证此数据被一系列事务“依次地”访问串行访问。 但是， 为了提高系统效率， 我们

3、希望系统能够并发执行。因此， 可要求其仅仅对共享数据执行串行操作。 这就是所谓的 “并行调度的串行化”的基本思想：事务并发执行，但是对共享数据保证“原子性”的方法是对数据项加锁，被锁数据只允许加锁者操作。从而保证此数据被一系列事务“依次地”访问串行访问。 但是， 为了提高系统效率， 我们希望系统能够并发执行。因此， 可要求其仅仅对共享数据执行串行操作。 这就是所谓的 “并行调度的串行化”的基本思想：事务并发执行，但是对共享数据1的操作是串行的。的操作是串行的。 另一个问题是锁的粒度，粒度过大，影响并发性；粒度过小，系统用于锁的开销过大。因此，需要两方面的平衡。另一个问题是锁的粒度，粒度过大，影

4、响并发性；粒度过小，系统用于锁的开销过大。因此，需要两方面的平衡。 我们要对引起冲突的操作进行控制，读操作和读操作是不冲突的， 只有读和写、 写和写才会发生冲突， 这是我们需要考虑的。我们要对引起冲突的操作进行控制，读操作和读操作是不冲突的， 只有读和写、 写和写才会发生冲突， 这是我们需要考虑的。 9-2 锁机制 9-2 锁机制 假设假设T1 ，T2为事务，为事务，D为数据对象为数据对象 一、 读锁和写锁一、 读锁和写锁 T1读读D的时候，的时候，T2不可以写不可以写D，但可以读，但可以读D； T1写写D的时候，的时候，T2既不可以写既不可以写D，又不可以读，又不可以读D。 按照此分析，一个

5、事务可以对按照此分析，一个事务可以对 D 实施读锁和写锁：实施读锁和写锁： 不同的事务可以因读而同时封锁同一个不同的事务可以因读而同时封锁同一个 D，所以，读锁又叫共享锁（，所以，读锁又叫共享锁（Sharing Lock） ；） ； 不同的事务不能因写而同时封锁同一个不同的事务不能因写而同时封锁同一个 D，所以，写锁又叫排它锁（，所以，写锁又叫排它锁（Exclusive Lock） ；） ； 根据上述分析，我们可得如下锁协议：根据上述分析，我们可得如下锁协议： 1、T ReadLock(D)，T 也可以也可以 ReadLock(D)，如果，如果 T WriteLock(D)，则，则 T 被挂起

6、，直到被挂起，直到 T UNLock（D） ；） ； 2、 T WriteLock(D)， 如果， 如果 T ReadLock(D)或者或者 WriteLock(D)，则，则 T 被挂起，直到被挂起，直到 T UNLock（D） ；） ； 3、T 使用完使用完 D 之后，之后，UNLock(D)。 2问题：因为事务可能被终止，该方法不能保证可串行化；可能产生死锁。问题：因为事务可能被终止，该方法不能保证可串行化；可能产生死锁。 二、 两段协议二、 两段协议 所谓两段锁协议，是为了保证并发调度的可串行化，要求所谓两段锁协议，是为了保证并发调度的可串行化，要求 T在执行过程中，有一个时间点在执行过

7、程中，有一个时间点 t，在，在 t 之前，之前，T 不执行不执行 UNLock操作，并且在操作，并且在 t 之后，之后，T 不再执行不再执行 ReadLock(D)和和 WriteLock(D)操作。操作。 所以，两段锁协议如下：所以，两段锁协议如下： 1、T ReadLock(D)，T 也可以也可以 ReadLock(D)，如果，如果 T WriteLock(D)，则，则 T 被挂起，直到被挂起，直到 T UNLock（D） ；） ； 2、 T WriteLock(D)， 如果， 如果 T ReadLock(D)或者或者 WriteLock(D)，则，则 T 被挂起，直到被挂起，直到 T U

8、NLock（D） ；） ； 3、 一旦、 一旦 T 执行执行 UNLock 操作， 它就不可再申请对其他资源的封锁。操作， 它就不可再申请对其他资源的封锁。 事实上，在严格的两段锁协议下，事实上，在严格的两段锁协议下，T 只用执行封锁操作，只用执行封锁操作，UNLock操作仅在操作仅在T提交的时候或者被中止的时候由服务器一并执行。提交的时候或者被中止的时候由服务器一并执行。 如果按照两段锁协议执行，则相应的并发调度是可串行化的。如果按照两段锁协议执行，则相应的并发调度是可串行化的。 两段锁协议解决不了死锁问题。两段锁协议解决不了死锁问题。 3三、 锁的实现三、 锁的实现 主要数据结构：主要数据

9、结构： LOCKLIST：Data_Item数据项名字数据项名字 TRANS_ID获得此数据项的事务集合获得此数据项的事务集合 LOCK_TYPERead / Write Lock(Trans, DataItem, LockType) Item=LOCKLIST.DataItem; IF Item= THEN 在在 LOCKLIST 设置一项纪录设置一项纪录(DataItem, Trans, LockType) ELSEIF Item.LOCK_TYPE=Write或或LockType=Write THEN 挂起挂起 Trans ELSE Item.TRANS_ID=Item.TRANS_ID

10、Trans UnLock(Trans) FOR ItemLOCKLIST DO IF Item.TRANS_ID=Trans THEN 删除此删除此 Item ELSEIF TransItem.TRANS_ID THEN 将将 Trans 从其中删除从其中删除 ELSE 报告无此报告无此 Trans 4四、 锁的改进四、 锁的改进 希望在一个事务写一个数据的期间， 其它的事务仍然可以读此数据项（的原值） 。希望在一个事务写一个数据的期间， 其它的事务仍然可以读此数据项（的原值） 。 （一） 两版本协议（一） 两版本协议 基本思想：数据项基本思想：数据项 D 有两个版本：提交版和试用版。提交版用

11、于读出，试用版供拥有者写。有两个版本：提交版和试用版。提交版用于读出，试用版供拥有者写。D 仅在被提交时不允许读。从而可以提高系统的并发度。仅在被提交时不允许读。从而可以提高系统的并发度。 1、 T 申请读申请读 D：如果：如果 D 有提交锁，则挂起；否则有提交锁，则挂起；否则 T 对对D 加读锁；加读锁； 2、 T 申请写申请写 D：如果：如果 D 有写锁或者提交锁，则挂起；否则有写锁或者提交锁，则挂起；否则 T 对对 D 加写锁； （此时加写锁； （此时 T 拥有拥有 D 的一个试用版）的一个试用版） 3、 T 提交：服务器将提交：服务器将 T 拥有的所有写锁改为提交锁，如果一个拥有的所有

12、写锁改为提交锁，如果一个 D 上有读锁，则上有读锁，则 T 等待；否则等待；否则 T 完成提交并结束，此时将数据完成提交并结束，此时将数据 D 的提交版的内容改为试用版的内容。的提交版的内容改为试用版的内容。 提交版提交锁读；试用版写锁写提交版提交锁读；试用版写锁写 5两版本锁的相容表两版本锁的相容表 读读 写写 提交（自己的写锁改为提交锁）提交（自己的写锁改为提交锁） 无锁无锁 读锁（提交版）读锁（提交版） 写锁（试用版）写锁（试用版）成功成功 读锁读锁 读锁（提交版）读锁（提交版） 写锁（试用版）写锁（试用版） 等待等待 写锁写锁 读锁（提交版）读锁（提交版） 挂起挂起 等待等待 提交锁提

13、交锁 挂起挂起 挂起挂起 挂起挂起 （二） 层次锁（二） 层次锁 在有的系统中，锁的粒度对不同的事务是不同的。因此，可以将数据的粒度分成不同的级别， 这样， 可以形成一个树型结构。当事务对树中的一个结点加锁时，它将封锁此结点的所有后代。因此，当封锁一个结点时，必须对父结点加意向锁。在有的系统中，锁的粒度对不同的事务是不同的。因此，可以将数据的粒度分成不同的级别， 这样， 可以形成一个树型结构。当事务对树中的一个结点加锁时，它将封锁此结点的所有后代。因此，当封锁一个结点时，必须对父结点加意向锁。 层次锁相容表层次锁相容表 待 设 置的锁待 设 置的锁 已 经 有 的锁已 经 有 的锁 读读 写写

14、 读意向读意向 写意向写意向 读读 成功成功 等等 成功成功 等等 写写 等等 等等 等等 等等 读意向读意向 成功成功 等等 成功成功 成功成功 写意向写意向 等等 等等 成功成功 成功成功 69-3 乐观并发控制 9-3 乐观并发控制 一、基本思想一、基本思想 Kung/Robinson 1981 年提出年提出 维护锁机制意味着额外的系统开销它们在不发生共享时无用，对读共享也无用。 维护锁机制意味着额外的系统开销它们在不发生共享时无用，对读共享也无用。 系统真正发生冲突的操作的机会可能非常少。 系统真正发生冲突的操作的机会可能非常少。 锁会引起死锁。 锁会引起死锁。 事务（两段锁协议）需要

15、在结束时解锁，可能严重减少并发潜力。 事务（两段锁协议）需要在结束时解锁，可能严重减少并发潜力。 乐观并发控制的基本思想是为每个事务设一独立的试用版，保留不加锁，只在提交时进行验证，看是否有冲突。若无，则提交；若有，则撤销重做。乐观并发控制的基本思想是为每个事务设一独立的试用版，保留不加锁，只在提交时进行验证，看是否有冲突。若无，则提交；若有，则撤销重做。 每个事务被分成每个事务被分成 3 个阶段：个阶段： 读出阶段相当于打草稿 读出阶段相当于打草稿 读操作：本事务若拥有试用版，则读此试用版，否则直接读此数据的提交版（最近提交的）读操作：本事务若拥有试用版，则读此试用版，否则直接读此数据的提交

16、版（最近提交的） 写操作：本事务若拥有试用版，则直接写此试用版，否则建立此数据的一个试用版，并对该试用版进行操作。写操作：本事务若拥有试用版，则直接写此试用版，否则建立此数据的一个试用版，并对该试用版进行操作。 当有多个事务并发时， 一个数据项可能存在多个不同的试用版。当有多个事务并发时， 一个数据项可能存在多个不同的试用版。 验证阶段 验证阶段 当事务结束时（当事务结束时（Close Transaction） ，就检验该事务对数据项） ，就检验该事务对数据项7的操作是否与其它的事务冲突，若无，则提交；否则作相应的验证处理。的操作是否与其它的事务冲突，若无，则提交；否则作相应的验证处理。 写入阶段 写入阶段 将已经通过验证的事务提交的修改记录置为永久的。只读事务可立即提交。将已经通过验证的事务提交的修改记录置为永久的。只读事务可立即提交。 二、