Practical considerations for lock-free concurrent objects

Abstract: "An important class of concurrent objects are those that are lock-free, that is, whose operations are not contained within mutually exclusive critical sections. A lock-free object can be accessed by many threads at a time, yet clever update protocols based on atomic Compare-And-Swap operations guarantee the object's consistency. In this paper we take a practical look at the Compare-And-Swap operation in the context of contemporary shared memory multiprocessors. We first describe an operating system-based solution that permits the construction of a non- blocking Compare-And-Swap function on processor architectures that only support lock-oriented atomic primitives.We then evaluate several locking strategies that can be used to synthesize a Compare-And-Swap operation. We show that the common techniques for reducing the overhead of lock-oriented synchronization in the presence of contention are inappropriate when used as the basis for lock-free synchronization. We then describe a simple modification to an existing synchronization protocol which allows us to avoid much of the overhead normally associated with contention.