Implementing wait-free objects on priority-based systems
James Horton Anderson, Srikanth Ramamurthy, Rohit Jain · 1997
Wait-free objects are often implemented through the use of a "helping scheme", whereby one process "helps" one or more other processes to complete an operation. This paper presents several new helping schemes that can be generally applied to efficiently implement a variety of different objects on priority-based uniprocessor and multiprocessor systems. Examples of such systems include lock-free multiprocessor kernels and real-time systems. Our helping schemes reduce overhead by exploiting the way in which processes are scheduled in priority-based systems. We illustrate the use of these schemes by presenting wait-free implementations of linked lists and a multi-word compare-and-swap primitive. 1 Introduction We consider the implementation of wait-free shared objects on multiprogrammed systems in which processes are scheduled for execution based on priority. We assume that processes are scheduled on a per-processor basis and do not migrate between processors during object accesses. Our ...