浅谈高级数据库并发控制方法
浅谈高级数据库并发控制方法
戴志龙
(浙江财经学院金融工程专业,浙江杭州310018)
摘
本文讨论了高级数据库系统的并发控制,分析并指出传统并发控制方法的局限性以及新的并发控制的需求,列举要:
L T 和N T/PV方法,并指出将来的发展方向。并讨论了典型的适于长事务并发控制的A
高级数据库;传统;并发控制;长事务关键词:
1传统并发控制技术
维护数据库的一致性是数据库管理系统的根本任务之一。传统数据库系统维护一致性的途径是事务。事务的本质特征是其原子性,它既是逻辑上的原子单位一段相对完整任务的操作序列,又是并发控制的原子单位各事务的运行互不干扰,也是恢复的原子单位〔一个事务的运行或者成功,或者不对数据库产生任何影响〕。
传统数据库对事务的调度基于可串行化原则,只有等价于一个串行调度的调度才是一个可以保证数据库一致性的调度,结果是并发事务被一个接一个地串行运行。数据库系统并发控制的任务就是在保证数据库系统一致性的前提下,提高系统的并行性能减少系统的额外开销。传统并发控制技术可分成三大类:
1.1悲观方法其基本前提是假设数据访问的冲突频率较高。悲观并发控制使一个产生冲突的事务处于等待状态,只有当冲突消解后处于等待状态的事务才可以继续运行。实现悲观并发控制的一般方法是锁机制,二阶段锁协议(2PL )是保证事务运行可串行性的充分条件。但是在没有任何额外语义除了抽象的读写操作可供利用的情况下,2PL 又是保证事务运行可串行化的必要条件。
基本2PL 无法避免死锁的产生,消除死锁的手段是放弃事务。为了避免死锁产生时的连锁放弃,可以采用严格2PL ,即事务拥有的锁只有在事务提交或放弃后才释放。显然,这是以降低并发度为代价的。
悲观并发控制还可以利用时间戳排序法实现,这种方法可以避免死锁,却以事务的放弃为代价。
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
值进行处理)。
(3)标记:如图4(c )所示,设定区域, 用来判断两个邻接的区域能是否可以合并,一致则将两区域合并,直到不到合并为止。(为下面的小区域消除做准备)。
(4)小区域消除:如图4(d )所示,小区域消除中的思想,其实是设定一个区连通区域,把大于此区域的在图像中删除(此处主要是去掉最边上的0和100还有uA 就可以了)。
(5)扫描:如图4(e )所示,对上面图像进行扫描定下表盘最两边的刻度线上的四个点,确定两线方程,设两方程相等得出交点(表盘的圆点,既指针的下顶点)。
(6)检测:对表盘进行检测的结果显示出刻度线之间是否均匀,刻度数是否合格和指针是否偏离中心。
5结论
该算法充分利用了表盘的几何特征,首先以表盘字符特征进行定位分割,检测其字符缺陷。然后进行其刻度线检测。这样就不用考虑边框是不是完整,另外采取八邻域算法,可以有效避免刻度线的漏检, 因此具有抗干扰能力强的特点。从实验结果看, 本算法简单、快速,抗干扰能力强。达到了预期的效果。
参考文献:
[1]冈萨雷斯. 数字图像处理[M].北京:电子工业出版社,2008.
[2]孙凤杰, 郭凤顺, 范杰清等. 基于图像处理技术的表盘指针角度识别研究[J].中国电机工程学报,2005,25(16):8.
[3]张艳玲, 汪仁煌, 黄宇华. 基于综合特征的仪表盘参数符号识别技术研究[J].计算机工程与应用,2008,44(16):221-224.
[4]季厌浮, 张绍兵. 无指针式仪表表盘数字识别方法的研究[J].自动化仪表,2008,29(12):25-32.
[5]杨淑莹, 边奠英.VC++图像处理程序设计[M].北京:清华大学出版社, 2007.
[6]王成福. 电厂指针式仪表的自动识别[J].东北电力技术,2008,10(1):26-31.
(a )表盘原始图像(b )表盘二值化处理(c )表盘小区域标记
(d )小区域消除
(e )结果
图4系统处理效果图
(1)拍摄原始表盘图片,如图4(a )。(2)二值化处理:如图4(b )所示,如图把待处理的图片进行二值化使得图像中只有黑和白两种(通过固定,设定适合的灰度
趷趦
2010年第4期
多版本方法通常与锁机制或时间戳方法结合在一起使用。多版本的缺点是系统代价较高,更为严重的是它用事务的回退替代等待,作为解决冲突的根本手段,代价高昂。
1.2乐观方法其基本前提是假设数据访问的冲突频率较低。乐观并发控制允许事务先不理会冲突而运行,当事务提交时系统才进行有效性验证。系统在事务开始运行时赋予每个事务一个时间戳,事务在其生存期内对数据库应该有一个一致的视
图。
在事务提交时,系统根据时间戳检验这种数据库的一致性视图是否在事务开始和结束这段时间里改变了,如果没有改变,事务提交,否则,事务放弃。
1.3自适应并发控制自适应并发控制方法是根据事务的冲突频率选用悲观或乐观方法,有的采用事务的长短作为计算事务冲突频率的依据,有的采用数据项的访问频率作为计算事务冲突频率的依据。但是这种方法的系统代价十分高昂, 可能抵消潜在的好处。事实上, 真正使用自适应并发控制的DBM S 未见报告。
综上所述, 传统并发控制可以总结为以数据的竞争性使用为假设, 以原子化和可串行性为原理, 以等待和放弃为基本手段,是一种相对消极的方法。
2新的并发控制需求
高级数据库应用,如CAD 、
CASE ,对并发控制提出了新的需求:
2.1支持长事务。
这种事务通常持续几小时乃至几天。长事务意味着事务间冲突和死锁概率的增加。以等待和放弃为基本手段的传统并发控制技术无法满足长事务的需求。
2.2支持用户控制。在CAD 等应用领域中,用户的工作通常是交互、非确定的。并发控制机制应该为用户提供丰富的控制手段,如开始一个事务、交互地在事务中运行操作、动态重构事务、随时提交或放弃事务等。事务的非确定性意味着并发控制机制除非实际运行事务并检验它的结果,否则它无法确定事务的运行是否会破坏数据库的一致性。这可能导致下面的情形用户很有兴致地工作了一段时间,等到后来准备提交事务时才发现工作中有操作会破
坏数据库的一致性。
用户当然不希望全部放弃所做的工作,而希望能显式地取消某些操作的结果以满足数据库一致性的要求。
2.3支持协作过程。在CAD 等设计环境中,多个用户分工合作完成一项大的设计任务。这种协作过程以合作生产数据资源为特征,它不同于传统数据库资源的竞争性使用。协作既是不同于传统数据库的新的需求,也为并发控制提供了新的途径。
数据库的传统并发控制技术无法满足以上新的并发控制需求,根本原因在于没有利用应用层的语义。DBM S 将数据的访问抽象为读、写两种操作,把事务看成是由读、写操作组成的原子序列,通过串行化方法来保证并发事务的正确性。但是可串行性降低了事务的并发度,给应用带来了过多的约束。事实上,将调度的一致性等同于事务的可串行性是一个极大的限制。如果DBM S 能利用更多的应用层语义,将应用层定义的一致性约束条件作为维护数据库一致性的依据,那么就可能冲破可串行性带来的侄桔,构造出非串行化的但却是一致的调度,从根本上提高事务的并发度。
3适于长事务的并发控制方法目前,对适合于长事务并发控制方法的研究分为两大流振:其一是依然以可串行性为判断事务正确运行的标准,同时利用事务的语义+扩展可串行化技术,达到提高系统并发度的目的,作者以利它锁协议为例。其二为突破可串行性标准的限制,充分利用应用层语义和一致性谓词,构造非串行化的、维护数据库状态一致的事务经历,如基于NT /PV 模型的并发控制方法。
2010年第4期
3.1ALT 方法
ALT 方法是对2PL 方法的改进和扩展,它的基本思想是在遵守2PL 规则的同时,对长事务占用的数据项,在一旦能够确定该事务不会再使用这一数据项时,即尽早释放相应锁,以便其它事务使用,这等于放宽厂事务获得镇的条件,缓解了事务长期等待情况,它同样具有2PL 易理解、易实现,确保事务可串行运行
的优点。同样,
也存在2PL 存在的问题。为了将事务不再使用的数据项让给其它事务使用,ALT 协议在加锁(Lock )和解锁(Unlock )两种基本的并发控制操作基础
上,增加了第三种并发控制操作:赠锁(Donate
)。经过赠锁的数据项,可被其它用户使用,赠锁操作不能代替解锁操作,最终事
务必须解锁所有数据项。
而不管是否已赠锁其中任一数据项,赠锁操作的规则如下:
(1)事务只能对它们当前上锁的数据项实行赠锁操作;(2
)事务不能存取任何已被自己赠锁后的数据项。基于赠锁操作规则,ALT 协议可描述为:(1)两事务不能同时拥有同一致数据项的冲突锁,除非其中事务赠锁该数据项;
(2)若事务T i 在事务T j 之后,那么T i 必须完全在T j 之后,
直至T j 执行第一个解锁操作,
ALT 方法虽不能完全解决长事务并发控制的问题,但可明显缓解事务的长期等待。
3.2基于NT/PV模型的并发控制方法
NT/PV模型被认为是一种适于长事务的事务模型,在模型中引入了嵌套事务(Nest Transaction ),谓词(Predicates )和多版本(M ultiple Version )的概念。这正是这一事务模型名字的来历.基于NT/PV模型的并发控制方法被认为是一种适于长事务管理,突破可串行化限制,具有前途的并发控制方法。
嵌套事务是指在NT/PV模型中,每个事务都可看作由若干子事务组成,每个子事务又是一个事务。如此形成事务的嵌套
树,直至用树的叶结点代表数据库操作。
谓词用来表示数据库的一致性限制;多版本允许一数据项同时存在不同时期的多个版本值;这三个概念的存在使NT/PV模型适于描述划分长事务,有利于提高系统并发度;在NT/PV模型中,将事务的运行看作是对满足一致性谓词的数据库状态的转变,若事务的运行将数据库的状态由满足输人一致性谓词转换为满足输出一致性谓词,则为NT/PV正确运行。它可能不是一个可串行经历,但却是维护数据库状态一致的正确经历。
ALT 方法和基于NT/PV的并发控制方法,代表了两种不同
的工作成果。
前者试图改进传统方法以适应数据库应用新需求,而后者则尝试突破传统方法的局限,充分利用应用层语义,构造基于新的正确性标准的事务经历。与前者相比,这一工作更加复杂和艰难,但它为开创适应级数据库系统的并发控制新方法,提供了潜在的可能性。只是由于其复杂和不成熟而尚未得以在面向对象的数据库管理系统(OODBM S )中实现,探求有效、实用的并发控制技术,是有待我们继续努力的目标。
4总结
本文首先介绍了传统并发控制的方法以及面临的问题,对新的并发控制的需求做了简单的介绍,同时以适于长事务并发控制的方法进行了详细的介绍,以此为例,指出了并发控制的良好的发展前景。
参考文献:
[1]孙建伶, 何志均,高级数据库系统中基于语义的并发控制. 计算机科学,1994(3):21.
[2]张杰敏, 适于高级数据库并发控制的方法—利它锁. 华北工学院学报, 1999(1):20.
[3]张杰敏, 有关高级数据库系统中的并发控制问题. 华北工学院学报,
1998
(3):19.趦趹