精华内容
下载资源
问答
  • 并发调度的可串行性

    千次阅读 2015-12-09 15:11:59
    并发调度的可串行性 什么样的并发操作是正确的? DBMS对并行事务中个指令的安排执行是随机的,而不同的调度可能会产生不同的结果。 将所有事务串行执行的调度策略一定是正确的调度策略。 以不同的顺序串行执行...
    并发调度的可串行性
    什么样的并发操作是正确的?
    DBMS对并行事务中个指令的安排执行是随机的,而不同的调度可能会产生不同的结果。
    将所有事务串行执行的调度策略一定是正确的调度策略。
    以不同的顺序串行执行事务也有可能会产生不同的结果,但由于不会将数据库置于不一致状态,所以都可认为是正确的。

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

    冲突操作是指不同的事务对同一个数据的读写操作和写写操作,其他操作是不冲突操作。
    一个调度Sc在保证冲突操作的次序不变的情况下,通过交换两个事务不冲突操作的次序的到另一个调度Sc',如果
    Sc'是串行的,称调度Sc为冲突可串行化的调度,一个调度是冲突可串行化,一定是可串行化的调度。

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


    保证并发操作调度正确性的方法
    封锁方法:两段锁(Two-Phase Locking,简称2PL)协议
    并发执行的所有事务均遵守两段锁协议,则对这些事务的所有并行调度策略都是可串行化的。
    即:
    (1)所有遵守两段锁协议的事务,其并行执行的结果的一定是正确的。
    (2)事务遵守两段锁协议是可串行化调度的充分条件,而不是必要条件。
    (3)可串行化的调度中,不一定所有的事务都符合两段锁协议。

    两段锁协议与防止死锁的一次锁法的比较:
    一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁,否则就不能继续执行,因此I一次封锁法遵守两段锁协议:
    但是两段所协议并不要求事务必须一次将所有要使用的数据全部加锁,因此遵守两段锁协议的事务可能发生死锁。

    封锁的粒度
    X锁和S锁都是加在某一个数据对象上的
    封锁的对象:
    逻辑单元:属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等
    物理单元:页(数据页或索引页)、物理记录等
    封锁对象可以很大也可以很小
    封锁对象的大小称为封锁的粒度
    多粒度封锁
    在一个系统中同时支持多种封锁粒度供不同的事务选择
    封锁粒度越大,系统被封锁的对象的个数越少,并发度越小,系统开销越小。
    选择封锁粒度:
    考虑封锁机构和并发度两个因素,对系统开销与并发度进行权衡。
    如:需要处理多个关系的大量元组:以数据库为封锁单位
    需要处理大量元组的用户事务:以关系为封锁单位
    只处理少量元组的用户事务:以元组为封锁单位

    多粒度封锁协议
    允许多粒度树中的每一个节点被独立的加锁
    (1)对一个节点加锁意味着这个节点的所有后羿节点也被加以同样类型的锁
    (2)在多粒度封锁中一个数据对象可能以两种方式封锁:显式封锁和隐式封锁
    显式封锁:直接加到数据对象上的封锁
    隐式封锁:由于其上级节点加锁而是该数据对象加上了锁
    显式封锁和隐式封锁的效果是一样的。



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

    万次阅读 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必须等待

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

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

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

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

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

    千次阅读 2020-03-14 11:27:33
    执行结果等价于串行调度的结果也是正确的,称之为可串行化调度 1、可串行化调度 现在有两个事务,分别包含下列操作: 事务T1:读B;A=B+1;写回A 事务T2:读A;B=A+1;写回B 不同的调度策略 2、冲突可串行...

    数据库管理系统对于并发事务的不同调度会产生不同的结果

    串行调度是正确的

    执行结果等价于串行调度的结果也是正确的,称之为可串行化调度

     

    1、可串行化调度

    现在有两个事务,分别包含下列操作:

    • 事务T1:读B;A=B+1;写回A
    • 事务T2:读A;B=A+1;写回B

    不同的调度策略

    2、冲突可串行化调度

    内涵

    • 冲突可串行化是以一个比可串行化更加严格的条件
    • 冲突操作是指不同事务对同一数据的读-写操作和写-写操作,涉及同一个数据库元素,但至少有一个是写操作,除此之外的其他操作都是不冲突操作
    • 一个调度Sc在保证冲突操作的次序不变的情况下, 通过交换两个事务不冲突操作的次序得到另一个调 度Sc ’,如果Sc ’是串行的,称调度Sc是冲突可串行 化的调度

    不能交换的操作

    • 同一事务的两个操作
    • 不同事务的冲突操作

    特点

    • 可串行化不好判定,而冲突可串行化有比较规范的判定方法
    • 若一个调度是冲突可串行化,则一定是可串行化的 调度

    • 冲突可串行化调度是可串行化调度的一个充分条件,而不是必要条件,不满足冲突可串行化的调度,可能执行结果是和串行调度是一样的,这样的调度也叫做串行化调度

    小结

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

    千次阅读 2017-12-27 15:00:12
    1.可串行化调度 ...另外,执行结果等价于串行调度的调度也是正确的,称为可串行化调度。 可串行化(Serializable)调度 多个事务的并发执行是正确的,当且仅当其结果与按某一次序串行地执行这些事务时的结果

    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的值。

    展开全文
  • 一、并发调度 并发调度啥意思? 就是当很多事务同时执行的时候应该...可串行性是并发事务正确调度的准则。 比如: 事务 T1: 读 B A=B+1;写回 A; 事务 T2: 读 A B=A+1;写回 B; 假设 A、B 的初始值都是 2,串行
  • 【数据库】并发调度的可串行性

    千次阅读 2018-10-22 18:44:33
    将所有事务串行执行的调度策略一定是正确的调度策略。 如果错了,一定是事务程序逻辑上错误,不是因调度而产生。 以不同顺序串行执行事务也有可能会产生不同结果,但由于不会将数据库置于不一致状态,所以...
  • 可串行调度:多个事务的并发执行是正确,当且仅当并发执行结果与这些事务按照某一串行顺序执行结果相同 (1) __如果两个操作X和Y,读写数据项不同,则调度事务操作顺序不会影响任何操作结果__ (2) ...
  • 在1级封锁协议中,如果是读数据,不需要加锁,所以它不能保证重复读和不读“脏”数据。 2>2级封锁协议 1级封锁协议+事务T在读取数据R前必须先加S锁,读完后即可释放S锁 2级封锁协议可以防止
  • 并发控制就是要用正确方式调度并发操作,使一个用户事务执行不受其他事务干扰,从而避免造成数据不一致 并发控制带来问题 并发操作带来数据不一致 丢失修改(Lost Update) 两个事务T1和T2读入...
  • 所带来问题是数据不一致,具体表现为:丢失更新、不重复读、读脏数据。 1、事务调度 1.1 串行调度:(Serial Schedule)是指多个事务依序串行执行,且 只有当一个事务所有操作执行完后,才执行另一个...
  • 关系的度(degree)一对一与一对多并发控制并发控制概述封锁三协议第一封锁协议第二封锁协议第三封锁协议活死锁死锁预防一次封锁(完全封锁)顺序封锁死锁诊超时法等待图法死锁解除并发调度的可串行性可串行化调度...
  • 数据库并发控制之并发调度

    千次阅读 2018-10-25 01:08:22
    一、并发调度的可串行性 二、两段锁协议 三、封锁的粒度 四、其他并发控制机制
  • 本章主要讨论事务基本概念与特性,并围绕如何保证事务ACID(即原子、一致、隔离、持久)特性详细阐述并发控制技术,同时简单介绍数据恢复基本原理和技术。 事务 事务是一系列数据库操作,是数据库应用...
  • 事务的并发 事务的并发是指在某一时间段内,多个事务同时存取相同数据库数据。 并发操作时由于不能隔离而产生问题: ①丢失修改 ②读入”脏“数据 ...可串行调度:一组并发执行事务,如果其一个调度与该组
  • Java并发编程实战-并发调度模式框架

    千次阅读 2020-03-11 09:45:48
    选择串行的方式执行任务,串行处理机制通常无法提高高吞吐率和快速响应,于是我们可以显式地为任务创建线程,为每一个请求创建一个线程来执行任务,这样可以实现更高响应。 但是这样会带来很多问题: 线程...
  • 必须保证事务并发执行正确; 必须用正确方法调度执行事务的并发操作; 这里就引入了一个概念:调度。 【1】调度调度定义 多个事务读写操作按时间排序执行序列: T1:r1(A)w1(A)r1(B)w1(B)...
  • 并发控制

    2020-05-02 15:32:37
    目录并发控制并发控制概述丢失修改不可重复读脏读封锁三级封锁协议一级封锁协议二级封锁协议三级封锁协议活锁和死锁活锁死锁死锁的预防死锁的诊断解除死锁并发调度的可串行性可串行化调度可串行性两段锁协议封锁粒度...
  • 数据库并发控制

    2011-10-16 14:12:53
    数据库并发控制 11.1 并发控制概述 11.2 封锁 11.3 活锁和死锁 11.3 并发调度的可串行性 11.5 两段锁协议 11.6 封锁的粒度
  • 一,并发控制概述 二,封锁 三,封锁协议 四,活锁和死锁 五,并发调度的可串行性 六,两端锁协议 七,封锁的粒度 八,其他并发控制机制
  • 数据库中并发操作一般分为数据级和事务级两种,由于资源竞争可能引起数据级冲突和事务级冲突,因此需要对并发执行事务转化为某个可串行调度,从而确保数据库一致。目前并发控制方法有很多,从锁和...
  • 第十一章 并发控制

    2019-12-25 14:19:58
    文章目录概述11.1 并发控制概述11.1.1 丢失修改11.1.2 不可重复读11.1.3 读“脏”数据11.2 封锁11.2.1 封锁定义11.2.2 基本封锁类型11.2.3 封锁...11.3 并发调度的可串行性11.3.1 可串行化调度11.3.2 冲突可串行化调度...

空空如也

空空如也

1 2 3 4 5 6
收藏数 114
精华内容 45
关键字:

并发调度的可串行性