Response time analysis of software transactional memory-based distributed real-time systems

ABSTRACT

We consider distributed real-time systems where concurrency control is managed using software transactional memory (or STM). For such a method we propose an algorithm to compute an upper bound on the response time. We compare the result of the proposed algorithm to a simulation of the system being studied in order to determine its efficacy. The results of our study indicate that it is possible to provide timeliness assurances for systems programmed using STM.

REFERENCES

• 1: James H. Anderson , Srikanth Ramamurthy, A framework for implementing objects and scheduling tasks in lock-free real-time systems, Proceedings of the 17th IEEE Real-Time Systems Symposium, p.94, December 04-06, 1996
• 2: J. H. Anderson , S. Ramamurthy , K. Jeffay, Real-time computing with lock-free shared objects, Proceedings of the 16th IEEE Real-Time Systems Symposium, p.28, December 05-07, 1995
• 3: J. Anderson, S. Ramamurthy, M. Moir, and K. Jeffay. Lock-free transactions for real-time systems. In Real-Time Databases: Issues and Applications. Amsterdam: Kluwer Academic Publishers., 1997.
• 4: J. Bobba, R. Rajwar, and M. Hill. Transactional memory biblography. http://www.cs.wisc.edu/trans-memory/biblio/swtm.html.
• 5: Robert L. Bocchino , Vikram S. Adve , Bradford L. Chamberlain, Software transactional memory for large scale clusters, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345242]
• 6: Sherif F. Fahmy , Binoy Ravindran , E. Douglas Jensen, On Scalable Synchronization for Distributed Embedded Real-Time Systems, Proceedings of the 6th IFIP WG 10.2 international workshop on Software Technologies for Embedded and Ubiquitous Systems, October 01-03, 2008, Anacarpi, Capri Island, Italy [doi>10.1007/978-3-540-87785-1_35]
• 7: M. González Harbour , J. C. Palencia, Response Time Analysis for Tasks Scheduled under EDF within Fixed Priorities, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.200, December 03-05, 2003
• 8: M. Herlihy and Y. Sun. Distributed transactional memory for metric-space networks. Distributed Computing, 20(3): 195--208, 2007.
• 9: Philip Holman , James H. Anderson, Supporting lock-free synchronization in Pfair-scheduled real-time systems, Journal of Parallel and Distributed Computing, v.66 n.1, p.47-67, January 2006 [doi>10.1016/j.jpdc.2005.06.011]
• 10: Mark H. Klein , Thomas Ralya , Bill Pollak , Ray Obenza , Michael González Harbour, A practitioner's handbook for real-time analysis, Kluwer Academic Publishers, Norwell, MA, 1993
• 11: Edward A. Lee, The Problem with Threads, Computer, v.39 n.5, p.33-42, May 2006 [doi>10.1109/MC.2006.180]
• 12: Kaloian Manassiev , Madalin Mihailescu , Cristiana Amza, Exploiting distributed version concurrency in a transactional memory cluster, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1123002]
• 13: Jeremy Manson , Jason Baker , Antonio Cunei , Suresh Jagannathan , Marek Prochazka , Bin Xin , Jan Vitek, Preemptible Atomic Regions for Real-Time Java, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.62-71, December 05-08, 2005 [doi>10.1109/RTSS.2005.34]
• 14: P. Pagano, P. Batra, and G. Lipari. A framework for modeling operating system mechanisms in the simulation of network protocols for real-time distributed systems. IPDPS, 0: 160, 2007.
• 15: J. Palencia and M. G. Harbour. Offset-based response time analysis of distributed systems scheduled under edf. ECRTS, 00: 3, 2003.
• 16: J. C. Palencia , M. González Harbour, Schedulability Analysis for Tasks with Static and Dynamic Offsets, Proceedings of the IEEE Real-Time Systems Symposium, p.26, December 02-04, 1998
• 17: R. Pellizzoni and G. Lipari. Improved schedulability analysis of real-time transactions with earliest deadline scheduling. RTAS, pages 66--75, 2005.
• 18: M. Spuri. Analysis of deadline scheduled real-time systems. Technical report, In Rapport de Recherche RR-2772, INRIA, 1996.
• 19: H. Sutter. The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb's Journal, 30(3), 2005.
• 20: Ken Tindell , John Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessing and Microprogramming, v.40 n.2-3, p.117-134, April 1994 [doi>10.1016/0165-6074(94)90080-9]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Keywords:
real-time, response time, software transactional memory