Wait-Free and Lock-Free Objects

Much of my past research involves lock-free and wait-free algorithms for accessing shared objects on uniprocessors and shared-memory multiprocessors. Lock-free algorithms constitute a fine-grained notion of optimistic concurrency control: a process performs an operation on a lock-free object without actually locking the object; in effect, the process optimistically assumes that no interference will occur as a result of a concurrent object access by another process. If an operation is interfered with, then it must be retried. Repeated retries may be needed before an operation is successful. Wait-freedom is an extreme form of lock-freedom that precludes all waiting dependencies among processes, including potentially unbounded operation retries. In particular, each operation of a process must be implemented without using blocking synchronization constructs, and must terminate within a bounded number of steps of that process. Lock-free and wait-free objects are mainly of interest because they avoid problems such as priority inversion and deadlock, and because they tolerate delays due to page faults, quantum expirations, etc., without kernel intervention.


Last modified 12 August 1996