Browse Prior Art Database

Enhanced Implementation of Compare-and-Swap

IP.com Disclosure Number: IPCOM000106578D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 179K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

The original implementation of Compare-and-Swap has an anomaly that can be eliminated by means of an enhancement described here. The enhancement is an alternate implementation of load with linking and conditional stores that have been implemented recently on some commercial multiprocessors.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 31% of the total text.

Enhanced Implementation of Compare-and-Swap

      The original implementation of Compare-and-Swap has an anomaly
that can be eliminated by means of an enhancement described here.
The enhancement is an alternate implementation of load with linking
and conditional stores that have been implemented recently on some
commercial multiprocessors.

      The proposal by [1] is subject to thrashing among
multiprocessors.  The present proposal reduces the thrashing somewhat
by delaying exclusive access to a variable until a store actually has
to be done.  It also protects against incorrect behavior in a
uniprocessor multiprogramming environment by assuring that the
variable reserved is correctly associated with the conditional store.

Compare-and-Swap is a Read/Modify/Write instruction that is used for
synchronizing processors and processes [1].  However, its use is
subject to a subtle failure mode.  The failure mode occurs in
single-operand implementations of the instruction, but can be
remedied in practice by using a double-operand implementation.  Even
the double-operand version is subject to rare failures, although the
probability of such a failure is essentially zero.

      An improved version of Compare-and-Swap as described in [2],
essentially corrected the problem.  This improvement eliminates a
potential for blocking indefinitely long.  It also is an enhancement
to the software technique described by [2]  for dealing with the
failure mode of Compare-and-Swap with a double-operand version of the
instruction.

      The enhancement provides additional protection for the
Compare-and-Swap against the anomalous behavior.  Commercial machines
have evolved independently along a different tack, and tend to use
the idea of the reservation as put forth in [1], coupled with a
conditional store.  Such implementations are available on the MIPS
R-4000, DEC Alpha, and Sparc 9 microprocessors, and they are somewhat
different from the implementation described here.  They provide for a
single active reservation per processor.  This implementation
provides for many active reservations per processor, and thereby can
eliminate some potential thrashing among processes on a single
processor.

Compare-and-Swap works as follows when a processor is required to
update a shared variable.

1.  The processor obtains a local copy of the shared variable.

2.  The processor locally computes a new value of the variable.

3.  The processor issues a Compare-and-Swap instruction with the
    following information:

    a.  The address in memory of the shared variable.
    b.  The original value of the variable that was used locally.
    c.  The updated value to be stored in memory.

4.  If the old value agrees with the current value, then the
    assumption is that no other processor has touched the variable
    since it was obtained by the present processor.  In this case,
    the new value is stored in memory.

        ...