Abstract
In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors can be used to achieve better performance. However, analytical and efficient validation methods for determining whether all the timing constraints are met do not yet exist for systems using modern dynamic scheduling strategies, and exhaustive methods are often infeasible or unreliable since the execution time and release time of each job may vary. In this paper, we present several upper bounds and efficient algorithms for computing the worst-case completion times of dependent jobs in dynamic systems where jobs are dispatched and scheduled on available processors in a priority-driven manner. The bounds and algorithms consider arbitrary release times and variable execution times. We present conditions under which dependent jobs execute in a predictable manner.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Graham, R.: Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics. 17(2) (1969) 416–429
Sha, L., Sathaye, S.: A systematic approach to designing distributed real-time systems. IEEE Computer. 26(9) (1993) 68–78
Rajkumar, L. Sha, L, Lehoczky, J.: Real-time synchronization protocols for multiprocessors. Proc. of IEEE 9th Real-Time Systems Symposium. (1988) 259–269
Sun, J., Bettati, R., Liu, J.: An end-to-end approach to schedule tasks with shared resources in multiprocessor systems. Proc. of IEEE 11th Workshop on Real-Time Operating Systems and Software. (1994) 18–22
Liu, C., Layland, J.: Scheduling algorithms for multiprogramming in a hard-realtime environment. Journal of the Association for Computing Machinery. 20(1) (1973) 46–61
Lehoczky, J., Sha, L., Ding, Y.: The rate monotone scheduling algorithm: Exact characterization and average case behavior. Proc. of IEEE 10th Real-Time Systems Symposium. (1989) 166–171
Han, C., Tyan, H.: A better polynomial-time schedulability test for teal-time fixedpriority scheduling algorithms. Proc. of IEEE 18th Real-Time Systems Symposium. (1997) 36–45
Palencia, J., Harbour, M.: Schedulability analysis for tasks with static and dynamic offsets. Proc. of IEEE 19th Real-Time Systems Symposium. (1998) 26–37
Liu, J., Ha, R.: Methods for validating real-time constraints. Journal of Systems and Software. 30 (1995) 85–98
Sun, J., Liu, J.: Bounding completion times of jobs with arbitrary release times and variable execution times. Proc. of IEEE 17th Real-Time Systems Symposium. (1996) 2–12
Meyer, M., Wong-Toi, H.: Schedulability analysis of acyclic processes. Proc. of IEEE 19th Real-Time Systems Symposium. (1998) 274–283
Ha, R., Cha, H., Liu, J.: Validating real-time constraints in heterogeneous multiprocessor and distributed systems. Journal of Systems Integration. 9(3) (1999) 207–222
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cha, H., Ha, R. (2002). Validating Timing Constraints of Dependent Jobs with Variable Execution Times in Distributed Real-Time Systems. In: Katoen, JP., Stevens, P. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2002. Lecture Notes in Computer Science, vol 2280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46002-0_7
Download citation
DOI: https://doi.org/10.1007/3-540-46002-0_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43419-1
Online ISBN: 978-3-540-46002-2
eBook Packages: Springer Book Archive