A Fault-Tolerant Scheduling Algorithm using Hybrid Overloading Technology for Dynamic Grouping based Multiprocessor Systems

  • Xing-biao Yu 1.Institute of Software Chinese Academy of Sciences 4# South Fourth Street, Zhongguancun, Beijing, P.R. China 2.Graduate University of Chinese Academy of Sciences 80# Zhongguancun East Road, Haidian District, Beijing, P.R. China
  • Jun-suo Zhao Institute of Software Chinese Academy of Sciences 4# South Fourth Street, Zhongguancun, Beijing, P.R. China
  • Chang-wen Zheng Institute of Software Chinese Academy of Sciences 4# South Fourth Street, Zhongguancun, Beijing, P.R. China
  • Xiao-hui Hu Institute of Software Chinese Academy of Sciences 4# South Fourth Street, Zhongguancun, Beijing, P.R. China

Abstract

In order to extend the application area of fault-tolerant scheduling algorithm based on hybrid overloading for multiprocessor and increase the fault-tolerant number of processors, we propose a new fault-tolerant scheduling algorithm, which is based on hybrid overloading and dynamic grouping for multiprocessor by combining logic grouping strategy for processors in primary backup overloading and backup backup overloading.This algorithm presents the formalization of the dynamic grouping for processors in fault-tolerant scheduling based on hybrid overloading and enlarges the task number included in overloading task link. In the process of fault-tolerant scheduling the processors are dynamically divided into some groups based on overloading task link, so as to keep good scheduling success ratio and enhance the fault-tolerant performance of processors. Both theoretical analysis and simulation experiment prove this algorithm’s effectiveness respectively.

Author Biography

Xing-biao Yu, 1.Institute of Software Chinese Academy of Sciences 4# South Fourth Street, Zhongguancun, Beijing, P.R. China 2.Graduate University of Chinese Academy of Sciences 80# Zhongguancun East Road, Haidian District, Beijing, P.R. China
Department of Mathematics and Computer Science

References

[1] R.Al-Omari,Arun K.Somani,G.Manimarna,Efficient overloading techniques for primarybackup scheduling in real-time systems, J.Parallel and Distributed Computing,64:629- 648,2004.
http://dx.doi.org/10.1016/j.jpdc.2004.03.015

[2] Wei Sun,Naixue Xiong,Laurence T.Yang,Chunming Rong, Towards free task overloading in passive replication based real-time multiprocessors, 10th IEEE International Conference on Computer and Information Technology, 1735-1742, 2010.

[3] Bindu Mirle,Albert M.K.Cheng, Simulation fault-tolerant scheduling on real-time multiprocessor systems using primary backup overloading, University of Houston, 1-10,2006.

[4] R.Al-Omari,Arun K.Somani,G.Manimarna, An adaptive scheme for fault-tolerant scheduling of soft real-time tasks in multiprocessor systems, J.Parallel and Distributed Computing, 65:595-608, 2005.
http://dx.doi.org/10.1016/j.jpdc.2004.09.021

[5] W.Sun,Y.Zhang,C.Yu,X.Defago,Y.Inoguchi, Dynamic scheduling real-time task using primary-backup overloading strategy for multiprocessor systems, IEICE Transactions on Information and Systems, 796-806, 2008.
http://dx.doi.org/10.1093/ietisy/e91-d.3.796

[6] W.Sun,Y.Zhang,C.Yu,X.Defago,Y.Inoguchi,Real-time task scheduling using extended overloading technique for multiprocessor system, 11th IEEE Symposium on Distributed Simulation and Real-time Applications, 95-102, 2007.
http://dx.doi.org/10.1109/DS-RT.2007.12

[7] W.Sun,Y.Zhang,C.Yu,X.Defago,Y.Inoguchi,Hybrid overloading and stochastic analysis for redundant scheduling in real-time multiprocessor systems, 26th IEEE International Symposium on Reliable Distributed Systems, 265-274, 2007.

[8] G. Manimaran, C. Siva Ram Murthy,A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis, IEEE Trans. Parallel Distributed System, 9(11):1137-1152, 1998.
http://dx.doi.org/10.1109/71.735960
Published
2014-09-14
How to Cite
YU, Xing-biao et al. A Fault-Tolerant Scheduling Algorithm using Hybrid Overloading Technology for Dynamic Grouping based Multiprocessor Systems. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 7, n. 5, p. 990-999, sep. 2014. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1358>. Date accessed: 13 july 2020. doi: https://doi.org/10.15837/ijccc.2012.5.1358.

Keywords

dynamic grouping; fault-tolerant; overloading; primary backup; backup backup