Abstract
Static scheduling has been well accepted for its predictability and online simplicity. Traditional static schedule generation techniques are usually based on the assumption of constant rate of resource supply known at design time. Under resource composition schemes, however, this assumption may not be valid for a workload to be statically scheduled. A pre-schedule is a static schedule without assuming constant and completely predictable rate of resource supply. In this paper, concepts of supply function and supply contract are introduced to define the actual online resource supply rate and the constraints to this rate known off-line. Based on these concepts, this paper defines the pre-scheduling problem, and presents a sound, complete, and PTIME pre-scheduler.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baker, T. P., and Shaw, A. 1988. The cyclic executive model and ada. In Real-Time Systems Symposium, pp. 120–129.
Deng Z., and Liu, J. 1997. Scheduling Real-time applications in an open environment. In Real-Time Systems Symposium, pp. 308–319.
Erschler J., Fontan, F., Merce, C., and Roubellat, F. 1983. A new dominance concept in scheduling n jobs on a single machine with ready times and due dates. Operations Research 31: 114–127.
Fohler G. 1994. Flexibility in statically scheduled real-time systems. PhD Thesis, Technisch-Naturwissenschaftliche Fakultaet, Technische Universitaet Wien, Austria.
Fohler G. 1995. Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems. in Real-Time Systems Symposium, pp. 152–161.
International Organization for Standardization: ISO/PRF 11898-4. Road vehicles — Controller area network (CAN) — Part 4: Time-triggered communication.
Isovic D., and Fohler, G. 1999. Handling sporadic tasks in off-line scheduled distributed real-time systems. EUROMICRO Conference on Real-Time Systems pp. 60–67.
Gerber R., Pugh, W., and Saksena, M. 1995. in Parametric dispatching of hard real-time tasks. IEEE Trans. on Computers, 44(3): pp. 471–479.
Karmarkar N. 1984. A new polynomial-time algorithm for linear programming. Combinatorica 4(4): 373–396.
Kopetz H. 1997. Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, ISBN 0-7923-9894-7.
Lipari G., Carpenter, J., and Baruah, S. 2000. A framework for achieving inter-application isolation in multiprogrammed, hard real-time environment. In Real-Time Systems Symposium, pp. 217–226.
Liu C. L., and Layland, J. W. 1973. Scheduling algorithms for multi-programming in hard real-time environment. Journal of ACM 20(1).
Mok A. K. 1983. Fundamental design problems of distributed systems for the hard-real-time environment. Ph.D. thesis, MIT.
Mok A. K., and Feng, X. 2001. Towards compositionality in real-time resource partitioning based on regularity bounds. In Real-Time Systems Symposium, pp. 129–138.
Peng D. T., Shin, K. G., and Abdelzaher, T. F. 1997. Assignment and scheduling communicating periodic tasks in distributed real-time systems. IEEE Transactions on Software Engineering 23(12): pp. 745–758.
Ramamritham K. 1995. Allocation and scheduling of precedence-related periodic tasks. IEEE Transactions on Parallel and Distributed Systems 6(4): pp. 412–420.
Regehr J., and Stankovic, J. A. 2001. HLS: A framework for composing soft real-time schedulers. In Real-Time Systems Symposium, pp. 3–14.
Shin I., and Lee, I. 2003. Periodic Resource Model for Compositional Real-Time Guarantees. Real-Time Systems Symposium, pp. 2–13.
Tsou D. 1997. Execution environment for real-time rule-based decision systems, PhD thesis, The University of Texas at Austin.
Wang W., Mok, A. K., and Fohler, G. 2003. Pre-scheduling: integrating off-line and on-line scheduling techniques. The Conference on Embedded Software, LNCS 2855, pp. 356–372.
Wang W., Mok, A. K., and Fohler, G. 2004. Pre-scheduling on the domain of integers. In Real-Time Systems Symposium.
Yuan X., Saksena, M. C., and Agrawala, A. K. 1994. A decomposition approach to non-preemptive real-time scheduling. Real-Time Systems 6(1): pp. 7–35.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is supported partially by grants from the Office of Naval Research under ONR contract N00014-03-1-0705 and the National Science Foundation under NSF grant CCR0207853.
Weirong Wang received B.E. in computer engineering from Beijing University of Technology, M.A. and Ph.D. in computer science from the University of Texas at Austin. He is currently an automation engineer in Intel. His research interests include real-time and embedded systems, software engineering and algorithms.
Aloysius K. Mok Aloysius K. Mok is Quincy Lee Centennial Professor in Computer Science at the University of Texas at Austin. He received the S.B. in electrical engineering, the S.M. in electrical engineering and computer science and the Ph.D. degrees in computer science, all from the Massachusetts Institute of Technology. Since 1983, Dr. Mok been on the faculty of the Department of Computer Sciences at the University of Texas at Austin. Professor Mok has done extensive research on computer software systems and is internationally known for his work in real-time systems. He is a past Chairman of the Techni- cal Committee on Real-Time Systems of the Institute of Electrical and Electronics Engineers, and has served on numerous national and international research and advisory panels. His current interests include real-time and embed- ded systems, robust and secure network-centric computing and real-time knowledge-based systems. Dr. Mok received in 2002 the IEEE TC on Real-Time Systems Award for his outstanding technical contributions and leadership achievements in real-time systems.
Gerhard Fohler is Professor and leader of the predictably flexible real-time systems group at SDL. He received his Ph.D. from Vienna University of Technology in 1994 for research towards flexibility for offline scheduling in the MARS system. He then worked at the University of Massachusetts at Amherst as postdoctoral researcher within the SPRING project. During 1996–97, he was a researcher at Humboldt University Berlin, investigating issues of adaptive reliability and real-time. Gerhard Fohler is currently chairman of the Technical Committee on Real-Time Systems of EUROMICRO.
Rights and permissions
About this article
Cite this article
Wang, W., Mok, A.K. & Fohler, G. Pre-Scheduling. Real-Time Syst 30, 83–103 (2005). https://doi.org/10.1007/s11241-005-0505-y
Issue Date:
DOI: https://doi.org/10.1007/s11241-005-0505-y