（计算机应用技术专业论文）嵌入式实时数据库系统并发控制技术.pdf

摘要 嵌入式实时数据库系统是指可在嵌入式设备上独立运行的一种实时数据库系 统，既具有嵌入式系统的特点，又具有实时数据库系统的特点。相对于普通的实 时事务来说，嵌入式实时数据库系统中的实时事务必须具备在无人工干预下运行 的能力，为此，事务需要具备功能替代性和补偿性，其中，功能替代性为事务的 执行提供了多条路径，提高了事务的适应能力和应变能力，从而提高了事务的成 功率。补偿性可以减轻或消除天折的硬实时事务对外部环境的影响，从而提高了 系统的可靠性。功能替代性和补偿性是嵌入式实时数据库系统中实时事务的重要 特点，同时也给实时事务处理技术带来了新的挑战。 本文所研究的是嵌入式实时数据库系统并发控制问题。首先描述了基于替代 补偿的实时事务模型，然后探讨了具有功能替代性和补偿性的实时事务并发控制 的新特点，最后指出了本文的研究重点是在无冲突并发控制的基础上对实时事务 并发控制问题进行进一步探讨，从而解决无冲突替代不存在条件下的并发控制问 题。 本文在基于替代补偿的实时事务模型的基础上提出一种新的实时事务并发控 制协议；a c b a s e dc c p 协议。该协议将基于替代辟h 偿的实时事务并发控制分成了 五个步骤，即：操作对象分析、相容性分析、替代选择、冲突处理和补偿处理。 a c b a s e dc c p 协议的主要研究对象是硬实时事务之间的冲突问题，提出了一套新 的冲突处理方法，旨在通过替代降低事务天折的概率，提高了实时事务的成功率。 a c - b a s e x ic c p 协议还充分利用了实时事务可补偿的特性，当硬实时事务中的某替 代必须夭折时，采用立即补偿的方式来消除夭折的替代对外部环境造成的影响， 提高了系统的可靠性。 论文还在l i n u x 系统上对嵌入式实时数据库系统的整体结构进行了重新设计， 并对嵌入式实时数据库系统结构的一些主要特点做了详细阐述。 关键词：嵌入式实时数据库系统，并发控制，替代，补偿 a b s t r a c t e m b e d d e dr e a l - t i m ed a t a b a s es y s t e mi so n eo fr e a l - t i m ed a t a b a s es y s t e m st h a tc a n r u ni n d e p e n d e n t l yo ne m b e d d e dd e v i c e s ，i th a st h ec h a r a c t e r so f n o to n l yt h ee m b e d d e d s y s t e mb u t a l s ot h er e a l - t i m ed a t a b a s es y s t e m c o m p a r e dw i t l l p l a i nr e a l - t i m e t r a n s a c t i o n ，t h er e a l - t i m et r a n s a c t i o no ft h ee m b e d d e dr e a l t i m ed a t a b a s es y s t e mm u s t h a v et h ea b i l i t i e so f a u t o m a t i c a l l yr u n n i n gw i t h o u th u m a ni n t e r r u p t ，t h e r e f o r e ，f u n c t i o n a l t e r n a t i v ec h a r a c t e r i s t i ca n dc o m p e n s a b i l i t ys h o u l db ea d o p t e di n t ot h er e a l - t i m e l r a n s a c t i o nm o d e l n ef o r m e rm a k e st r a n s a c t i o ne x e c u t i o nh a v em a n yr o u t e ss oa st o i m p r o v et h es u i t a b i l i t yo f r e a l - - t i m et r a n s a c t i o n , t h e r e b ya d v a n c i n gs u c c e s s f u l r a t i oo f r e a l - t i m et r a n s a c t i o n a n dt h el a t t e rc a na l l e v i a t eo re l i m i n a t et h ei n f l u e n c et oe x t e r n a l e n v i r o n m e n tc a u s e db yd e f e a t e dh a r dr e a l - t i m et r a n s a c t i o n s ，i m p r o v i n gr e l i a b i l i t yo f t h e s y s t e m 码e f u n c t i o na l t e r n a t i v ec h a r a c t e r i s t i ca n dc o m p e n s a b i l i t ya r eb e t ht w o i m p o r t a n t c h a r a c t e r i s t i c so fe m b e d d e dr e a l - t i m ed a t a b a s es y s t e m ，a n db r i n gn e w c h a l l e n g et ot h er e a l - t i m et r a n s a c t i o np r o c e s s i n gt e c h n i q u e s t h i sp a p e rm a i n l ys t u d i e so nt h ep r o b l e m so fc o n c u r r e n c yc o n t r o lt h a ta r es u i t e d f o re m b e d d e dr e a l - t i m ed a t a b a s es y s t e mb a s e do na l t e r n a t i v e c o m p e n s a t i o n f k s t l y d e s c r i b e st h er e a l - t i m et r a n s a c t i o nm o d e l a n dt h e nd i s c u s s c st h en e wc h a r a c t e r so f c o n c u r r e n c yc o n t r o lf o rr e a l t i m et r a n s a c t i o nw h i c h h a sa l t e r n a t i v ea n dc o m p e n s a t i o n , a tl a s t , p o i n t so u tt h em a i nt a s ko ft h i sp a p e rw h i c hi st oc a f l yo nr e s e a r c h i n gt h e p r o b l e mo f c o n c u r r e n c yc o n t r o la tt h eb a s eo f t h ec o n f l i c t - f r e ec o n c u r r e n c yc o n t r o l ，a n d t or e s o l v et h ep r o b l e mo fc o n c u r r e n c yc o n t r o lu n d e rt h ec o n d i t i o nt h a tc o n f l i c t - f r e e a l t e m a t i v ed o s en o te x i s t a c c o r d i n gt ot h er e a l - t i m et r a n s a c t i o nm o d e lb a s e do na l t e r n a t i v e c o m p e n s a t i o n ， t h i sp a p e rp u t sf o r w a r dan e wc o n c u r r e n c yc o n t r o lp r o t o c o la c b a s e dc c pf o r r e a l t i m et r a n s a c t i o n a c b a s e dc c pd i v i d e st h ec o n c u r r e n c yc o n t r o lo fr e a l t i m e t r a n s a c t i o nb a s e do na l t e r n a t i v e c o m p e n s a t i o ni n t of i v es t e p s ，w h i c ha r ea n a l y z i n gt h e o p e r a t i n go b j e c t ，a n a l y z i n g t h ec o m p a t i b i l i t y , s e l e c t i n ga l t e m a t i v e , p r o c e s s i n gt h e c o n f l i c ta n dp r o c e s s i n gt h ec o m p e n s a t i o n a n dt h em a i nr e s e a r c ho b j e c to fa c - b a s e d c c pi st h ec o n f l i c tp r o b l e mb e t w e e nh a r dr e a l - t i m et r a n s a c t i o n s s oas u i to fn e w m e t h o dt op r o c e s st h ec o n f l i c ti sp r o p o s e di na c b a s e dc c p , w i t ht h ep u r p o s eo f r e d u c i n gt h ep r o b a b i l i t yo fa b o r t i n gt h et r a n s a c t i o nb ys e l e c t i n ga n o t h e ra l t e r n a t i v et o l u l l ，a n dt h en e wm e t h o de n h a n c e st h es u c c e s s f u l r a t i oo ft h er e a l - t i m et r a n s a c t i o n a c b a s e dc c pa l s om a k e sf u nu s eo f t h ec o m p e n s a b i l i t yo f t h er e a l t i m et r a n s a c t i o n i f 2 o n ea l t e r n a t i v eo ft h eh a r dt r a n s a c t i o nm u s tb ea b o r t e d t h ei n f l u e n c et oe x t e n l a l e n v i r o n m e n tc a nb ee l i m i n a t e db ys c h e d u l i n gt h ec o m p e n s a t i o nt a s ki m m e d i a t e l y , s ot h e r e l i a b i l i t yo f t h es y s t e mi se n h a n c e d t h i sp a p e ra l s or e - d e s i g nt h eg e n e r a ls t r u c t u r eo ft h ee m b e d d e dr e a l t i m ed a t a b a s e s y s t e m ，s o m em a i nf e a t u r e so f w h i c h a l ee x h a u s t e dd e t a i l e d k e y w o r d s ： e m b e d d e dr e a l - t i m ed a t a b a s es y s t e m , c o n c u r r e n c yc o n t r o l ， a l t e m m n e ， c o m p e n s a t i o n 3 独创性声明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含 为获得江西财经大学或其他教育机构的学位或证书所使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了睨确 的说明并表示了谢意。 签名： 蓝盔血 日期： 生：f 2 ：塑 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存沦文。 ( 保密的论文在解密后遵守此规定) 签名：盐耸导师签缉吼丝厶掣 1 引言 1 引言 1 1 研究背景 2 1 世纪，人类进入了“后p c ”时代，各种嵌入式产品得到了广泛应用，嵌入式 软件开发也越来越受到关注。对于嵌入式系统而言，数据仍然是最重要的元素和 处理对象。所以，嵌入式环境下的数据管理问题成了嵌入式系统构建的重要环节， 这也是嵌入式数据库系统产生的根本原因，嵌入式数据库系统要求在最小的干涉 和最小的系统影响下进行数据存储和恢复。由于嵌入式数据库系统常常要对环境 做出实时反应，提供实时或近似实时的嵌入式处理，嵌入式实时数据库系统便成 为我们的研究重点。 嵌入式实时数据库系统可在嵌入式设备上独立运行，用以处理大量的、时效 性强且有严格时序的数据，它以高可靠性、高实时性和高信息吞吐量为目标，其 数据的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间【1 1 1 2 1 f 1 1 4 1 1 5 1 。不 难看出，嵌入式实时数据库系统应该是嵌入式数据库系统和实时数据库系统相结 合的产物，同时具备实时性、主动性和嵌入式的特点，是一个新的研究方向。 嵌入式实时数据库系统的研究尚处于初级阶段，尽管市面上有一些嵌入式数 据库系统和实时数据库系统的产品，但是，还没有出现嵌入式实时数据库的成熟 产品嘲。主要存在两方面的问题，一方面，目前的嵌入式数据库系统不具备实时性。 另一方面，目前的实时数据库系统又由于难以保证高成功率而不能适应嵌入式环 境，除此之外，嵌入式实时数据库系统还应该具备一定的主动性，能捕获特殊事 件并做出相应反应。 嵌入式实时数据库系统是一项非常具有前景的研究领域。其高可靠性、实时 和主动性的特点主要依赖于事务处理技术，并发控制就是其中一个重要方面，这 也是本文研究的主要内容。 目前，对嵌入式实时数据系统并发控制的研究还比较少，但是在实时数据库 的并发控制方面，国内外已经取得了不少的研究成果，主要是集中在对正确性标 准的探讨和对传统的并发控制协议进行实时性改造上。在正确性标准的探讨方面， 主要的理论成果有：e 一可串行化并发控制【7 j 【8 1 1 9 、_ 一可串行化并发控制【、基于 语义的并发控制l ，准一致性可串行化并发控制【2 】；在对传统的并发控制机制进 行实时性改造方面，主要的理论成果有：基于2 p l 的实时并发控制协议，如： 2 p l h p 1 3 1 、2 p l p l 堋、2 p l c p i l l 4 1 、2 p l ，p c l l 5 】等，基于o c c 的实时并发控制协 议，如：o c c b c i 、o c c f v 、o c c b v l j “、o c c - s a c r i f i c e 、o c c w a i t 、 o c c w a i t - x i 闱、o c c - t i l l 9 1 1 2 0 1 、o c c d a l 2 ”、o c c d a t i l 2 2 1 、o c c p d a t i l 2 3 、 o c c r p d a t i l 2 4 1 1 2 ”等，基于s c c 的并发控制协议，如：s c c 2 s 、s c c k s 、s c c d c 、 嵌入式实时数据库系统并发控制技术 s c c v w 、a v c c 【2 6 】【2 7 】【2 8 】【2 9 】 3 0 l 、s c c d p l 3 1 等。另外，还有基于资源预报的并发 控制协议【3 2 1 、多版本并发控制协议 3 3 】p 4 】、两级并发控制协议【3 5 1 d 6 1 1 3 7 1 3 5 1 等。 以上的并发控制协议基本上从非实时数据库系统中将假设和结果转换过来， 带来的问题是人们在设计并发控制协议时，将注意力集中在时间限制上，并不适 应于嵌入式实时数据库系统1 6 】。 传统的实时并发控制协议不能适应于嵌入式实时数据库系统是因为传统的实 时事务模型不能为事务提供高可靠性，为此，还必须重新探讨嵌入式实时数据库 系统的事务模型。夏家莉教授提出了基于功能替代辟h 偿的实时事务模型及其相关 处理技术【6 】【3 9 1 1 4 0 1 1 4 1 1 1 4 2 1 1 4 3 1 1 4 q 4 5 1 1 4 6 1 1 4 7 1 ，该事务模型支持功能替代性和补偿性，功能替 代性使事务具有多条执行路径，从而提高了事务的成功率，而补偿性可以减轻或 消除夭折的硬实时事务对外部环境的影响，提高了嵌入式实时数据库系统的可靠 性。功能替代性和补偿性使得实时事务能更好的适应嵌入式环境中，但是，也给 并发控制带来新的问题。 具有功能替代性和补偿性的实时事务的并发控制更加复杂，不仅有事务级的 并发控制，还有替代级的并发控制，并且补偿也要参与并发控制，所以需要基于 这些新的特点对并发控制机制进行研究。 在基于替代补偿的实时事务并发控制方面，夏家莉教授也提出了f h c 并发控 制策略和无冲突并发控制协议c c c p 【4 s 】，f h c 策略提出了硬实时事务多个替代并 发执行的思想，c c c p 协议的重点在于选择一个无冲突替代参与并发控制，而无冲 突替代存在只是一个理想的情形，还必须解决无冲突替代不存在的情形，所以， 本文是基于c c c p 协议的基础上对嵌入式实时事务并发控制技术的进一步研究， 研究的重点是，如果潜在的冲突不可避免，系统应该选取什么样的替代代表事务 参与并发执行，以及当冲突实际发生时应该怎样处理冲突，怎样把补偿任务考虑 到并发控制中来。 1 2 本文的主要工作 本文基于实时事务替代性和补偿性的特点，在分析现有典型的实时并发控制 协议的基础上，探讨既能很好地满足实时性又能更好地适应嵌入式环境的并发控 制协议。具体说来，本文所做的主要工作如下： 本文最主要的贡献在于在基于替代辟 偿的实时事务模型的基础上提出一种新 的实时事务并发控制协议：a c b a s e dc c p 协议。该协议是在无冲突替代不存在条 件下对实时事务并发控制的进一步研究，将基于替代幸h 偿的实时事务并发控制分 为五个步骤，即操作对象分析、相容性分析、替代选择、冲突处理和补偿处理。 a c b a s e dc c p 协议的主要研究对象是硬实时事务之间的冲突问题，提出了一套新 1 引言 的冲突处理方法，旨在通过替代降低事务夭折的概率，提高了实时事务的成功率。 a c b a s e dc c p 协议还充分利用了实时事务可补偿的特性，当硬实时事务中的某替 代必须夭折时，采用立即补偿的方式来消除替代的夭折对外部环境造成的影响， 提高了系统的可靠性。a c b a s e dc c p 协议适用于嵌入式实时数据库系统中。 论文的最后在l i n u x 系统上对嵌入式实时数据库系统的整体结构进行了重新 设计，并对嵌入式实时数据库系统结构的一些主要特点做了详细阐述。 1 3 论文结构安排 论文分为六章，各章的具体内容如下： 第一章为引言。简单地介绍了本文的研究背景、主要工作以及结构安排。 第二章实时事务并发控制综述。综述目前实时事务并发控制方面的主要研究 成果，着重对一些主要的实时并发控制协议进行了描述和分析，其中有些协议被 借鉴到嵌入式实时并发控制协议中。 第三章初步探讨了基于替代牢 偿的实时事务并发控制问题。首先介绍了基于 替代辛 偿的实时事务模型，然后阐述了替代和补偿给实时事务并发控制带来的新 特点。 第四章提出了一种基于替代辟h 偿的实时事务并发控制协议a c - b a s c dc c p ，该 协议研究了无冲突替代不存在条件下的并发控制问题，重点设计了一套新的冲突 处理方法，以处理硬实时事务之间的冲突问题。 第五章是嵌入式实时数据库系统。在l i n u x 系统上对嵌入式实时数据库系统的 整体结构进行了重新设计，并对嵌入式实时数据库系统结构的一些主要特点做了 详细阐述。 第六章总结全文并提出下一步的工作。 嵌入式实时数据库系统并发控制技术 2 实时事务并发控制综述 2 1 并发控制的标准 实时数据库系统是指事务和数据都具备定时限制的数据库管理系统，系统的 正确执行既要满足逻辑约束，又要满足时间约束。与传统数据库不同，实时数据 库中数据一致性标准有所放松。传统的数据一致性标准是可串行化，并发控制的 目的是保证数据的逻辑一致性，具有a c i d 特性。由于实时数据库系统必须满足 数据的时态一致性，则此标准过于严格，因为在并发控制算法中，由于事务的重 启或者受阻，可能导致无法预计的延迟。为了使尽可能多的事务满足截止期，需 要放松正确性标准以满足或兼顾时间一致性要求。 比较流行的适合于实时数据库的并发控制正确性标准有： ( 1 ) 8 一可串行化并发控制。8 可串行化( e p s i l o n - s e r i a l i z a b i l i t y ) 是事务处 理中的一种正确性标准，它是一种更一般的误差受跟的串行化。对于查询事务， 它允许访问不一致数据，并控制不一致性的程度，使误差限制在一个指定范围， 而使数据最终能达到一个一致性的状态；而对于更新事务，只能遵循严格的可串 行化协议。- 可串行化需要数据库的数据空间是一可度量空间，使用e 一可串行化 放松逻辑一致性要求以期满足时间一致性要求啊【8 】【9 】。 ( 2 ) _ 一可串行化并发控制。蝴串行化是基于“相似性”概念对正规可串行 化的扩展。相似性概念是指在时间和精确性上有略微差别的数据可以彼此替换地 作为事务的可读数据。“相似是内在地依赖于应用的概念，不同的事务对同样的数 据对象可以有不同的相似性要求，两个值有多大的“细微差别”才能算相似，应依特 定的应用而定【l 。 ( 3 ) 基于语义的并发控制。可串行化不是维护逻辑一致性的唯一方法，还可 以依据事务在数据库中的操作语义将事务分类，使用兼容性而非可串行化作为正 确性标准。在r h o d ei s l a n d 大学开发的r t s o r a c 系统中使用了基于语义的并发控制 技术【1 l 】。 2 2 基于2 p l 的并发控制协议 与传统数据库系统不同，在实时数据库系统中，事务都具有优先级。当个 低优先级事务锁住了某个数据之后，那么高优先级事务再申请该数据项的不相容 锁时，高优先级事务将被阻塞，结果可能引起高优先级事务错过期截止期。也就 是说，将2 p l 不加修改地运用到实时事务的并发控制中来，必然引发这种严重的 优先级倒置问题。 4 2 实时事务并发控制综述 在实时数据库中，为了解决死锁和优先级倒置问题，必须对传统的2 p l 进行 实时性改造，以下主要介绍了改进后的几种协议。 ( 1 ) 2 p l h p 协议 2 p l - h p 就是在传统的2 p l 的基础上，用高优先级优先的冲突解决机制来保证 高优先级事务不被低优先级事务所阻塞。在高优先级机制中，所有解决数据访问 冲突的方法倾向于高优先级事务。当一个事务以冲突方式请求已经被一个或多个 低优先级事务所持有的锁时，则持有锁的所有低优先级事务将被夭折并被重启， 优先级较高的申请者被授予锁；如果请求事务的优先级低于其中任何个锁持有 者，则请求者被阻塞1 1 3 】。 该算法不但能够避免死锁，而且解决了优先级倒置问题。但也存在一个严重 的缺点，就是可能导致浪费的重启【4 9 】，即一个事务由于一个较高优先级的事务而 重启，但是这个高优先级的事务随后也夭折了。浪费的重启将会严重影响系统的 性能。 ( 2 ) 2 p l p i 协议 优先级继承( 蹦。向i r l l l e r i t a n c e ) 协议1 1 4 1 。采用优先级继承策略来解决优先级 倒置问题。其基本思想是，当一个高优先级事务被一个低优先级事务阻塞时，持 有锁的低优先级事务以在等待锁的事务的最高优先级执行，直到它释放锁。由于 优先级的升级，它能够比没有优先级升级时执行得快，这样释放锁也快。结果是， 高优先级事务的阻塞时间可能降低。 虽然该策略解决了死锁和优先级倒置的问题，但是，优先级继承策略也阻止 了中等优先级事务抢占锁，从而可能引起这些事务错失截止期。 ( 3 ) 2 p l - c p i 协议 2 p l - h p 使得高优先级事务抢占低优先级事务的锁，如果低优先级事务几乎接 近完成，这样可能导致c p u 时间的严重浪费，因为被抢占的事务重启，所有已经 做过的事务都必须重新做。而2 p l p i 阻塞高优先级事务，尽管优先级继承策略可 以加速低优先级事务的执行，但是，阻塞也很可能导致高优先级事务错失截止期。 所以这两种策略都没有明显的压过对方的优势。 2 p l c p i ( c o n d i t i o n a lp r i o r i t yi n h e r i t a n c e ) 1 1 4 j 是2 p l h p 和2 p l p i 协议的有机 结合。在2 p l c p i 协议中，仅仅当冲突的低优先级事务接近于完成的时候，才使 用优先级继承；否则，低优先级事务被中断。简单地说，如果冲突的低优先级事 务剩余的步骤少于某个预先定义的阀值h ，则使用优先级继承。 ( 4 ) 2 p l p c 协议 2 p l - p c ( p r i o r i t yc e i l i n g ) 1 1 5 】的目标是，保证不会出现死锁和级联阻塞。该算 法为每个关键段( c r i t i c a ls e c t i o n ) 分配一个优先级项( c e i l i n g ) ，记录可能进入该 嵌入式实时数据库系统并发控制技术 关键段的任务的最高优先级。任务的优先权顶为所有当前已被其它任务锁住的关 键段的最大优先级顶。当前没有被阻塞的优先级最高的任务允许进入关键段的前 提条件是：该任务的优先级高于该任务的系统优先级顶，否则任务被阻塞，并采 用优先级继承来提升阻塞该任务的优先级。 2 p l - p c 特别适合于硬实时环境中，因为它阻止死锁形成并且严格限制了优先 级倒置产生的事务阻塞时间。然而这种协议需要每一事务存取的数据对象的优先 级知识。这种情形在许多数据库应用中不适用，因为在很多情形下事务执行是数 据依赖的，从并发的角度来说，这一机制很保守。 2 3 乐观并发控制协议0 c c 在乐观并发控制协议中，事务不受阻碍地执行，直到到达其提交点，并且事 务在该点进行验证，这样事务的执行包括读、验证、写三个阶段。在验证阶段检 测数据访问冲突的方法主要有两种：向前验证( f o r w a r dv a l i d a t i o n ) 和向后验证 ( b a c k w a r dv a l i d a t i o n ) 0 7 1 。在向后验证中，主要检测验证事务和已提交事务之间 的数据访问冲突；而在向前验证中，主要检测验证事务跟活跃事务之间的数据访 问冲突。传统的乐观并发控制协议采用向后验证方法，在检测到数据访问冲突时， 将重启正在验证的事务。而在向前验证方法中检测到数据访问冲突时，可以通过 重启发生冲突的活跃事务或者正在验证的事务来解决数据访问冲突，这种能活性 选择有利于对乐观并发控制协议进行实时性改造。以下介绍几种适合于实时数据 库系统中的乐观并发控制协议。 ( 1 ) o c c b c 协议 o c c - b c ( b r o a d c a s tc o m m i t ) 【1 6 】，广播提交的乐观并发控制协议。它采用向 前验证方法，其基本思想是，当某个事务进入验证阶段时，广播通知与验证事务 相冲突的活跃事务立即重启。 该算法能够较早地检测出数据访问冲突，提早事务重启的时间，可以减少浪 费的执行，增加了事务满足截止期的机会，其性能比传统的乐观并发控制协议好。 ( 2 ) o c c s a c r i f i c e 协议 o c c s a c r i f i c e 1 8 l 是一种采用优先级牺牲策略来处理冲突的乐观并发控制 协议。当事务到达验证阶段，如果一个或多个冲突事务比验证事务的优先级高， 验证事务夭折；否则，它将提交，并且将所有与之冲突的活跃事务重启。 o c c s a c r i f i c e 的主要目的是牺牲低优先级事务来确保高优先级事务满足 截止期，但是存在浪费的牺牲问题，将会降低系统的性能。 ( 3 ) o c c w i t 协议 o c c w a i t 1 8 】主要采用了优先级等待机制。当事务f 到达验证阶段，如果其 6 2 实时事务并发控制综述 优先级不比与之冲突的所有事务的优先级高，那么z 必须等待优先级比它高的事 务完成。这样，高优先级事务满足截止期的机会大大提高了。如果事务z 在等待 了一段时间之后，其优先级比冲突集中所有事务的优先级高，那么事务z 提交， 冲突集中所有的事务重启。 o c c w a i t 协议保持了实时冲突处理最初的目标，但是也存在浪费的牺牲问 题。 ， 。( 4 ) o c c w a i t - x 协议 o c c w 舢t - x 协议【1 8 1 是o c c w a i t 协议的扩展。该协议检测事务的冲突，并 且动态地决定什么时候一个高优先级事务应该去等待与它冲突的低优先级事务， 以及等待多长时间。 与o c c - w a i t 相比，o c c - w a i t - x 主要增加了一个条件。验证事务在验证阶 段等待，直到它的冲突集中更高优先级的活跃事务所占的比率小于x 时，才重启 冲突集中的活跃事务并进入写阶段。 ( 5 ) o c c t i 协议 o c c - t i 19 】1 2 川协议主要采用事务的时间戳间隔( t i m e s t a m pi n t e r v a l ) 来消解冲 突。其基本思想是：每个事务在读阶段被分配一个时间戳间隔，在执行过程中不 断地对这个时间戳间隔进行调整，当事务的时间戳间隔为空时，事务将被重启。 事务开始执行时初始化时间戳间隔为【o ，+ m 】。o c c - t i 同样被分为读，预写、验 证三个阶段。 研究表明，在乐观并发控制协议中，o c c - t i 的性能好于0 c c b c 姗。当一个 数据对象被修改的可能性很低时，o c c - b c 和o c c - t i 之间的性能差距更大。 ( 6 ) o c c - d a 协议 o c c d a t 2 1 】主要是靠动态安排事务的时间戳来调整事务之间的执行顺序。在 o c c d a 中，事务执行的串行化顺序不同于事务提交的先后顺序。 对于每个事务z ，都有一个时间戳s o t ( s e r i a l i z a t i o no r d e rt i m e s t a m p ) 来标 识该事务相对于其它事务的串行化顺序，初始值设为+ o o ，如果某事务的最终时间 戳不是+ m ，那么意味着在某个事务被提交之前该事务已经被向后调整了。 o c c d a 协议是基于对时间戳进行向后调整基础上的，对于所有事务来说，时间 戳总是递减的。该方法在验证阶段采用三步来确认向后调整是否可行，对于通过 验证的事务，又用第四步来确定事务的最终时间戳，事务的最终时间戳就是其串 行化顺序。o c c - d a 协议也实现了动态调整串行化顺序，能够避免一些不必要的 重启，从而提高了实时数据库系统性能。 ( 7 ) o c c d a t i 协议 0 c c d a t l l 2 2 】结合了o c c d a 和o c c t i 的优势，采用o c c t i 中的时间戳间 7 嵌入式实时数据库系统并发控制技术 隔来限制最终时间戳范围，另外，和o c c d a 一样，只需要在验证阶段检测数据 访问冲突，从而可以获得更多的信息来解决数据访问冲突。o c c - d a t i 的时间复杂 度低于o c c - d a ，实验证明o c c d a t i 能够比o c c d a 和o c c - t i 协议避免更多 不必要的重肩，从而进一步提高了实时数据库系统性能。 ( 8 ) o c c - p d a n 协议 o c c p d a t i 2 3 】协议是基于向前验证和o c c d a t i 协议的基础上产生的。在 验证阶段，o c c - p d a t i 协议和o c c - d a t i 协议所采用的方法是一样的。 o c c - p d a t i 协议与o c c d a t i 协议最大的不同是：在冲突的处理阶段， o c c p d a t i 把事务的重要性信息考虑进去了，使得相对比较重要的事务能够更好 地满足截止期。 2 4 推测并发控制机制s c o 传统的并发控制协议分为悲观的并发控制协议( p c c ) 和乐观的并发控制协议 ( o c c ) 。两者的主要区别在于检测冲突的时间和进行冲突处理的方法不同。p c c 只要发生冲突就立即检测它，并且用阻塞的方法解决冲突；而o c c 在事务提交的 时候检测冲突，使用重启的方式来解决冲突。 在性能方面，悲观并发控制协议在检测出一些事务存在潜在的数据访问冲突 时，禁止这些事务并发执行，因此存在严重的阻塞问题，从而降低了事务执行的 并发度。相反地，乐观并发控制协议允许事务无阻塞地执行，直到事务进入验证 阶段之后才进行冲突检测，当检测到数据访问冲突时将重启事务，然而，此时的 重启可能已经太晚了，往往导致事务错过截止期，并且事务重启也是对系统资源 的极大浪费。在性能方面，实时数据库系统主要追求的有两方面：高并发度和最 大限度地满足事务的截止期。所以必须综合乐观并发控制协议和悲观并发控制协 议的优点，并尽可能地避免二者的缺点，由此推测并发控制协议( s c c ) 产生了。 s c c 主要依靠冗余计算来尽早寻求可串行化的调度。同活跃事务存在几个 相同的事务版本并发执行，事务的每个事务版本称为影子事务。影子事务分为乐 观影子事务和推测影子事务两种类型，每个事务在执行过程中可以有多个推测影 子事务，但只能有一个乐观影子事务。事务在检测到冲突威胁时，就产生多个推 测影子事务，同时事务本身变为乐观影子事务继续执行，这样，就出现了乐观影 子事务和推测影子事务并发执行的局面。乐观影子事务采用无阻塞运行的乐观协 议，而推测影子事务采用的是阻塞的悲观协议，当乐观影子事务夭折时，就从推 测影子事务中选择一个合适的事务继续执行。这样，s c c 就充分综合了o c c 和 p c c 的优点，避免了其缺点，真正起到了扬长避短的效果，是一种更适合实时数 据库系统的并发控制协议。以下将介绍一些主要的s c c 协议。 8 2 实时事务并发控制综述 ( 1 ) s c c - 2 s 协议 在s c c 2 s 口8 1 【2 9 l 【3 0 1 中，2 s 指的是影子事务的数目。s c c 2 s 允许有一个乐 观影子事务和一个推测影子事务。 如图2 1 所示，事务正、e 分别以乐观影子掣和露开始执行，当霹尝试读数 据对象x 时，检测到了潜在的冲突。此时，派生出一个备份影子霹，乐观影子口、 硭继续无阻塞地执行，而乏被阻塞。最后，如果卵被提交，那么霹就被夭折， 而霹将被起用以代替譬。如果掣被夭折，那么霉就可以成功提交。 图2 1s c c - 2 s 影子事务调度 ( 2 ) s c c - k s 协议 对于s c c 来说，影子事务数目的多少也会对系统的性能产生影响，影子事务 越多，事务成功执行和满足截止期的几率越高，但是，影子事务越多，必然引起 激烈的资源竞争，从而又会导致系统性能下降，因此，必须限定影子事务的数量。 s c c - k s 的基本思想就是，系统中未提交的影子事务最多有k 个影子，其中一个 以乐观的模式运行，其余的k - 1 个影子是推测影子，以悲观的模式运行。 ( 3 ) s c c - d c 协议 s c c d c ( s c c - d e f e r r e dc o m m i t ) ，是一种基于价值来延迟事务提交的s c c 协 议。 s c c 协议与其它一般的并发控制协议都存在一个问题，即只要事务一完成验 证就将其提交，这也许会导致系统总体价值的降低，也就是说，事务应该存在一 个合适的提交时机，在这个时机提交事务会使系统的整体效益处于最大，如果这 个时机不是在事务完成验证之时，那么必须延期事务的提交。 系统的整体效益主要是以系统中满足截止期的事务数量来衡量，或者以错失 率来衡量，系统的错失率越低，那么系统的整体效益越大。在实时数据库系统中， 低优先级事务的提交可能导致高优先级事务错过截止期，此时，对事务进行延迟 9 嵌入式实时数据库系统并发控制技术 提交可能会提高系统的整体效益，使更多的高优先级事务满足其截止期。s c c d c 协议就是采用这种方法，延迟低优先级影子事务的提交，给高优先级的影子事务 更多的时间来执行和提交。s c c d c 协议的基本思想是，对于每个通过验证并即将 提交的影子事务，都要评估一下将其延迟是否有益。如果该影子事务不与其它未 提交的影子事务冲突，则按照提交规则提交；否则，则对当前提交影子事务的效 益和将影子事务延迟提交的效益进行评估，如果前者大，才将该影子事务提交， 否则，将该影子事务的提交延迟。但是，这样增加了很大的计算量，反而又影响 了执行效率。 ( 4 ) s c c o v w 协议 s c c - v w ，s c c v o t e dw a i t i n g ，是基于s c c o d c 协议基础上的，旨在减少 s c c - d c 的计算复杂度。s c c - v w 的基本思想是，让未提交的事务来对已完成事 务的提交进行投票，未完成事务主要是根据该己完成事务提交对系统的效益进行 投票，如果认为该完成事务现在提交使系统的整体效益最大，那么就同意提交， 否则，就不同意提交。至于最终该完成事务是否可以提交，则是由各未完成事务 的投票结果来确定的，每个投票事务的权值取决于该事务的相对价值。 s c c - v w 相对于s c c - d c 来说有了一定的改进。一方面，它在决定事务提交 的时候，考虑了系统的整体效益；另一方面，它的计算量相对来说有了一定的减 少。 ( 5 ) s c c d p 协议 s c c d p 协议【3 1 】的基本思想就是，每当检测到可能导致数据库不一致的冲突 时，要根据当前的事务的执行情况和系统状况，来决定是否建立一个新的推测影 子。当其中一个事务的乐观影子到达确认阶段时，是否将完成执行的事务提交也 要动态处理。 模拟实验证明，在系统中事务到达率比较高的情况下，s c c - d p 协议的性能明 显好于s c c - 2 s 。 2 5 本章小结 本章主要对实时数据库系统的并发控制问题进行综述。首先介绍了实时数据 库中数据的致性标准，然后详细阐述了实时事务并发控制中所采用的2 p l 协议、 乐观并发控制协议o c c 和推测并发控制协议s c c ，这些并发控制协议都是在传统 的并发控制协议的基础上进行实时改造后的结果。本文还简单地分析了这些并发 控制协议的优缺点。这些实时并发控制协议虽然不能照搬到嵌入式实时数据库系 统中，但也可以被借鉴到嵌入式实时数据库系统并发控制中来。 1 0 3 基于替代丰h 偿的实时并发控制特点分析 3 基于替代补偿的实时并发控制特点分析 3 1 嵌入式实时数据库系统特点 虽然嵌入式系统与台式和服务器版本的对应部分具有很多共性，但是它有着 独特的需求和局限性，主要体现在以下方面： ( 1 ) 小体积和功能局限性 通常而言，嵌入式数据库面临着完整数据库所没有的挑战，例如：它们必须 集成到小的设备中，因而存储器和内存较小，要求无维护地运行或者维护量很小。 ( 2 ) 无管理的运行和可预报性 嵌入式实时数据库系统嵌入到设备中，常常在没有人工干预的情况下独立运 行，或者它们的用户意识不到它们在与计算机打交道，此时，没有数据库管理员 的管理，当出现异常情况时，系统应具备自我纠错的能力，为了达到这个目的， 嵌入式系统的可预见性甚至比桌面应用系统更重要。 为了提高可预见性，需要给定一些约束，系统运行时必须时时检查返回值和 应用中的其它错误指示，以便在无外部干预的情况下识别错误和恢复。例如：如 果一个写操作因为没有足够的存储空间而失败，系统应该清