Real-Time Computing with Lock-Free Shared Objects

ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept, ACM Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissions@acm.org. 2 \Delta J. Anderson, S. Ramamurthy, and K. Jeffay 1. INTRODUCTION Most work on implementing shared objects in preemptive hard real-time uniprocessor systems has focused on using critical sections to ensure object consistency. One of the main problems that arises when using critical sections is that of priority inversion. A priority inversion exists when a given task must wait on a task of lower priority to release a critical section. In a hard real-time system, unless priority inversions are carefully controlled, it may be difficult or impossible to ensure that task deadlines are always met. Most conventional mechanisms for cont..