Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!crackers!m2c!risky.ecs.umass.edu!dime!dime.cs.umass.edu!moss From: moss@cs.umass.edu (Eliot Moss) Newsgroups: comp.arch Subject: Re: Atomic operations (Was Re: Living With Old Baggage) Message-ID: Date: 14 May 91 16:27:31 GMT References: <1991May2.201917.15062@dg-rtp.dg.com> <1991May6.113149.14531@decvax.dec.com> <1991May13.140634.17669@dg-rtp.dg.com> <1991May14.033023.26083@iecc.cambridge.ma.us> Sender: news@dime.cs.umass.edu Reply-To: moss@cs.umass.edu Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) Lines: 22 In-reply-to: johnl@iecc.cambridge.ma.us's message of 14 May 91 03:30:23 GMT I posted something liek this recently, but would like to repeat it. I have been working with Maurice Herlihy for a little while now on problems such as lock-free garbage collection (that work will be presented at the next SPAA and will appear in an IEEE journal next year). I have a firm belief (but no proof yet) that CAS2, which allows atomic compare and swap of TWO, ARBITRARY memory locations is strictly more powerful than CAS, in the sense that it allows implementation of EFFICIENT lock-free (and wait-free) algorithms that CAS is not strong enought to implement efficiently. In particular, to update many elements of a shared structure atomically with CAS appears to require building a copy of the ENTIRE structure and then using CAS to swing a pointer to the new version. CAS2 supports a reasonable, atomic, update-in-place of any number of elements of a shared data structure. I hope to have firm results and proofs before too long. Meanwhile, it is something hardware designers may wish to start thinking about .... Eliot Moss -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu