Disentangling multi-object operations (extended abstract)
Yehuda Afek, Michael Merrit, Gadi Taubenfeld, Dan Touitou · 1997
We consider the problem of implementing atomic operations on multiple shared memory objects, in systems which directly support only single-object atomic operations.Our motivation is to design algorithms that exhibit both low contention between concurrent operations and a high level of concurrency, by disentangling long chains of conflicting operations.That is, operations that access widely disjoint parts of a data structure, or are widely separated in time, should not interfere with each other.The algorithm reported here extends and is based on the work of Attiya and Dagan [A D96], where a nonblocking solution is presented for two-object atomic operations.For any number, k, we present a wait-free solution for atomically accessing up to k objects.Notions of local contention and local step complexity are defined, and it is shown that the solution has low local contention and local step complexity.Relations between multi-objects and the familiar resource allocation problem are explored-the algorithm presented also provides a solution to the resource allocation problem. Int roduct ionConsider a data structure stored in shared memory and accessed concurrently by n processes.The shared data structure is abstracted w an array of memory locations.To perform its operation, a process needs to get exclusive access to the set of locations necessary to carry out qComputer