基于EDF的实时数据库动态容错调度算法.pdfVIP

第 39卷第4期 郑 州 大 学学报(理 学 版) Vo1．39 NO．4 2007年12月 J．of Zhengzhou Univ．(Nat．Sci．Ed．) Dee．2007 基于EDF的实时数据库动态容错调度算法 刘文晓， 贾智平 (山东大学计算机科学与技术学院 济南250061) 摘要：实时数据库系统的事务调度过程中，对于即将完成的事务的抢占会造成CPU时间的浪费，降低系统的性 能．针对实时数据库中的周期性实时事务提出了一种PEA(preemptive estimate algorithm)软件容错调度算法，算法 基于EDF(earliest deadline first)进行事务调度，并结合负载优化算法进行适当调整，采用抢占评估策略来确定是否 允许事务抢占，以最大化系统的资源利用率．通过实验测试，证明其具有良好的性能，能有效提高事务的成功率． 关键词：实时数据库系统；软件容错；调度算法 中图分类号：TP 311 文章编号：1 671—6841(2007)04—0056—05 0 引言 实时数据库及时性比正确性更重要，系统宁可得到部分正确而及时的结果，也不要绝对正确但过时的 结果．因此在实时数据库中引人容错机制，保证出现错误的情况下，实时事务仍能满足其时限要求和最低 功能要求．当前数据库容错主要采用多副本技术和功能替代技术l_】 ]，利用不同的功能替代集进行事务容 错． 单处理器容错调度算法研究的主要目的是在满足系统实时性、可靠性等要求的前提下提高系统资源的 利用率和吞吐率，降低任务的拒绝率．其中实时调度算法通常采用RMS(rate monotonic scheduling)和 EDFl_3 两种经典调度策略．文献[4]中提出了一种APR(alternate—primary recovery)调度方法，当一个主任 务的错误次数超过预定值时，使用一个替代主任务代替出错主任务执行，能有效提高主任务的成功率；文E53 对任务之间的抢占进行了研究，给每个任务分配一个常规优先级和抢占极限，只有抢占任务的常规优先级高 于被抢占任务的抢占极限时才能抢占成功．文[6—8]提出了一种BCE算法，由基本算法、可用时间计算(chec— king available time，CAT)和空闲时间消除(eliminating idle time，EIT)算法组成：按基本算法分配替代任 务、调度主任务，使用CAT对任务可行性进行判断，降低由于任务没有足够时间执行而导致的失败，并在系 统空闲时调用EIT方法优化任务调度． 本文将容错技术引人实时数据库系统，对其中的周期性实时事务进行容错调度，确保其时限的满足，以 免造成灾难性后果．针对可抢占周期性任务的调度过程中，对即将完成的低优先级任务的抢占会降低系统性 能的情况，提出了一种抢占评估算法PEA(preemptive estimate algorithm)，以提高系统的任务成功率和资 源利用率． 1 系统模型 实时数据库中的事务为若干任务的集合，每个任务又由若干等价子任务组成，在每个任务中取一个子任 务就组成该事务的一个替代．为简单起见，我们将实时事务分为两个功能等价的子任务：主任务，包含了更多 的功能，提供精确的结果，但需要更多的CPU计算时间和数据i／o，由于其复杂性不能保证它的可靠性；替 代任务，提供不是十分精确但及时的结果，以满足系统的最低功能要求，能够保证其可靠性． 仅考虑实时数据库中的周期性实时事务，调度前，对事务进行预分析，得到其周期、资源需求、截止期、各 收稿日期：2007 07—03 基金项目：山东省科技攻关项目，编号2004GG22051O8． 作者简介：刘文晓(1982 )，男，硕士研究生，主要从事实时系统、嵌人式系统研究，E—mail：1iu985104@163．COrn． 第4期 刘文晓等：基于EDF的实时数据库动态容错调度算法 57 任务的最差执行时间等信息．其中，截止期取事务截止期和其访问的数据的有效期中的较小者．事务具有可 抢占性，仅考虑暂态错误，事务之间相互独立．由于事务的主任务提供了更好的结果，所以设法执行