Lock-free synchronization for dynamic embedded real-time systems

ABSTRACT

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger "adversary" than most traditional arrival models. We derive the upper bound on lock-free retries under the UAM with utility accrual scheduling the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities' accrued timeliness utility is greater under lock-free than lock-based, and the consequent upper bound on the increase in accrued utility that is possible with lock-free. We confirm our analytical results with a POSIX RTOS implementation.

REFERENCES

• 1: J. H. Anderson , R. Jain , K. Jeffay, Efficient Object Sharing in Quantum-Based Real-Time Systems, Proceedings of the IEEE Real-Time Systems Symposium, p.346, December 02-04, 1998
• 2: J. H. Anderson , R. Jain , S. Ramamurthy, Wait-free object-sharing schemes for real-time uniprocessors and multiprocessors, Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS '97), p.111, December 03-05, 1997
• 3: 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]
• 4: J. Chen and A. Burns. Asynchronous data sharing in multiprocessor real-time systems using process consensus. In 10th Euromicro Workshop on Real-Time System, 1998.
• 5: Hyeonjoong Cho , Binoy Ravindran , E. Douglas Jensen, A Space-Optimal Wait-Free Real-Time Synchronization Protocol, Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS'05), p.79-88, July 06-08, 2005 [doi>10.1109/ECRTS.2005.5]
• 6: Raymond Clark , E. Douglas Jensen , Arkady Kanevsky , John A. Maurer , Paul Wallace , Thomas Wheeler , Yun Zhang , Douglas Wells , Tom Lawrence , Pat Hurley, An Adaptive, Distributed Airborne Tracking System ("process the Right Tracks at the Right Time"), Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.353-362, April 12-16, 1999
• 7: R. K. Clark, E. D. Jensen, and N. F. Rouquette. Software organization to facilitate dynamic processor scheduling. In IEEE WPDRTS, April 2004.
• 8: J.-F. Hermant , G. Le Lann, A Protocol and Correctness Proofs for Real-Time High-Performance Broadcast Networks, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.360, May 26-29, 1998
• 9: Hai Huang , Padmanabhan Pillai , Kang G. Shin, Improving Wait-Free Algorithms for Interprocess Communication in Embedded Real-Time Systems, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.303-316, June 10-15, 2002
• 10: E. D. Jensen, C. D. Locke, and H. Tokuda. A time-driven scheduling model for real-time systems. In IEEE RTSS, pages 112--122, December 1985.
• 11: H. Kopetz and J. Reisinger. The non-blocking write protocol nbw: A solution to a real-time synchronisation problem. In IEEE RTSS, pages 131--137, 1993.
• 12: Peng Li , Binoy Ravindran , Syed Suhaib , Shahrooz Feizabadi, A Formally Verified Application-Level Framework for Real-Time Scheduling on POSIX Real-Time Operating Systems, IEEE Transactions on Software Engineering, v.30 n.9, p.613-629, September 2004 [doi>10.1109/TSE.2004.45]
• 13: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 14: Maged M. Michael , Michael L. Scott, Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors, Journal of Parallel and Distributed Computing, v.51 n.1, p.1-26, May 25, 1998 [doi>10.1006/jpdc.1998.1446 ]
• 15: Binoy Ravindran , E. Douglas Jensen , Peng Li, On Recent Advances in Time/Utility Function Real-Time Scheduling and Resource Management, Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'05), p.55-60, May 18-20, 2005 [doi>10.1109/ISORC.2005.39]
• 16: 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 ]
• 17: R. K. Treiber. System programming: Copying with parallelism. Technical report, IBM Almaden Research Center, April 1986. RJ 5118.
• 18: John D. Valois, Lock-free linked lists using compare-and-swap, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.214-222, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224988]
• 19: H. Wu, B. Ravindran, et. al. Utility accrual scheduling under arbitrary time/utility functions and multiunit resource constraints. In IEEE RTCSA, August 2004.
• 20: H. Cho. Utility Accrual Scheduling with Non-Blocking Synchronization on Uniprocessors and Multiprocessors. In PhD Dissertation Proposal, ECE Dept., Virginia Tech, 2005, http://www.ee.vt.edu/~realtime/cho-proposal05.pdf.