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

    千次阅读 2017-12-27 15:00:12
    1.可串行化调度 数据库管理系统对并发事务不同的调度可能会产生不同的结果,比如两个事务T1和T2,先执行T1或者先执行T2产生的结果可能是不一样的。由于串行调度没有事务间的相互干扰,所以串行调度是正确的。另外,...

    1.可串行化调度

    数据库管理系统对并发事务不同的调度可能会产生不同的结果,比如两个事务T1和T2,先执行T1或者先执行T2产生的结果可能是不一样的。由于串行调度没有事务间的相互干扰,所以串行调度是正确的。另外,执行结果等价于串行调度的调度也是正确的,称为可串行化调度。

    可串行化(Serializable)调度

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

    可串行性(Serializability) 

    可串行性是并发事务正确调度的准则。可串行性调度规定,一个给定的并发调度,当且仅当它是可串行化的,才认为是正确调度。

    比如,两个事务的并发调度的某一执行方式,与先执行T1后执行T2(或先执行T2后执行T1)的结果是一样的,称这一调度符合可串行化调度。

    并发控制除了要保证数据的一致性之外,还要保证事务的调度是可串行化调度。

    2.冲突可串行化调度

    冲突可串行化,是一个比可串行化更严格的条件!

    冲突操作:是指不同的事务对同一数据的读写操作和写写操作:

    Ri(x)与Wj(x) /*事务Ti读x,Tj写x,其中i≠j*/

    Wi(x)与Wj(x) /*事务Ti写x,Tj写x,其中i≠j*/

    冲突操作的特点:涉及同一个数据库元素, 并且至少有一个是操作。

     

    不冲突操作:

    ri(X); rj(X) 两个相同对象的读操作不冲突  

    wi(X); rj(Y), X不等于Y,两个不同对象的操作不冲突

    wi(X); wj(Y), X不等于Y,两个不同对象的操作不冲突

    不能交换(Swap)的动作:

    同一事务的两个操作不能交换;

    不同事务的冲突操作不能交换;

    例如:Ri(x)与Wj(x)

       Wi(x)与Wj(x)

     

    冲突可串行化

    一个调度Sc在保证冲突操作的次序不变的情况下,通过交换两个事务不冲突操作的次序得到另一个调度Sc’,如果Sc’是串行的,称调度Sc是冲突可串行化的调度。若一个调度是冲突可串行化,则一定是可串行化的调度。

    [例] 有3个事务的一个调度r3(B) r1(A) w3(B) r2(B) r2(A) w2(B)r1(B) w1(A),判断该调度是否是冲突可串行化的调度。

    解:Sc1 = r3(B) r1(A) w3(B)r2(B) r2(A) w2(B) r1(B) w1(A)

    由于r1(A)和w3(B)是对不同事务间的操作,所以不冲突,两个事务可以交换,由此得到:

    r3(B) w3(B) r1(A) r2(B)r2(A) w2(B) r1(B) w1(A)

    由于r1(A)和r2(B)r2(A) w2(B),要么都是对同一操作的读操作,要么是对不同对象的读写操作,所以不冲突,r1(A)可以与r2(B) r2(A) w2(B)交换,因此得到:

    r3(B) w3(B) r2(B) r2(A) w2(B) r1(A)r1(B) w1(A)

    所以:  Sc2 = r3(B) w3(B) r2(B) r2(A)w2(B) r1(A) r1(B) w1(A) ----> T3 T2 T1

    因此Sc1是冲突可串行化的调度。

    再例如:

    Sd=r1(A)w1(A)r2(A)w2(A)r2(B)w2(B)r1(B)w1(B)

    此例无论如何都不能通过无冲突交换将Sd变换为串行调度,因此Sd不是冲突可串行化的调度。

    3.可串行化调度与冲突可串行化调度之间的关系

    冲突可串行化调度一定是可串行化调度,但冲突可串行化调度只是可串行化调度的充分条件,不是必要条件。还有不满足冲突可串行化条件的可串行化调度。

    [例]有3个事务,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的值。

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

    2019-10-08 09:49:37
    可串行化:多个任务并发执行是正确的,当且仅当起结果与按某种次序串行执行这些任务时产生的结果一样,称这种调度策略为可串行化调度。 冲突操作:不同任务对同一数据的读写操作和写写操作,其它任务都是不冲突的。...

    可串行化:多个任务并发执行是正确的,当且仅当起结果与按某种次序串行执行这些任务时产生的结果一样,称这种调度策略为可串行化调度。

    冲突操作:不同任务对同一数据的读写操作和写写操作,其它任务都是不冲突的。

    冲突可串行化:冲突操作的顺序是不能调换的,不冲突操作可以调换顺序。这样的调换之后,调度仍然是串行的,所以叫冲突可串行化的调度。

    冲突可串行化是可串行化的充分条件,不是必要条件,所以冲突可串行化的一定是可串行化的调度,但是可串行化的调度不一定是冲突可串行化的调度,还有不满足冲突可串行化的客串性话调度。

    两段锁协议:满足1)一个任务对任何数据进行读、写之前,首先要获得对该数据的锁,2)释放一个锁之后,进入释放阶段,就不能再继续获得新的锁了。也就是说把锁的过程分为获得锁(扩展阶段)和释放锁(收缩阶段)两个阶段,且两个阶段没有重叠区。

    可以证明,遵循两段锁的调度是是可串行化调度的充分条件。

    转载于:https://www.cnblogs.com/JMLiu/p/8410761.html

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

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

    最终结果

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

    ,

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

    别喷我!

     

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

    千次阅读 2020-03-14 11:27:33
    执行结果等价于串行调度的结果也是正确的,称之为可串行化调度 1、可串行化调度 现在有两个事务,分别包含下列操作: 事务T1:读B;A=B+1;写回A 事务T2:读A;B=A+1;写回B 不同的调度策略 2、冲突可串行...
  • DF113 证明步骤: 1.以两个并发事务情况为例证明,推导到多个事务; 2.列举出两个事务发生不可串行化时...3.针对2中的两种情况,证明若T1和T2遵守两段锁协议,在不发生死锁的情况下,则它们的调度可串行化的。 ...
  • 如果改变顺序之后执行的结果和串行调度的执行结果一致,那么就说这种调度可串行化调度串行性是并发事务正确调度的准则。 比如: 事务 T1: 读 B A=B+1;写回 A; 事务 T2: 读 A B=A+1;写回 B; 假设 A...
  • 可串行化调度:多个事务的并发执行是正确的,当且仅当并发执行的结果与这些事务按照某一串行顺序执行的结果相同 (1) 如果两个操作X和Y,读写的数据项不同,则调度中的事务操作顺序不会影响任何操作结果 (2) 当两个...
  • 【数据库】并发调度可串行

    千次阅读 2018-10-22 18:44:33
    将所有事务串行执行的调度策略一定是正确的调度策略。 如果错了,一定是事务程序逻辑上的错误,不是因调度而产生的。 以不同的顺序串行执行事务也有可能会产生不同的结果,但由于不会将数据库置于不一致状态,所以...
  • .3)是解决可串行化调度较好的方法之一,但满足可串行化调度可能会出现死锁并发控制中要研究的一个重要课题。.2:96 网并发、异步、分布式系统的一种形式化方法,已被许多文献用于描述和分析数据库系统中的并发控制...
  • 关系的度(degree)一对一与一对多并发控制并发控制概述封锁三协议第一封锁协议第二封锁协议第三封锁协议活死锁死锁预防一次封锁(完全封锁)顺序封锁死锁诊超时法等待图法死锁解除并发调度串行性可串行化调度...
  • 延续上篇博文一文读懂Spring事务和MySQL...必须用正确的方法调度执行事务的并发操作; 这里就引入了一个概念:调度。 【1】调度调度定义 多个事务的读写操作按时间排序的执行序列: T1:r1(A)w1(A)r1(B)w1(B)...
  • 设数据项x,y存放在S1场地,u,v存放在S2场地,有分布式事务T1和T2,T1在S1场地上的操作为R1(x)W1(x)R1(y)W1(y),T2在S1...对下情况1和2各举出一种并发历程,如果是串行化的,指出事务的执行次序。对第三种情况,给出符
  • 一些常用的关于数据库并发操作、串行调度的习题及其答案。
  • 可串行化调度的概述

    千次阅读 2020-12-09 08:57:14
    串行化调度是正确 对于串行调度,各个事务的操作没有交叉,也就没有相互干扰,当然也不会产生并发所引起的。如前所述,事务对数据库的作用是将数据库从一个一致的状态...可串行化调度当然也保持数据库的一致状态 ...
  • 在1级封锁协议中,如果是读数据,不需要加锁的,所以它不能保证重复读和不读“脏”数据。 2>2级封锁协议 1级封锁协议+事务T在读取数据R前必须先加S锁,读完后即可释放S锁 2级封锁协议可以防止
  • 并发操作进行正确调度;保证事务的隔离性;保证数据库的一致性 数据不一致性:由于并发操作破坏了事务的隔离性 并发控制就是要用正确的方式调度并发操作,使一个用户事务的执行不受其他事务的干扰,从而避免...
  • 判断冲突可串行化

    万次阅读 多人点赞 2018-03-18 22:21:01
    这种并发调度被称为可串行化调度。 可串行化是并发事务正确调度的基本准则。对于一个并发调度,当且仅当它是可串行化的时候,才被认为是正确调度。 本文主要讲解判断可串行化调度的充要条件。 1.冲突操作指的是...
  • 数据库并发控制之并发调度

    千次阅读 2018-10-25 01:08:22
    一、并发调度可串行性 二、两段锁协议 三、封锁的粒度 四、其他并发控制机制
  • 什么是可串行化MVCC

    万次阅读 2020-11-25 18:27:23
    这种调度称为可串行化调度。 通过时间戳的调度规则通过比较时间戳来判定读写请求是否被允许。与封锁相比,时间戳规则采取一种乐观的方式,假设事务所有操作都是串行的,只有操作确实导致了非可串行化
  • 数据库保护主要是通过并发控制、数据恢复、安全性控制和完整性控制4个方面实现的。 本章主要讨论事务的基本概念与特性,并围绕如何保证事务的ACID(即原子性、一致性、隔离性、持久性)特性详细阐述并发控制技术,同时...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,390
精华内容 15,756
关键字:

并发调度的可串行化