Category: CMUTR
Institution: Department of Computer Science, Carnegie
        Mellon University
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 multi-
        processors.
        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 synch-
        ronization.
        We then describe s simple modification to an existing synch-
        ronization protocol which allows us to avoid much of the 
        overhead normally associated with contention. 
Number: CMU-CS-91-183
Bibtype: TechReport
Month: Sep
Author: Brian N. Bershad		
Title: Practical Considerations for Lock-Free Concurrent Objects
Year: 1991
Address: Pittsburgh, PA
Super: @CMUTR