Object-oriented real-time concurrency

ABSTRACT

The primary goal of a real-time system is predictability. Achieving this goal requires all levels of the system to work in concert to provide fixed worst-case execution-times. Un-fortunately, many real-time systems are overly restrictive, providing only ad-hoc scheduling facilities and basic concurrent functionality. Ad-hoc scheduling makes developing, verifying, and maintaining a real-time system extremely difficult and time consuming. Basic concurrent functionality forces programmers to develop complex concurrent programs without the aid of high-level concurrency features.Encouraging the use of sophisticated real-time theory and methodology, in conjunction with high-level concurrency features, requires flexibility and extensibility. Giving real-time programmers access to the underlying system data-structures makes it possible to interact with the system to incorporate new ideas and fine-tune specific applications. This paper explores this approach by examining its effect on a selection of crucial real-time issues: real-time monitors, timeouts, dynamic-priority scheduling and basic priority inheritance. The approach is implemented in μC++.

REFERENCES

• 1: Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983 [doi>10.1145/356901.356903]
• 2: N. C. Audsley, A. Bums, M. F. Pdcbardson, and A. J. Wellings. Hard real-time scheduling: The deadline-monotonic approach. In Proceedings of the 1991 IFA C/IFIP Workshop on Real-Time Operating Systems and Software AND 8th IEEE Workshop on Real-Time Operating Systems and Software, pages 127-132, Atlanta, Georgia, U. S. A., 1992.
• 3: T. P. Baker, Stack-based scheduling for realtime processes, Real-Time Systems, v.3 n.1, p.67-99, March 1991 [doi>10.1007/BF00365393]
• 4: T. Baker and O. Pazy. Real-time features of Ada 9x. In Proc. IEEE Real-Time Systems Symposium, pages 172-180, 1991.
• 5: G. Bollella, B. Brosgol, P. Dibble, S. Furr, J. Gosfing, D. Hardin, and M. Tm-nbull. The Real-Time Specification for Java. The Real-Time for Java Expert Group, http://www.rtj.org. Addison-Wesley, 2000.
• 6: M. W. Borger and R. Rajkumat'. Implementing priority inheritance algorithms in an ada rmatime system. Technical Report CMU/SEI-89-TR-15, Carnegie Mellon, 1989.
• 7: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 8: P. A. Buhr. Are safe. concurrency libraries possible? Commun. ACM, 38(2):117-120, Feb. 1995.
• 9: Peter A. Buhr , Michel Fortier , Michael H. Coffin, Monitor classification, ACM Computing Surveys (CSUR), v.27 n.1, p.63-107, March 1995 [doi>10.1145/214037.214100]
• 10: P. A. Buhr and R. A. Stroobosscher. ttC++ armotated reference manual, version 4.7. Technical report, Dept. of Computer Science, University of Waterloo, Aug. 1999. ftp:/ /plg.uwaterloo.ca/pub/uSystem/uC ++.psgz.
• 11: Alan Burns , A. J. Wellings, Real-time systems and their programming languages, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 12: David R. Butenhof, Programming with POSIX threads, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 13: Min-Ih Chen , Kwei-Jay Lin, Dynamic priority ceilings: a concurrency control protocol for real-time systems, Real-Time Systems, v.2 n.4, p.325-346, Nov. 1990 [doi>10.1007/BF01995676]
• 14: (7. L. A. Clarke. Language mad compiler support for synchronous message passing arctfitectures. Master's thesis, University of gqaterloo, gqaterloo, Ontario, Canada, N2L 3Gl, 1990.
• 15: R. I. Davis, K. W. TindeR, mad A. Burns. Scheduling slack time in fixed priority preemptive systems. In Proceedings of the Real-Time Systems Symposium, pages 222-231, Raleigh-Durham, NC, U. S. A., Dec. 1993. IEEE Computer Society Press.
• 16: Narain Gehani , William D. Roome, The concurrent C programming language, Silicon Press, Summit, NJ, 1989
• 17: T. M. Ghazalie , T. P. Baker, Aperiodic servers in a deadline scheduling environment, Real-Time Systems, v.9 n.1, p.31-67, July 1995 [doi>10.1007/BF01094172]
• 18: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 19: M. Haines. On designing fightweight threads for substrate software. In USENIX 1997 Annual Technical Conference. Anaheim, CA, pages 243-255, Jan. 1997.
• 20: A. S. Harji. High-level real-time concurrency. Master's thesis, University of Waterloo, Dec. 1999. ftp://plg.uwaterloo.ca/pub/uSystem/HarjiThesis.ps.g-z.
• 21: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 22: Nima Homayoun , Parameswaran Ramanathan, Dynamic priority scheduling of periodic and aperiodic tasks in hard real-time systems, Real-Time Systems, v.6 n.2, p.207-232, March 1994 [doi>10.1007/BF01088596]
• 23: Intermetrics, Inc. Annotated Ada Reference Manual, international standard ISO/IEC 8652:1995(E) edition, Dec. 1994. Language mad Standards Librzwies, V 6.0.
• 24: M. Joseph, editor. Real-time Systems, Specifications, Verification and Analysis. Prentice Hall, 1996.
• 25: J. P. Lehoczky, L. Sha, mad J. K. Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In Proc. IEEE Real-Time Systems Symposium, pages 261-270, 1987.
• 26: J. Y. T. Letmg mad J. Whitehead. On the complexity of fixed-priority schedufing of periodic, real-time tasks. Performance Evaluation, North Holland, 2:237-250, 1982.
• 27: P. E. Lim, Jr. Real-time in a concurrent, object-oriented programming environment. Master's thesis, University of Waterloo, Aug. 1996. ftp://plg.uwaterloo.ca/pu b/uSystem/kimThesis.ps.gz.
• 28: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 29: R. Maheshwari. An empirical evaluation of priority queue algorithms for real-time applications. Master's thesis, Florida State University, 1990.
• 30: A. K. Mok. Fundamental design problems of distributed systems for the hard real-time environment. PhD thesis, MIT, 1983.
• 31: P. J. Moylma, R. E. Betz, mad R. H. Middleton. The priority disinheritance problem. Technical Report EE9345, The University of Newcastle, 1993. ftp://- ee.newcastle.ed u.au/pu b/reports/Disi n heritance.ps.Z.
• 32: Ragunathan Rajkumar, Synchronization in Real-Time Systems: A Priority Inheritance Approach, Kluwer Academic Publishers, Norwell, MA, 1991
• 33: Douglas C. Schmidt , Fred Kuhns, An Overview of the Real-Time CORBA Specification, Computer, v.33 n.6, p.56-63, June 2000 [doi>10.1109/2.846319]
• 34: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 35: B. Sprmat, L. Sha, and J. Lehoczky. Aperiodic task scheduling for hard real-time systems. Journal of Real-Time Systems, 1(1):27-60, June 1989.
• 36: John A. StankovicThis work was done while the , Marco Spuri , Marco Di Natale , Giorgio C. Buttazzo, Implications of Classical Scheduling Results for Real-Time Systems, Computer, v.28 n.6, p.16-25, June 1995 [doi>10.1109/2.386982]
• 37: H. Takada and K. Sakamura. Experimental impDmentations of priority inheritance semaphore on itron-specification kernal. In Proceedings of 11th TRON Project International Symposium, pages 106-113. IEEE Computer Society Press, Dec. 1994.
• 38: P. van Emde Boas, R. Kaas, mad E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, 1977.
• 39: Priority Inheritance Spin Locks for Multiprocessor Real-Time Systems, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, p.70, June 12-14, 1996
• 40: J. W. J. Williams. Algorithm 232: Heapsort. Commun. ACM, 7:347-348, 1964.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Performance, Theory