We present a new wait-free implementation of a Fetch&Inc object shared by n processes from read-write registers and load-linked/store-conditional (LL/SC) objects. The step complexity of each FI operation is O(log n), which is optimal. Our implementation uses O(max{m, n}) objects, each of which stores O(log m) bits, where m is the number of FI operations that are performed. For large m, the number of objects can be reduced to O(n~2). Similar implementations of other objects, such as Fetch&Add and Swap, are also obtained. Our implementation uses a new object, called an Aggregator. It supports an operation which, if successful, puts a value into its in-buffer that can depend on the value that is currently there, an operation that copies the value in its in-buffer to its out-buffer, provided its out-buffer is empty, and an operation that empties its out-buffer. We show how to implement an Aggregator from a small constant number of LL/SC objects so that all three operations have constant step complexity.
展开▼
