Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!johnl
From: johnl@iecc.cambridge.ma.us (John R. Levine)
Newsgroups: comp.arch
Subject: Re: Atomic operations (Was Re: Living With Old Baggage)
Summary: CAS is more powerful than XMEM
Keywords: 68040 CAS2
Message-ID: <1991May14.033023.26083@iecc.cambridge.ma.us>
Date: 14 May 91 03:30:23 GMT
References: <1991May2.201917.15062@dg-rtp.dg.com> <1991May6.113149.14531@decvax.dec.com> <1991May13.140634.17669@dg-rtp.dg.com>
Organization: I.E.C.C.
Lines: 31

In article <1991May13.140634.17669@dg-rtp.dg.com> hamilton@siberia.rtp.dg.com (Eric Hamilton) writes:
>Atomic operations, such as compare-and-swap, that update memory with a value
>which is a function of the old value are generally useful.  They allow you
>to do things that cannot be done with operations such as xmem or test-and-
>set, which update memory with a value that cannot be a function of the
>previous value.
>
>Compare-and-swap cannot be fabricated out of xmem or test-and-set without
>disabling interrupts or severely constraining its use.  This is
>unsatisfactory for user code and many places inside the operating system.

This is entirely true.  Everyone who has any interest in locking primitives
should immediately get a copy of the January 1991 ACM TOPLAS and read the
article by Maurice Herlihy entitled "Wait-free synchronization."  He shows
that for a realistic model problem (getting N processors to agree on the
value of a shared variable) CAS can synchronize arbitrarily many processes or
processors without blocking, while test-and-set or xmem can only do two.

Most other locking primitives are less powerful than CAS.  The only ones that
are as powerful are at least as complex, e.g. atomic queue operations with
peeking or atomic move from one shared memory location to another.

Many people seem to believe that one can't do useful synchronization without
disabled interrupts, spin locks, or some other scheme that makes one
processor hang around and wait for another one to get out of its way.  They
are wrong.

-- 
John R. Levine, IECC, POB 349, Cambridge MA 02238, +1 617 492 3869
johnl@iecc.cambridge.ma.us, {ima|spdcc|world}!iecc!johnl
Cheap oil is an oxymoron.