Abstract
In the design of real-time systems, it is often the case that certain process parameters, such as its execution time are not known precisely. The challenge in real-time system design is to develop techniques that efficiently meet the requirements of impreciseness. Traditional models tend to simplify the issue of impreciseness by assuming worst-case values. This assumption is unrealistic and at the same time, may cause certain constraints to be violated at run-time. In this paper, we study the problem of scheduling a set of ordered, non-preemptive jobs under non-constant execution times. Typical applications for variable execution time scheduling include process scheduling in Real-time Operating Systems such as Maruti, compiler scheduling, database transaction scheduling and automated machine control. An important feature of application areas such as robotics is the interaction between execution times of various processes. We explicitly model this interaction through the representation of execution time vectors as points in convex sets. Our algorithms do not assume any knowledge of the distributions of execution times, i.e. they are zero-clairvoyant. We present both sequential and parallel algorithms for determining the existence of a zero-clairvoyant schedule.
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
M. Berkelaar. Linear programming solver. Software Library for Operations Research, University of Karlsruhe, 1995.
Azer Bestavros and Victor Fay-Wolfe, editors. Real-Time Database and Information Systems, Research Advances. Kluwer Academic Publishers, 1997.
Seonho Choi. Dynamic time-based scheduling for hard real-time systems. Journal of Real-Time Systems, 2000.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill Book Company, 6th edition, 1992.
B. Dasarathy. Timing Constraints of Real-Time Systems: Constructs for Expressing Them, Methods of Validating Them. IEEE Transactions on Software Engineering, SE-11(1):80–86, January 1985.
R. Dechter, I. Meiri, and J. Pearl. Temporal constraint networks. Artificial Intelligence, 49:61–95, 1991.
A. Damm, J. Reisinger, W. Schwabl, and H. Kopetz. The Real-Time Operating System of MARS. ACM Special Interest Group on Operating Systems, 23(3):141–157, July 1989.
R. Gerber, W. Pugh, and M. Saksena. Parametric Dispatching of Hard Real-Time Tasks. IEEE Transactions on Computers, 1995.
S. Hong and R. Gerber. Compiling real-time programs into schedulable code. In Proceedings of the ACM SIGPLAN’ 93 Conference on Programming Language Design and Implementation. ACM Press, June 1993. SIGPLAN Notices, 28(6):166–176.
C. C. Han and K. J. Lin. Job scheduling with temporal distance constraints. Technical Report UIUCDCS-R-89-1560, University of Illinois at Urbana-Champaign, Department of Computer Science, 1989.
C. C. Han and K. J. Lin. Scheduling Distance-Constrained Real-Time Tasks. In Proceedings, IEEE Real-time Systems Symposium, pages 300–308, Phoenix, Arizona, December 1992.
C. C. Han and K. J. Lin. Scheduling real-time computations with separation constraints. Information Processing Letters, 12:61–66, May 1992.
Dorit S. Hochbaum and Joseph (Seffi) Naor. Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM Journal on Computing, 23(6):1179–1192, December 1994.
J. B. Hiriart-urruty and C. Lemarechal. Convex Analysis and Minimization Algorithms. Springer-Verlag, 1993.
Joseph Ja'Ja'. An introduction to parallel algorithms (contents). SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 23, 1992.
F. Jahanian and A.K. Mok. Safety analysis of timing properties in realtime systems. IEEE Transactions on Software Engineering, SE-12(9):890–904, September 1986.
S. T. Levi, S. K. Tripathi, S. D. Carson, and A. K. Agrawala. The Maruti Hard Real-Time Operating System. ACM Special Interest Group on Operating Systems, 23(3):90–106, July 1989.
D. Mosse, Ashok K. Agrawala, and Satish K. Tripathi. Maruti a hard real-time operating system. In Second IEEE Workshop on Experimental Distributed Systems, pages 29–34. IEEE, 1990.
D. Mosse, Keng-Tai Ko, Ashok K. Agrawala, and Satish K. Tripathi. Maruti: An Environment for Hard Real-Time Applications. In Ashok K. Agrawala, Karen D. Gordon, and Phillip Hwang, editors, Maruti OS, pages 75–85. IOS Press, 1992.
M. Pinedo. Scheduling: theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs, 1995.
Manas Saksena. Parametric Scheduling in Hard Real-Time Systems. PhD thesis, University of Maryland, College Park, June 1994.
A. Stoyenko and T. P. Baker. Real-Time Schedulability Analyzable Mechanisms in Ada9X. Proceeding of the IEEE, 82(1):95–106, January 1994.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1987.
M. Saksena, J. da Silva, and A. Agrawala. Design and Implementation of Maruti-II. In Sang Son, editor, Principles of Real-Time Systems. Prentice Hall, 1994. Also available as CS-TR-2845, University of Maryland.
K. Subramani. Duality in the Parametric Polytope and its Applications to a Scheduling Problem. PhD thesis, University of Maryland, College Park, July 2000.
K. Subramani. Modeling clairvoyance and constraints in real-time scheduling. In Proceedings of the 6th European Conference on Planning, September 2001.
P. M. Vaidya. An algorithm for linear programming which requires O(((m + n)n2 + (m + n)1.5n)L) arithmetic operations. In Alfred Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 29–38, New York City, NY, May 1987. ACM Press.
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
Subramani, K. (2002). An Analysis of Zero-Clairvoyant Scheduling. 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_8
Download citation
DOI: https://doi.org/10.1007/3-540-46002-0_8
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