Bershad, Brian N. 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." Operating systems (Computers);Performance. 2000-09-01
    https://kilthub.cmu.edu/articles/journal_contribution/Practical_considerations_for_lock-free_concurrent_objects/6608510
10.1184/R1/6608510.v1