CHAOSarc: kernel support for multiweight objects, invocations, and atomicity in real-time multiprocessor applications

ABSTRACT

CHAOSarc is an object-based multiprocessor operating system kernel that provides primitives with which programmers may easily construct objects of differing types and object invocations of differing semantics, targeting multiprocessor systems, and real-time applications. The CHAOSarc can guarantee desired performance and functionality levels of selected computations in real-time applications. Such guarantees can be made despite possible uncertainty in execution environments by allowing programs to adapt in performance and functionality to varying operating conditions. This paper reviews the primitives offered by CHAOSarc and demonstrates how the required elements of the CHAOSarc real-time kernel are constructed with those primitives.

REFERENCES

• 1: ALMES, C-. T., BLACK, A. P., LAZOWSKA, E D., AND NOE, J D. The Eden system: A techmcal review. IEEE Trans. Softw. Eng. SE-11, 1 (Jan. 1985), 43-58.
• 2: Brian N. Bershad , Edward D. Lazowska , Henry M. Levy , David B. Wagner, An open enviornment for building parallel programming systems, ACM SIGPLAN Notices, v.23 n.9, p.1-9, Sept. 1988
• 3: T. Bihari , D. Pugh , T. Walliser , E. Ribble, Timing analysis for robot motion-planning algorithm, IEEE Real-Time Systems Newsletter, v.6 n.2, p.104-107, Spring 1990
• 4: Thomas E. Bihari , Karsten Schwan, Dynamic adaptation of real-time software, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.143-174, May 1991 [doi>10.1145/103720.103723]
• 5: Ben A. Blake , Karsten Schwan, Experimental Evaluation of a Real-Time Scheduler for a Multiprocessor System, IEEE Transactions on Software Engineering, v.17 n.1, p.34-44, January 1991 [doi>10.1109/32.67577 ]
• 6: Gene D. Carlow, Architecture of the space shuttle primary avionics software system, Communications of the ACM, v.27 n.9, p.926-936, Sept. 1984 [doi>10.1145/358234.358258]
• 7: J. Chase , F. Amador , E. Lazowska , H. Levy , R. Littlefield, The Amber system: parallel programming on a network of multiprocessors, ACM SIGOPS Operating Systems Review, v.23 n.5, p.147-158, Dec. 3–6, 1989
• 8: CROWTHER, W., GOODHUE, J., GURWICH, R., RETTBERG, R., AND THOMAS, R. The Butterfly parallel processor. IEEE Comput. Arch. Tech. Committee Newsl. (Dec. 1985), 18-45.
• 9: Partha Dasgupta , Richard J. LeBlanc, Jr. , Mustaque Ahamad , Umakishore Ramachandran, The Clouds Distributed Operating System, Computer, v.24 n.11, p.34-44, November 1991 [doi>10.1109/2.116849 ]
• 10: M. L. Dertouzos , A. K. Mok, Multiprocessor Online Scheduling of Hard-Real-Time Tasks, IEEE Transactions on Software Engineering, v.15 n.12, p.1497-1506, December 1989 [doi>10.1109/32.58762 ]
• 11: Marc Daniel Donner, Control of walking: local control and real time systems, 1984
• 12: Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
• 13: Ahmed Mohamed Gheith , K. Schwan, Support for multiweight objects, invocations and atomicity in real-time systems, 1990
• 14: Ahmed Gheith , Karsten Schwan, CHAOSarc: kernel support for multiweight objects, invocations, and atomicity in real-time multiprocessor applications, ACM Transactions on Computer Systems (TOCS), v.11 n.1, p.33-72, Feb. 1993 [doi>10.1145/151250.151252]
• 15: GHOSH, K., FUJIMOTO, R. M., AND SCHWAN, K. Speculative execution in time-constrained systems. Tech. Rep. GIT-CC-92/22, College of Computing, Georgia Institute of Technology, Atlanta, May 1992.
• 16: GLIGOR, Y. D., AND LUCKENBAUGH, G. L. An assessment of the real time requirements for programming environments and languages. In IEEE Real-Time Systems Symposium (Dec. 1983), 3-19.
• 17: Prabha Shankar Gopinath , Karsten S. Schwan, Programming and execution of object-based, parallel, hard, real-time applications, 1988
• 18: 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]
• 19: JENSEN, E. D., LOCKE, C. D., A~D TOKUDA, $. A time-driven scheduling model for real-time operating systems. In IEEE Real-Trine System Symposium (1985), 112-122.
• 20: Zvi M. Kedem , Abraham Silberschatz, Locking Protocols: From Exclusive to Shared Locks, Journal of the ACM (JACM), v.30 n.4, p.787-804, Oct. 1983 [doi>10.1145/2157.322406]
• 21: Carol Kilpatrick , Karsten Schwan, ChaosMON—application-specific monitoring and display of performance information for parallel and distributed systems, ACM SIGPLAN Notices, v.26 n.12, p.57-67, Dec. 1991
• 22: Anthony Klug, Locking Expressions for Increased Database Concurrency, Journal of the ACM (JACM), v.30 n.1, p.36-54, Jan. 1983 [doi>10.1145/322358.322362]
• 23: KNIGHTEN, B. Posix standard for threads, multiprocessor study group. Personal communications with ongoing study group, 1990.
• 24: Walter H. Kohler, A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.149-183, June 1981 [doi>10.1145/356842.356845]
• 25: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 26: LEBLANC, T. J., AND FRIEDBERG, S. h. Hierarchical process composition in distributed operating systems. In Proceedtngs of the 5th International Conference on Distributed Computing Systems (Denver, Colo., May 1985), IEEE, ACM, 26-34.
• 27: LEE, I., AND GEHLOT, V. Language constructs for distributed real-time programming. In Proceedings of the 6th Real-Time Systems Symposium (San Diego, Calif., Dec. 1985), IEEE, 57-66.
• 28: LIN, K.-J., NATARAJAN, S., AND LIU, J.W.-S. Imprecise results: Utilizing partial computations in real-time systems. In IEEE Real-Time System Symposium (1987), 210-217.
• 29: Carey Douglass Locke, Best-effort decision-making for real-time scheduling, 1986
• 30: H. Massalin , C. Pu, Threads and input/output in the synthesis kernal, ACM SIGOPS Operating Systems Review, v.23 n.5, p.191-201, Dec. 3–6, 1989
• 31: MCGHEE, R. B., ORIN, D. E., PUGH, D. R., AND PATTERSON, M.R. A hierarchically-structured system for computer control of a hexapod walking machine. In Proceedings of 5th IFTOMM Symposium on Robots and Manipulator Systems (Udine, Italy, June 1984), IFTOMM.
• 32: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 33: MEYEr, J.F. On evaluating the performability of degradable computing systems. IEEE Trans. Comput. C-29, 8 (Aug. 1980), 720-731.
• 34: MOK, A. K.-L. Sartor--a design enwronment for real-time systems. In IEEE Real-Time Systems Symposium (Dec. 1985), 174 181.
• 35: MOK, A. K.-L. Fundamental problems of distributed systems for the hard real-time environment. Ph.D. Thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, May 1983.
• 36: J. E.B. Moss, Nested transactions: an approach to reliable distributed computing, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 37: U.S. DEPARTMENT OF DEFENSE. Reference Munual for the Ada Language. U.S. Department of Defense, 1984.
• 38: OR~N, D. E. Supervisory control of a multilegged robot. Int. J. Robotic Res. 1, i (Spring 1982).
• 39: PAUL, R. P., AND ZHANG, H. Design of a robot force motion server. In {EEE International Conference on Robotics andAutomatzon (San Francisco, Cahf., April 1986), IEEE, 1878-1883.
• 40: L. Peterson , N. Hutchinson , S. O'Malley , M. Abbott, RPC in the x-Kernel: evaluating new design techniques, Proceedings of the twelfth ACM symposium on Operating systems principles, p.91-101, November 1989
• 41: RAMAMRITHAM, K., AND STANKOVIC, J. h. Dynamic task scheduling in hard real-time distributed systems. IEEE Softw. 1, 3 (July 1984), 65 75.
• 42: RANDELL, B. System structure for software fault tolerance. IEEE Trans. Softw. Eng. 1, 2 (1975).
• 43: Karsten Schwan , Tom Bihari , Bruce W. Weide , Gregor Taulbee, High-performance operating system primitives for robotics and real-time control systems, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.189-231, Aug. 1987 [doi>10.1145/24068.24070]
• 44: SCHWAN, K., FOgBES, H., GHEITH, A., MUKHEP~JEE, B., AND SAMIOTAKIS, Y. A c thread hbrary for multlprocessors. Tech. Rep., College of Computing, Georgia Institute of Technology, Atlanta, GIT-ICS-91/02, Jan. 1991.
• 45: SCHwAN, K., GHEITH, A., AND ZHOU, H. From chaos-min to chaos-arc: A family of real-tmle multlprocessor kernels. In Proceedings of the IEEE Real-Tzme Systems Symposium (Orlando, Fla., Dec. 1990), 82-92.
• 46: K. Schawn , P. Gopinath , W. Bo, CHAOS- kernel support for objects in the real-time domain, IEEE Transactions on Computers, v.36 n.8, p.904-916, Aug. 1987
• 47: Karsten Schwan , Rajiv Ramnath , Sridhar Vasudevan , David Ogle, A Language and System for the Construction and Tuning of Parallel Programs, IEEE Transactions on Software Engineering, v.14 n.4, p.455-471, April 1988 [doi>10.1109/32.4669 ]
• 48: 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 ]
• 49: Karsten Schwan , Hongyi Zhou , Ahmed Gheith, Real-time threads, ACM SIGOPS Operating Systems Review, v.25 n.4, p.35-46, Oct. 1991 [doi>10.1145/122098.122102]
• 50: Peter M. Schwarz , Alfred Z. Spector, Synchronizing shared abstract types, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.223-250, Aug. 1984 [doi>10.1145/989.1188]
• 51: M. L. Scott , T. J. LeBlanc , B. D. Marsh, Multi-model parallel programming in psyche, ACM SIGPLAN Notices, v.25 n.3, p.70-78, Mar. 1990
• 52: Lui Sha , John Lehoczky , E. Douglas Jensen, Modular Concurrency Control and Failure Recovery, IEEE Transactions on Computers, v.37 n.2, p.146-159, February 1988 [doi>10.1109/12.2144 ]
• 53: Alfred Z. Spector , Dean Daniels , Daniel Duchamp , Jeffrey L. Eppinger , Randy Pausch, Distributed transactions for reliable systems, Proceedings of the tenth ACM symposium on Operating systems principles, p.127-146, December 1985, Orcas Island, Washington, United States
• 54: STANXOWC, J A. The design of the spring kernel. In IEEE Real-Time System Svmposzum (Dec. 1987), 146 157.
• 55: TEVAN~AN, A., AND RASIng), R. F. Mach A basis for future unix development. Tech. Rep, Carnegie-Mellon University, June 1987
• 56: H. Tokuda , C. W. Mercer, ARTS: a distributed real-time kernel, ACM SIGOPS Operating Systems Review, v.23 n.3, p.29-53, July 1989 [doi>10.1145/71021.71023]
• 57: William Weihl , Barbara Liskov, Implementation of resilient, atomic data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.244-269, April 1985 [doi>10.1145/3318.3319]
• 58: Niklaus Wirth, Toward a discipline of real-time programming, Communications of the ACM, v.20 n.8, p.577-583, Aug. 1977 [doi>10.1145/359763.359798]
• 59: W. Zhao , K. Ramamritham , J. A. Stankovic, Scheduling tasks with resource requirements in hard real-time systems, IEEE Transactions on Software Engineering, v.13 n.5, p.564-577, May 1987 [doi>10.1109/TSE.1987.233201]
• 60: Hongyi Zhou, Task scheduling and synchronization for multiprocessor real-time systems, Georgia Institute of Technology, Atlanta, GA, 1992
• 61: ZHOU, H., SCHWaN, K., AND Ak~qLmZ, I. Pertbrmance effects of mformation sharing in a distributed multiprocessor real-time scheduler. In Proceedzngs of 1992 IEEE Real-Ttrne Systems Symposium (Phoenix, Ariz., Dec. 1992).
• 62: Hongyi Zhou , Karsten Schwan , Ahmed Gheith, Dynamic synchronization of real-time threads for multiprocessor systems, Papers from the symposium on Experiences with distributed and multiprocessor systems, p.93-107, January 1992, Newport Beach, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Real time

General Terms:
Design, Experimentation, Measurement, Performance