基于截止期错失率可预测的高利用率容错调度  

A Fault-Tolerant Scheduling Method Based on Predictable Deadline Miss Ratio in High Utilization

作　　者：伍微[1] 倪少杰[1] 王飞雪[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,长沙410073

出　　处：《计算机研究与发展》2010年第2期370-376,共7页Journal of Computer Research and Development

基　　金：教育部新世纪优秀人才支持计划基金项目(NCET-04-0995)~~

摘　　要：现代导航与通信等实时系统经常面临着复杂的实时数字信号处理及信息交互需求,处理器处于高利用率状态.对于此类高利用率实时系统,传统的时间冗余容错通常会引发多个任务连续错失截止期的灾难性后果.针对高利用率情况,提出一种截止期错失率可预测的容错调度方法,截止期错失次数不大于出现错误的次数,消除了多个任务截止期连续错失的多米诺效应.进一步地在该方法中融合时间冗余方法的优点,提出了求解检测点上界位置的离线快速算法,有效地降低了截止期错失率.仿真实验表明,与目前已知的同类方法相比,该方法具有更低的截止期错失率.Modern real-time systems, such as navigation and communication, emphasize high reliability and validity, which requires 100% error detection and fault recovery. Meanwhile, those systems also face the requirement of sophisticated real-time digital signal processing and information intercommunication, where real-time processing is in high utilization, resulting in a lack of timing resource for error detection and fault recovery. This requires that systems have predictable performance. Traditional time redundancy methods cannot deal with high utilization, since they need to guarantee fault recovery while no deadline is miSsed, which severely restricts their use in high utilization systems. Researches show that traditional time redundancy fault-tolerance in high utilization real-time systems may result in a disaster. A new fault-tolerant method is presented to deal with the problem. The main contribution of this paper is that a fault-tolerant method with predictable DMR（deadline miss ratio） in high utilization is proposed. The number of deadline missing is not greater than the number of error occurrences, which eliminates the domino effect of continuous deadline missing. A further improved approach is presented, and DMR can be effectively reduced by adopting time redundancy techniques based on off-line checkpointing analysis. The simulation experiments show that the proposed method leads to lower predictable DMR compared with the well- known algorithms so far.

关 键 词：容错调度 高利用率 截止期错失率 时间冗余 多米诺效应 检测点 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]