Object technologies and real-time scheduling

ABSTRACT

Any object-based real-time system gives rise to real-time scheduling issues not easily solved by use of standard scheduling methods, including: (1) the invocation of an object's method may imply the need for online schedulability analysis for the thread(s) able to execute method code, (2) parallelism internal to objects may result in the need to schedule multiple threads and target processors simultaneously, and (3) methods that invoke other methods as part of their execution give rise to hierarchically composed groups of to-be-scheduled real-time threads. The Rapid scheduler presented in this paper addresses such dynamic object-based real-time systems for target machines comprised of both multi- and uniprocessor machines. To address the variety of needs of object-based real-time systems, Rapid is 1) configurable to the target multiprocessor architecture, 2) dynamically re-configurable to changes in application requirements, 3) efficient in terms of processor utilization, and 4) effective in producing high quality schedules. Rapid's current implementation addresses hard deadline application, with future work concerning alternative formulations of timing constraints.

REFERENCES

• 1: [Anderson et al., 1990] T.E. Anderson, B.N. Bershad, E.D. Lazowska, and H.M. Levy. Scheduler activations: Effective kernel support for the user-level management of parallelism. Technical report, Department of Computer Science and Engineering, University of Washington, TR 90-04-02, April 1990.
• 2: T. E. Bihari , T. M. Walliser , M. R. Patterson, Controlling the Adaptive Suspension Vehicle, Computer, v.22 n.6, p.59-65, June 1989 [doi>10.1109/2.30721]
• 3: Ben Arthur Blake, A fast, effective scheduling framework for parallel computing systems, Ohio State University, Columbus, OH, 1990
• 4: [III et al., 1992] H. Burkhardt III, S. Frank, B. Knobe, and J. Rothnie. Overview of the ksr1 computer system. Technical Report KSR-TR-9202001, Kendall Square Research, Boston, February 1992.
• 5: D. D. Kandlur , D. L. Kiskis , K. G. Shin, HARTOS: a distributed real-time operating system, ACM SIGOPS Operating Systems Review, v.23 n.3, p.72-89, July 1989 [doi>10.1145/71021.71025]
• 6: [Locke et al., 1985] C. D. Locke, H. Tokuda, and E. D. Jensen. A time-driven scheduling model for real-time operating systems. Technical report, Carnegie-Mellon University, 1985.
• 7: [Mok and Dertouzos, 1978] A. K. Mok and M. L. Dertouzos. Multiprocessor scheduling in a hard real-time environment. In Proc. of the Seventh Texas Conference on Computing Systems, November 1978.
• 8: [Niehaus et al., 1993] Douglas Niehaus, Krithi Ramamritham, John A. Stankovic, Gary Wallace, and Charles Weems. The spring scheduling co-processor: Design, use and performance. In Proceedings of the Real-Time Systems Symposium, pages 106-111. IEEE Computer Society Press, December 1993.
• 9: K. Ramamritham , J. A. Stankovic , W. Zhao, Distributed Scheduling of Tasks with Deadlines and Resource Requirements, IEEE Transactions on Computers, v.38 n.8, p.1110-1123, August 1989 [doi>10.1109/12.30866]
• 10: Karsten Schwan , Hongyi Zhou, Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads, IEEE Transactions on Software Engineering, v.18 n.8, p.736-748, August 1992 [doi>10.1109/32.153383]
• 11: [Sprunt et al., 1989] Brinkley Sprunt, Lui Sha, and John Lehoczky. Aperiodic task scheduling for hard-real-time systems. The Journal of Real-Time Systems, 1:27-60, 1989.
• 12: John A. Stankovic , Krithi Ramamritham, The Spring Kernel: A New Paradigm for Real-Time Systems, IEEE Software, v.8 n.3, p.62-72, May 1991 [doi>10.1109/52.88945]
• 13: [Wisniewski and Brown, 1993] R. W. Wisniewski and C. M. Brown. Ephor, a run-time environment for parallel intelligent applications. In Proceedings of the Workshop on Parallel and Distributed Real-Time Systems, pages 51-60, April 1993. Newport Beach, CA.
• 14: [Zhou et al., 1992] Hongyi Zhou, Karsten Schwan, and Ian F. Akyildiz. Performance effects of information sharing in a distributed multiprocessor real-time scheduler. In Real-Time Systems Symposium. IEEE, IEEE, 1992. Also available as GIT-CC-91/40 from Ga. Tech.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Concurrent C

General Terms:
Experimentation, Management