允许多处理机故障的实时任务容错调度算法

殷进勇; 顾国昌

doi:10.3724/SP.J.1146.2009.00263

允许多处理机故障的实时任务容错调度算法

doi: 10.3724/SP.J.1146.2009.00263

计量
- 文章访问数: 3071
- HTML全文浏览量: 68
- PDF下载量: 845
- 被引次数: 0
出版历程
- 收稿日期: 2009-03-04
- 修回日期: 2009-09-25
- 刊出日期: 2010-02-19

A Real-time Fault-tolerant Scheduling Algorithm for Multiple Processor Faults

摘要

摘要: 随着故障处理机个数增加，基于主/从版本技术的实时容错调度算法对处理机利用率迅速下降。论文提出了一种能够调度周期和非周期混合实时任务的容错调度算法，该算法允许多个处理机出现故障。把DS(Deferrable Server)算法扩展到多处理机系统，可在系统中设置多个DS服务器来处理非周期任务。当处理机出现故障时，通过在其他处理机上回卷执行故障任务，保证了系统的容错性能。实验结果表明，该算法能够使系统接收的所有实时任务满足截止期限并有效地减少了所需的处理机数。
- 实时容错调度; 整体调度; 混合任务; 延时服务器; 多处理机故障
Abstract: The existing fault-tolerant scheduling algorithms are mainly based on primary/backup copies technology and the utilization of processor decreases greatly with the number of faults increases. In this paper, a real-time fault-tolerant scheduling algorithm is proposed to schedule periodic and aperiodic tasks jointly and tolerate multiple processor faults. The DS (Deferrable Server) algorithm is extended to the multiprocessors system, and several deferrable servers can be set to schedule aperiodic tasks. The faults can be tolerated by tasks rollback executing on the other processors. The experimental results demonstrate that this algorithm can guarantee all accepted tasks deadlines and decreases the number of required processor significantly.

HTML全文

参考文献(1)

罗威, 阳富民, 庞丽萍等. 基于延迟主动副版本的分布式实时容错调度算法 [J]. 计算机研究与发展, 2007, 44(3): 521-528.Luo Wei, Yang Fu-min, and Pang Li-ping, et al.. A real-time fault-tolerant scheduling algorithm for distributed systems based on deferred active backup-copy [J].Journal of Computer Research and Development.2007, 44(3):521-528[2]罗威, 阳富民, 庞丽萍等. 异构分布式系统中实时周期任务的容错调度算法[J]. 计算机学报, 2007, 30(10): 1740-1749.Luo Wei, Yang Fu-min, and Pang Li-ping, et al.. A real-time fault-tolerant scheduling algorithm of periodic tasks in heterogeneous distributed systems[J]. Chinese Journal of Computers, 2007, 30(10): 1740-1749.[3]吴俊. 基于双优先级队列的异构分布式控制系统容错调度算法[J]. 东南大学学报(自然科学版), 2008, 38(3): 407-412.Wu Jun. Fault-tolerant scheduling algorithm for heterogeneous distributed control systems based on dual priorities queues [J]. Journal of Southeast University (Natural Science Edition), 2008, 38(3): 407-412.[4]潘雪增, 姚鑫骅, 傅建中等. 基于回卷恢复的数控系统实时容错调度策略[J]. 浙江大学学报(工学版), 2007, 41(12): 2011-2016.Pan Xue-zeng, Yao Xin-zua, and Fu Jian-zhong, et al.. Tolerant real-time scheduling strategy for nc system based on rollback recovery [J]. Journal of Zhejiang University (Engineering Science), 2007, 41(12): 2011-2016.[5]Strosnider J A, Lehoczky J P, and Sha L. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments [J]. IEEE Transactions on Computers, 1995 , 44(1): 73-91.[6]Lehoczky J P and Thuel S R. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems [C]. Proceedings of the 13th IEEE Real-Time Systems Symposium, Phoenix, Arizona: 1992, 110-123.[7]阳春华, 桂卫华, 计莉. 基于多处理机的混合实时任务容错调度[J]. 计算机学报, 2003, 26(11): 1480-1486.Yang Chun-hua, Gui Wei-hua, and Ji Li. A fault-tolerant scheduling algorithm of hybrid real-time tasks based on multiprocessors [J]. Chinese Journal of Computers, 2003, 26(11): 1480-1486.[8]Baker T P. Multiprocessor EDF and deadline monotonic schedulability analysis [C]. Proceedings of the 24th IEEE International Real-Time Systems Symposium, 2003: 120-129.[9]Baker T P. An analysis of deadline-monotonic scheduling on a multiprocessor. technical report TR-030301, Florida State University Department of Computer Science, Tallahassee, Florida (February 2003).[10]Abdelzaher T F and Sharma T F. A utilization bound for aperiodic tasks and priority driven scheduling [J].IEEE Transactions on Computers.2004, 53(3):334-350

施引文献

资源附件(0)

访问统计