A modular approach to real-time synchronization

ABSTRACT

In this paper, we discuss real-time barrier synchronization as an example of timing constraints on synchronization. Real-time barrier synchronization is constrained by two timing values: earliest release time and release time skew. Earliest release time is the delay from the time when the last object participating in barrier synchronization issues a barrier operation, till when one of the participating objects resumes its method. Release time skew is the delay between the first and the last resumption times of objects. The implementation of real-time barrier synchronization consists of a negotiation phase and a scheduling phase. In the negotiation phase, all the participating objects communicate with one another and agree on the time when they are going to resume their method execution. Local scheduling at individual nodes must then ensure that the agreement is implemented. Thus, earliest release time and release time skew are defined by the procedures of the negotiation and the scheduling phase, respectively. We describe an architecture which enables the implementation of real-time barrier synchronization in a distributed system with unreliable channels.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Gul Agha, Concurrent object-oriented programming, Communications of the ACM, v.33 n.9, p.125-141, Sept. 1990 [doi>10.1145/83880.84528]
• 3: [3] K. Arvind. A New Probabilistic Algorithm for Clock Synchronization. Proc. IEEE Real-Time Systems Symp., pp. 330-339, December 1989.
• 4: S. Chatterjee , J. Strosnider, Distributed Pipeline Scheduling: End-to-End Analysis of Heterogeneous, Multi-Resource Real-Time Systems, Proceedings of the 15th International Conference on Distributed Computing Systems, p.204, May 30-June 02, 1995
• 5: Svend Frølund, Inheritance of Synchronization Constraints in Concurrent Object-Oriented Programming Languages, Proceedings of the European Conference on Object-Oriented Programming, p.185-196, June 29-July 03, 1992
• 6: Svend Frølund , Gul Agha, A Language Framework for Multi-Object Coordination, Proceedings of the 7th European Conference on Object-Oriented Programming, p.346-360, July 26-30, 1993
• 7: [7] R. Gerber et al. Guaranteeing End-to-End Timing Constraints by Calibrating Intermediate Processes. Proc. IEEE Real-Time Systems Symp., December 1994.
• 8: Yutaka Ishikawa , Hideyuki Tokuda, Object-oriented real-time language design: constructs for timing constraints, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.289-298, September 1990, Ottawa, Canada
• 9: Yutaka Ishikawa , Hideyuki Tokuda , Clifford W. Mercer, An Object-Oriented Real-Time Programming Language, Computer, v.25 n.10, p.66-73, October 1992 [doi>10.1109/2.161281]
• 10: [10] K. Kim and H. Kopetz. A Real-Time Object Model RTO.k and an Experimental Investigation of Its Potentials. Proc. IEEE Computer Society's Computer Software and Applications Conf. (COMPSAC), November 1994.
• 11: K. H. Kim , L. Bacellar , Yuseok Kim , D. K. Choi , S. Howell , M. Jenkins, Distinguishing features and potential roles of the RTO.k object model, Proceedings of the 1st Workshop on Object-Oriented Real-Time Dependable Systems, p.36, October 24-25, 1994
• 12: [12] H. Kopetz and K. Kim. Temporal Uncertainties in Interactions among Real-Time Objects. Proc. IEEE 9th Symp. on Reliable Distributed Systems, pp. 165- 174, October 1990.
• 13: [13] H. Kopetz and K. Kim. Consistency Constraints in Distributed Real-Time Systems, in Distributed Computer Control Systems 1988, M.G. Rodd and T.L. d'Epinay ed., Pergamon Press, pp. 29-34, 1989.
• 14: [14] E. L. Lawler and C. U. Martel. Scheduling Periodically Occurring Tasks on Multiple Processors. Information Processing Letters, Vol. 12, No. 1, February 1981.
• 15: [15] J. Lehoczky et al. Enhancing A periodic Responsiveness in a Hard Real-Time Environment. Proc. IEEE Real-Time Systems Symp., December 1987.
• 16: 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]
• 17: [17] J. W. S. Liu et al. Imprecise Computations. Proc. IEEE, Vol. 82, No. 1, pp. 83-94, January 1994.
• 18: Pattie Maes, Concepts and experiments in computational reflection, Conference proceedings on Object-oriented programming systems, languages and applications, p.147-155, October 04-08, 1987, Orlando, Florida, United States
• 19: [19] A. K. Mok and M. L. Dertouzos. Multiprocessor Scheduling in a Hard Real-Time Environment. Proc. 7th Texas Conf. on Computer Systems, November 1978.
• 20: [20] A. K. Mok. The Design of Real-Time Programming Systems Based on Process Models. Proc. IEEE Real-Time System Symp., December 1984.
• 21: Krithi Ramamritham , Gerhard Fohler , Juan Manuel Adan, Issues in the static allocation and scheduling of complex periodic tasks, Proceedings of the tenth IEEE workshop on Real-time operating systems and software, p.11-16, March 1993, New York, New York, United States
• 22: K. Ramamritham , J. A. Stankovic , P. F. Shiah, Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.184-194, April 1990 [doi>10.1109/71.80146]
• 23: Shangping Ren , Gul A. Agha, RTsynchronizer: language support for real-time specifications in distributed systems, Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, p.50-59, November 1995, La Jolla, California, United States
• 24: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]

INDEX TERMS

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

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

          Nouns: Concurrent C
      D.3.4 Processors
          Subjects: Run-time environments
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

General Terms:
Design, Management, Theory