Lock-Free and Wait-Free Synchronization in Multiprogrammed Systems

Principal Investigator: James Anderson
Funding Agency: National Science Foundation
Agency Number: CCR-9732916

Abstract
Research will be conducted on lock-free and wait-free shared-object algorithms for multiprogrammed concurrent systems. In multiprogrammed systems, several processes may execute on the same processor. Processes on the same processor are scheduled for execution either by priority or by allocating a scheduling quantum. One of the main reasons for adopting a multiprogrammed execution model is that it enables problems to be solved without static constraints on the number of processes that may be employed.

In multiprogrammed systems, process delays are quite common, due to preemptions. Most lock-based synchronization algorithms perform poorly in the face of such delays, because a delayed process holding a lock, can impede the progress of other processes waiting for that lock. Furthermore, lock-based algorithms are susceptible to problems such as deadlock and priority inversion. Lock-free and wait-free algorithms are implemented without locking mechanisms. and therefore do not suffer from these problems.

Previous research on lock-free and wait-free algorithms has almost exclusively focused on asynchronous models of concurrent program execution in which processes may interleave arbitrarily. Such models can be a hindrance when designing algorithms for multiprogrammed systems, because they force process interleavings to be considered that in fact cannot arise. What is needed is a new framework for lock-free and wait-free synchronization directed toward multiprogrammed systems. The main objective of this project is to develop such a framework.

This framework will be established through a combination of research on new algorithmic techniques for efficiently implementing lock-free and wait-free shared objects in multiprogrammed systems, and new lower-bound and impossibility results that help reveal characteristics that optimal or near-optimal algorithms must have. The framework to be developed will be evaluated experimentally through research involving simulation models, synthetic workloads, and real-world applications.