微信服务号

微信订阅号

2025-4-6- 9
Home > Archive>Volume 27, Issue 12, 2016 >3158-3171. DOI:10.13328/j.cnki.jos.004917
PDF HTML XML Export Cite reminder
Fault Tolerant Global Scheduling with Non-Preemptive Backups
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61370088); International S&T Cooperation Program of China (2014DFB10060)

  • Article
    • | |
  • Metrics
    • |
  • Reference [26]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Fault tolerance is a critical capability of hard real-time systems. Even with faults, fault tolerant scheduling algorithms are able to guarantee the real time property of tasks. In primary-backup based fault tolerant scheduling algorithms, only a small time window is left for the backup when the primary faults occur, therefore the backup will likely miss its deadline. This paper proposes a fault tolerant global scheduling with non-preemptive backups (FTGS-NPB). By assigning the highest priority to all backups, the backup can attain processor immediately in case of primary faults, and keep executing until finishing its job. In this way the backup can achieve the shortest response time. The schedulability tests are set up based on deadline analysis and response time analysis. The compatibility of priority assignment algorithms and schedulability tests is discussed. The simulation results show that FTGS-NPB can reduce the amount of additional processors for achieving fault tolerant capability.

    Reference
    [1] Monot A, Navet N, Bavoux B, Simonot-Lion F. Multisource software on multicore automotive ECUs-Combining runnable sequencing with task scheduling. IEEE Trans. on Industrial Electronics, 2012,59(10):3934-3942.[doi:10.1109/TIE.2012.2185913]
    [2] Navet N, Monot A, Bavoux B, Simonot-Lion F. Multi-Source and multicore automotive ECUs-OS protection mechanisms and scheduling. In:Proc. of the IEEE Int'l Symp. on Industrial Electronics. IEEE, 2010. 3734-3741.[doi:10.1109/ISIE.2010. 5637677]
    [3] Mossinger J. Software in automotive systems. IEEE Software, 2010,27(2):92-94.[doi:10.1109/MS.2010.55]
    [4] Gaska T, Werner B, Flagg D. Applying virtualization to avionics systems-The integration challenges. In:Proc. of the 29th Digital Avionics Systems Conf. Salt Lake City:IEEE, 2010. 2155-2195.[doi:10.1109/DASC.2010.5655297]
    [5] Krishna CM. Fault-Tolerant scheduling in homogeneous real-time systems. ACM Computing Surveys, 2014,46(4):48:1-48:34.[doi:10.1145/2534028]
    [6] Bertossi AA, Mancini LV, Menapace A. Scheduling hard-real-time tasks with backup phasing delay. In:Proc. of the 10th IEEE Int'l Symp. on Distributed Simulation and Real-Time Applications. IEEE, 2006. 107-118.[doi:10.1109/DS-RT. 2006.33]
    [7] Wang J, Sun JL, Wang XY, Yang XH, Wang SK, Chen JB. Efficient scheduling algorithm for hard real-time tasks in primary-backup based multiprocessor systems. Ruan Jian Xue Bao/Journal of Software, 2009,20(10):2628-2636. http://www.jos.org.cn/1000-9825/577.htm[doi:10.3724/SP.J.1001.2009.00577]
    [8] Zhu P, Yang FM, Tu G. Real-Time fault-tolerant scheduling for distributed systems based on improving priority of passive backup. Journal of Computer Research and Development, 2010,47(11):2003-2010(in Chinese with English abstract).[doi:10.3724/SP.J. 1001.2009.00577]
    [9] Chen HM, Luo W, Wang W, Xiang J. A novel real-time fault-tolerant scheduling algorithm based on distributed control systems. In:Proc. of the Int'l Conf. on Computer Science and Service System. Nanjing:IEEE, 2011. 80-83.[doi:10.1109/CSSS.2011.5972233]
    [10] Zhu P, Yang FM, Tu G, Zhang J, Zhou ZY. Feasible fault-tolerant scheduling algorithm for distributed hard-real-time system. Ruan Jian Xue Bao/Journal of Software, 2012,23(4):1010-1021(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4004.htm[doi:10.3724/SP.J.1001.2012.04004]
    [11] Pathan RM, Jonsson J. FTGS:Fault-tolerant fixed-priority scheduling on multiprocessors. In:Proc. of the IEEE 10th Int'l Conf. on Trust, Security and Privacy in Computing and Communications. Changsha:IEEE, 2011. 1164-1175.[doi:10.1109/TrustCom. 2011.158]
    [12] Berten V, Goossens J, Jeannot E. A probabilistic approach for fault tolerant multiprocessor real-time scheduling. In:Proc. of the 20th Int'l Parallel and Distributed Processing Symp. Rhodes Island:IEEE, 2006. 1-10.[doi:10.1109/IPDPS.2006.1639409]
    [13] Samala AK, Mallb R, Tripathy C. Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm. Swarm and Evolutionary Computation, 2014,14(1):92-105.[doi:10.1016/j.swevo.2013.10.002]
    [14] Baumann R. Soft errors in advanced computer systems. Design & Test of Computers, 2005,22(3):258-266.[doi:10.1109/MDT. 2005.69]
    [15] Krishna I, Krishna CM. Fault-Tolerant Systems. New York:Morgan Kaufmann Publishers, 2007.
    [16] Guan N, Stigge M, Wang Y, Ge Y. New response time bounds for fixed priority multiprocessor scheduling. In:Proc. of the Real-Time Systems Symp. Washington:IEEE, 2009. 387-397.[doi:10.1109/RTSS.2009.11]
    [17] Davis RI, Burns A. Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real-Time Systems, 2011,47(1):1-40.[doi:10.1007/s11241-010-9106-5]
    [18] Lee J, Shin I. Limited carry-in technique for real-time multi-core scheduling. Journal of Systems Architecture, 2013,59(7):372-375.[doi:10.1016/j.sysarc.2013.05.012]
    [19] Davis RI, Burns A, Marinho J, Nelis V, Petters SM, Bertogna M. Global fixed priority scheduling with deferred pre-emption. In:Proc. of the IEEE 19th Int'l Conf. on Embedded and Real-Time Computing Systems and Applications. Taipei:IEEE, 2013. 1-11.[doi:10.1109/RTCSA.2013.6732198]
    [20] Bertogna M, Cirinei M, Lipari G. New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In:Proc. of the 9th Int'l Conf. on Principles of Distributed Systems. Pisa:Springer-Verlag, 2005. 306-321.[doi:10.1007/11795490_24]
    [21] Andersson B. Global static-priority preemptive multiprocessor scheduling with utilization bound 38%. In:Proc. of the 12th Int'l Conf. on Principles of Distributed Systems. Luxor:Springer-Verlag, 2008. 73-88.[doi:10.1007/978-3-540-92221-6_7]
    [22] Andersson B, Jonsson J. Fixed-Priority preemptive multiprocessor scheduling:To partition or not to partition. In:Proc. of the 7th Int'l Conf. on Real-Time Computing Systems and Applications. Cheju:IEEE, 2000. 337-346.[doi:10.1109/RTCSA.2000.896409]
    [23] Audsley NC. On priority assignment in fixed priority scheduling. Information Processing Letters, 2001,79(1):39-44.[doi:10.1016/S0020-0190(00)00165-4]
    附中文参考文献:
    [8] 朱萍,阳富民,涂刚.基于被动副版本优先级提高策略的分布式实时容错调度.计算机研究与发展,2010,47(11):2003-2010.
    [10] 朱萍,阳富民,涂刚,张杰,周正勇.一种可行的分布式硬实时容错调度算法.软件学报,2012,23(4):1010-1021. http://www.jos.org. cn/1000-9825/4004.htm[doi:10.3724/SP.J.1001.2012.04004]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

彭浩,陆阳,孙峰,韩江洪.副版本不可抢占的全局容错调度算法.软件学报,2016,27(12):3158-3171

Copy
Share
Article Metrics
  • Abstract:1940
  • PDF: 3746
  • HTML: 1475
  • Cited by: 0
History
  • Received:November 11,2014
  • Revised:September 07,2015
  • Online: December 06,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033330Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063