实时容错调度策略研究.doc

华中科技大学硕士学位论文分类号学号642100200672285学校代码10487密级硕士学位论文实时容错调度策略研究学位申请人：胡志鹏学科专业：计算机软件与理论指导教师：徐丽萍副教授答辩日期：2008年5月28日AThesisSubmittedtoHuazhongUniversityofScienceandTechnologyfortheDegreeofMasterofEngineeringResearchofReal-timeFaultTolerantSchedulingStrategyCandidate:HuZhipengMajor:ComputerSoftwareandTheorySupervisor:AssociateProf.XuLipingHuazhongUniversityofScienceandTechnologyWuhan430074,P.R.ChinaMay,2008独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□，在_____年解密后适用本授权书。不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月摘要随着实时系统在各个领域的广泛应用，实时容错技术也得到了深入的研究。在实时系统中，任务执行失败可能导致灾难性的后果。这就对实时系统的实时性和可靠性提出了很高的要求。实时容错技术是针对实时系统的故障提出的一种解决方案，主要的方法就是对系统的资源进行冗余。对硬件冗余技术的研究已经很成熟了，这里主要是针对实时系统的软件冗余技术做出一些初步的探讨。软件冗余策略有两种：N版本软件冗余策略和恢复块策略。重点对恢复块软件冗余策略展开研究，采用主副版本冗余的策略，在单处理机环境下的主副版本任务的实时容错调度算法。实时容错调度算法是根据实时调度算法改进而来，这种改进主要是根据RM算法和EDF算法。BCE(BasicAlgorithm,CATAlgorithm,EITAlgorithm)算法根据RM算法改进而来。EBPA(Expectation-BasedProbingAlgorithm)算法提出了容错截止期的概念，改进EDF算法得来。在容错松弛时间和实际可利用执行时间两个概念的基础上，一种实时容错调度算法——FT-LLF(FaultTolerantLeastLaxityFirst)算法，经过理论分析和实验验证，FT-LLF算法能够有效地降低主版本任务丢失率，降低浪费的CPU时间片的数量。关键词：容错松弛时间;触发时刻;实际可利用执行时间;FT-LLF算法AbstractWiththereal-timesystemextensivelyappliedinvariousfields,real-timefaulttoleranttechniquehasbeendeeplystudied.Task’sexecutionfailuremayresultindisastrousconsequence.Thatproposeshighdemandsforreal-timeandreliabilityforthereal-timesystem.Re