精华内容
下载资源
问答
  • 云计算环境下的复杂数据库并行调度模型仿真.pdf
  • 数据库是一个共享资源,可以提供多个用户使用。这些用户程序可以一个一个地串行...因此,为了充分利用数据库资源,发挥数据库共享资源的特点,应该允许多个用户并行地存取数据库。但这样就会产生多个用户程序并发存取

    数据库是一个共享资源,可以提供多个用户使用。这些用户程序可以一个一个地串行执行,每个时刻只有一个用户程序运行,执行对数据库的存取,其他用户程序必须等到这个用户程序结束以后方能对数据库存取。但是如果一个用户程序涉及大量数据的输入/输出交换,则数据库系统的大部分时间处于闲置状态。因此,为了充分利用数据库资源,发挥数据库共享资源的特点,应该允许多个用户并行地存取数据库。但这样就会产生多个用户程序并发存取同一数据的情况,若对并发操作不加控制就可能会存取和存储不正确的数据,破坏数据库的一致性,所以数据库管理系统必须提供并发控制机制。

    并发控制机制的好坏是衡量一个数据库管理系统性能的重要标志之一。

     

    DM用封锁机制来解决并发问题

    它可以保证任何时候都可以有多个正在运行的用户程序,

    但是所有用户程序都在彼此完全隔离的环境中运行。

     

    一、  并发控制的预备知识

    (一)  并发控制概述

    并发控制是以事务(transaction)为单位进行的。

    1.  并发控制的单位――事务

     

    事务是数据库的逻辑工作单位,它是用户定义的一组操作序列。

    一个事务可以是一组SQL语句、一条SQL语句或整个程序。

     

    事务的开始和结束都可以由用户显示的控制,

    如果用户没有显式地定义事务,则由数据库系统按缺省规定自动划分事务。

    事务应该具有4种属性:ACID 原子性、一致性、隔离性和持久性

     

    (1)原子性

    事务的原子性保证事务包含的一组更新操作是原子不可分的,也就是说这些操作是一个整体,对数据库而言全做或者全不做,不能部分的完成。这一性质即使在系统崩溃之后仍能得到保证,在系统崩溃之后将进行数据库恢复,用来恢复和撤销系统崩溃处于活动状态的事务对数据库的影响,从而保证事务的原子性。系统对磁盘上的任何实际数据的修改之前都会将修改操作信息本身的信息记录到磁盘上。当发生崩溃时,系统能根据这些操作记录当时该事务处于何种状态,以此确定是撤销该事务所做出的所有修改操作,还是将修改的操作重新执行。

     

    (2)一致性

    一致性要求事务执行完成后,将数据库从一个一致状态转变到另一个一致状态。它是一种以一致性规则为基础的逻辑属性,例如在转账的操作中,各账户金额必须平衡,这一条规则对于程序员而言是一个强制的规定,由此可见,一致性与原子性是密切相关的。

    事务的一致性属性要求事务在并发执行的情况下事务的一致性仍然满足。

    它在逻辑上不是独立的,它由事务的隔离性来表示。

     

    (3) 隔离性

    隔离性意味着一个事务的执行不能被其他事务干扰。

     

    即一个事务内部的操作及使用的数据对并发的其他事务是隔离的,并发执行的各个事务之间不能互相干扰。

    它要求即使有多个事务并发执行,看上去每个成功事务按串行调度执行一样。

    这一性质的另一种称法为可串行性,也就是说系统允许的任何交错操作调度等价于一个串行调度。

    串行调度的意思是每次调度一个事务,在一个事务的所有操作没有结束之前,另外的事务操作不能开始。

     

    由于性能原因,我们需要进行交错操作的调度,但我们也希望这些交错操作的调度的效果和某一个串行调度是一致的。

     

    DM实现并发的可串行化机制是通过对事务的数据访问对象加适当的锁,从而排斥其他的事务对同一数据库对象的并发操作。

     

    (4)持久性

    系统提供的持久性保证要求一旦事务提交,那么对数据库所做的修改将是持久的

    无论发生何种机器和系统故障都不应该对其有任何影响。

     

    例如,自动柜员机( ATM)在向客户支付一笔钱时,就不用担心丢失客户的取款记录。事务的持久性保证事务对数据库的影响是持久的,即使系统崩溃。正如在讲原子性时所提到的那样,系统通过做记录来提供这一保证。

    DM没有提供显式定义事务开始的语句,第一个可执行的SQL语句(除CONNECT语句外)隐含事务的开始,但事务的结束可以由用户显式的控制。在DM中以下几种情况都结束 (正常,非正常)某一事务:

    (1)当某一连接的属性设置为自动提交,每执行一条语句都会提交;

    (2)遇到COMMIT/ROLLBACK语句,便提交/回滚一事务;

    (3)当系统的 DDL自动提交开关打开时(缺省为打开),遇到DDL语句则自动提交该DDL语句和以前的DML和DDL操作;

    (4)事务所在的程序正常结束和用户退出;

    (5)系统非正常终止时;

    说明:DM在配置文件中提供了DDL语句的自动提交开关DDL_AUTO_COMMIT。 当此配置项的值为 1(缺省情况)时,所有DDL语句自动提交;当此配置项的值为0时,除CREATEDATABASE、ALTERDATABASE和CREATESCHEMA语句外的所有DDL语句都不自动提交。

    DM中的一致性是以事务为基础的。DM通过提交和回滚分别用于将对数据库的修改永久化和废除,但是无论是提交和回滚,DM保证数据库在每个事务开始前、结束后是一致的。为了提高事务管理的灵活性,DM提供了设置保存点(SAVEPOINT)语句和回滚到保存点语句。保存点提供了一种灵活的回滚,事务在执行中可以回滚到某个保存点,在该保存点以前的操作有效,而以后的操作被回滚掉。

    DM中的事务同样具有上述4个属性:原子性、一致性、隔离性和持久性。

    2. 并发操作与数据的不一致性

    如果没有锁定且多个用户同时访问一个数据库,则当他们的事务同时使用相同的数据时可能会发生问题,导致数据库中的数据的不一致性。

    一个最常见的并发操作的例子是火车/飞机订票系统中的订票操作。例如,在该系统中的一个活动序列:

    ① 甲售票员读出某航班的机票张数余额A,设A=16;

    ②  乙售票员读出同一航班的机票张数余额A,也是16;

    ③  甲售票员卖出一张机票,修改机票张数余额A=A-1=15,把A写回数据库;

    ④  乙售票员也卖出一张机票,修改机票张数余额A=A-1=15,把A写回数据库。

    结果明明卖出两张机票,数据库中机票余额只减少1。

    这种情况称为数据库的不一致性。这种不一致性是由甲、乙两个售票员并发操作引起的。在并发操作情况下,对甲、乙两个事务操作序列的调度是随机的。若按上面的调度序列行,甲事务的修改就被丢失。这是由于第4步中乙事务修改A并写回覆盖了甲事务的修改。

    并发操作带来的数据库不一致性可以分为四类:丢失或覆盖更新、脏读、不可重复读和幻像读,上例只是并发问题的一种。


    <!--[if !supportLists]-->(1)       <!--[endif]-->丢失或覆盖更新(lost update)

    当两个或多个事务选择同一数据,并且基于最初选定的值更新该数据时,会发生丢失更新问题。每个事务都不知道其它事务的存在。最后的更新将重写由其它事务所做的更新,这将导致数据丢失。上面预定飞机票的例子就属于这种并发问题。事务1与事务2先后读入同一数据A=16,事务1执行A-1,并将结果A=15写回,事务2执行A-1,并将结果A=15写回。事务2提交的结果覆盖了事务1对数据库的修改,从而使事务1对数据库的修改丢失了。

     

     
    (2)    脏读
    一个事务读取了另一个未提交的并行事务写的数据。当第二个事务选择其它事务正在更新的行时,会发生未确认的相关性问题。第二个事务正在读取的数据还没有确认并且可能由更新此行的事务所更改。换句话说,当事务1修改某一数据,并将其写回磁盘,事务2读取同一数据后,事务1由于某种原因被撤销,这时事务1已修改过的数据恢复原值,事务2读到的数据就与数据库中的数据不一致,是不正确的数据,称为脏读。
    例如,在下图中,事务1将C值修改为200,事务2读到C为200,而事务1由于某种原因撤销,其修改作废,C恢复原值100,这时事务2读到的就是不正确的“脏“数据了。

     

    (3)    不可重复读(nonrepeatable read)
    一个事务重新读取前面读取过的数据,发现该数据已经被另一个已提交的事务修改过。

    即事务1读取某一数据后,事务2对其做了修改,当事务1再次读数据时,得到的与第一次不同的值。
    例如,在下图中,事务1读取B=100进行运算,事务2读取同一数据B,对其进行修改后将B=200写回数据库。事务1为了对读取值校对重读B,B已为200,与第一次读取值不一致。

     

    (4)    幻像读
    如果一个事务在提交查询结果之前,另一个事务可以更改该结果,就会发生这种情况。这句话也可以这样解释,事务1按一定条件从数据库中读取某些数据记录后未提交查询结果,事务2删除了其中部分记录,事务1再次按相同条件读取数据时,发现某些记录神秘地消失了;或者事务1按一定条件从数据库中读取某些数据记录后未提交查询结果,事务2插入了一些记录,当事务1再次按相同条件读取数据时,发现多了一些记录。
    产生上述四类数据不一致性的主要原因是并发操作破坏了事务的隔离性。并发控制就是要用正确的方式调度并发操作,使一个用户事务的执行不受其他事务的干扰,从而避免造成数据的不一致性。

    3.    并发场景列举
    结合SQL语句,列举各种并发情况(包括可能导致数据不一致性和对数据一致性不产生影响的情况)。A表示某一条数据,b和c都表示满足某一个标准的两条或多条数据,^表示“非”的意思,∈表示属于或包含于的意思,1表示第一个事务,2表示第二个事务。

     

    (二)    并发操作的调度
    计算机系统对并行事务中并行操作的调度是随机的,而不同的调度可能会产生不同的结果,那么哪个结果是正确的,哪个是不正确的呢?
    如果一个事务运行过程中没有其他事务在同时运行,也就是说没有受到其他事务的干扰,那么就可能认为该事务的运行结果是正常的或者预想的,因此将所有事务串行起来的调度策略是正确的调度策略。虽然以不同的顺序串行执行事务也可能会产生不同的结果,但由于不会将数据库置于不一致状态,所以都可以认为是正确的。由此可以得到如下结论:几个事务的并行执行是正确的,当且仅当其结果与按某一次序串行地执行它们的结果相同。我们称这种并行调度策略为可串行化(serializable)的调度。可串行性(serializability)是并行事务正确性的唯一准则。


    例如,现在有两个事务,分别包含下列操作:
    事务1:读B;A=B+1;写回A;
    事务2:读A;B=A+1;写回B;
    假设A的初值为10,B的初值为2。下图给出了对这两个事务的三种不同的调度策略,(a)和(b)为两种不同的串行调度策略,虽然执行结果不同,但他们都是正确的调度。(c)中两个事务是交错执行的,由于执行结果与(a)、(b)的结果都不同,所以是错误的调度。(d)中的两个事务也是交错执行的,由于执行结果与串行调度1(图(a))的执行结果相同,所以是正确的调度。

     

    为了保证并行操作的正确性,DBMS的并行控制机制必须提供一定的手段来保证调度是可串行化的。
    从理论上讲,在某一事务执行时禁止其他事务执行的调度策略一定是可串行化的调度,这也是最简单的调度策略,但这种方法实际上是不可行的,因为它使用户不能充分共享数据库资源。
    目前DBMS普遍采用封锁方法(悲观方法,DM采用的就是这种方法,SQL Server也是采用的这种方法)来保证调度的正确性;即保证并行操作调度的可串行性。除此之外还有其他一些方法,如时标方法、乐观方法等。

     

    •    悲观并发控制
    锁定系统阻止用户以影响其它用户的方式修改数据。如果用户执行的操作导致应用了某个锁,则直到这个锁的所有者释放该锁,其它用户才能执行与该锁冲突的操作。该方法主要用在数据争夺激烈的环境中,以及出现并发冲突时用锁保护数据的成本比回滚事务的成本低的环境中,因此称该方法为悲观并发控制。

     

    •    乐观并发控制
    在乐观并发控制中,用户读数据时不锁定数据。在执行更新时,系统进行检查,查看另一个用户读过数据后是否更改了数据。如果另一个用户更新了数据,将产生一个错误。一般情况下,接收错误信息的用户将回滚事务并重新开始。该方法主要用在数据争夺少的环境内,以及偶尔回滚事务的成本超过读数据时锁定数据的成本的环境内,因此称该方法为乐观并发控制。

     

    •    时标并发控制
    时标和封锁技术之间的基本区别是封锁是使一组事务的并发执行(即交叉执行)同步,使用它等价于这些事务的某一串行操作;时标法也是使用一组事务的交叉执行同步,但是使它等价于这些事务的一个特定的串行执行,即由时标的时序所确定的一个执行。如果发生冲突,是通过撤销并重新启动一个事务解决的。事务重新启动,则赋予新的时标。

     

    (三)    封锁
    封锁是事项并发控制的一个非常重要的技术。所谓封锁就是事务T在对某个数据对象,例如,在标、记录等操作之前,先向系统发出请求,对其加锁。加锁后事务T就对数据库对象有了一定的控制,在事务T释放它的锁之前,其他事务不能更新此数据对象。

    1.    封锁类型
    DBMS通常提供了多种数据类型的封锁。一个事务对某个数据对象加锁后究竟拥有什么样的控制是由封锁类型决定的。基本的封锁类型有两种:排他锁(X锁)共享锁(S锁)

    排他锁又称为写锁。

    若事务T对数据对象A加上X锁,则只允许T读取和修改A,

    其他任何事务都不能再对A加任何类型的锁,直到T释放A上的锁

    这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。

    共享锁又称为读锁。

    若事务T对数据对象A加上S锁,则其他事务只能再对A加S锁,

    而不能加X锁,直到T释放A上的锁。

    这就保证了其他事务可以读A,但在T释放A上的S锁之前不能对A做任何修改。


    排他锁与共享锁的控制方式可以用下图的相容矩阵来表示。 
    在下图的封锁类型相容矩阵中,最左边一列表示事务T1已经获得的数据对象上的锁的类型,其中横线表示没有加锁。最上面一行表示另一事务T2对同一数据对象发出的封锁请求。T2的封锁请求能否被满足用Y和N表示,其中Y表示事务T2的封锁要求与T1已持有的锁相容,封锁请求可以满足。N表示T2的封锁请求与T1已持有的锁冲突,T2请求被拒绝。

     

    2.    封锁粒度

    X锁和S锁都是加在某一个数据对象上的。封锁的对象可以是逻辑单元,也可以是物理单元。例如,在关系数据库中,封锁对象可以是属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等逻辑单元;也可以是页(数据页或索引页)、块等物理单元。封锁对象可以很大,比如对整个数据库加锁,也可以很小,比如只对某个属性值加锁。封锁对象的大小称为封锁的粒度(granularity)。

    封锁粒度与系统的并发度和并发控制的开销密切相关。封锁的粒度越大,系统中能够被封锁的对象就越小,并发度也就越小,但同时系统开销也越小;相反,封锁的粒度越小,并发度越高,但系统开销也就越大。
    因此,如果在一个系统中同时存在不同大小的封锁单元供不同的事务选择使用是比较理想的。而选择封锁粒度时必须同时考虑封锁机构和并发度两个因素,对系统开销与并发度进行权衡,以求得最优的效果。一般说来,需要处理大量元组的用户事务可以以关系为封锁单元;需要处理多个关系的大量元组的用户事务可以以数据库为封锁单位;而对于一个处理少量元组的用户事务,可以以元组为封锁单位以提高并发度。

     

    3.    封锁协议

    封锁的目的是为了保证能够正确地调度并发操作。为此,在运用X锁和S锁这两种基本封锁,对一定粒度的数据对象加锁时,还需要约定一些规则,例如,应何时申请X锁或S锁、持锁时间、何时释放等。我们称这些规则为封锁协议(locking protocol)。对封锁方式规定不同的规则,就形成了各种不同的封锁协议,它们分别在不同的程度上为并发操作的正确调度提供一定的保证。本节介绍保证数据一致性的三级封锁协议和保证并行调度可串行性的两段锁协议,下一节将介绍避免死锁的封锁协议。

     

    (5)    保证数据一致性的封锁协议――三级封锁协议

    对并发操作的不正确调度可能会带来四种数据不一致性:丢失或覆盖更新、脏读、不可重复读和幻想读。三级封锁协议分别在不同程度上解决了这一问题。

     

    ①    1级封锁协议

    1级封锁协议的内容是:事务T在修改数据R之前必须先对其加X锁,直到事务结束才释放。事务结束包括正常结束(commit)和非正常结束(rollback)。

    1级封锁协议可以防止丢失或覆盖更新,并保证事务T是可以恢复的。例如,下图使用1级封锁协议解决了定飞机票例子的丢失更新问题。

     

    上图中,事务1在读A进行修改之前先对A加X锁,当事务2再请求对A加X锁时被拒绝,只能等事务1释放A上的锁。事务1修改值A=15写回磁盘,释放A上的X锁后,事务2获得对A的X锁,这时他读到的A已经是事务1更新过的值15,再按此新的A值进行运算,并将结果值A=14回到磁盘。这样就避免了丢失事务1的更新。

    在1级封锁协议中,如果仅仅是读数据不对其进行修改,是不需要加锁的,所以它不能保证可重复读和脏读。

     

    ②  2级封锁协议

    2级封锁协议的内容是:1级封锁协议加上事务T在读取数据R之前必须先对其加S锁,读完后即可释放S锁
    2级封锁协议除防止了丢失或覆盖更新,还可进一步防止脏读
    例如,下图使用2级封锁协议解决了脏读的问题。
    |
    下图中,事务1在对C进行修改之前,先对C加X锁,修改其值后写回磁盘。这时事务2请求C加上S锁,因T1已在C上加了X锁,事务2只能等待事务1释放它。之后事务1因某种原因被撤销,C恢复为原值100,并释放C上的X锁。事务2获得C上的S锁,读C=100。这就避免了事务2脏读数据。

    在2级封锁协议中,由于读完数据后即可释放S锁,所以它不能保证可重复读。

     

    ③    3级封锁协议

    3级封锁协议的内容是:1级封锁协议加上事务T在读取数据之前必须先对其加S锁,直到事务结束才释放。
    3级封锁协议除防止丢失或覆盖更新和不脏读数据外,还进一步防止了不可重复读和幻想读。例如下图,使用3级封锁协议解决了不可重复读和幻像读问题。

     

    上图中,事务1在读A,B之前,先对A,B加S锁,这样其他事务只能再对A,B加S锁,而不能加X锁,即其他事务只能读A,B,而不能修改它们。所以当事务2为修改B而申请对B的X锁时被拒绝,使其他无法执行修改操作,只能等待事务1释放B上的锁。接着事务1为验算再读A,B,这时读出的B仍是100,求和结果仍为150,即可重复读。

    上述三级协议的主要区别在于什么操作需要申请封锁以及何时释放锁(即持锁时间)。三级封锁协议可以总结为下表。

     

    (6)    保证并行调度可串行性的封锁协议――两段封锁协议

    可串行性是并行调度正确性的唯一准则,两段锁(two-phase locking,简称2PL)协议是为保证并行调度可串行性而提供的封锁协议。

     

    两段封锁协议规定:

    ①  在对任何数据进行读、写操作之前,事务首先要获得对该数据的封锁,

    ②  在释放一个封锁之后,事务不再获得任何其他封锁

    所谓“两段”锁的含义是:事务分为两个阶段,

    第一阶段是获得封锁,也称为扩展阶段,第二阶段是释放封锁,也称为收缩阶段。

     

    (在一个事务中,从任何有解锁释放点的地方开始,如果后面还发生加锁,就违反了两段封锁协议)

     

    例如,事务1的封锁序列是:

    Slock A... Slock B… Xlock C… Unlock B… Unlock A… Unlock C;

    事务2的封锁序列是:

    Slock A... Unlock A… Slock B… Xlock C… Unlock C… Unlock B;

    则事务1遵守两段封锁协议,而事务2不遵守两段封锁协议。

     

    若并行执行的所有事务均遵守两段锁协议,则对这些事务的所有并行调度策略都是可串行化的。

    因此我们得出如下结论:所有遵守两段锁协议的事务,其并行的结果一定是正确的。

    需要说明的是,

    事务遵守两段锁协议可串行化调度的充分条件,而不是必要条件。

    可串行化的调度中,不一定所有事务都必须符合两段封锁协议

     

    例如,在下图中,(a)和(b)都是可串行化的调度,但(a)遵守两段锁协议,(b)不遵守两段锁协议。

     

    4.    死锁和活锁

    封锁技术可以有效地解决并行操作的一致性问题,但也带来一些新的问题,即死锁和活锁的问题。

    (1)    活锁

    如果事务T1封锁了数据对象R后,事务T2也请求封锁R,于是T2等待。接着T3也请求封锁R。T1释放R上的锁后,系统首先批准了T3的请求,T2只得继续等待。接着T4也请求封锁R,T3释放R上的锁后,系统又批准了T4的请求……,T2有可能就这样永远等待下去。这就是活锁的情形,如下图所示。

     

    避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时,封锁子系统按请求封锁的先后次序对这些事务排队,该数据对象上的锁一旦释放,首先批准申请队列中第一个事务获得锁。

    (2)    死锁

    如果事务T1封锁了数据A,事务T2封锁了数据B。之后T1又申请封锁数据B,因T2已封锁了B,于是T1等待T2释放B上的锁。接着T2又申请封锁A,因T1已封锁了A,T2也只能等待T1释放A上的锁。这样就出现了T1在等待T2,而T2又在等待T1的局面,T1和T2两个事务永远不能结束,形成死锁。如下图所示。

     

    死锁问题在操作系统和一般并行处理中已做了深入研究,但数据库系统有其自己的特点,操作系统中解决死锁的方法并不一定合适数据库系统。

    目前在数据库中解决死锁问题主要有两类方法,一类方法是采取一定措施来预防死锁的发生,另一类方法是允许发生死锁,采用一定手段定期诊断系统中有无死锁,若有则解除之。

    ①    死锁的预防
    在数据库系统中,产生死锁的原因是两个或多个事务都已封锁了一些数据对象,然后又都请求对已为其他事务封锁的数据对象加锁,从而出现死锁等待。防止死锁的发生其实就是要破坏产生死锁的条件。预防死锁通常有两种方法。

    ◆ 一次封锁法
    一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁,否则就不能继续执行。例如,在上图的例子中,如果事务T1将数据对象A和B一次加锁,T1就可以执行下去,而T2等待。T1执行完后释放A,B上的锁,T2继续执行。这样就不会发生死锁。

    一次封锁法虽然可以有效地防止死锁的发生,但也存在问题。第一,一次就将以后要用到的全部数据加锁,势必扩大了封锁的范围,从而降低了系统的并发度。第二,数据库中数据是不断变化的,原来不要求封锁的数据,在执行过程中可能会变成封锁对象,所以很难实现精确地确定每个事务所要封锁的数据对象,只能采取扩大封锁范围,将事务在执行过程中可能要封锁的数据对象全部加锁,这就进一步降低了并发度。

    ◆    顺序封锁法
    顺序封锁法是预先对数据对象规定一个封锁顺序,所有事务都按这个顺序执行封锁。在上例中,我们规定封锁顺是A,B,T1和T2都按此顺序封锁,即T2也必须先封锁A。当T2请求A的封锁时,由于T1已经封锁住A,T2就只能等待。T1释放A,B上的锁后,T2继续运行。这样就不会发生死锁。

    顺序封锁法同样可以有效地防止死锁,但也同样存在问题。第一,数据库系统中可封锁的数据对象及其众多,并且随数据的插入、删除等操作而不断地变化,要维护这样极多而且变化的资源的封锁顺序非常困难,成本很高。

    第二,事务的封锁请求可以随着事务的执行而动态地决定,很难事先确定每一个事务要封锁哪些对象,因此也就很难按规定的顺序取施加封锁。例如,规定数据对象的封锁顺序为A,B,C,D,E。事务T3起初要求封锁数据对象B,C,E,但当它封锁B,C后,才发现还需要封锁A,这样就破坏了封锁顺序。

    可见,在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点,因此DBMS在解决死锁的问题上更普遍采用的是诊断并解除死锁的方法。

    ②    死锁的诊断与解除
    数据库系统中诊断死锁的方法与操作系统类似,即使用一个事务等待图,它动态地反映所有事务的等待状况。并发控制子系统周期性地(比如每隔1分钟)检测事务等待图,如果发现图中存在回路,则表示系统中出现了死锁关于诊断死锁的详细讨论请参阅操作系统的有关书籍。

    DBMS的并发控制子系统一旦检测到系统中存在死锁,就要设法解除。

    通常采用的方法是选择一个处理死锁代价最小的事务,将其撤销,

    释放此事务持有的所有的锁,使其他事务能继续运行下去。


    二、    DM的并发控制
    (一)    事务隔离级
    事务的隔离级描述了给定事务的行为对其它并发执行事务的暴露程度。 SQL-92共规定了四种隔离级别,通过选择四个隔离级中的一个,用户能增加对其它未提交事务的暴露程度,获得更高的并发度。隔离级别是一个事务必须与其它事务进行隔离的程度。
    SQL-92的四种隔离级别如下所示,DM支持所有这些隔离级别:
    (1)脏读(READ UNCOMMITTED):事务隔离的最低级别,事务可能查询到其它事务未提交的数据,仅可保证不读取物理损坏的数据)。
    (2)读提交(READ COMMITTED):DM默认级别,保证不读脏数据。 
    (3)可重复读(REPEATABLE READ):保证不可重复读,但有可能读入幻像数据。
    (4)可串行化(SERIALIZABLE):事务隔离的最高级别,事务之间完全隔离。

    DM允许用户改变未启动的事务的隔离级和读写特性,而且设置的选项将一直对那个连接保持有效,直到显式更改该选项为止。设置事务隔离级别虽然使程序员承担了某些完整性问题所带来的风险,但可以换取对数据更大的并发访问权。与以前的隔离级别相比,每个隔离级别都提供了更大的隔离性,但这是通过在更长的时间内占用更多限制锁换来的。DM还提供设置事务只读属性的语句,使用该语句后该事务只能做查询操作,不能更新数据库。
    需要注意的是,事务的隔离级别并不影响事务查看本身对数据的修改,也就是说,事务总可以查看自己对数据的修改。事务的隔离级别需要根据实际需要设定,较低的隔离级别可以增加并发,但代价是降低数据的正确性。相反,较高的隔离级别可以确保数据的正确性,但可能对并发产生负面影响。应用程序要求的隔离级别确定了DM使用的锁定行为。
    下表中列出四种隔离级别允许不同类型的现象

     

    注意:丢失或覆盖更新在所有的标准SQL隔离级中都是禁止的。

     

    (二)    并发处理

    1.    数据锁定机制

    DM用数据锁定机制来解决并发问题。它可以保证任何时候都可以有多个正在运行的事务,但是所有事务都在彼此完全隔离的环境中运行。

    DM的封锁对象为表和元组。封锁的实施有自动和手动两种,即隐式上锁和显式上锁。隐式封锁动作的封锁根据事务的隔离级有所不同。同时, DM提供给用户4种手动上锁语句,用以适应用户定义的应用系统。

    一般而言, DM的隐式封锁足以保证数据的一致性,但用户可以根据自己的需要改变对表的封锁。 DM提供给用户四种表锁:意向共享锁(IS:INTENSIVE SHARE)、共享锁(S:SHARE)、意向排它锁(IX:INTENSIVE EXCLUSIVE)和排它锁(X:EXCLUSIVE)。例如,在读提交隔离级下,系统缺省的表锁是 IS或IX ,在这两种表锁下,在访问元组前还需对元组进行封锁,为了提高系统的效率,用户可以手动对表进行 X封锁,这样,就不需对访问元组封锁。

    封锁机制要达到以下目的:

    (1)一致性:保证用户正在查看时,改变的数据并未从根本上发生变化。

    (2)完整性:保证数据库的基本结构以正确的顺序,准确地反映对它们的所有改变。

    一个“ 锁定” 可以认为是当某一进程需要防止其它进程做某事时获得的某种东西,当该进程不再关心此事时就 “释放 ”此锁定,通常一个锁定是加在某个 “资源 ”(某些客体,如表 )上的。

    DM的内部锁定是自动完成的。当某一进程要查看一个客体但不允许其他人修改它时,就获得一个共享方式的锁定。当某一进程要修改一客体,并且防止任何其它进程修改它时,就获得更新方式的锁定。当某一进程要修改一客体,并且防止任何其它进程修改它或以共享方式封锁它时,就获得独占方式的锁定。

    2.    锁定类型

    DM中的锁有三种,表锁、行锁和键范围锁。

    ◆   表锁
    表锁用来封锁表对象,在对表进行检索和更新时,DM会对表对象进行封锁,但是DM为用户提供手动的表锁语句,用户可以根据自己的需要改变对表的封锁类型。表锁的模式:意向共享锁 IS,意向排它锁 IX,共享锁 S,排它锁 X,共四种,其相容矩阵可定义如下表。

     

    ◆   行锁
    行锁封锁元组,在存取元组和更新元组前, DM会对元组上行锁,系统不提供手动的行封锁语句。行锁有两种模式:共享锁(S)、排它锁(X),其相容矩阵定义如下表。

     

    ◆     键范围锁
    键范围锁用在可串行事务上,主要解决了幻像读并发问题。键范围锁覆盖单个记录以及记录之间的范围,可以防止对事务访问的记录集进行幻像插入或删除。键范围锁仅用于在可串行隔离级别上操作的事务。
    可串行性要求,如果任意一个查询在一个事务中后面的某一时刻再次执行,其所获取的行集应与该查询在同一事务中以前执行时所获得的行集相同。如果本查询试图提取的行不存在,则在试图访问该行的事务完成之前,其它事务不能插入该行。如果允许另一个事务插入该行,则它将以幻像出现。
    如果另一个事务试图插入驻留在锁定数据页上的行,页级锁定可以防止添加幻像行,并维护可串行性。但是,如果该行要添加到未被第一个事务锁定的数据页,应设定锁定机制防止添加该行。
    键范围锁通过覆盖索引行和索引行之间的范围来工作(而不是锁定整个基础表的行)。因为第二个事务在该范围内进行任何行插入、更新或删除操作时均需要修改索引,而键范围锁覆盖了索引项,所以在第一个事务完成之前会阻塞第二个事务的进行。
    键范围锁由系统自行执行,执行的条件是: (1) 事务隔离级为可串行化级; (2) 查询结果通过某个索引得出。
    用户上锁成功后锁将一直有效,直到当前事务结束时,该锁被系统自动解除。

    3.    锁定类型比较

     

    4.    SQL语句锁定分析
    DM对各种 DDL和GRANT 等非DML 语句都分解为增、删、改。下表为DM对各种DML语句和查询语句的封锁策略。


    表:SQL语句封锁策略

     

    注:S* 表示瞬时锁,在语句结束后释放;Range表示键范围锁。

    上表只是系统在一般情况下的处理,当系统检测到有锁升级的可能,则会升级锁。一般而言,IS锁升级为 S锁,IX锁升级为 X锁,同时,不再进行行封锁。

    5.    自定义锁定提高系统效率

    DM也提供了两个函数 SET_TABLE_OPTION([db.][sch.]tablename, option, value) 、SET_INDEX_OPTION([db.]indexname, option, value)(具体语法参见《 DM_SQL语言使用手册》第 8 章)供用户自行定义锁定类型,以增强系统并发度,提高系统效率。这两个函数是为那些清楚地知道特定类型的锁适用于何种情况的专家级用户提供的。

    函数SET_TABLE_OPTION() 用于禁用指定表上的页级锁、行级锁或同时禁用二者,这一设置对该表上的所有索引都生效。函数 SET_INDEX_OPTION() 则用于禁用某一索引上的页级锁、行级锁或同时禁用二者。

    例如,当用户只需要修改索引中某定长字段时,修改操作不会造成 B 树的分裂与合并,此时就可以禁用该索引的页级锁。又如,当所有的用户都只做插入操作时,用户之间并不会对同一元组进行操作,此时就可以禁用行级锁。当用户能保证不对表进行增、删、改,而只是进行查询时,则可以同时禁用该表上的页级锁和行级锁,此时并发度最高。

    6.    死锁处理

    解决死锁问题的三种方法:预防死锁、检测死锁及避免死锁。死锁预防要求用户进程事先申报所需的资源或按严格的规程申请资源,而死锁检测原则上应允许死锁发生,在适当的时机检查,若发生死锁,则设法排除之。与预防死锁相比,后者过于放手,致使死锁频繁。而避免死锁则以事务撤消为前提,当不能获得资源批准时,立刻进行死锁检测。它既不象预防死锁那样过于保守,也不象死锁检测那样过于放开,由于检测及时,由归纳法可知,在已获准等待的事务中,不可能存在死锁,所以检测算法比较简单。

    DM4系统采用的是避免死锁方法。每当一个事务所申请占有的资源不能被立即获得时,便进行死锁检测,不存在死锁,则该事务入等待队列。否则,DM4视为产生运行时错误,将当前语句回滚。采用这种机制,从用户的角度看,DM4不存在解锁问题。

    7.    加索引和不加索引的封锁区别

    加索引和不加索引的情况下,DM的封锁机制会影响到实际的封锁范围。索引的作用就在于,可以在查询中减少对无关数据的扫描。而在一般的隔离级中,总是要对扫描到的数据进行封锁。所以,利用索引可以减少封锁的数量,冲突的可能性也会大大减少。

    展开全文
  • 并行数据库

    千次阅读 2014-07-04 16:30:42
    并行数据库 计算机系统性能价格比的不断提高迫切要求硬件、软件结构的改进。硬件方面,单纯依靠提高微处理器速度和缩小体积来提高性能价格比的方法正趋于物理极限;磁盘技术的发展滞后于微处理器的发展速度,...

    并行数据库


    计算机系统性能价格比的不断提高迫切要求硬件、软件结构的改进。硬件方面,单纯依靠提高微处理器速度和缩小体积来提高性能价格比的方法正趋于物理极限;磁盘技术的发展滞后于微处理器的发展速度,使得磁盘 I/O 颈瓶问题日益突出。软件方面,数据库服务器对大型数据库各种复杂查询和联机事务处理 (OLTP) 的支持使得对响应时
     
    并行数据库新记录
    间和吞吐量的要求顾此失彼。同时,应用的发展超过了主机处理能力的增长速度,数据库应用 (DSSS , OLAP 等 ) 的发展对数据库的性能和可用性提出了更高要求,能否为越来越多的用户维持高事务吞吐量和低响应时间已成为衡量 DBMS 性能的重要指标。

      计算机多处理器结构以及并行数据库服务器的实现为解决以上问题提供了极大可能。随着计算机多处理器结构和磁盘阵列技术的进步,并行计算机系统的发展十分迅速,出现了 Seqnent 等商品化的并行计算机系统。为了充分可法多处理器硬件,并行数据库的设计者必须努力开发面向软件的解决方案。为了保持应用的可移植性,这一领域的多数工作都围绕着支持 SQL 查询语言进行。目前已经有一些关系数据库产品在并行计算机上不同程度地实现了并行性。

      将数据库管理与并行技术结合,可以发挥多处理器结构的优势,从而提供比相应的大型机系统要高的多的性能价格比和可用性。通过将数据库在多个磁盘上分布存储,可以利用多个处理器对磁盘数据惊醒并行处理,从而解决了磁盘 I/O 瓶颈问题。同样,潜在的主存访问瓶颈也可以通过开发查询间并行性 ( 即不同查询并行执行 ) ,查询内并行性 ( 即同提查询内的操作并行执行 ) 以及操作内并行性 ( 即子操作并行执行 ) ,从而大大提高查询效率。

      并行数据库系统的功能有:

      一个并行数据库系统可以作为服务器面向多个客户机进行服务。典型的情况是,客户机嵌入特定应用软件,如图形界面, DBMS 前端工具 4GL 以及客户机 / 服务器接口软件等。因此,并行数据库系统应该支持数据库功能,客户机 / 服务器结构功能以及某些通用功能 ( 如运行 C 语言程序等 ) 。此外,如果系统中有多个服务器,那么每个服务器还应包含额外的软件层来提供分布透明性。

      对于客户机 / 服务器体系结构的并行数据库系统,它所支持的功能一般包括:

      会话管理子系统。提供对客户与服务器之间交互能力的支持。

      请求管理子系统。负责接收有关查询编译和执行的客户请求,触发相应操作并监管事务的执行与提交。

      数据管理子系统。提供并行编译后查询所需的所有底层功能,例如并行事务支持,高速缓冲区管理等。

      上述功能构成类似于一个典型的 RDBMS ,不同的是并行数据库必须具有处理并行性,数据划分,数据复制以及分布事务等的能力。依赖于不同的并行系统体系结构,一个处理器可以支持上述全部功能或其子集。

      并行数据库的结构:

      并行数据库系统的实现方案多种多样。根据处理器与磁盘及内存的相互关系可以将并行计算机结构划分为三种基本的类型,下面分别介绍这三种基本的并行系统结构,并从性能,可用性和可扩充性等三个方面来比较这些方案。

      Shared-Memory( 共享内存 ) 结构,又称 Shared-Everything 结构,简称 SE 结构。

      Shared-Memory 方案中,任意处理器可通过快速互连 ( 高速总线或纵横开关 ) 访问任意内存模块或磁盘单元,即所有内存与磁盘为所有处理器共享, IBM3090 , Bull 的 DPS8 等大型机以及 Sequent , Encore 等对称多处理器都采用了这一设计方案。

      并行数据库系统中, XPRS , DBS3 以及 Volcano 都在 Shared-Memory 体系结构上获得实现。但是迄今为止,所有的共享内存商用产品都只开发了查询间并行性,而尚未实现查询内并行性。


    参考:

    http://blog.csdn.net/linnet2000/article/details/888649

    ===========================================================


    并行数据库


    并行数据库系统是新一代高性能的书局库系统,致力于开发数据库操作的时间并行性和空间并行性,是当今研究热点之一。并行数据库技术起源于20世纪70年代的数据库机研究,希望通过硬件实现关系操作的某些功能。研究主要集中在关系代数操作的并行化和实现关系操作的专用硬件设计上。80年代后,逐步转向通用并行机的研究。90年代以后,存储技术、网络技术、微机技术的迅猛发展,以及通用并行计算机硬件的发展,为并行数据库技术的研究奠定了基础。
    早期并行数据库系统的研究重点主要集中在并行数据库的物理组织、操作算法、优化和调度策络上。目前它致力于开发数据操作的时间并行性和空间并行性。关系模型仍是研究的基础,给予对象模型的并行数据库也是一个重要的研究方向。
         并行数据库系统的目标及问题
    1并行数据库系统的目标
    一个并行数据库系统应该实现高性能、高可用性、可扩充性等目标。
    1)高性能
    并行数据库系统通过将数据库管理技术与并行处理技术有机结合,发挥多处理机结构的优势,从而提供比相应的大型机系统要求高得多的性价比和可用性。例如,通过将数据库得多个磁盘上分布存储,利用多个处理机对磁盘数据进行并行处理,可以解决磁盘的瓶颈问题。通过开发查询时间并行行(不同查询并行执行)、查询并行性(同一查询内地子操作并行执行)以及其他操作内并行性(子操作并行执行),可以大大提高查询效率。
    1)  可用性
    并行数据库系统可通过数据复制等手段来增强数据库的可用性。这样,当一个磁盘损坏时,该攀上的数据在其他磁盘上的副本仍可供使用,且无需额外的开销(与基于日志的恢复不同)。数据复制还应与数据划分技术相结合,以保证当磁盘损坏时系统仍能并行访问数据。
    2)  可扩充性
        并行数据库系统的可扩充性是指系统通过增加处理和存储能力,是器具有可平滑地扩展性能的能力。并行数据库系统可以具有两个方面的可扩充性优势:性性伸缩和线性加速。
    2)并行数据库研究的问题
    并行数据库特别是并行关系数据库已经成为数据库研究的热点。最近几年,伴随着MPP的发展,新的并行机分布式计算技术、计算机机群(Cluster-technology)等引起了人们的极大关注,成为十分活跃的研究领域。除了这些,目前在并行数据库领域主要有下列问题需要解决。
    (1)并行体系结构。目前的并行计算机其各个处理机都具有自己独立的主存和磁盘,不共享计算机,不共享硬件资源,处理机之间的通信由高速网络实现。需要研究与这些并行计算机结构相一致的并行数据库的体系结构及有关实现技术。
    (2)并行操作算法。为提高并行查询的效率,需要研究联接、句集合统计等数据操作的并行算法。
    (3)并行查询优化。对并型操作的步骤进行优化组合,以进一步提高系统执行效率。
    (4)并行数据库的物理设计。它包括数据分布算法的研究和数据库设计工具的研究等。
    (5)并行数据库的数据加载和再组织技术。

    参考:

    http://blog.csdn.net/oliveleave/article/details/614421

    展开全文
  • 数据库 - 并发调度的可串行性

    万次阅读 2015-05-12 17:35:31
    并发调度的可串行性DBMS对并发事务不同的调度(schedule)可能会产生不同的结果 什么样的调度是正确的?串行化(Serial)调度是正确的 对于串行调度,各个事务的操作没有交叉,也就没有相互干扰,当然也不会产生并发所...

    并发调度的可串行性

    DBMS对并发事务不同的调度(schedule)可能会产生不同的结果
    什么样的调度是正确的?

    串行化(Serial)调度是正确的
    对于串行调度,各个事务的操作没有交叉,也就没有相互干扰,当然也不会产生并发所引起的。如前所述,事务对数据库的作用是将数据库从一个一致的状态转变为另一个一致的状态。多个事务串行执行后,数据库仍旧保持一致的状态。

    可串行化(Serializable)调度
    多个事务的并发执行是正确的,当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。可串行化调度当然也保持数据库的一致状态

    [例]现在有两个事务,分别包含下列操作:
    事务T1:读B;A=B+1;写回A
    事务T2:读A;B=A+1;写回B
    现给出对这两个事务不同的调度策略 
    

    可串行性(Serializability)
    是并发事务正确调度的准则。在RDBMS中,作为并发控制的正确性准则。一个给定的并发调度,当且仅当它是可串行化的,才认为是正确调度

    可串行化调度的充分条件

    一个调度Sc在保证冲突操作的次序不变的情况下,通过交换两个事务不冲突操作的次序得到另一个调度Sc‘,如果Sc’是串行的,称调度Sc为冲突可串行化的调度
    一个调度是冲突可串行化,一定是可串行化的调度
    一般RDBMS都将冲突可串行化作为并发控制的正确性准则

    冲突操作(Conflict Operation)

    冲突操作是指不同的事务对同一个数据的读写操作和写写操作
    Ri (x)与Wj(x) /* 事务Ti读x,Tj写x*/
    Wi(x)与Wj(x) /* 事务Ti写x,Tj写x*/
    其他操作是不冲突操作
    不同事务的冲突操作和同一事务的两个操作不能交换(Commute) ,否则会影响执行的效果

    [例]今有调度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
    把w2(A)与r1(B)w1(B)交换,得到:
        r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)
    再把r2(A)与r1(B)w1(B)交换:
       Sc2=r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
    Sc2等价于一个串行调度T1,T2,Sc1冲突可串行化的调度
    
    冲突可串行化调度是可串行化调度的充分条件,不是必要条件。还有不满足冲突可串行化条件的可串行化调度,称为目标可串行化(view serializability)的调度。
        [例]有3个事务, L1和L2是目标等价的(view equivalence)
           T1=W1(Y)W1(X),T2=W2(Y)W2(X),T3=W3(X)
    调度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一个串行调度。
    调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。但是调度L2是可串行化的,因为L2执行的结果与调度L1相同,Y的值都等于T2的值,X的值都等于T3的值 
    

    封锁协议

     运用封锁方法时,对数据对象加锁时需要约定一些规则 
    

    何时申请封锁
    持锁时间
    何时释放封锁等
    两段封锁协议(Two-Phase Locking,简称2PL)是最常用的一种封锁协议,理论上证明使用两段封锁协议产生的是可串行化调度

    两段锁协议
    指所有事务必须分两个阶段对数据项加锁和解锁
    在对任何数据进行读、写操作之前,事务首先要获得对该数据的封锁
    在释放一个封锁之后,事务不再申请和获得任何其他封锁

    “两段”锁的含义
    事务分为两个阶段
    第一阶段是获得封锁,也称为扩展阶段
    事务可以申请获得任何数据项上的任何类型的锁,但是不能释放任何锁
    第二阶段是释放封锁,也称为收缩阶段
    事务可以释放任何数据项上的任何类型的锁,但是不能再申请任何锁

    例
    事务Ti遵守两段锁协议,其封锁序列是 :
    Slock A    Slock B    Xlock C     Unlock B    Unlock A   Unlock C;
    |←      扩展阶段    →|  |←      收缩阶段           →|
    事务Tj不遵守两段锁协议,其封锁序列是: 
    Slock A    Unlock A    Slock B    Xlock C    Unlock C    Unlock B;
    

    事务遵守两段锁协议是可串行化调度的充分条件,而不是必要条件。
    若并发事务都遵守两段锁协议,则对这些事务的任何并发调度策略都是可串行化的
    若并发事务的一个调度是可串行化的,不一定所有事务都符合两段锁协议
    两段锁协议与防止死锁的一次封锁法
    一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁,否则就不能继续执行,因此一次封锁法遵守两段锁协议
    但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁,因此遵守两段锁协议的事务可能发生死锁

    封锁粒度(Granularity)

    封锁对象的大小称为封锁粒度(Granularity)
    封锁的对象:逻辑单元,物理单元
    例:在关系数据库中,封锁对象:
    逻辑单元: 属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等
    物理单元:页(数据页或索引页)、物理记录等

    封锁粒度与系统的并发度和并发控制的开销密切相关。
    封锁的粒度越大,数据库所能够封锁的数据单元就越少,并发度就越小,系统开销也越小;
    封锁的粒度越小,并发度较高,但系统开销也就越大

    若封锁粒度是数据页,事务T1需要修改元组L1,则T1必须对包含L1的整个数据页A加锁。如果T1对A加锁后事务T2要修改A中元组L2,则T2被迫等待,直到T1释放A。
    如果封锁粒度是元组,则T1和T2可以同时对L1和L2加锁,不需要互相等待,提高了系统的并行度。
    又如,事务T需要读取整个表,若封锁粒度是元组,T必须对表中的每一个元组加锁,开销极大

    多粒度封锁(Multiple Granularity Locking)

    在一个系统中同时支持多种封锁粒度供不同的事务选择
    

    选择封锁粒度
    同时考虑封锁开销和并发度两个因素,适当选择封锁粒度
    需要处理多个关系的大量元组的用户事务:以数据库为封锁单位
    需要处理大量元组的用户事务:以关系为封锁单元
    只处理少量元组的用户事务:以元组为封锁单位

    多粒度树
    以树形结构来表示多级封锁粒度
    根结点是整个数据库,表示最大的数据粒度
    叶结点表示最小的数据粒度
    允许多粒度树中的每个结点被独立地加锁
    对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
    在多粒度封锁中一个数据对象可能以两种方式封锁:显式封锁和隐式封锁
    显式封锁: 直接加到数据对象上的独立封锁
    隐式封锁: 该数据对象没有独立加锁,是由于其上级结点加锁而使该数据对象加上了锁
    显式封锁和隐式封锁的效果是一样的!

    系统检查封锁冲突时
    要检查显式封锁
    还要检查隐式封锁
    例如事务T要对关系R1加X锁
    系统必须搜索其上级结点数据库、关系R1
    还要搜索R1的下级结点,即R1中的每一个元组
    如果其中某一个数据对象已经加了不相容锁,则T必须等待

    对某个数据对象加锁,系统要检查
    该数据对象
    有无显式封锁与之冲突
    所有上级结点(祖先)
    检查本事务的显式封锁是否与其它事务在该数据对象上的隐式封锁冲突:(由上级结点已加的封锁造成的)
    所有下级结点(后裔)
    看其它事务在下级节点上的显式封锁是否与本事务的隐式封锁(将加到下级结点的封锁)冲突

    数据共享与数据一致性是一对矛盾
    数据库的价值在很大程度上取决于它所能提供的数据共享度
    数据共享在很大程度上取决于系统允许对数据并发操作的程度
    数据并发程度又取决于数据库中的并发控制机制
    数据的一致性也取决于并发控制的程度。施加的并发控制愈多,数据的一致性往往愈好

    数据库的并发控制以事务为单位
    数据库的并发控制通常使用封锁机制
    两类最常用的封锁

    并发控制机制调度并发事务操作是否正确的判别准则是可串行性
    并发操作的正确性则通常由两段锁协议来保证。
    两段锁协议是可串行化调度的充分条件,但不是必要条件

    展开全文
  • 所谓并发操作,是指在多用户... 1.1 串行调度:(Serial Schedule)是指多个事务依序串行执行,且 只有当一个事务的所有操作执行完后,才执行另一个事务的所用操作。 1.2 并发调度:(Concurrent Schedule)利用分...

    所谓并发操作,是指在多用户共享的系统中,许多用户可能同时对同一数据进行操作。所带来的问题是数据的不一致性,具体表现为:丢失更新、不可重复读、读脏数据。

    1、事务调度

         1.1 串行调度:(Serial Schedule)是指多个事务依序串行执行,且 只有当一个事务的所有操作执行完后,才执行另一个事务的所用操作。

       1.2 并发调度:(Concurrent Schedule)利用分时的方法同时处理多个事务;

      1.2.1 并发调度的可串行性

       1.2.1.1可串行化的调度

                多个事务并发执行是正确的,当且仅当其结果与某一次序串行的执行它们时的结果相同,称这种调度策略是可串行化的调度

       (Serializability Schedule).可串行性是并发事务正确性的准则,按这个准则规定,一个给定的并发调度,当且仅当它是可串行化的才认为是正确调度

      1.2.1.2冲突可串行化判定(write =w, R=read)

        测试调度S的可串行化:
       对于调度S的事务T1,在图中创建一个节点 T1
       A步、对于每种这样的情形:如果S中的在T1执行了W(X)操作后,执行T2的R(X),那么优先图中创建一条边(T1 --》T2 )
       B步、对于每种这样的情形:如果S中的在T1执行了R(X)操作后,执行T2的W(X),那么优先图中创建一条边(T1 --》T2 ) 
       C步、对于每种这样的情形:如果S中的在T1执行了W(X)操作后,执行T2的W(X),那么优先图中创建一条边(T1 --》T2 )
       当且仅当优先图中没有闭环时,调度S是可串行化的。(不用考虑 T1 、T2两个读的情况) 

    用有向图判断是否可串行化

    如图

    上图有两个事务并发,则在纸上分别画两个圆图,并在圆中注明事务号,如下图

    对于T0

    A步,在T0列中找W(X),我们发现T0只有在T8处有Write(A),又在T8之后,T1列有Write(B),但是因为参数不同,一个是A,一个是B,所以不符A步的规则。不能画箭头。

    B步,在T0列中找R(X),我们发现T0在T1有Read(A),之后,到T1列中找W(X),我们发现在T1列T6处Write(A),符合

    因此得画一条箭头从T0指向T1,如图  

     因为已经画了一条从T0到T1的箭头,没有必要再进行C步。

    对T1

    A步 在T1列中找W(X),我们发现在T1在T6时间有Write(A),在T6之后找不到对应的Read(A),所以不能画线;

    B步在T1列中找R(X),我们发现在T1,在T3处有Read(A),在T3之后,T0在T8处有Write(A),参数一致,得画线了。

    结果如图

    形成闭环。表明调度错误。


    再看下图

    用有向图分析调度是否正确

    有上 图,仍然有两个事务,T0,T1,则分别画两个图,并注明

     

    对T0

     A步:T0在t3处有Write(A),于是我们到T1列中查找对应的R(A),我们 发现T1列在t4处有Read(A)(并且T4,在T3 之后),得画线了,如图因为A已经画了一条线,B步,C步没必要再找了

     

    对于T1 

    A步  在T7,在t7处发现Write(A ,在t0列,t7之后没有Read(A)对应,所以不能画线

    B步  在T1列中找Read(X),在t4处发现Read(A),在t4之后,T0列并没有 Write(A)跟着对应,所以不能画线

    C步 在T1列中找到Write(X),在t7处发现Write(A),在t7之后,在t0列没有Write(A),跟着对应,所以不能画线,

           在T1列中t13处找到write(B),在t13之后,T0列已经执行完毕,也就是找不到对应的write(B),所以不能画线。

    结论:上图中的调度是正确,


    又如下图,用有向图判断

     

    有上 图,仍然有两个事务,T0,T1,则分别画两个图,并注明

    对于T0

    A步 在T0列找Write(X),我们发现在t3列中发现Write(A),而T1在t3之后的t4处有Read(A),得画线了如图

     

    如图因为A步已经画了一条线,B步,C步没必要再找了




    对于T1 

    A步   在t9处发现Write(A),在t9之后,t0列并没有发read(A),所以不能画线,在T1列,t13处发现Write(B)但在t0,t13处之后并没有到对应的read(B)

    B 步  在T1列中t4处找到 Read(A),但在t4之后T0列并没有对应的Write(A),不能画线,在t11处发现Read(B),在t11之后并没有发现Write(B)对应,也不能画线。

    C步 在T1列中找write(X),在T9处找到write(A),在t9之后并没找到write(A)跟之对应,所以不能画线;

         在T1列t13处发现Write(B),在t13之后,没有发现 write(B)与之对应对,所以也不能画线。

    最终结果

    没有行成循环,所以上面的调度是正确的,

    ,

    事务高深,我只是学了皮毛而已,仅当做笔记吧。

    别喷我!

     

    展开全文
  • 数据库原理 并发调度的可串行性

    千次阅读 2020-03-14 11:27:33
    数据库管理系统对于并发事务的不同调度会产生不同的结果 串行调度是正确的 执行结果等价于串行调度的结果也是正确的,称之为可串行化调度 1、可串行化调度 现在有两个事务,分别包含下列操作: 事务T1:读B;...
  • 并行数据库技术分析与发展展望

    千次阅读 2014-12-17 11:51:29
    我将首先描述什么是并行数据库以及它们的典型特征;然后从存储、执行、管理等方面分析其技术要点;最后展望一下并行数据库的未来发展方向。 一、并行数据库的定义和架构特点 在维基百科上,并行数据库被定义为通过...
  • 数据库】并发调度的可串行性

    千次阅读 2018-10-22 18:44:33
    DBMS对并行事务中各指令的安排执行(调度)是随机的,而不同的调度可能会产生不同的结果。 将所有事务串行执行的调度策略一定是正确的调度策略。 如果错了,一定是事务程序逻辑上的错误,不是因调度而产生的。 以...
  • 并发(或并行)调度:多个事务从宏观上看是并行执行的,但其微观上的基本操作(读、写)则是交叉执行的。 并发调度的正确性:当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全...
  • 情况二:后面的事务覆盖:加入有三个事务,其中T1和T2分别对数据库对象X进行write操作,即分别执行了W1(X)和W2(X),然后第三个事务对数据库对象X执行了W3(X)操作,这个调度一定是串行化的,因为最终结果去绝对第三个...
  • 数据库并发控制之并发调度

    千次阅读 2018-10-25 01:08:22
    一、并发调度的可串行性 二、两段锁协议 三、封锁的粒度 四、其他并发控制机制
  • ...在2010年1月的ACM上,有...一篇文章是Google的Jeffrey Dean、Sanjay Ghemawat发表的标题为《MapReduce:一个灵活的数据库处理工具》,另一篇文章是Michael Stonebraker、Daniel Abadi、David J. DeWitt、
  • 并行数据库及其主要研究的问题

    千次阅读 2008-10-31 10:56:00
    年代后期,并行数据库技术的研究方向逐步转到了通用并行机方面,研究的重点是并行数据库的物理组织、操作算法、优化和调度策络。从 90 年代至今,随着处理器、存储、网络等相关基础技术的发展,并行数据库技术的研究...
  • 事务的并发 事务的并发是指在某一时间段内...一致性调度:如果执行一个调度能使得数据库从一个一致性状态转入另一个一致性状态,则称该调度是一个一致性调度。 可串行化调度:一组并发执行的事务,如果其一个调度与该组
  • MySQL数据库面试题(2020最新版)

    万次阅读 多人点赞 2020-03-10 17:20:40
    文章目录数据库基础知识为什么要使用数据库什么是SQL?什么是MySQL?数据库三大范式是什么mysql有关权限的表都有哪几个MySQL的binlog有有几种录入格式?分别有什么区别?数据类型mysql有哪些数据类型引擎MySQL存储...
  • 一篇文章是Google的Jeffrey Dean、Sanjay Ghemawat发表的标题为《MapReduce:一个灵活的数据库处理工具》,另一篇文章是Michael Stonebraker、Daniel Abadi、 David J. DeWitt、Sam Madden、Erik Paulson、Andrew ...
  • 数据库运行过程中,数据库管理系统需要对数据库进行保护管理,以保证数据的正确性与一致性,避免数据丢失、泄露或遭到破坏。数据库保护主要是通过并发控制、数据恢复、安全性控制和完整性控制4个方面实现的。 本章...
  • 数据库学习】数据库总结

    万次阅读 多人点赞 2018-07-26 13:26:41
    1,数据库 1)概念 数据库是长期存储在计算机内、有组织的、可共享的大量数据的集合。 常见数据库管理系统有:Access、mysql、sql server 2)特点 ①数据库数据特点 永久存储、有组织...
  • 数据库

    千次阅读 2010-04-20 13:30:00
    数据库编程总结 收藏 此文于2010-04-12被推荐到CSDN首页此文于2010-04-16被推荐到CSDN首页如何被推荐?数据库编程总结当前各种主流数据库有很多,包括Oracle, MS SQL Server, Sybase, Informix, MySQL, DB2, ...
  • C#多线程进阶(并行编程Parallel ,任务调度器 ,async/await ,线程安全(各种锁机制))
  • 第14章 并行执行并行执行(parallel execution)是Oracle企业版才有的特性(标准版中没有这个特性),最早于1994年在Oracle 7.1.6中引入。所谓并行执行,是指能够将一个大型串行任务(任何DML,或者一般的DDL)物理...
  • Android中的数据库连接池

    千次阅读 2019-11-02 20:19:14
    最近在看数据库相关的三方库的时候,我发现在Android应用开发的时候是可以并行操作数据库的读写,但Android默认的数据连接池中只有一个数据库链接。一个数据库连接能实现并发么?要是一个数据库链接可以实现并发,...
  • 数据库 - 并发控制

    千次阅读 2015-05-12 17:30:51
    并发控制机制的任务对并发操作进行正确调度 保证事务的隔离性 保证数据库的一致性多用户数据库系统的存在 允许多个用户同时使用的数据库系统 飞机定票数据库系统 银行数据库系统 特点:在同一时刻并发运行的...
  • Oracle 数据库实例介绍

    万次阅读 多人点赞 2018-11-23 15:44:13
    本章介绍 Oracle 数据库实例的原理,实例的参数文件和诊断文件,以及实例创建和数据库的打开与关闭的过程。
  • 事务调度

    千次阅读 2018-10-18 17:16:34
    1、可串行性:并行操作对并行事务的操作的调度事随机的,不同的调度可能产生不同的结果。在这些不同的调度中,肯定有些调度的结果是正确的,正确的调度有哪些 若每个事物的基本操作都串连在一起,没有其他事务的操作...
  • 数据库编程总结

    万次阅读 热门讨论 2010-04-11 20:10:00
    数据库编程总结当前各种主流数据库有很多,包括Oracle, MS SQL Server, Sybase, Informix, MySQL, DB2, Interbase / Firebird, PostgreSQL, SQLite, SAP/DB, TimesTen, MS ACCESS等等。数据库编程是对数据库的创建、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,166
精华内容 22,066
关键字:

数据库并行调度