软件容错模型中的容错实时调度算法

Fault-Tolerant Real-Time Scheduling Algorithm in Software Fault-Tolerant Module

在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务.DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.

In the fault-tolerant real-time scheduling algorithms of software fault-tolerant module, each task possesses two versions, namely, primary and alternate. The prediction of executable primaries is the key issue that affects scheduling performance. In order to improve the prediction precision of primaries, new algorithms named DPA （deep-prediction based algorithm） and EDPA （EDF-based DPA） are put forward. Two algorithms schedule tasks with the help of prediction-table, which is created for the released primary and contains the information of the tasks between the current time and the notification time. In DPA algorithm, the primaries in prediction-table are scheduled according to the temporal sequence of their corresponding alternates＇ notification time. EDPA algorithm schedules primaries using EDF algorithm in prediction-table. If primaries in prediction-table do not fail, the table is referenced to schedule tasks with no cost. Simulation results show that DPA and EDPA algorithms provide more execution time for primaries and waste less CPU time than the well-known algorithms so far. It is shown that the two algorithms can get higher scheduling performance with lower cost in the circumstance when tasks periods are short and software fault probability is low .