Real-time synchronization on distributed architecture with Ada-2005

ABSTRACT

Ada is found in most Avionics processing. It is often the hidden software that makes life safe in systems that fly most passenger/private aircraft. In an effort to promote the use of Ada-2005 in more embedded systems, we will present a Distributed Stack Resource Policy (DSRP) suitable for synchronizing tasks executing on distributed systems, meaning the protocol relies only on message-passing between processors. Accordingly, we will present an empirical evaluation that tests the performance of the DSRP with the Distributed Priority Ceiling Protocol (DPCP) created by Rajkumar. To the best of our knowledge, no empirical distributed-based evaluation of the DPCP has ever been conducted prior to this. We will also discuss the efficacy of Ada and examine the resulting design issues and trade-offs, and the ability of the DSRP to manage multiple shared resources efficiently on distributed processors.

REFERENCES

• 1: James H. Anderson , Srikanth Ramamurthy , Kevin Jeffay, Real-time computing with lock-free shared objects, ACM Transactions on Computer Systems (TOCS), v.15 n.2, p.134-165, May 1997 [doi>10.1145/253145.253159]
• 2: Baker T. A stack-based scheduling of real-time processes. In Real Time Systems Symposium, pages 191--200, 1990.
• 3: Aaron Block , Hennadiy Leontyev , Bjorn B. Brandenburg , James H. Anderson, A Flexible Real-Time Locking Protocol for Multiprocessors, Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.47-56, August 21-24, 2007 [doi>10.1109/RTCSA.2007.8]
• 4: Björn B. Brandenburg , John M. Calandrino , Aaron Block , Hennadiy Leontyev , James H. Anderson, Real-Time Synchronization on Multiprocessors: To Block or Not to Block, to Suspend or Spin?, Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, p.342-353, April 22-24, 2008 [doi>10.1109/RTAS.2008.27]
• 5: A. J. Wellings , A. Burns, Beyond Ada 2005: allocating tasks to processors in SMP systems, ACM SIGAda Ada Letters, v.XXVII n.2, August 2007
• 6: A. Burns , A. J. Wellings, Programming Execution-Time Servers in Ada 2005, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.47-56, December 05-08, 2006 [doi>10.1109/RTSS.2006.39]
• 7: A. Zerzelidis , A. Burns , A. J. Wellings, Correcting the EDF protocol in Ada 2005, ACM SIGAda Ada Letters, v.XXVII n.2, August 2007
• 8: John M. Calandrino , Dan Baumberger , Tong Li , Scott Hahn , James H. Anderson, Soft Real-Time Scheduling on Performance Asymmetric Multicore Platforms, Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium, p.101-112, April 03-06, 2007 [doi>10.1109/RTAS.2007.35]
• 9: Cheng A. M. K., Real-Time Systems Scheduling, Analysis, and Verification. 2nd. ed.: Wiley & Sons 2002, 2005.
• 10: Cheng A. M. K. and Ras J. The Implementation of the Multiprocessor Priority Ceiling Protocol in Ada-2005 Using a Shared Memory Programming Model. RTAS, WIP, 4/2007.
• 11: Albert M. K. Cheng , James Ras, The implementation of the Priority Ceiling Protocol in Ada-2005, ACM SIGAda Ada Letters, v.XXVII n.1, p.24-39, April 2007 [doi>10.1145/1274610.1274611]
• 12: Chen C. M. and Tripathi S. Multiprocessor priority ceiling based protocols. ACM Computer Science Technical Report; Vol. CS-TR-3252. Technical Report: CS-TR-3252, 1994.
• 13: Chen M. I. and Lin K. J. Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems. Technical report UIUCDCS-R-89-1511, Dept. of Computer Science, University of Illinois at Urbana-Champaign, 4/89.
• 14: Cottet F., Deacroix J., Kaiser C., Mammeri Z. Scheduling in Real-time Systems. John Wiley & Sons Ltd, 2002.
• 15: Paolo Gai , Marco Di Natale , Giuseppe Lipari , Alberto Ferrari , Claudio Gabellini , Paolo Marceca, A comparison of MPCP and MSRP when sharing resources in the Janus multiple-processor on a chip platform, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.189, May 27-30, 2003
• 16: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: Lee E. The problem with Threads. Berkeley report, Jan/2006.
• 18: 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]
• 19: Locke D., Vogel D. R., and Mesher T. J. Building a Predictable Avionics Platform in Ada: A Case Study. Proc. of IEEE Real-Time Systems Symposium, 1991.
• 20: D. Locke , L. Sha , R. Rajikumar , J. Lehoczky , G. Burns, Priority inversion and its control: An experimental investigation, ACM SIGAda Ada Letters, v.VIII n.7, p.39-42, June 1-3, 1988
• 21: J. M. López , J. L. Díaz , D. F. García, Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems, Real-Time Systems, v.28 n.1, p.39-68, October 2004 [doi>10.1023/B:TIME.0000033378.56741.14]
• 22: Rajkumar R. Synchronization in multiple processor systems. In Synchronization in Real-Time Systems: A Priority Inheritance Approach. Kluwer Publishing, 1991.
• 23: 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]
• 24: Hongfeng Shen , Arnaud Charlet , Theodore P. Baker, A ``Bare-Machine'' Implementation of Ada Multi-tasking Beneath the Linux Kernel, Proceedings of the 1999 Ada-Europe International Conference on Reliable Software Technologies, p.287-297, June 07-11, 1999
• 25: K. W. Tindell , A. Burns , A. J. Wellings, An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems, v.6 n.2, p.133-151, March 1994 [doi>10.1007/BF01088593]
• 26: http://www.quadros.com/
• 27: http://www.windriver.com/
• 28: http://www.cs.fsu.edu/~baker/florist.html

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance, Reliability

Keywords:
ada, dpcp, dsrp, edf, pcp, rms, srp