Abstract
Most existing real-time fault-tolerant scheduling algorithms for heterogeneous distributed systems can achieve high reliability for non-preemptive and aperiodic tasks. However, the existing scheduling algorithms assume that status of each backup copy is either active or passive. To remedy this deficiency, we propose a novel reliability model tailored for preemptive periodic tasks. Next, we develop two real-time fault-tolerant algorithms (NRFTAHS and RDFTAHS) for heterogeneous distributed systems. NRFTAHS manages to assign tasks in a way to improve system schedulabilties, whereas RDFTAHS aims at boosting system reliability without adding extra hardware. Unlike the existing scheduling schemes, our algorithms consider backup copies in both active and passive forms. Therefore, our approaches are more flexible than the alternative ones. Finally, we quantitatively compare our schemes with two existing algorithms in terms of performability measured as a function of schedulability and reliability. Experiments results show that RDFTAHS substantially improves the overall performance over NRFTAH.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ranaweera, S., Agrawal, D.P.: Scheduling of Periodic Time Critical Applications for Pipelined Execution on Heterogeneous Systems. In: Proceeding of the 2001 International Conference on Parallel Processing, Spain (2001)
Srinivasan, S., Jha, N.K.: Safety and Reliability Driven Tasks Allocation in distributed Systems. IEEE Trans. Parallel and distributed systems 10, 238–251 (1999)
Dogan, A., Ozguner, F.: Reliable matching and scheduling of precedence-constrained tasks in heterogeneous distributed computing. In: Proceeding of 29th International Conference on Parallel Processing, Spain (2001)
Yang, C.H., Deconinck, G., Gui, W.H.: Fault-tolerant scheduling for real-time embedded control systems. Journal of Computer Science and Technology 19, 191–202 (2004)
Liu, H., Fei, S.M.: A Fault-Tolerant Scheduling Algorithm Based on EDF for Distributed Control Systems. Chinese Journal of Computers 14, 1371–1378 (2003)
Omari, R.A.l., Somani, A.K., Manimaran, G.: An adaptive scheme for fault-tolerant scheduling of soft real-time tasks in multiprocessor systems. Journal of Parallel and Distributed Computing 65, 595–608 (2005)
Bertossi, A.A., Mancini, L.V., Rossini, F.: Fault-tolerant rate-monotonic first-fit scheduling in hard-real-time systems. IEEE Trans. Parallel and Distributed Systems 10, 934–945 (1999)
Qin, X., Han, Z.F., Pang, L.P.: Towards Real-time Scheduling with Fault-tolerance in Heterogeneous Distributed Systems. Chinese Journal of Computers 25, 121–124 (2002)
Qin, X., Hong, J.: Dynamic, Reliability-driven Scheduling of Parallel Real-time Jobs in Heterogeneous Systems. In: Proceeding of the 2001 International Conference on Parallel Processing, Spain (2001)
Qin, X., Hong, J., David, R.S.: An Efficient Fault-tolerant Scheduling Algorithm for Real-time Tasks with Precedence Constraints in Heterogeneous Systems. In: Proceeding of the 31st International Conference on Parallel Processing (ICPP), Canada (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Luo, W., Yang, F., Pang, L., Qin, X. (2006). Fault-Tolerant Scheduling Based on Periodic Tasks for Heterogeneous Systems. In: Yang, L.T., Jin, H., Ma, J., Ungerer, T. (eds) Autonomic and Trusted Computing. ATC 2006. Lecture Notes in Computer Science, vol 4158. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11839569_56
Download citation
DOI: https://doi.org/10.1007/11839569_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38619-3
Online ISBN: 978-3-540-38622-3
eBook Packages: Computer ScienceComputer Science (R0)