Practical Considerations for Non-Blocking Concurrent Objects

An important class of concurrent objects are those that are non-blocking, that is, whose operations are not contained within mutually exclusive critical sections. A non-blocking object can be accessed by many threads at a time, yet update protocols based on atomic Compare-And-Swap operations can be used to guarantee the object's consistency. In this paper we take a practical look at the Compare-And-Swap operation in the context of contemporary bus-based shared memory multiprocessors, although our results generalize to distributed shared memory multiprocessors. We first describe an operating system-based solution that permits the construction of a non-blocking Compare-And-Swap function on architectures that only support more primitive atomic primitives such as Test-And-Set or Atomic Exchange. We then evaluate several locking strategies that can be used to synthesize a Compare-And-Swap operation, and show that the common techniques for reducing synchronization overhead in the presence of..