`

并发控制原理

阅读更多
事务之间的相互影响可能导致数据库状态的不一致,即使各个事务能保持状态的正确性,而且也没有任何故障发生。因此,不同事务中各个步骤的执行顺序必须以某种方式进行规范。控制这些步骤的功能由DBMS的调度器部件完成,而保证并发执行的事务能保持一致性的整个过程称为并发控制。调度器的作用如图1所示。


   首先讨论如何保证并发执行的事务能保持数据库状态的正确性。抽象的要求称为可串行性,另外还有一个更强的、重要的条件为冲突可串行性,它是大多数调度器所真正实现的。我们考虑实现调度器的最重要技术:封锁、时间戳和有效性确认。
1.串行调度和可串行化调度
1.1 调度
   调度是一个或多个事务的重要操作按时间排序的一个序列。
   例1 考虑两个事务以及它们的动作按照某些顺序执行时的数据库的影响。T1和T2的重要动作如表1所示。
表1 两个事务
T1 T2
READ(A,t) READ(A,s)
t := t + 100 s := s*2
WRITE(A,t) WRITE(A,s)
READ(B,t) READ(B,s)
t := t + 100 s := s*2
WRTIE(B,t) WRITE(B,s)


1.2 串行调度
   如果一个调度的动作首先是一个事务的所有动作,然后是另一个事务的所有动作,以此类推,而没有动作的混合,那么我们说这一调度是串行的。
  例2 对表1中的事务而言,两个串口调度,一个是T1在T2前,而另一个是T2是T1之前,初态为A=B=25。
表2 T1在T2前的串行调度
T1 T2 A B
    25 25
READ(A,t)      
t := t + 100      
WRITE(A,t)   125  
READ(B,t)      
t := t + 100      
WRTIE(B,t)     125
  READ(A,s)    
  s := s*2    
  WRITE(A,s) 250  
  READ(B,s)    
  s := s*2    
  WRITE(B,s)   250


表3 T2在T1前的串行调度
T1 T2 A B
    25 25
  READ(A,t)    
  t := t + 100    
  WRITE(A,t) 50  
  READ(B,t)    
  t := t + 100    
  WRTIE(B,t)   50
READ(A,s)      
s := s*2      
WRITE(A,s)   150  
READ(B,s)      
s := s*2      
WRITE(B,s)     150



1.3 可串行化调度
   事务的正确性原则告诉我们,每个串行调度都将保持数据库状态的一致性。
   通常,不管数据库初态怎样,一个调度对数据库状态的影响都和某个串行调度相同,我们就说这个调度是可串行化的。
   例3 表4是例1中事务的一个调度,此调度是可串行化的,但不是串行的。表5不是可串行化的。
表5 一个非串行的可串行化调度
T1 T2 A B
    25 25
READ(A,t)      
t := t + 100      
WRITE(A,t)   125  
  READ(A,s)    
  s := s*2    
  WRITE(A,s) 250  
READ(B,t)      
t := t + 100      
WRTIE(B,t)     125
  READ(B,s)    
  s := s*2    
  WRITE(B,s)   250


表6 一个非可串行化的调度
T1 T2 A B
    25 25
READ(A,t)      
t := t + 100      
WRITE(A,t)   125  
  READ(A,s)    
  s := s*2    
  WRITE(A,s) 250  
  READ(B,s)    
  s := s*2    
  WRITE(B,s)   50
READ(B,t)      
t := t + 100      
WRTIE(B,t)     150



1.4 事务语句的影响
   事务细节确实有关系的,正如我们将在下面的例子中看到的那样。
   例4 表7,T2并非将A和B乘2,而是乘1。现在,在这一调度的结尾,A和B的值相等。
表7 一个仅仅由于事务细节行为而可串行化的调度
T1 T2 A B
    25 25
READ(A,t)      
t := t + 100      
WRITE(A,t)   125  
  READ(A,s)    
  s := s*1    
  WRITE(A,s) 125  
  READ(B,s)    
  s := s*1    
  WRITE(B,s)   25
READ(B,t)      
t := t + 100      
WRTIE(B,t)     150

   遗憾的是,调度器考虑事务所进行的计算的细节是不现实的。但是,调度器的确能看到来自事务的读写请求,于是能够知道每个事务读哪些数据库元素,以及它可能改变哪些元素。为了简化调度器的工作,通常假定:
   1)事务T所写的任意数据元素A被赋予一个值,该值以这样一种方式依赖于数据库状态,即不会发生算术上的巧合。

1.5 事务和调度的一个记法
   我们接受事务所进行的精确计算可以是任意的,那么我们不需要考虑像t := t+100这样的局部计算步骤。只有事务的读和写需要考虑。因此,我们将用一种新的记法来表示事务和调度,其中动作有rT(X)和wT(X)分别表示事务T读和写数据库元素X。
   例5  表1所示的事务可以写为:
        T1:  r1(A); w1(A); r1(B);w1(B);
        T2: r2(A); w2(A); r2(B);w2(B);
   表5中T1和T2的可串行化调度。这一调度写为:
   r1(A); w1(A); r2(A); w2(A); r1(B);w1(B); r2(B);w2(B);


为使这一记法更精确:
1)动作是形如ri(X)或wi(X)的表达式,分别表示事务Ti读或写数据元素X。
2)事务Ti是具有下标i的动作序列。
3)事务集合T的调度S是一个动作序列,其中对T中的每个事务Ti,Ti中的动作在S中出现的顺序和其在Ti自身定义出现的顺序一样。我们说S是组成它的事务动作的一个交错。

2.冲突可串行化
   我们现在将提出一个足以保证调度可串行化的条件。它基于冲突这一概念:调度中一对连续的动作,它们满足:如果它们的顺序交换,那么涉及的事务中至少有一个的行为会改变。

2.1 冲突
大多数的动作对按上面的理解并不冲突。
不同事务的任意两个动作在顺序上可以交换,除非:
1)它们涉及同一数据库元素;并且
2)至少有一个是写。

   将这一思想进行扩展,我们可以接受任一调度,进行任意非冲突的交换,目标是将该调度转换为一个串行调度。如果我们能做到这一点,那么初始的调度是可穿行化的,因为它对数据库状态的影响在我们做一个非冲突交换时是不变的。
   我们说两个调度是冲突等价的,如果通过一系列相邻的动作的非冲突化交换能将它们中的一个转换为另一个。如果一个调度冲突等价于一个串行调度,那么我们记说该调度是冲突可串行化的。
   例6   考虑例5中的调度
          r1(A); w1(A); r2(A); w2(A); r1(B);w1(B); r2(B);w2(B);
   通过交换相邻动作将冲突可串行化调度转换为串行调度
          r1(A); w1(A); r1(B);w1(B);r2(A); w2(A); r2(B);w2(B);


2.2 优先图及冲突可串行化判断
   已知调度S,其中涉及事务T1和T2,可那个还有其他事务,我们说T1优先于T2,写作T1<ST2,如果有T1的动作A1和T2的动作A2,满足:
1)在S中A1在A2前;
2)A1和A2都涉及同一数据库元素;并且
3)A1和A2至少有一个是写动作。
   这正是我们不能交换A1和A2顺序的情况。因此,在任何冲突等价于S的调度中,A1将出现在A2的前面。所以,如果这些调度中有一个是串行调度,那么该调度必然是T1在T2前。
   我可以使用优先图概括这样的先后次序。优先图中的结点是调度S中的事务。如果Ti<STj,则有一条从结点i到结点j的弧。

例7 下面的调度S涉及三个事务T1、T2和T3。
    S:r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)

判断调度S是否是冲突可串行化有一条简单的规则:
1)构造S的优先图,并判断其中是否有环。
如果有,那么S不是冲突可串行化的。如果该图是无环的,那么S是冲突可串行化的。

例8  考虑调度:
     S1: r2(A);r1(B);w2(A); r2(B);r3(A);w1(B);w3(A); w2(B)


   该图中显然有环,我们断定S1不是冲突可串行化的。


3.使用锁的可串行性实现
   设想以一种不受约束的方式进行其动作的事务的一个集合。这些动作将形成以个调度,但是这一调度不大可能是可串行化的。
   我们考虑调度器最常用的体系结构,这种结构在数据库元素上维护“锁”,以防止非可串行化的行为。
   在本节中,我们用一个(过于)简单的封锁模式来介绍封锁的概念。这种模式中只有一种锁,它是事务想要在数据库元素上执行任何操作时都必须在该数据库元素上获得的。


3.1 锁
   在图4中我们看到一个使用锁表来协助自己工作的调度器。


    当调度器使用锁时,事务在读写数据库元素以外还必须申请和释放锁。锁的使用必须在两种意义上都是正确的:一种适用于事务的结构,而另外一种适用于调度的结构。
·事务的一致性:动作和锁必须按预期的方式发生联系:
1)事务只有以前已经在数据库元素上申请了锁并且还没有释放锁时才能读或写该数据元素。
2)如果事务封锁某个数据库元素,它必须为该元素解锁。
·调度的合法性:锁必须具有其预期的含义:任何两个事务都不能封锁同一元素,除非其中一个事务已经先释放其锁。

  扩展我们先前关于动作的记法,并加入封锁和解锁动作:
li(X):事务Ti请求数据库元素X上的锁。
ui(X):事务Ti释放它在数据库元素X上的锁(解锁)。

   因此,事务的一致性条件可以表述为:“只要事务Ti有动作ri(X)或wi(X),那么前面必然有一个动作li(X)且两者之间没有ui(X),并且后面将会有一个ui(X)”。
   调度的合法性表述为:“如果调度中现有li(X)后有lj(X),那么这些动作之间的某个地方必然有一个动作ui(X)”





例9 考虑例1中介绍的事务T1和T2。
  T1:  l1(A);r1(A); A := A+100;w1(A); u1(A);l1(B);r1(B);B:=B+100;w1(B);u1(B);
   T2: l2(A);r2(A); A := A*2;w2(A); u2(A);l2(B);r2(B);B:=B*2;w2(B);u2(B);

表8 一致事务的一个合法调度;但不幸的是,它不是可串行化的
T1 T2 A B
    25 25
l1(A);r1(A);      
A := A+100;      
w1(A); u1(A);   125  
  l2(A);r2(A);    
  A := A*2;    
  w2(A); u2(A); 250  
  l2(B);r2(B);    
  B:=B*2;    
  w2(B);u2(B);   50
l1(B);r1(B);      
B:=B+100;      
w1(B);u1(B);     150



3.2 封锁调度器
  基于封锁的调度器的任务是当且仅当请求将产生合法调度时同意请求。为了帮助进行决策,调度器有一个锁表,对于每一个数据库元素,如果其上有锁,那么锁表明当前持有该锁的事务。我们将在5.2节更详细地讨论锁表的结构。

例10对来自例9的T1和T2稍作修改,其中T1和T2都在释放A上的锁之前封锁B
   T1:  l1(A);r1(A); A := A+100;w1(A); l1(B); u1(A);r1(B);B:=B+100;w1(B);u1(B);
   T2: l2(A);r2(A); A := A*2;w2(A); l2(B); u2(A);r2(B);B:=B*2;w2(B);u2(B);

T1 T2 A B
    25 25
l1(A);r1(A);      
A := A+100;      
w1(A); l1(B); u1(A);   125  
  l2(A);r2(A);    
  A := A*2;    
  w2(A);  250  
  l2(B);    
r1(B);B:=B+100;      
w1(B);u1(B);     125
  l2(B); u2(A);r2(B);    
  B:=B*2;    
  w2(B);u2(B);   250



3.3 两阶段封锁
    在一个另人吃惊的条件下,我们可以保证一致事务的合法调度是冲突可串行化的。这一条件称为两阶段封锁或2PL,在商用封锁系统中被广泛采用。2PL条件是:
   ·在每个事务中,所有封锁请求先于所有解锁请求。
因此2PL中所指的“两阶段”是获得锁的第一阶段和释放锁的第二阶段。服从2PL条件的事务被称为两阶段封锁事务或2PL事务。



本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/whyangwanfu/archive/2007/12/10/1926675.aspx
分享到:
评论

相关推荐

    mysql并发控制原理知识点

    MySQL并发控制原理是数据库系统中不可或缺的部分,它确保在多用户环境下数据的一致性和完整性。在高并发场景下,数据库必须有效地处理多个事务同时访问相同数据的情况,避免数据的不一致性和丢失更新等问题。以下是...

    SQL Server并发控制原理

    事务的原理 SQL Server锁原理及锁类型 SQL Server查询数据库所利用的锁 SQL Server数据库更新及删除所利用的锁 SQL Server数据库阻塞原因及性能优化

    数据库原理并发控制PPT学习教案.pptx

    数据库并发控制是数据库管理系统(DBMS)中确保多个事务在并行执行时保持数据完整性的重要机制。本PPT学习教案详细介绍了并发控制的基本概念和技术...掌握并发控制原理对于理解和设计高效、可靠的数据库系统至关重要。

    数据库原理第十一章并发控制PPT学习教案.pptx

    数据库并发控制是数据库管理系统中的关键组成部分,特别是在多用户环境下,保证数据一致性与事务隔离性至关重要。本章主要探讨并发控制的原理与...在设计和实施数据库系统时,理解并发控制原理及其应用是至关重要的。

    Linux课程设计 linux下多线程并发控制的机制分析

    通过这样的课程设计,学生不仅能够掌握Linux内核中的并发控制原理,还能提升在实际问题中解决问题的能力。同时,心得体会部分可以帮助学生反思学习过程,深化理论知识与实践经验的结合。 参考书籍的选择通常涵盖...

    DB2和 Oracle的并发控制(锁)的比较

    在数据库管理系统中,并发控制是确保多个用户同时访问数据库时数据完整性的重要机制。DB2和Oracle作为两大主流的关系型数据库,它们都采用了锁...理解这两种系统的并发控制原理,有助于优化数据库设计和提升系统性能。

    数据库原理与设计课件:第9章 并发控制.ppt

    "数据库原理与设计课件:第9章 并发控制" 本节课主要讲解数据库系统中的并发控制理论和技术。并发控制是数据库系统中的一种机制,用于确保多个事务并发执行时的正确性和一致性。 首先,数据库系统具有多用户特征,...

    处理多用户更新数据并发问题

    在IT行业中,尤其是在数据库系统和分布式系统的设计与开发中,多用户更新数据并发问题是一个重要的挑战。...在设计系统时,平衡性能和数据一致性至关重要,这通常需要深入理解并发控制原理,并在实践中不断优化。

    PV操作的实现(源代码+报告)

    PV操作,源自荷兰计算机科学家Edsger Dijkstra的信号量理论,是进程间通信和同步的重要工具。在操作系统中,PV操作(P操作和V操作)用于...这份资源对于学习和研究操作系统、并发编程以及多线程控制具有很高的价值。

    Hibernate事务和并发控制

    事务和并发控制是数据库管理中的核心概念,特别是在使用ORM框架如Hibernate时,理解它们的工作原理至关重要。本文将深入探讨Hibernate中的事务管理和并发控制。 首先,事务是数据库操作的基本单位,它保证了数据的...

    《数据库原理》并发操作、串行调度

    并发控制是指在多个用户并发地存取数据库时,避免数据不一致性的技术。其核心问题是对并发操作进行正确的调度,以保证数据的一致性。并发控制的主要技术是封锁和有效性确认。 二、并发操作可能会产生哪几类数据不...

    一种基于时间戳的分布式数据库并发控制方法.pdf

    接着,详细分析了锁和时间戳这两种并发控制方法的原理和优缺点。最后,详细阐述了在VS2008开发环境和SQL Server 2008平台上采用时间戳顺序方法来解决并发冲突的实现过程。 文章指出,在设计数据表时,可以通过设置...

    Java并发机制的底层实现原理.pdf

    Java通过synchronized和volatile关键字提供了一套高级并发控制机制,而处理器通过原子指令来保证基本的并发操作。比如x86架构的lock前缀指令,可以保证在执行操作时其他处理器不能访问对应的内存地址,从而实现原子...

    如何在同步过程中将数据库日志线性交易转化为并发载入

    综合以上知识点,要完成这个任务,我们需要理解数据库的事务处理机制,熟悉并发控制原理,掌握数据同步工具的使用,并具备一定的编程能力来定制和优化这个过程。同时,阅读提供的PDF文件(如何在数据库同步中将...

    并发控制指的是当多个用户同时更新行时,用于保护数据库完整性的各种技术。并发机制不正确可能导致脏读、幻读和不可重复读等此类问题。

    并发控制是数据库管理系统中至关重要的一个方面,它确保在多用户环境下,多个事务可以同时进行而不会破坏数据的完整性。...理解并发控制的原理和实践对于优化数据库性能和保证数据完整性至关重要。

    深入理解高并发编程-核心技术原理

    总的来说,这本书全面覆盖了高并发编程中的关键知识点,包括多线程原理、线程池实现、并发控制、分布式系统架构以及面试技巧,适合有志于提升并发编程能力的后端开发者阅读,尤其是对分布式锁和Java并发编程感兴趣的...

    自考数据库系统原理4375音频同步教程 6.3数据库的并发控制

    本音频同步教程——“自考数据库系统原理4375”专注于讲解6.3章节,即“数据库的并发控制”,这是一段旨在帮助自学者深入理解并发控制机制的教育资源。 在数据库系统中,当多个用户同时对数据库进行读写操作时,...

Global site tag (gtag.js) - Google Analytics