[1]吴俊.基于双优先级队列的异构分布式控制系统容错调度算法[J].东南大学学报(自然科学版),2008,38(3):407-412.[doi:10.3969/j.issn.1001-0505.2008.03.009]
 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.[doi:10.3969/j.issn.1001-0505.2008.03.009]
点击复制

基于双优先级队列的异构分布式控制系统容错调度算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
38
期数:
2008年第3期
页码:
407-412
栏目:
计算机科学与工程
出版日期:
2008-05-20

文章信息/Info

Title:
Fault-tolerant scheduling algorithm for heterogeneous distributed control systems based on dual priorities queues
作者:
吴俊
东南大学机械工程学院, 南京 210096
Author(s):
Wu Jun
School of Mechanical Engineering, Southeast University, Nanjing 210096, China
关键词:
分布式控制系统 双优先级队列 容错调度算法 任务分配 版本复制技术
Keywords:
distributed control system dual priority queues fault-tolerance scheduling algorithm task assignment duplication technique
分类号:
TP316
DOI:
10.3969/j.issn.1001-0505.2008.03.009
摘要:
在对分布式控制系统进行分析的基础上,给出了任务模型和处理器模型.为了调度多种实时性的任务,提出了双优先级队列调度算法,用于调度每个处理器上的任务.该算法设置2个优先级队列,其中高优先级队列用于调度实时任务,低优先级队列用于调度非实时任务,高优先级队列中的任务可抢占低优先级队列中的任务.在此基础上,采用版本复制技术使系统具有容错能力,并分析了任务的容错可调度条件.基于此,采用首次适应的启发式任务分配策略,将任务分配到各个处理器上,在确保任务容错可调度的条件下使处理器负载均衡.仿真结果表明所提出的算法是有效的.
Abstract:
Based on the analysis of distributed control system(DCS), the task models and processor model are given. In order to schedule all kinds of tasks, a novel tasks scheduling algorithm named dual-priority queues for uniprocessor is presented. Two priority queues, one is called high priority queue to be used to schedule real-time tasks and the other is called low priority queue to be used to schedule non-real-time tasks, are set in the algorithm. The task in high priority queue can preempt the running of the task in low priority queue. Based on this, task duplication technique is adopted to make DCS have fault-tolerance. The fault-tolerant and schedulable condition is investigated. Therefore, heuristic task assignment method named first-fit is applied to assign tasks to processor. The algorithm can equilibrate the load of every processor under the fault-tolerant scheduling condition of tasks. Finally, the simulation experiments show that the algorithm is effective.

参考文献/References:

[1] 刘怀,费树岷.基于EDF的分布式控制系统容错调度算法[J].软件学报,2003,14(8):1371-1378.
  Liu Huai,Fei Shumin.A fault-tolerant scheduling algorithm based on EDF for distributed control systems [J].Journal of Software,2003,14(8):1371-1378.(in Chinese)
[2] Bertossi Alan A,Mancini Luigi V,Rossini Federico.Fault-tolerant rate-monotonic first-fit scheduling in hard-real-time systems [J]. IEEE Transactions on Parallel and Distributed Systems, 1999,10(9):934-945.
[3] 罗威,杨富民,庞丽萍,等.基于延迟主动副版本的分布式实时容错调度算法[J].计算机研究与发展,2007,44(3):521-528.
  Luo Wei,Yang Fumin,Pang Liping,et al.A real-time scheduling algorithm for distributed systems based on differed active backup-copy[J].Journal of Computer Research and Development,2007,44(3):521-528.(in Chinese)
[4] 阳春华,桂卫华,计莉.基于多处理机的混合实时任务容错调度[J].计算机学报,2003,26(11):1479-1486.
  Yang Chunhua,Gui Weihua,Ji Li.A fault-tolerant scheduling algorithm of hybrid real-time tasks based on multiprocessors [J].Chinese Journal of Computers,2003,26(11):1479-1486.(in Chinese)
[5] Manimaran G,Murthy C Siva Ram.A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis [J]. IEEE Transactions on Parallel and Distributed Systems,1998,9(11):1137-1152.
[6] Ghosh Sunondo,Melhem Rami,Mosse Daniel.Fault-tolerance through scheduling of periodic tasks in hard real-time multiprocessor systems[J].IEEE Transactions on Parallel and Distributed Systems,1997,8(3):272-284.
[7] Han Ching-Chih,Shin Kang G,Wu Jian.A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults[J]. IEEE Transactions on Computers,2003,52(3):362-372.
[8] 刘怀,费树岷.控制系统中实时任务的动态优化调度算法[J].控制与决策,2005,20(3):246-250.
  Liu Huai,Fei Shumin.Optimal dynamic scheduling algorithm for real-time tasks in digital control systems [J].Control and Decision,2005,20(3):246-250.(in Chinese)
[9] Liu C L,Layland J W.Scheduling algorithms for multiprogramming in hard real-time environment[J]. Journal of Association for Computing Machinery,1973,20(1):46-61.
[10] 刘怀,沈捷,费树岷.用双优先级算法调度控制系统的实时周期性任务[J].东南大学学报:自然科学版,2003,33(2):190-193.
  Liu Huai,Shen Jie,Fei Shumin.Scheduling real-time periodic task of control system with dual priority algorithm [J]. Journal of Southeast University:Nature Science Edition,2003,33(2):190-193.(in Chinese)
[11] Tovar E,Vasques F.Non pre-emptive scheduling of messages on SMTV token-passing networks [C] //Proceedings of the 12th Euromicro Conference on Real-time Systems(RTS 2000).Stockholm,Sweden:IEEE CS Press,2000:209-218.

备注/Memo

备注/Memo:
作者简介: 吴俊(1969—),男,博士生,副教授,wu_jun@seu.edu.cn.
引文格式: 吴俊.基于双优先级队列的异构分布式控制系统容错调度算法[J].东南大学学报:自然科学版,2008,38(3):407-412.
更新日期/Last Update: 2008-05-20