精华内容
下载资源
问答
  • 数据库 - 并发调度可串行

    万次阅读 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.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)与之对应对,所以也不能画线。

    最终结果

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

    ,

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

    别喷我!

     

    展开全文
  • 并发调度可串行

    千次阅读 2017-04-10 00:12:17
    计算机系统对并发事务中并发操作的调度是随机的,而不同的调度可能会产生不同的结果,那么哪个结果是正确的,哪个是不正确的呢?  如果一个事务运行过程中没有其他事务同时运行,也就是说它没有受到其他事务的干扰...

    计算机系统对并发事务中并发操作的调度是随机的,而不同的调度可能会产生不同的结果,那么哪个结果是正确的,哪个是不正确的呢?
        如果一个事务运行过程中没有其他事务同时运行,也就是说它没有受到其他事务的干扰,那么就可以认为该事务的运行结果是正常的或者预想的。因此将所有事务串行起来的调度策略一定是正确的调度策略。虽然以不同的顺序串行执行事务可能会产生不同的结果,但由子不会将数据库置于不一致状态,所以都是正确的。
        定义 多个事务的并发执行是正确的,当且仅当其结果与按某一次序串行地执行它们时的结果相同,我们称这种调度策略为可串行化(Serializable)的调度。
        可串行性(Serializability)是并发事务正确性的准则。按这个准则规定,一个给定的并发调度,当且仅当它是可串行化的,才认为是正确调度。
        例如,现在有两个事务,分别包含下列操作:
            事务T1:读B;A=B+1;写回A;
            事务T2:读A;B=A+1;写回B;
        假设A,B的初值均为2。按T1→T2次序执行结果为A=3,B=4;按T2→T1次序执行结果为B=3,A=4。
        图8.5给出了对这两个事务的三种不同的调度策略。
        图8.5(a)和(b)为两种不同的串行调度策略,虽然执行结果不同,但它们都是正确的调度;图8.5(c)产两个事务是交错执行的;由于其执行结果与(a),(b)的结果都不同,所以是错误的调度;图8.5(d)中两个事务也是交错执行的,其执行结果与串行调度(a)执行结果相同,所以是正确的调度。
    图8.5

    http://blog.csdn.net/sxhyniulin/article/details/9087879



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

    展开全文
  • 冲突可串行化的判定

    千次阅读 2010-12-26 15:22:33
    在设计并发控制机制时,必须保证由该机制产生的调度可串行化的。在此我们只讨论冲突可串行化的判定。 二. 冲突可串行化的判定 判定方法分为两个步骤: - 步骤1:产生调度的优先图; - 步骤2:采用一个合适的...
    一.问题的提出   在数据库系统工程师的下午考试中,对事务的并发操作多次考到,且占有很高的分值。这部分知识学习不难,但考试得分不高,纠其原因是不太理解。在设计并发控制机制时,必须保证由该机制产生的调度是可串行化的。在此我们只讨论冲突可串行化的判定。
       二. 冲突可串行化的判定
      判定方法分为两个步骤:
       - 步骤1:产生调度的优先图;
      - 步骤2:采用一个合适的算法(如基于深度优先或广度优先的环检测算法,这是《图论》课程中的内容)检查优先图中是否有有向环。如果有,则该调度就不是冲突可串行化的,否则就是冲突可串行化的。
      设S是一个调度,由S构造一个有向图,称为优先图。该图由两部分G=(V,E)组成,其中V是顶点集,E是边集。顶点集由所有参与调度的事务组成。边集由满足下列三个条件之一的边Ti→Tj组成:
      - Ti的write(Q)在Tj的read(Q)之前执行;
      - Ti的read(Q)在Tj的write(Q)之前执行;
      - Ti的write(Q)在Tj的write(Q)之前执行;如果有向图中存在边Ti→Tj,则在任何与S等价的串行调度S'中,Ti都必须出现在Tj之前,即如下所示:<…, Ti,…, Tj,…>。
      注意,在画优先图时,不管有多少对冲突的指令使得存在有向边Ti→Tj,在优先图中只画一条从Ti到Tj的边,而不是多条。
      1、示例1:
      调度1如图1所示:
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图1:并发调度1
      它的优先图构造如下:
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图2:并发调度1的优先图
      因此调度1等价于串行调度。
      2、示例2
        调度2如图3所示:
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图3:调度2
      它的优先图构造如下:
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图4:调度2的优先图
      因此调度2等价于串行调度。
      3、示例3
      并发调度3如图5所示:
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图5:调度3
      它的优先图构造如下:
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图6:调度3的优先图
      因为存在有向环,所以调度8不是冲突可串行化的。
      4、示例4
      假设并发调度4的优先图如图7所示,由于图中不存在有向环,因此它是冲突可串行化的。根据图可以确定在串行调度中Ti排在最前,Tm排在最后。因此调度4等价于串行调度:或。
    冲突可串行化的判定 - johnlxj - johnlxj的博客
      图7:调度4的优先图
    展开全文
  • sql并发控制

    2016-10-25 00:49:32
    并发控制机制调度并发事务操作是否正确的判别准则是可串行并发操作的正确性则通常由两段锁协议来保证。 两段锁协议是可串行化调度的充分条件,但不是必要条件
  • 冲突可串行的判定

    万次阅读 2011-09-08 20:37:55
    我们先拿08年4月的四级数据库一道题目来分析。 首先我们要明确的是什么事冲突,简单点就是不同事务对同一事件的Read和Write...如果是并发,则T1的Read(A)在T2的Write(A)前面完成,如果是串行T1->T2,明显T1的Read
  • 并发调度的正确性:当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全一致,则说调度是正确的。 可串行性: 如果不管数据库初始状态如何,一个调度对数据库状态的影响都...
  • JAVA并发十二连招,你能接住吗?
  • 导读1.概览 2.事务 3.事务调度可串行性 4.并发控制的两个大问题
  • MySQL_并发控制复习

    2020-06-08 09:46:49
    这里写自定义目录标题事务的概念事务的宏观性和微惯性事务的特性不一致性的三种情况事务的特性:ACIDDBMS对事务的控制事务调度可串行性(1)基本概念(2)一种简单的事务调度的标记模型(3)冲突可串行性 ...
  • Java并发

    2021-03-20 13:52:54
    2.1 JDK7 JDK7中的 ConcurrentHashMap 使用 Segment + HashEntry 分段锁实现并发,它的缺点是并发程度是由Segment 数组个数来决定的,并发度一旦初始无法扩容,扩容的话只是HashEntry的扩容。Segment ...
  • 文章目录概述为什么要进行并发控制三种典型的不一致引入并发控制什么是事务事务的基本概念事务的宏观特性(程序员眼中的事务)事务的微观特性(DBMS看到的事务)事务的特性【TODO:深入阐释】事务的特性: ACIDDBMS对...
  • 数据库系统并发控制基本概念三种不一致现象 丢失修改:非互斥的修改 不能重复读:两次读结果不一致 脏读:读到错误的值 数据一致性对共享事务应该反映出一致的状态事务一系列操作作为一个整体进行操作和控制 应用...
  • java并发知识

    2021-01-06 14:44:03
    2.1 JDK7 JDK7中的 ConcurrentHashMap 使用 Segment + HashEntry 分段锁实现并发,它的缺点是并发程度是由Segment 数组个数来决定的,并发度一旦初始无法扩容,扩容的话只是HashEntry的扩容。 Segment ...
  • mysql并发相关知识梳理 1.事务隔离级别 事务隔离级别 脏读 不重复读 幻读 REPEATABLE READ InnoDB 默认隔离级别。 同一事务内的一致读操作读取由第一次读操作建立的快照 。对应普通查询, 这些SELECT语句...
  • 谈谈那些年我们装B的并发编程 每个人对并发编程的理解会有差异,但是终极目标始终是追求尽可能高的处理性能。那么如何尽可能的提升处理性能呢? 我们可以从单核,多核,并发,并行的基础出发。首先,介绍下基础...
  • 封锁粒度与系统的并发度和并发控制的开销密切相关 封锁的粒度越大,数据库所能够封锁的数据单元就越来越少,并发度就越小,系统开销也越小。 封锁的粒度越小,并发度越高,但是系统开销也就越大。 封锁粒度越小,...
  • JAVA虚拟机允许一个应用拥有多个并发执行的线程 每个线程都有一个优先级,高优先级的线程要优先于低优先级的执行 1-10的优先级 1最低 如果当一段代码创建了一个线程 那么这个线程的优先级和这个代码的线程的...
  • 并发调度的正确性:不管数据库初始状态,一个调度对数据库状态的影响都和某个串行调度相同,则说明这个调度是可串行化的。 冲突:调度中以对连续的动作,它们满足:如果它们的顺序交互,那么设计的事务中至少有一个...
  • 并发调度的正确性:当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得到的新数据库完全一致,则说调度是正确的 可串行性:如果不管数据库初始状态如何,一个调度对数据库状态的影响都和...
  • 并发编程重点: 并发编程:线程、进程、队列、IO多路模型 操作系统工作原理介绍、线程、进程演化史、特点、区别、互斥锁、信号、 事件、join、GIL、进程间通信、管道、队列。 生产者消息者模型、异步模型...
  • 数据库期末

    2021-01-07 16:24:00
    2018年数据库原理 一、简答题**为什么要在数据库中引入...****为什么要数据库的调度进行可串行化判别,其实际意义是什么?****若对数据库进行BCNF范式的分解,从而导致没有保持依赖,在数据库中要如何解决***...
  • 2.1 JDK7 JDK7中的 ConcurrentHashMap 使用 Segment + HashEntry 分段锁实现并发,它的缺点是并发程度是由Segment 数组个数来决定的,并发度一旦初始无法扩容,扩容的话只是HashEntry的扩容。 Segment 继承自 ...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 323
精华内容 129
关键字:

并发调度可串行化判别