《系统实现技术》PPT课件.ppt

《《系统实现技术》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《系统实现技术》PPT课件.ppt（79页珍藏版）》请在装配图网上搜索。

1、系统实现技术,第七章,本章内容,本章主要涉及实现DBMS时的具体技术。 系统目录 ：存放数据库结构的描述。 事务：所有对数据库的操作，都要以事务作为一个整体单 位来执行或撤销。 在DBS运行时，DBMS要对DB进行监控，以保证整个系统的正常运转，防止数据意外丢失和不一致数据的产生。DBMS对 DB的监控，称为数据库的管理，有时也称为数据库的保护。对数据库的管理主要通过四个方面实现： 数据库的恢复 并发控制 完整性控制 安全性控制 每一方面构成了DBMS的一个子系统。,71 系统目录,系统目录（System Catalog）是任何通用 DBMS的核心。 系统目录本身就是一个“微型数据库”，其主要

2、功能是存储DBMS管理的数据库的定义或描述。这类信息被称为元数据（Metadata），主要包括数据库三级结构、两级映象的定义。,图1-15 访问数据库的主要步骤,数据字典,71 关系 DBMS的目录,关系DBMS的系统目录存储下列信息： （1）关系名，属性名，属性域（数据类型）； （2）各种约束，主键，辅助键，外键，空值 非空值； （3）视图的外部级描述，存储结构和索引的内部级描述； （4）安全性和授权规则； （5）数据完整性规则。,在关系 DBMS中，系统目录被组织成关系（表格）， 例如 Oracle系统中，系统目录由42个关系组成。DBMS可以对目录执行查询、修改和维护操作；而用户一般只能

3、执行查询操作不能进行修改或维护。,图7.1所示的是教学数据库三个关系的定义存储在目录中的形式。系统目录中的关系名为REL_AND _ATTR_CATALOG，存储用户关系中属性的性质，包括数据类型、主键、外键等。这个关系的主键为（REL_NAME，ATTR_NAME）,图7.1示的是教学数据库三个关系的定义存储在目录中的形式。系统目录中的关系名为REL_AND ATTR_ CATALOG，存储用户关系中属性的性质，包括数据类型、主键、外键等。这个关系的主键为（REL _NAME，ATTR_NAME）,索引信息可用目录关系 RELATION_INDEXES表示，如图 72（b）所示，主键为（IN

4、DEX_NAME，MEMBER_ATTR）。 视图的定义可用两个目录关系实现，如图72（C）所示。,至此，我们介绍了系统目录中的一些基本的信息存储方式。日前，在大多数DBMS的系统日录中，还存储了数据库运行的信息，例如每个基本关系中元组的数目和各个属性的平均访问次数，索引的层次数等。这些信息必须由DBMS经常更新，以反映数据库的使用状况。因此，系统目录对任何一个DBMS而言，都是十分重要的组成部分。 有的系统，甚至把系统目录数据字典系统从DBMS中分离出来，成为一个独立的数据字典系统，并使之成为一个比DBMS还要高级的用户与系统之间的接口，用户对数据库的所有操作都要通过数据字典实现，而不直接与

5、DBMS接触。,7.2 事务,7.2 事务举例 从用户观点看，对数据库的某些操作应是一个整体，也就是一个独立的工作单元，不能分割。 例如，客户认为电子资金转账（从账目A转一笔款到账号B）是一个独立的操作，而在DBS中这是由几个操作组成的。显然，这些操作要么全都发生，要么由于出错（可能账号A二透支）而全不发生。保证这一点非常重要，我们决不允许发生下面的事情：在账号A透支情况下继续转账；或者从账号A转出了一笔钱，而不知去向未能转人账号B中.这样就引出了事务的概念。,7.2.1 事务的概念,事务是一个操作序列。 这些操作要么什么都做， 要么都不做，是一个不可分割的工作单位。 是构成单一逻辑工作单元的

6、操作集合; DBS的主要意图是执行“事务”; 相当于操作系统环境中的“进程”概念。 一个程序的执行可通过若干事务的执行序列来完成。事务是不能嵌套的，可恢复的操作必须在一个事务的界限内才能执行.,事务的开始与结束可以由用户显式控制。如果用户没有显式地定义事务，则由DBMS按缺省规定自动划分事务。 在SQL语言中，定义事务的语句有三条： BEGIN TRANSACTION:事务开始 COMMIT:提交事务的所有操作,即将事务中所有对数据库的更新写回到磁盘上的物理数据库中去，事务正常结束 ROLLBACK:回滚，即在事务运行的过程中因发生某种故障而不能继续执行，通过ROLLBACK对数据库的所有已完

7、成的操作全部撤消，滚回到事务开始时的状态 ROLLBACK语句保证数据库处于正确的状态,事务举例的代码,T：BEGIN TRANSACTION； Read（A）； A:=A-50; write（A）； if（A0）ROLLBACK； else read（B）； B：=B+50； write（B）； COMMITE;,1原子性（Atomicity） ：事务是数据库的逻辑工作单位，事务中包括的诸操作要么都做，要么都不做。 由DBMS的事务管理子系统来实现。 2一致性(Consistency) ：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。如果数据库系统运行中发生故障，有些事务

8、尚未完成就被迫中断，系统将事务中对数据库的所有已完成的操作全部撤消，滚回到事务开始时的一致状态。 由DBMS的完整性子系统执行测试任务。,7.2.2事务的特性(ACID),3隔离性（Isolation） ：一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对其他并发事务是隔离的，并发执行的各个事务之间不能互相干扰。 隔离性是由DBMS的并发控制子系统实现的。 4持续性 （Durability）:事务完成之后，它对于系统的影响是永久性的。该修改即使出现系统故障也将一直保持。 事务的持久性由DBMS的恢复管理子系统实现的。,T：BEGIN TRANSACTION； Read（A）；

9、 A:=A-50; write（A）； if（A0）ROLLBACK； else read（B）； B：=B+50； write（B）； COMMITE; 原子性 一致性 隔离性 持久性 一旦事务成功完成，该事务对数据库施加的所有更新都是永久的。也就是计算机系统 的故障将会导致内存的数据丢失，但已写人磁盘的数据决不会丢失。,为了精确地描述事务的工作，我们建立一个抽象的事务模型，事务的状态变迁图如图74所示。,事务是恢复和并发控制的基本单位。保证事务ACID特性是事务处理的重要任务。事务ACID特性可能遭到破坏的因素有： 1. 多个事务并行运行时，不同事务的操作交叉执行。 要求数据库管理系统必须

10、保证多个事务的交叉运行不影响这些事务的原子性.(并发控制机制) 2. 事务在运行过程中被强行停止 :要求数据库管理系统必须保证被强行终止的事务对数据库和其它事务没有任何影响。(恢复机制),对事务的进一步研究,尽管数据库系统中采取了各种保护措施来防止数据库的安全性和完整性被破坏，保证并发事务的正确执行，但: 计算机系统中硬件的故障 软件的错误 操作员的失误以及恶意的破坏 这些故障时有发生,轻则造成运行事务非正常中断，影响数据库中数据的正确性，重则破坏数据库，使数据库中全部或部分数据丢失，因此数据库管理系统（恢复子系统）必须具有把数据库从错误状态恢复到某一已知的正确状态（亦称为一致状态或完整状态）

11、的功能. 这就是数据库的恢复。,7.3 数据库恢复概述,7.3.1 故障类型,事务故障 系统故障 介质故障 计算机病毒,一、事务内部的故障 预期故障(即可通过事务程序本身发现,如下面转帐事务的例子. 例如：银行转帐事务把一笔金额从一个帐户甲转给另一个帐户乙。 BEGIN TRANSACTION； Read（A）； A:=A-50; write（A）； if（A0）ROLLBACK； else read（B）； B：=B+50； write（B）； COMMITE;,故障的种类,非预期故障 事务内部更多的故障是非预期的，不能由应用程序处理。如运算溢出、并发事务发生死锁而被选中撤消该事务、违反了某

12、些完整性限制等。后面所提到的事务故障仅指这类非预期的故障。 事务故障意味着事务没有达到预期的终点，因此，数据库可能处于不正确状态。恢复程序要在不影响其它事务运行的情况下，强行回滚该事务，撤消该事务已经作出的任何对数据库的修改,此类恢复操作称为事务撤消（UNDO）。,故障的种类,二、系统故障 (软故障（Soft Crash）) 系统故障是指造成系统停止运转的任何事件，使得系统要重新启动。如: 特定类型的硬件错误（CPU故障） 操作系统故障 DBMS代码错误 突然停电 出现此类故障,主存内容(尤其是内存中的数据库缓冲区的内容都被丢失，所有运行事务都非正常终止。可能会有: 一些尚未完成的事务的结果已

13、送入物理数据库 有些已完成的事务可能有一部分甚至全部留在缓冲区，尚未写回到磁盘上的物理数据库中 从而破坏了数据库的一致性，恢复子系统在系统重新启动时将会针对所有非正常终止的事务回滚: 强行撤消（UNDO）所有未完成事务 重做（Redo）所有已提交的事务,故障的种类,影响正在运行的所有事 务，但不破坏数据库,三、介质故障(硬故障（Hard Crash）) 硬故障指外存故障，如磁盘损坏、磁头碰撞，瞬时强磁场干扰等。这类故障将破坏数据库或部分数据库，并影响正在存取这部分数据的所有事务。这类故障比前两类故障发生的可能性小得多，但破坏性最大。 四、计算机病毒 计算机病毒是具有破坏性、可以自我复制的计算机

14、程序。计算机病毒已成为计算机系统的主要威胁，自然也是数据库系统的主要威胁。因此数据库一旦被破坏仍要用恢复技术把数据库加以恢复。,故障的种类,总结各类故障，对数据库的影响有两种可能性： 一是数据库本身被破坏。 二是数据库没有破坏，但数据可能不正确，这是因为事务的运行被非正常终止造成的 。 恢复的基本原理：冗余。 即根据存储在系统别处的冗余数据来重建或恢复数据库中任何一部分被破坏的或不正确的数据。,故障的种类,恢复机制涉及的两个关键问题是： (1)如何建立冗余数据； (2)如何利用这些冗余数据实施数据库恢复。 建立冗余数据最常用的技术: (1)定期对数据库进行复制或转储(dump) (2)建立“日

15、志”文件 (3)恢复 通常在恢复时,两种方法一起使用。,7.3.2 恢复的实现技术,一、含义 转储：DBA定期地将整个数据库复制到磁带或另一个磁盘上保存起来的过程。这些备用的数据文本称为后备副本或后援副本。 当数据库遭到破坏后: 将后备副本重新装入，数据库恢复到转储时的状态 重新运行自转储以后的所有更新事务,恢复到故障发生时的状态,1. 数据转储,Ta：系统停止运行事务，进行数据库转储； Tb：转储完毕，得到Tb时刻的数据库一致性副本 Tf：系统发生故障。 恢复数据库的过程： 由DBA重装数据库后备副本，将数据库恢复至Tb时刻的状态 重新运行自Tb时刻至Tf时刻的所有更新事务，这样就把数据库恢

16、复到故障发生前的一致状态。 问题：1.转储是十分耗费时间和资源的，不能频繁进行。DBA应该根据数据库使用情况确定一个适当的转储周期。 2.系统需要停止运行事务,1. 数据转储,1. 数据转储,分类 静态转储 动态转储 海量转储 增量转储,按转储方式分,按转储量分,1. 数据转储,静态转储 静态转储是在系统中无运行事务时进行的转储操作。即转储操作开始的时刻，数据库处于一致性状态，而转储期间不允许（或不存在）对数据库的任何存取、修改活动。 静态转储得到的一定是一个数据一致性的副本。 静态转储简单，但必须等待正运行的用户事务结束才能进行，而且新的事务也必须等待转储结束才能执行。这会降低数据库的可用性

17、。,1. 数据转储,动态转储 动态转储是指转储期间允许对数据库进行存取或修改。即转储和用户事务可以并发执行。 动态转储不用等待正在运行的用户事务结束，也不会影响新事务的运行。但是，转储结束时后援副本上的数据并不能保证正确有效。 如，在转储期间的某个时刻Tc，系统把数据A=100转储到磁带上，而在下一时刻Td，某一事务将A改为200。转储结束后，后备副本上的A已是过时的数据了。 因此采用动态转储，必须把转储期间各事务对数据库的修改活动登记下来，建立日志文件（log file）。这样，后援副本加上日志文件就能把数据库恢复到某一时刻的正确状态。,1. 数据转储,转储还可以分为海量转储和增量转储两种方

18、式： 海量转储:每次转储全部数据库 增量转储:每次只转储上一次转储后更新过的数据。 分析: 从恢复角度看，使用海量转储得到的后备副本进行恢复一般说来会更方便些。但如果数据库很大，事务处理又十分频繁，则增量转储方式更实用更有效。,2. 日志文件,一. 日志文件的内容 记录事务对数据库的更新操作的文件。 以记录为单位的日志文件，需要登记的内容包括： 每个事务的开始(BEGIN TRANSACTION)标记 每个事务的结束(COMMIT或ROLL BACK)标记 每个事务的所有更新操作 一个事务开始的标记、结束标记及所有的更新操作即构成了日志文件中的一个日志记录。,2. 日志文件,更具体一点,每个日

19、志记录的内容主要包括： 事务标识（标明是哪个事务） 操作的类型（插入、删除或修改） 操作对象(记录内部标识) 更新前数据的旧值（对插入操作而言，此项为空值） 更新后数据的新值（对删除操作而言, 此项为空值）,2. 日志文件,二、日志文件的作用 用于进行事务故障恢复和系统故障恢复，并协助后备副本进行介质故障恢复。 具体如下： 事务故障恢复和系统故障必须用日志文件 在动态转储方式中必须建立日志文件，后援副本和日志文件的综合才能有效地恢复数据库。 静态转储方式中，也可建立日志文件。当数据库毁坏后可重新装入后援副本把数据库恢复到转储结束时刻的正确状态，然后利用日志文件，把已完成的事务进行重做处理，对故

20、障发生时尚未完成的事务进行撤消处理。这样不必重新运行那些已完成的事务程序就可把数据库恢复到故障前某一时刻的正确状态,如图7.2所示。,2. 日志文件,2. 日志文件,三、登记日志文件（logging） 为保证数据库可恢复，登记日志文件时必须遵循： 1. 登记的次序严格按并发事务执行的时间次序。 2. 必须先写日志文件，后写数据库。 把对数据的修改写到数据库中和把表示这个修改的日志记录写到日志文件中是两个不同的操作。故障可能发生在两个操作之间，即这两个写操作只完成了一个: 若先写数据库修改，而在运行记录中没有登记下这个修改，则以后就无法恢复这个修改。 如果先写日志，但没有修改数据库，则可以根据日

21、志文件进行REDO或者UNDO，不会影响数据库的正确性。 因此,要先把日志记录写到日志文件中，然后再写数据库的修改。这就是“先写日志文件”的原则。,3.系统故障恢复策略,系统故障造成数据库不一致状态的原因： 未完成事务对数据库的更新可能已写入数据库 已提交事务对数据库的更新可能还留在缓冲区没来得及写入数据库。,3. 系统故障恢复策略,系统的恢复步骤是： 1. 对未完成事务进行(UNDO)处理，即将日志记录中“更新前的值”写入数据库。 2. 对重做队列中的各个事务进行重做(REDO)处理。即将日志记录中“更新后的值”写入数据库 系统故障的恢复是由系统在重新启动时自动完成的，不需要用户干预。,3.

22、事务故障的恢复策略,事务故障的恢复 事务故障的恢复由系统自动完成，对用户透明。恢复过程如下: 1. 反向扫描文件日志（即从最后向前扫描日志文件），查找该事务的更新操作。,3.事务故障的恢复策略,2. 对该事务的更新操作执行逆操作。即将日志记录中“更新前的值”写入数据库:1) 若日志记录中是插入操作，则相当于做删除操作 （此时“更新前的值”为空）2) 若是删除操作，则做插入操作3) 若是修改操作，则用修改前值代替修改后值。 3. 继续反向扫描日志文件，查找该事务的其他更新操作，并做同样处理。 4. 如此处理下去，直至读到此事务的开始标记，事务故障恢复完成。,3. 介质故障的恢复,介质故障会导致磁

23、盘上的物理数据和日志文件被破坏，这是最严重的一种故障。 恢复方法是重装数据库，然后重做已完成的事务。 具体操作： 1. 装入最新的数据库后备副本（离故障发生时刻最近的转储副本），使数据库恢复到最近一次转储时的一致性状态。 2. 装入相应的日志文件副本（转储结束时刻的日志文件副本），重做已完成的事务。,4. 具有检查点的恢复技术,4. 具有检查点的恢复技术,利用日志技术进行数据库恢复时，恢复子系统必须搜索日志，确定哪些事务需要REDO，哪些事务需要UNDO。一般需要检查所有日志记录。这样做有两个问题： 搜索整个日志将耗费大量的时间 很多需要REDO处理的事务实际上已经将它们的更新操作结果写到数据

24、库中了，然而恢复子系统又重新执行了这些操作，浪费时间。 为了解决这些问题，又发展了具有检查点的恢复技术。这种技术在日志文件中增加一类新的记录-检查点记录（checkpoint），增加一个重新开始文件，并让恢复子系统在登录日志文件期间动态地维护日志。,4. 具有检查点的恢复技术,动态维护日志文件的方法是：建立检查点，保存数据库状态，这个操作反复执行。具体步骤是： 将当前日志缓冲中的所有日志记录写入磁盘的日志文件上。 在日志文件中写入一个检查点记录。 将当前数据缓冲的所有数据记录写入磁盘的数据库中。 把检查点记录在日志文件中的地址写入一个重新开始文件。,4. 具有检查点的恢复技术,恢复子系统可以定

25、期或不定期地建立检查点保存数据库状态： 按照预定的一个时间间隔建立检查点，如每隔一小时建立一个检查点； 按照某种规则建立检查点，如日志文件已写满一半建立一个检查点。 使用检查点可以改善恢复效率。当事务T在一个检查点之前提交，T对数据库所做的修改一定都已写入数据库，写入时间是在这个检查点建立之前或在这个检查点建立之时。这样，在进行恢复处理时，没有必要对事务T执行REDO操作。 系统出现故障时恢复子系统将根据事务的不同状态采取不同的恢复策略。如图7.4中：,T1 : 在检查点之前提交，不必执行REDO操作。 T2：在检查点前开始执行，检查点之后故障点之前提交。 T4：在检查点之后开始执行，在故障点

26、之前提交。 T3：在检查点之前开始执行，在故障点时还未完成。 T5：在检查点之后开始执行，在故障点时还未完成。,检查点后提交，对数据 库的修改可能还在缓冲 区中，尚未写入数据库， 需REDO；,故障发生时还未完成， 需撤消(UNDO ),7.4 数据库的并发控制,并发现象 多用户数据库系统 允许多个用户同时使用数据库系统称多用户数据库系统,如银行数据库系统,飞机订票系统。在多用户系统中，同一时刻并行运行的事务数可达数百个。 并发目的 串行执行事务 事务可以串行执行，即每一时刻只有一个事务运行，其它事务必须等到该事务结束后才能运行。事务执行过程中可能用到的资源有：CPU、存取物理数据库、I/O、

27、通信道。如事务串行执行，会使许多系统资源处于空闲状态。因此为了充分利用系统资源，发挥数据库共享的特点，应允许多个事务并行的执行。,单处理机系统的事务并行执行 在单处理机中，事务的并行执行实际是这些并行事务的并行操作轮流交叉运行（称为交叉并发方式），实际并没有真正地并行运行，但减少了处理机的空闲时间，提高了系统效率。 多处理机系统的事务并行执行 在多处理机中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并发运行（称为同时并发方式） 当多个用户并发存取数据库即会产生多个事务同时存取同一数据库的情况。若对并发操作不加控制可能会存取和存储不正确数据，破坏数据库的一致性

28、。所以DBMS必须提供并发控制机制。并发控制机制是衡量一个DBMS的主要标志之一。,7.4.1 并发控制概述,事务是并发控制的基本单位，保证事务ACID的特性是事务处理的重要任务，而并发操作有可能会破坏其ACID特性。 DBMS并发控制机制的责任： 对并发操作进行正确调度，保证事务的隔离性更一般，确保数据库的一致性。 以下的实例说明并发操作带来的数据不一致的问题。,考虑飞机订票系统中的一个活动序列（同一时刻读取） 甲售票点（甲事务）读取某航班的机票余额A，A=16 乙售票点（乙事务）读取同一航班机票余额A，A=16 甲售票点卖出一张机票，修改A=A-1，即A=15，写入数据库 乙售票点也卖出一

29、张机票，修改A=A-1，即A=15，入加数据库 结果：卖出两张票，数据库中机票余额只减少1。 造成数据库的不一致性是由并发操作引起的。在并发操作情况下，对甲、乙事务的操作序列是随机的。若按上面的调度序列执行，甲事务的修改被丢失，因为第4步中乙事务修改A并写回后覆盖了甲事务的修改。,如果没有锁定且多个用户同时访问一个数据库，则当他们的事务同时使用相同的数据时可能会发生问题。由于并发操作带来的数据不一致性包括： 1.丢失更新 当两个或多个事务选择同一行，然后基于最初选定的值更新该行时，会发生丢失更新问题。每个事务都不知道其它事务的存在。最后的更新将重写由其它事务所做的更新，这将导致数据丢失。 如上

30、例。 再例如，两个编辑人员制作了同一文档的电子复本。每个编辑人员独立地更改其复本，然后保存更改后的复本，这样就覆盖了原始文档。最后保存其更改复本的编辑人员覆盖了第一个编辑人员所做的更改。如果在第一个编辑人员完成之后第二个编辑人员才能进行更改，则可以避免该问题。,2.不可重复读 指事务T1读取数据后，事务T2执行更新操作，使T1无法读取前一次结果。不可重复读包括三种情况： 事务T1读取某一数据后，T2对其做了修改，当T1再次读该数据后，得到与前一不同的值。 T1按一定条件从数据库中读取了某些记录后，T2删除了其中部分记录，当T1再次按相同条件读取数据时，发现某些记录消失 T1按一定条件从数据库中

31、读取某些数据记录后，T2插入了一些记录，当T1再次按相同条件读取数据时，发现多了一些记录。 例如，一个编辑人员两次读取同一文档，但在两次读取之间，作者重写了该文档。当编辑人员第二次读取文档时，文档已更改。原始读取不可重复。如果只有在作者全部完成编写后编辑人员才可以读取文档，则可以避免该问题。,3. 读“脏”数据（脏读） 读“脏”数据是指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤消，而此时T1把已修改过的数据又恢复原值，T2读到的数据与数据库的数据不一致，则T2读到的数据就为“脏”数据，即不正确的数据。 例如，一个编辑人员正在更改电子文档。在更改过程中，另

32、一个编辑人员复制了该文档（该复本包含到目前为止所做的全部更改）并将其分发给预期的用户。此后，第一个编辑人员认为目前所做的更改是错误的，于是删除了所做的编辑并保存了文档。分发给用户的文档包含不再存在的编辑内容，并且这些编辑内容应认为从未存在过。如果在第一个编辑人员确定最终更改前任何人都不能读取更改的文档，则可以避免该问题。 产生这些数据的不一致性的主要原因是并发操作破坏了事务的隔离性。,图8.1 三种数据不一致性,7.4.2 封锁(locking).,并发控制：用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性。 并发控制的主要技术是封锁(locking

33、).如在飞机订票例子中,甲事务要修改A,若在读出A前先锁住A,其它事务不能再读取和修改A，直到甲修改并写回A后解除了对A的封锁为止。这样甲就不会丢失修改。,1. 含义,事务T在对某个数据对象如表、记录等操作之前，向系统发出请求，对其加锁。加锁后T对数据对象有一定的控制（具体的控制由封锁类型决定），在事务T释放前，其它事务不能更新此数据对象。,2. 锁类型,排它锁（X锁、写锁） 若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务不能对A加任何类型的锁，直到T释放A上的锁。从而保证其它事务在T释放A上的锁前不能再读取和修改A。 共享锁（S锁、读锁） T对数据对象A加上S锁，则T可以

34、读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。保证了在T对A加S锁过程中其它事务对A只能读，不能修改。,3. 封锁协议（Locking Protocol）,封锁协议:在运用X锁和S锁对数据对象加锁时，需要遵循的规则（如 何时申请X锁或S锁、持锁时间、何时释放等），这些规则即为封锁协议。 对封锁方式规定不同的规则即形成了各种不同的封锁协议，不同级别的封锁协议分别在不同程度上解决一定程度的一致性问题。,3.封锁协议（Locking Protocol）,一、一级封锁协议 事务T在修改数据R之前必须先对其加X锁，直到事务结束(即通过commit和rollback结束)

35、才释放。 作用：防止丢失修改，保证事务T可恢复。 二、二级封锁协议 一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。 作用：防止丢失修改及读“脏”数据 三、三级封锁协议 一级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。 作用：防止丢失修改，防止读“脏”数据以及防止不可重复读。,三个级别的封锁协议的主要区别在于什么操作需要申请封锁，以及何时释放锁（即持锁时间）。,T1读A,在修改之前先对A加X锁 当T2再请求对A加X锁时被拒绝，T2等待T1释放A上的锁 T2获得对A的X锁，此时T2读到A是T1更新过的值15 T2按A的新值进行运算，并将结果

36、值A=14送回磁盘 可避免丢失T1的更新。 一级封锁协议不能保证可重复读和不读“脏数据”,一级封锁协议,T1在对C进行修改之前，先对C加X锁，修改其值后写磁盘 此时，T2请求在C上中S锁，因T1已在C上加了X锁，T2只能等待 T1因某种原因被撤消，C恢复原值100，T1释放C上的X锁，T2获C上的S锁，读C=100。 可避免T2读“脏”数据。 二级封锁协议不能保证可重复读。,二级封锁协议,T1在读A，B之前先对A，B加S锁，即其它事务只能再对A，B加S锁，不能加X锁。 当T2修改B而申请B的X锁时被拒绝，等待T1释放B上的锁 T1为验算，再读A，B，读出的B仍是100，求和结果仍是150，即可

37、重复读。 T1释放A，B上的S锁后，T2获得对B的X锁。 三级封锁协议防止丢失修改，防止读“脏”数据以及防止不可重复读。,三级封锁协议,4. 活锁和死锁,封锁可能导致活锁和死锁。 一、活锁 指某个事务永远处于等待状态，得不到执行的现象。 二、死锁 两个或以上的事务均处于等待状态，每个事务都在等待另一个事务解除封锁， 以便继续执行下去，结果任何一个事务都无法执行，这种现象就是死锁。,活锁的情况： T1封锁了数据R，T2也请求封锁R，于是T2等待。 T3也请求封锁R，当T1释放R上的封锁，系统首先批准了T3的请求，T2仍然等待。 T4请求封锁R，当T3释放了R上的封锁，系统批准了T4的请求。 T2

38、有可能永远等待。,活锁与死锁,死锁的情况： T1封锁了数据R1， T2封锁了数据R2 T1又请求封锁R2，因 T2已封锁了R2 ，因此T1等待T2释放R2的锁 T2又请求封锁R1，因 T1已封锁了R1 ，因此T2等待T1释放R1的锁 T1在等待T2，T2等待T1，导致T1和T2两个事务永远不能结束。,死锁,三、活锁的解决方案 避免活锁的方法是采用“先来先服务”策略。当多个事务请求封锁同一个数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中的第一个事务获得锁。 四、死锁的解决方案 两种方法： 采取一定的措施来预防死锁的发生 允许发生死锁，采用的一定手段诊

39、断系统中有无死锁，若有则解除。,解锁？,死锁的预防 防止死锁的发生即是要破坏死锁的条件，有两种方法： 一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。 如上图 (b)中可以使T1对R1和R2一次加锁，T1可以执行下去，而T2等待。T1执行完后释放R1，R2的锁，T2继续执行。 一次封锁存在的问题： 一次将所有将要用到的数据加锁，扩大了封锁的范围，降低了系统的并发度； 数据库中数据不断变化，原来不要求封锁的数据在执行过程中可能变成封锁对象，所以很难事先精确确定每个事务所要封锁的数据对象，为此只能扩大封锁范围，将事务在执行过程中可能要封锁的数据对象全部加锁，这进一步

40、降低了并发度。,顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务按照这个顺序实行封锁。 如B树结构的索引中，可规定封锁的顺序必须是从根结点开始，然后是下一级的子女结点，逐级封锁。 顺序封锁存在的问题： DBMS中封锁的数据对象极多，并且随着数据的插入、删除等操作不断变化，要维护这样的资源的封锁顺序非常困难，成本高。 事务的封锁请求可以随着事务的执行而动态地决定，很难事先确每一个事务要封锁哪些对象，因此很难按规定的顺序去施加封锁。 可见预防死锁的策略不可行，一般DBMS在解决死锁的问题上普遍采用诊断并解除死锁的方法。,5. 并发调度的可串行性,可串行化调度：多个事务的并发执行是正确的，当且仅

41、当其结果与按某一次序串行地执行它们时的结果相同。这种调度策略即为可串行化的调度。 可串行性：并发事务正确性的准则。按这个准则规定，一个给定的并发调度，当且仅当它是可串行化，才认为是正确调度。 例 有两个事务，分别包含下列操作： 事务T1：读B；A=B+1；写回A； 事务T2：读A；B=A+1；写回B； 假设A，B的初值均为2。按T1T2次序执行结果为A=3，B=4；按T2T1次序执行结果为B=3，A=4。 下图给出这两个事务的三种不同的调度策略。,(a)和(b)为两种不同的串行调度策略，但均正确的调度； (c)中T1，T2交错执行，执行结果与(a)，(b)的结果不同，为错误的调度; (d)中T

42、1，T2交错执行，执行结果与(a)的结果相同，为正确的调度;,为保证并发操作的正确性，DBMS的并发控制机制必须提供一定的手段来保证调度可串行化。 理论上，某一事务执行时禁止其它事务执行的调度策略一定是可串行批的调度，但这使用户不能充分共享数据库资源。目前BDMS普遍采用封锁方法实现并发操作调度的可串行性，从而保证调度的正确性。 两段锁（Two-Phase Locking,简称2PL）协议是保证并发调度可串行性的封锁协议。,6. 两段锁协议,两段封锁协议规定所有事务必须分以下两个阶段对数据项加锁和解锁： (1)在对任何数据进行读写操作之前，事务首先要获得对该数据的封锁；-封锁阶段（扩展阶段）封

43、锁阶段，事务可以申请获取任何数据项上的任何类型的锁，但不能释放任何锁。 (2)在释放一个封锁之后，事务不再获得任何其他封锁。-释放封锁阶段（收缩阶段）释放封锁阶段可以释放任何数据项上的任何类型的锁，但不能申请任何锁。,6. 两段锁协议,T1 遵守2PL： Slock A Slock B Xlock C Unlock B Unlock A Unlock C T2 不遵守2PL： Slock A Unlock A Slock B Xlock C Unlock C Unlock B 若并发事务遵守2PL，则这些事务的任何并发调度策略都是可串行化的；但一个可串行化的调度中，不一定所有事务都符合2PL。如下图所示：,由于两段封锁不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段协议的事务可能发生死锁。如图所示：,7. 封锁的粒度,封锁粒度：封锁对象的大小。 封锁对象（针对关系数据库）： 逻辑单元：属性值、属性值的集合、元组、关系、索引项、整个索引、整个数据库 物理单元：页（数据页和索引页）、块等 封锁粒度与并发控制的开销的关系： 封锁粒度越大，数据库能够封锁的数据单元越少，并发度也越小，系统开销也越小； 封锁粒度越小，并发度较高，系统开销也就越大；,