实时容错调度策略研究

作     者：胡志鹏 

作者单位：华中科技大学 

学位级别：硕士

导师姓名：徐丽萍

授予年度：2008年

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：容错松弛时间 触发时刻 实际可利用执行时间 FT-LLF算法 

摘      要：随着实时系统在各个领域的广泛应用,实时容错技术也得到了深入的研究。在实时系统中,任务执行失败可能导致灾难性的后果。这就对实时系统的实时性和可靠性提出了很高的要求。 实时容错技术是针对实时系统的故障提出的一种解决方案,主要的方法就是对系统的资源进行冗余。对硬件冗余技术的研究已经很成熟了,这里主要是针对实时系统的软件冗余技术做出一些初步的探讨。 软件冗余策略有两种:N版本软件冗余策略和恢复块策略。重点对恢复块软件冗余策略展开研究,采用主副版本冗余的策略,在单处理机环境下的主副版本任务的实时容错调度算法。 实时容错调度算法是根据实时调度算法改进而来,这种改进主要是根据RM算法和EDF算法。BCE(Basic Algorithm, CAT Algorithm, EIT Algorithm)算法根据RM算法改进而来。EBPA (Expectation-Based Probing Algorithm)算法提出了容错截止期的概念,改进EDF算法得来。 在容错松弛时间和实际可利用执行时间两个概念的基础上,一种实时容错调度算法——FT-LLF(Fault Tolerant Least Laxity First )算法,经过理论分析和实验验证,FT-LLF算法能够有效地降低主版本任务丢失率,降低浪费的CPU时间片的数量。