Lock-Free Synchronization for Dynamic Embedded Real-Time Systems
Authors:
- Hyeonjoong ChoHCHyeonjoong Cho
- E.D. JensenEJE.D. Jensen
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (15301591) , 1-6
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 implementationKeywords
This publication has 12 references indexed in Scilit:
- On Recent Advances in Time/Utility Function Real-Time Scheduling and Resource Management2005
- A formally verified application-level framework for real-time scheduling on POSIX real-time operating systemsIEEE Transactions on Software Engineering, 2004
- Software organization to facilitate dynamic processor scheduling2004
- The non-blocking write protocol NBW: A solution to a real-time synchronization problem2002
- Efficient object sharing in quantum-based real-time systems2002
- Wait-free object-sharing schemes for real-time uniprocessors and multiprocessors2002
- Real-time computing with lock-free shared objectsACM Transactions on Computer Systems, 1997
- Lock-free linked lists using compare-and-swap1995
- A methodology for implementing highly concurrent data objectsACM Transactions on Programming Languages and Systems, 1993
- Priority inheritance protocols: an approach to real-time synchronizationIEEE Transactions on Computers, 1990