（计算机应用技术专业论文）基于替代补偿的实时事务优先级分派策略研究.pdf

摘要 嵌入式实时数据库系统设计目的是在最小的干涉和最小的系统影响下进行数 据处理，它通常需要对环境做出实时反应。为适应嵌入式实时数据库系统的特殊 要求，夏家莉教授提出了基于替代屏h 偿的实时事务模型，在此模型支持下系统具 备更高的可预见能力，可以更好地实现无人工干预地运行。替代性与补偿性是嵌 入式实时数据库实时事务的新特点，也给事务处理技术带来新的挑战，不能直接 引用传统的事务处理策略和方法。夏教授及其科研团队对基于替代补偿的事务模 型，在事务预分析、接纳控制策略、调度策略和并发控制策略等方面做了初步研 究。为了进一步地实现并发控制和事务调度等后续处理，必须完成基于替代$ 1 - 偿 模型下事务的优先级分派等前期工作。 论文第一章阐述了选题的背景和意义，介绍了实时事务的研究现状和优先级 分派的研究现状，说明了本文的研究内容和组织结构。第二章从单项指标( 包括 事务的时间特性和事务的价值) 和复合指标( 包括有利于系统成功率和有利于系 统收益) 分析已有的优先级分派算法，并对这些策略进行详细的比较，为本文的 研究提供理论支持。第三章分析了基于替代补偿的事务模型及其处理技术，包括 事务模型、二重调度策略、并发控制策略和优先级分派策略四个部分。第四章首 先分析了事务优先级和替代优先级之间的关系，接着给出本文优先级分派策略 p b a c 策略的思路，并且对替代的价值密度和紧迫性进行了详细的分析。构造出实 时事务的价值函数，并且给出静态价值密度和动态价值密度表达式，并且利用替 代在放行时的空余时间表示替代的紧迫性。接着提出了优先级分派策略p b a c 。其 中替代优先级分派从动态性、紧迫性两个方面进行考虑；利用最高继承、最低继 承、平均继承和加权继承四种不同的继承方式继承替代的优先级得到事务优先级 继承函数，然后分别从乐观和悲观的角度考虑事务的执行度的影响，构造出不同 的事务优先级分派函数。 p b a c ( p r i o r i t yb a s e do na l t e r n a t i v ea n dc o m p e n s a t e ) 策略包括替代优 先级分派p f a ( p r i o r i t yf u n c t i o no fa l t e r n a t i v e ) 和事务优先级分派p f l ( p r i o r i t yf u n c t i o no ft r a n s a c t i o n ) 两个部分。其中，p f a 策略又包括非紧急 静态价值密度大者优先、非紧急动态价值密度大者优先、紧急静态价值密度大者 优先和紧急动态价值密度大者优先四种策略。动态性表示优先级在执行全过程中 动态变化，通过价值密度进行描述；紧急性表示替代执行的紧急程度，由替代在 放行时的空余时间描述。p f t 策略包括可替代优先和非替代优先两种策略，前者重 视事务的应变能力，而后者更重视减轻系统的管理成本。它们根据代表事务执行 能力的执行度调整优先级，事务的优先级继承替代的优先级。p b a c 策略结合支持 替代脾 、偿事务的新特点并借鉴经典的优先级分派算法构造得来，提高了事务的适 应能力和应变能力，最终提高了系统的成功率和收益值，具有很高的理论意义。 关键词：嵌入式实时数据库事务调度优先级分派 替代补偿 2 a b s t r a c t t h eg o a lo fd e s i g n i n ge 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 st oc a r r yo nt h ed a t a s t o r a g ea n d t h er e s t o r a t i o ni nt h es m a l l e s ts y s t e mi n f l u e n c ea n dt h es m a l l e s ti n t e r f e r e n c e ； i tu s u a l l yn e e d st om a k et h er e a l - t i m er e s p o n s et ot h ee n v i r o n m e n t w ec a n n o td i r e c t l y q u o t et r a d i t i o nt r a n s a c t i o n - p r o c e s s i n gs t r a t e g y a n dt h em e t h o dt ot h ee m b e d d e d r e a l t i m ed a t a b a s es y s t e m p r o f e s s o rx i aj i a l ip r o p o s e dr e a l - t i m et r a n s a c t i o nm o d e l b a s e do na l t e r n a t i v ea n dc o m p e n s a t e ，t h es y s t e mh a ss op o w e r f u lf o r e s i g h ta b i l i t yt h a ti t c a nw o r km o r et r a n s p a r e n t l yi nan o n a r t i f i c i a lw a y a l t e r n a t i v ea n dc o m p e n s a t et h a ta r e n e wf e a t u r e st ot h et r a n s a c t i o no 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 mb r i n gn e w c h a l l e n g e st ot h et r a n s a c t i o n - p r o c e s s i n gt e c h n i q u e s p r o f e s s o rx i aj i a l ia n dr e s e a r c h t e a md i dh a ss t u d i e di n i t i a l l yo nm a n ya s p e c t so ft 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 a n dc o m p e n s a t e ，s u c ha st r a n s a c t i o np r e a n a l y s i s ，a d m i s s i o nc o n t r o l ，s c h e d u l i n gs t r a t e g y a n dc o n c u r r e n tc o n t r 0 1 t h ef i r s tc h a p t e ro ft h i sp a p e ri n t r o d u c e dt h ep r i o r i t ya s s i g n m e n tr e s e a r c hp r e s e n t s i t u a t i o n ，i ta n a l y z e dt h ef e a t u r e so ft r a n s a c t i o nb a s e do nt h ea l t e r n a t i v ea n dc o m p e n s a t e ， c o m p a r e da l t e r n a t i v ea s s i g n m e n t t ot r a n s a c t i o na s s i g n m e n t t h es e c o n dc h a p t e r a n a l y z e de x i s t i n gp r i o r i t ya s s i g n m e n ta l g o r i t h mf r o mt h es i n g l ei t e mi n d e xa n dt h e c o m p o s i t ei n d e x ，w h e r et h es i n g l ei t e mi n d e xc o n t a i n st h et i m e c o n s t r a i n ta n dt h ev a l u e a n dt h ec o m p o s i t ei n d e xc o n t a i n sb e i n ga d v a n t a g e o u st ot h es y s t e ms u c c e s sr a t i oa n d b e i n ga d v a n t a g e o u st ot h es y s t e mi n c o m e t h ep a p e rc o m p a r e dt h e s ea l g o r i t h m se a c h o t h e rt op r o v i d i n gt h e o r ys u p p o r tt ot h i sp a p e r sr e s e a r c h t h et h i r dc h a p t e ra n a l y z e dt h e t r a n s a c t i o nm o d e la n di t sr e l e v a n tp r o c e s s i n gt e c h n o l o g y , i n c l u d i n gt r a n s a c t i o nm o d e l ， d u a ls c h e d u l i n gs t r a t e g y , a n dc o n c u r r e n c yc o n t r o la n dp r i o r i t ya s s i g n m e n ts t r a t e g yf o u r p a r t s e x p l a i n i n gt h i sp a p e r sr e s e a r c ha p p l i c a t i o nb a c k g r o u n du n i f y i n gt h er e a l t i m e t r a n s a c t i o n sn e wf e a t u r e s ，t h et h i r dc h a p t e rp r o p o s e dt h ea l t e r n a t i v ep r i o r i t ya s s i g n m e n t s t r a t e g y a n dt r a n s a c t i o n p r i o r i t ya s s i g n m e n ts t r a t e g yp b a c ( p r i o r i t y b a s e do n a l t e r n a t i v ea n dc o m p e n s a t e ) t h i sp a p e rc o m p a r e dt h ea l t e r n a t i v ep r i o r i t ya s s i g n m e n t s t r a t e g yw h i c hp r o p o s e dh e r ef r o mt h ep r e s s i n gt w oa s p e c t so fs t a t i cs t a t ea n du r g e n c y a n de x p l a i n e dt h e i rs u i t a b l ee n v i r o n m e n tr e s p e c t i v e l y a c c o r d i n gt ot r a n s a c t i o n s e x e c u t i o nf r o mo p t i m i s t i ca n dp e s s i m i s t i ca n g l e ，t h i sp a p e rc o n s t r u c t e df u n c t i o no f t r a n s a c t i o n sp r i o r i t ya s s i g n m e n t p b a cs t r a t e g ym a k e su po ft w op a r t s ，a l t e r n a t i v ep r i o r i t ya s s i g n e ds t r a t e g y p f a ( p r i o r i t y f u n c t i o no fa l t e r n a t i v e ) a n dt r a n s a c t i o np r i o r i t ya s s i g n e ds t r a t e g y 二l p f t ( p r i o r i t yf u n c t i o no ft r a n s a c t i o n ) p f ac o n t a i n ss t a t i ch v d f , d y n a m i ch v d f , s t a t i cu r g e n th v d f , a n dd y n a m i cu r g e n th v d es t a t i cd e n o t e sp r i o r i t yl 【e 印s t e a d yi n t h ec o u r s eo fe x e c u t i o n ；u r g e n c yi sd e s c r i b e db yt h ea l t e r n a t i v ev a c a n c yt i m e p f t c o n t a i n sa l t e m a t i v ep r i o r i t ys t r a t e g ya n dn o n - a l t e r n a t i v ep r i o r i t ys t r a t e g y , t h ef o r m e r a t t a c hi m p o r t a n c et ot h ea b i l i t yo fm e e t i n ga ne m e r g e n c yw h i l et h el a t e ra t t a c hm o r e i m p o r t a n c et ol i g h t e nt h em a n a g ec o s t t h e ya d j u s tt h et r a n s a c t i o np r i o r i t yp r o p e r l y a c c o r d i n gt ot h et r a n s a c t i o n si m p l e m e n t a t i o nd e g r e ew h i c hs t a n df o rt h ea b i l i t yo f t r a n s a c t i o n sr u n n i n g ，t r a n s a c t i o n sp r i o r i t yi n h e r i tf r o ma l t e m a t i v e sp r i o r i t y p b a ct h e s t r a t e g ye n h a n c e dt h es y s t e mt ob ep o s s i b l et h ef o r e s i g h ta n dt h er e l i a b i l i t y , w a s a d v a n t a g e o u si nr a i s e ds y s t e m ss u c c e s sr a t i oa n dt h es y s t e mi n c o m e ，a n d h a dt h ev e r y h i 曲t h e o r ys i g n i f i c a n c e 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 e t r a n s a c t i o ns c h e d u l i n g a s s i g n m e n to fp r i o r i t y a l t e r n a t i v ea n dc o m p e n s a t e 4 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得江西财经大学或其他教育机构的学位或证书所使用 过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 签名：至垒坠日期：兰堕：! 三 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定， 印：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 他复制手段保存论文 ( 保密的论文在解密后遵守此规定) 1 绪论 1 绪论 1 1选题的背景与意义 1 1 1选题背景 嵌入式数据库系统是指可在嵌入式设备中独立运行的一种数据库管理系统， 以高可靠性、高实时性和高信息吞吐量为目标，其数据的正确性不仅依赖于逻辑 结果，而且依赖于逻辑结果产生的时间。嵌入式数据库系统的兴起可以归功于便 携式计算设备的开发兴起。这些设备具备成熟的数据管理能力，所需功能常常如 此复杂以至于平坦的文件系统不足以处理和操纵这些数据，这就促进了对嵌入式 数据库的需求。 嵌入式实时数据库系统设计目的是在最小的干涉和最小的系统影响下进行数 据处理，它却常常被要求对环境做出实时反应，它要求嵌入、主动、实时、内存 数据库的完善集成，尤其是在事务模型、特征、正确性标准、事务处理及系统的 存储体系结构等方面具有其特点，但目前的嵌入式系统并不具备实时性。对于它 的研究尚处于初级阶段，未见成熟的产品，市面上的一些嵌入式数据库系统和实 时数据库系统的产品基本上是传统商业数据库系统的剪裁，在事务模型和并发控 制机制上并无新意，它们沿用了普通数据库系统的一些控制机制，或加以部分改 造，难以满足上述要求。 夏家莉教授曾经在分析现有嵌入式数据库系统的基础上，针对其中存在的不 足，提出了非常适合于嵌入式实时系统的基于替代- i 偿的实时事务模型，并且在 事务预分析、接纳控制、调度策略和并发控制策略等方面作了初步研究。在此基 础上，本文将就基于替代补偿的优先级分派策略作进一步的研究，为实现事务调 度及后续处理提供支持。 1 1 2 选题意义 夏家莉教授及其科研团队在研究具有自适应能力的实时事务模型及其处理技 术方面取得了初步成果，本文继续针对支持替代补偿的实时事务模型，研究与之 匹配的优先级分派策略。 夏家莉教授前期研究已证明：替代有助于提高事务成功率，补偿则有助于提 高系统可靠性；由于事务模型的复杂化， 不再适用，需要考虑替代和补偿的关系， 不支持功能替代性模型的优先级分派将 提出新的优先级分派策略，以提供后续 的二重调度和二重并发控制等事务处理技术支持。夏家莉于2 0 0 7 年成功申请了国 家自然科学基金基于替代i - i , 偿的并发控制机制策略研究，具有传统并发控制 基于替代补偿的实时事务优先级分派策略研究 机制所不能处理的一些优点，提高事务的自适应能力，支持嵌入式实时数据库系 统在无人控制环境下运行。本论文的研究内容作为其中的关键技术之一，具有重 大的理论意义。 本研究成果所支持的嵌入式数据库技术可被嵌入到移动或非移动设备中，在 无人工干预的环境下自动运行，事务具备更高的可预见能力和应变能力，适应复 杂而瞬息万变的运行环境f l 】，可以广泛应用于国防、航空、航海、矿下和水下作业 等领域，有助于提高生产效率、降低安全事故发生率，因而研究成果具有较大的 潜在应用价值。 1 2 国内外研究现状分析 1 2 1事务模型研究现状 实时数据库事务组合了实时任务和传统数据库事务两者的特征，但并非它们 在概念、机制、技术上的简单集合，而有一系列的问题需要研究与解决，如扩展 事务模型及其机构特征，事务处理的硬软限制、事务间的关系，事务正确性和数 据一致性及其数据语义和事务特征的联系，失去调度的协议和算法。因此，实时 数据库事务处理比传统的实时任务和数据库事务都要更复杂、更困难。他们必须 同时实现数据一致性，包括外部、相互和动态一致性【2 】，和定时限制两者。近年来， 许多研究者已对实时事务模型做了大量的研究，具有代表性的有：刘云生【2 j 在分 析实时数据库事务应用特征与需求的基础上，给出了一个复杂事务结构的框架， 并讨论了实时事务间的结构相关性、数据相关性、行为相关性以及是实时事务的 结果、结构、行为及时问的正确性。k i m 3 】建立了一个包含硬实时事务和软实时事 务的实时数据库事务模型，该模型能够维护数据的时态和逻辑一致性。b r a o u d a k i s l 4 j 将事务与一个表示时间约束以及事务的重要性的价值函数进行关联，构造一个实 时数据事务模型，其主要特点是能够用一致的方法处理不同类型的事务，能够对 非实时事务、软实时事务、固实时事务和硬实时事务进行说明。z h o u ，r u n d e n s t e i n e r 和s h i n 5 】将面向对象的观点结合到实时数据库系统中，提出了实时的对象模型 r o m p p ，用面向对象的框架探讨了时态和逻辑一致性和正确性。n a g ys 等【6 j 提出 事务由主任务和补偿任务组成，但由于补偿任务不具备实时性，因此文章并没有 对补偿任务调度作进一步研究。 以上这些实时事务模型不支持事务应变性，并不是针对嵌入式环境的。嵌入 式实时数据库除了具备实时性、嵌入性和主动性之外，还应该具备高的可预见性 等特点，以保证系统能在无人干涉的环境下自主地进行数据处理。目前在国际国 内都尚未发现能实现可预见能力的嵌入式实时数据库系统的有关报道，研究具有 2 1 绪论 可预见性和高可靠性的事务模型及其处理技术是非常必要的。 1 2 2 优先级分派研究现状 优先级驱动的事务调度以事务优先级为基础，它决定一个事务的开始执行时 间和结束时间，以及在执行过程中改变事务的状态，即可能将它挂起等待或者夭 折重新开始等。对于系统重要性越高的事务，其优先级就相对越高。优先级分派 分为静态( f i x e d p r i o f i t y ) t g 动态( d y n a m i c - p r i o r i t y ) 两种策略。前者整个调度过程中给 予事务静态的优先级，它实现简单，额外开销小，但存在资源利用率低、支持的 优先级个数有限以及灵活性差和自适应性差等缺点，单调速率策略( i 洲) 属于静 态范畴。后者根据环境变化动态分派事务的优先级，高优先级的事务可抢占正在 执行的低优先级事务，以适应复杂多变的应用环境。需要说明的是：本文中事务 调度指单c p u 调度，对于实时事务而言时间是最重要的。截止期最短最优先 ( e d f ) 、空余时间最短最优先( l s f ) 和价值密度最大最优先( h v d f ) 等策略属 于动态的范畴。 s e r l i n 【7 j 和l i u 等【8 1 对实时事务优先级分派策略研究的结果表明：在满足对于 同步周期任务( 具有相同的放行时间) 的硬实时事务，并且它们的截止期等于周 期时，单调速率算法( r m ) 性能最优。刘云生、李国徽【9 】在论述了事务的优先级 分派问题的基础上，给出了触发事务及被触发事务优先级分派的各种策略，并按 不同情况对这些策略进行性能评价。廖国琼、刘云生【l o 】提出了立即和推迟两种模 式下执行的被触发事务截止期的确定方法和事务紧急度计算方法，并结合事务的 应用语义提出一种基于多优先级队列的优先级分派策略，有利于主动事务和被触 发事务的顺利提交，改善系统的性能。宾雪莲【1 1 】等针对优先级个数有限的情况， 给出了在截止期限大于周期时任务可调度的充分必要条件，并提出了基于有限优 先级的静态优先级分配算法a g p ，这对于解决在嵌入式实时系统中任务的优先级 分配问题具有一定的意义。 一般地，优先级分派用一个函数表示，它可以针对单个任务( 事务) 或一个 任务组( 事务集) 。当被用于单个事务时，函数的结果就是对应策略确定的该事务 的优先级；当被用于事务集时，函数的结果是这些事务的一个排序表，优先级最 高者排第一，最低者排最后。 嵌入式实时数据库系统追求的目标，是单个事务定时限制的满足及全系统满 足定时限制事务的比率最大。因此，事务的优先级与时间限制有着密切关系，不 同的优先级反映了不同的紧迫程度。以下介绍几种典型的优先级分派算法： ( 1 ) 最早放行最优先( e a r l i e s tr e l e a s ef i r s t ，简称e r f ) ：具有最早“放行”( r e l e a s e ) 时间的事务，获得最高优先级。其主要优点是简单，而主要缺点是未考虑事务的 基于替代奉卜偿的实时事务优先级分派策略研究 截止期，不适合实时系统。 ( 2 ) 截止期最短最优先( e a r l i e s td e a d l i n ef i r s t ，简称e d f ) 【8 】：具有最早的截止 期者优先级最高，主要缺点是它让已超过或几乎要超过截止期者获得最高优先级， 而这种事务无论如何不能满足其截止期。 ( 3 ) 可达截止期最早最优先( e a r l i e s tf e a s i b l ed e a d l i n ef i r s t ，简称e f d f ) u 2 】：具有最 早的可达截止期者优先级最高，如果所有的事务都具有不可达截止期，则按e d f 指派优先级，这样具有不可达截止期的事务可不必立即夭折，e f d f 策略显然克服 了e d f 的缺点，是其改进版本。 ( 4 ) 空余时间最短者最优先( 1 e a s ts l a c kf i r s t ，简称l s f ) 1 1 2 ：考虑了当前时间与 剩余执行时间估算，随事务的停止执行其优先级动态上升，该策略也有类似于e d f 的缺点。 ( 5 ) 价值最高者最优先( h i 曲e s tv a l u ef i r s t ，简称h v f ) 1 3 ，1 4 】：使每一事务有一价值 函数，其函数值最大者最优先。 ( 6 ) 关键性截止期优先算法( c r i t i c a l n e s s d e a d l i n ef i r s t ，简称c d f ) n 5 】：综合考虑 事务的截止期与价值两个独立特征，每个事务在到达时按照“相对截止期价值” 分配优先级。该策略相对于单独使用截止期或价值作为特征参数的策略，系统性 能有较大改进。 ( 7 ) 价值密度最大者最优先( h i g h e s tv a l u ed e n s i t yf i r s t ，简称h v d f ) 【1 3 1 6 】：事务 完成时的期望价值与实现所需计算量的比值最大者，优先级最高。实验证明，从 事务执行的整体效果来看，基于价值密度的调度效果最优。 1 3 本文的主要研究内容及组织结构 1 3 1本文的研究主要内容 本文的研究内容来自于夏家莉教授主持的国家自然科学基金项目“基于替代 补偿的并发控制机制，优先级分派策略是其中的关键技术之一。本文的优先级 分派策略研究构建于基于替代辟 、偿的复杂事务模型之上，在分析现有经典优先级 分派策略的基础上，讨论能更好地适应嵌入式环境的优先级分派策略。主要研究 内容有： 在基于替代补偿的实时事务模型的基础上提出事务优先级分派策略( p b a c 策略) ，并对优先级分派函数进行具体构建。优先级分派策略分为三个步骤：替代 优先级函数的构造、事务优先级函数的构造和优先级继承函数的构造。在p b a c 策略中，替代优先级基于替代的价值密度，并且与替代的紧迫性相关；事务的优 4 ) 基金项目：国家自然科学基金基于替代，补偿的并发控制机制研究( 6 0 7 6 3 0 0 2 ) 4 1 。绪论 先级继承替代的优先级，事务的执行度表示了事务的适应能力对事务优先级存在 一定的影响。 1 3 2 本文的组织结构 论文分为五章，各章的具体内容如下： 第一章首先阐述了本文选题的背景和意义，并介绍了实时事务的研究现状和 优先级分派的研究现状，说明了本文的研究内容和组织结构。 第二章从单项指标( 包括事务的时间特性和事务的价值) 和复合指标( 包括 有利于系统成功率和有利于系统收益) 分析已有的优先级分派算法，并对这些策 略进行详细的比较，为本文的研究提供理论支持。 第三章分析了基于替代补偿的事务模型及其处理技术，包括事务模型、二重 调度策略、并发控制策略和优先级分派策略四个部分，本章内容是夏家莉教授及 其研究团队的研究成果。基于替代补偿的事务模型中，替代成为基本的组成单元 和执行单元，使相应的事务调度变为二重调度，并发控制策略具体新特点，优先 级分派也变得包括事务优先级和替代优先级两部分，这些能更好地使嵌入式系统 在无人干涉的环境下独立地运行。 第四章首先给出了本文的相关理论与假设，分析了事务优先级和事务优先级 之间的关系，并且对替代的价值密度和紧迫性进行了详细的分析。构造出事务的 价值函数，并且给出静态价值密度和动态价值密度表达式，并且利用替代在放行 时的空余时间表示替代的紧迫性。接着提出了优先级分派策略p b a c 。其中替代优 先级分派从动态性、紧迫性两个方面进行考虑；利用最高继承、最低继承、平均 继承和加权继承四种不同的继承方式继承替代的优先级得到事务优先级继承函 数，然后分别从乐观和悲观的角度考虑事务的执行度的影响，构造出不同的事务 优先级分派函数。 第五章对论文进行总结与展望。 基于替代脾卜偿的实时事务优先级分派策略研究 经典的优先级分派策略 优先级分派相关的指标可分为单项指标和复合指标两大类。本章将就分别从 这两大类对相关优先级分派策略进行阐述。 2 1 基于单项指标的优先级分派策略 基于单项指标的策略，考虑基于时间特性或基于事务价值的两种策略，时间 特性是实时事务首先需要满足的要求，价值体现事务对于系统重要性的衡量指标。 2 1 1基于时间特性的优先级分派策略 实时事务具备很强的实时性，对时间特性有很高的要求。实时事务在其截止 期之内完成才能带来预期效果，若错过截止期则效果降低甚至产生负面影响。实 时事务的相关时间特性因素有：绝对截止期( 本文后面简称截止期) ，执行时间和 周期等。最早的优先级分派策略，就考虑了事务的周期和截至期等时间特性。以 下介绍几种基于时间特性的经典策略及其改进策略： 1 1 9 6 7 年，m s f i n e b e r g 等提出了适用于周期事务的单调速率策略( r m ) 1 1 7 1 ：对于周期事务，任务的周期越短，其优先级越高。a u d s l e yn c 通过实验证明： 当所有任务的周期等于其截止期时，r m 策略是最优的f l 引。此后，有不少研究者提 出修改算法，s h i hw k 提出了改进的单调速率策略( m o d i f i e dr a t e - m o n o t o n i c a l g o r i t h m ) 1 1 9 1 ：当每个任务的截止期限不超过m a x ( 1 ，g 1 ) 幸与其周期之积时，该策 略是最优静态优先级分配算法。其中g 表示等于任务集合中任务的最大周期除以 任务集合中任务的最小周期。r m 策略是静态优先级分派策略，缺乏灵活性和自适 应性。 2 1 9 7 3 年，c l l i u 等提出了截止期最短最优先策略( e d f ) t g 】：对于具有不同 截止期的任务，截止期越早，任务的优先级就越高。该策略的缺点：让已超过或几乎 要超过截止期者获得最高优先级，而这种事务无论如何不能满足其截止期。r a b b o t 等提出了一种e d f 的改进策略，可达截止期最早最优先( e f d f ) ：具有最早的可 达截止期者优先级最高，如果所有的事务都具有不可达截止期，则按e d f 指派优 先级，这样具有不可达截止期的事务可不必立即夭折，从而克服了e d f 的缺点。 3 1 9 9 3 年，ra b b o t t 提出空余时间最短最优先( l s f ) 吲：对于具有不同空余 时间的任务，空余时间越短，任务的优先级就越高，事务就越需要尽快执行。若空余 时间大于等于零时，代表事务若不被抢占，可以在其截止期内执行完成，具有可 调度性；若空余时间小于零时，无论如何，事务无法执行完成。由于等待执行事 务的空余时间是严格递减的，其等待执行的缓急程度也随时间越来越紧急，因此在 6 2 经典的优先级分派策略 系统执行过程中，等待执行事务随时可能会抢占当前执行的事务。当多个事务具有 相同的空余时间时，会造成任务之间的频繁切换或严重的颠簸现象，增大了系统开 销，从而限制该策略不适用。 h i l d e b r a n d tj 等提出一种新的增强l s f 算法，针对具有相同最小空余时间的事 务，截止期越早越先执行，执行过程中不进行切换【2 0 l 。o hs h 提出一种修改的l s f 算法，在有两个或更多任务具有最小空余时间的情况下，它用一个更复杂的算法确 定任务执行的顺序【2 1 1 。这些措施都需对具有相同最小空余时间的事务进行单独管 理，增加了事务调度的复杂度。金宏等【2 2 】提出适用于l s f 算法的抢占阈值分配方法。 动态地给每个任务配置抢占阈值，减少任务之间的切换，同时提高了系统成功率。 以上这些策略都是依据事务的某个时间特性分派优先级，这样是不够的，如 具有最短空余时间的事务并不一定是最重要的。在实际应用中，由于环境的变化、 某些强健事务的影响或系统故障的级联作用，常会导致过载情况的发生；嵌入式 实时系统中，调度算法中必须考虑系统过载情况的处理。以上这些策略在过载的 情况下，可能会出现急剧的性能降级，甚至导致多米诺现象【1 6 1 ，即当第一个事务 错过其截止期后，导致后续队列的事务都错过它们的截止期。 2 1 2 基于事务价值的优先级分派策略 价值函数表示时间约束以及所有重要的系统使命，事务价值以及价值函数的 观点被广泛应用于实时数据库系统中，价值是衡量实时事务性能的一个重要因素。 下面介绍几种经典的基于事务价值( 或基于价值密度) 的策略： ( 1 ) j e n s e n 等【1 3 j 首先提出了事务具有价值。其价值函数基于时间，并且给出 了一个价值函数如( 2 1 ) 式所示。 y o ) = k 1 + k 2 t k 3 f 2 + k 4 p 一鬈， ( 2 1 ) 其中，k 。，k ：，k ，k 。，k ，是常量。根据事务是否在截至期之前完成，通过改变 5 个常量的值设定事务的价值。 ( 2 ) h a r i t s a 等【1 4 捌给出了不同的基于价值的优先级分配算法：h i g h e s tv a l u e f i r s t ( h v f ) 、v a l u e - i n f l a t e dd e a d l i n e ( v d ) 以及v a l u e i n f l a t e dr e l a t i v ed e a d l i n e ( v r d ) 算法，其中v d 算法中事务的优先级按照( 截止期价值) 进行分派( 等同于c d f 算 法) 。通过实验表明，e d f 算法在负载较轻时表现最佳，h v f 与v d 算法在较高负 载下性能较好，而v r d 算法表现出最好的综合性能。没有一个固定的折衷算法能 够适用于所有负载情况，根据负载情况合理选择参数能够产生最好的性能。 ( 3 ) t s e n g 等1 2 l j 提出了另一种基于价值的调度算法h r f ( h i g h e s tr e w a r d f i r s t ) ，其中事务的优先级按照( 价值剩余执行时间) 进行分配，这种优先级是时变 的。t s e n g 与h a r i t s a 等2 4 , 2 5 】在磁盘驻留的实时数据库( i 沁a 1 t i m ed i s kr e s i d e n t 7 基于替代$ b 偿的实时事务优先级分派策略研究 d a t a b a s e s ) 系统以及主内存数据库( m a i nm e m o r yd a t a b a s e s ) 系统进行研究，结果显 示：h r f 算法在低负载时性能仅次于e d f ，在高负载下性能最好，表现出非常好 的综合性能。 ( 4 ) 基于价值的调度算法的性能指标，通常采用系统实现的累积价值( 事务 调度完成后，所有事务的价值之和) 来衡量，b u t t a z z o 等【2 6 】提出价值密度最大最优 先( h v d f ) 算法：事务完成时的期望价值与所需计算量的比最大者优先级最高。对 于期望价值一样的事务，该策略偏向用时较短者，因为单位时间内所获价值更大。 这里的价值同样是基于时间的：当事务在截至期之前完成，其价值等于其执行时 间；否则，其价值为零，如( 2 2 ) 式所示。 f c ：c d ： ( 2 2 ) l 1z 其中，c ，q ，d 。分别为事务z 的估算执行时间、执行完成时间以及截止期。 对于给定的任务集，累积价值随着时间而增长。b u t t a z z o 等实验证明，在系统 负载较高甚至过载时相比于比基于时间的优先级策略，h v d f 策略使系统使事务 性能优雅地降级而不会出现多米诺现象，具有较高的系统成功率和实现更高的累 积价值而体现出良好的性能。考虑到嵌入式系统在无人环境下可能存在各种负载 的情况，为了使事务调度具有较高的性能以保证系统可靠性和自适应性，本文的 策略考虑借鉴h v d f 策略。并且对于基于价值的优先级分派策略，价值函数的构造 是个难题；根据系统指标构造一个具有代表意义的函数十分必要。 2 2基于复合指标的优先级分派策略 在实时数据库中，单项指标不足以全面反映事务执行对于系统的影响，优先 级分派应该考虑复合指标，如有利于系统的成功率和系统的收益。系统成功率反 映事务成功执行的比例；系统收益是反映事务执行给系统带来的某种收益效果， 其收益值因具体应用环境不同不尽相同。基于复合指标的策略分析不仅能够全面 反映事务的特性，而且有利于提高系统成功率以及系统收益，因此在研究优先级 分派时必须考虑复合指标。 2 2 1有利于提高系统成功率的优先级分派策略 系统成功率：系统中成功提交的事务数与系统接受的事务总数之比，是衡量 实时系统性能标准的重要指标。实时数据库事务除满足一般的一致性限制外，必 须满足时间限制( 尤其是截止期) ，故高成功率的调度策略是系统的关键。从某种 意义上说，基于时间特性的策略，保证事务的实时特性以降低事务的夭折率，其 实就是提高事务的系统成功率。以下介绍传统实时数据库下两种有利于系统成功 8 2 经典的优先级分派策略 率的策略： ( 1 ) 金宏等提出一种基于优先级表设计方法的策略，综合考虑事务的相对截 止期和空余时间，相对于单独使用e d f 或l s f ，系统的成功率大大提耐2 6 1 。他们 首先对于特征参数建立优先级表，然后对优先级表进行优先级插值，根据参数之间 的关系设置任务的优先级值，不同的任务获得唯一的优先级值，并且通过实验证 明了该策略的优越性。 ( 2 ) 王强等提出一种基于优先级表的实时调度算法，综合考虑了实时任务的 截止期和价值密度两个参数，适应于多种负载情况。通过实验证明，在正常负载和 过载情况下，该算法比e d f 算法在性能方面有明显的改进，提高了系统成功率2 7 1 。 以上两种策略，综合考虑两个特征参数，提高了系统的成功率，从而提高调 度性能。这些传统实时事务下的策略，不能直接用于在支持替代* b 偿的事务模型 中，但可以借鉴。具有功能替代性的事务模型定义事务为一组功能等价的替代， 任意一个替代成功执行则该事务可以提交，所有的替代都夭折则该事务夭折，这 种思想为事务的执行提供了多条路径，相比于传统实时事务，提高了系统成功率。 设系统接受的事务数为n ，每个事务的成功率为p 系统负载对成功率的修正 值为( 七) ， 口为权值，则事务的成功率可表示为( 2 3 ) 式。 p ， p t = 口上l + p ( k ) ( 2 3 ) ，2 相对于传统实时数据库，每个事务只随机选取一个替代参与系统调度，此时 替代的成功率取平均成功率托；支持功能替代性的模型，总是选取事务中成功率 最高的替代m a x ( p ) ，存在m a x ( p “) p ，同时其他参数不变，从而提高了事务 的成功率。 新事务模型下，系统成功率是事务调度和并发控制的重要目标，优先级分派 必须考虑。相应的事务( 替代) 优先级分派，结合事务的新特点，借鉴已有的经 典策略，可以构造出新的优先级函数。 2 2 2 有利于提高系统收益的优先级分派策略 系统收益指系统中所有事务给系统带来的价值总和，它是不同于执行时间的。 当系统中的事务都能完成执行时，则系统获得的收益值最大；但是当系统过载时 必定有事务不能完成，从而影响系统获得的收益值。此时系统必须赋予预期收益 值大的事务以高的优先级，使它们具有高的执行能力完成执行，最终有利于系统 收益。 基于事务价值的优先级分派策略目的是为了整个系统累计价值最大化，其实 9 基于替代补偿的实时事务优先级分派策略研究 也就是使系统收益最大化。h a r i t s a 等【l 犯o 】等提出的h v f 算法，使具有高价值的事 务优先级执行，从而增大了整个系统的收益值。b u t t a z z o 等【1 6 】提出的h v d f 策略 在h v f 策