Abstract
Often hard real-time systems require results that are produced on time despite the occurrence of processor failures. This paper considers a distributed system where tasks are periodic and each task occurs in multiple copies which are periodically synchronized in order to handle failures. The problem of preemptively scheduling a set of such tasks is discussed where every occurrence of a task has to be completely executed before the next occurrence of the same task. First, a static scheduling algorithm is proposed which uses periodic checkpoints to tolerate processor failures. Then, the performance of the algorithm is substancially improved employing a mixed strategy which constructs a schedule where high frequency tasks are duplicated, and low frequency tasks are periodically checkpointed. The performance of the solution proposed is evaluated in terms of the minimum achievable processor utilization due to the useful computation of the tasks. Moreover, analytical and simulation studies are used to reveal interesting trade-offs associated with the scheduling algorithm. In particular, if high frequency tasks are less than 70 percent of the total number of tasks then the mixed strategy yields a higher processor utilization than the task duplication scheme.
Similar content being viewed by others
References
Agne, R. 1991. Global cyclic scheduling: a method to guarantee the timing behaviour of distributed real-time systems.Real-Time Systems 3: 45–66.
Balaji, S., et al. 1989. Workload redistribution for fault-tolerance in a hard real-time distributed computing system.FTCS-19 Chicago, Illinois, pp. 366–373.
Bertossi, A. A., and Mancini, L. V. 1994. Scheduling algorithms for fault-tolerance in hard-real-time systems.Real-Time Systems, Special Issue on Responsive Computer Systems.
Blake, B. B., and Schwan, K. 1991. Experimental evaluation of a real-time scheduler for multiprocessor system.IEEE Trans. Soft. Eng 17(1): 34–44.
Coffman, E. G. Jr. (ed.). 1976.Computer and Job-Shop Scheduling Theory. New York: Wiley.
Davari, S., and Dhall, S. K. 1986. An on line algorithm for real time tasks allocation.IEEE Int. Real-Time System Symposium 194–200.
Dhall, S. K., and Liu, C. L. 1978. On a real time scheduling problem.Operations Research 26: 127–140.
Dertouzos, M. L., and Mok, A. K. 1989. Multiprocessor on-line scheduling of hard-real-time tasks.IEEE Trans. Soft. Eng 15(12): 1497–1506.
Krishna, C. M., and Shin, K. G. 1986. On scheduling tasks with a quick recovery from failure.IEEE Trans. on Computers 35(5): 448–454.
Lawler, E. L., et al. 1981. Scheduling periodically occurring tasks on multiple processors.Inform. Proc. Lett. 12: 9–12.
Liestman, A. L., and Campbell, R. H. 1986. A fault-tolerant scheduling problem.IEEE Trans. Soft. Eng 12(11): 1089–1095.
Liu, C. L., and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment.Journal ACM 20: 46–61.
Leung, J.Y.-T., and Merrill, M. L. 1980. A note on preemptive scheduling periodic real-time tasks.Inform. Proc. Lett. 11: 115–118.
Lehoczky, J. P., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: exact characterization and average case behavior.Proc. IEEE Real-Time Systems Symposium.
Lehoczky, J. P., Sprunt, B., and Sha, L. 1988. Aperiodic task scheduling for hard-real-time systems.Proc. IEEE Real-Time Systems Symposium.
McNaughton, R. 1959. Scheduling with deadlines and loss functions.Management Science 12(7).
Randell, B., Lee, P. A., and Treleaven, P. C. 1978. Reliability issues in computing system design.ACM Computing Surveys 10(2): 123–166.
Ramamritham, K., and Stankovic, J. A. 1991. Scheduling strategies adopted in SPRING: an overview.Found. of Real-Time Computing.
Stankovic, J. A. 1989. Decentralized decision making for task reallocation in hard real-time systems.IEEE Trans. on Computers 38(3): 341–355.
Stankovic, J. A., et al. 1985. Evaluation of a flexible task scheduling algorithm for distributed hard real-time systems.IEEE Trans. on Computers 34(12): 1130–1143.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bertossi, A.A., Bonometto, M. & Mancini, L.V. Increasing processor utilization in hard-real-time systems with checkpoints. Real-Time Syst 9, 5–29 (1995). https://doi.org/10.1007/BF01094171
Issue Date:
DOI: https://doi.org/10.1007/BF01094171