Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!sun-barr!newstop!sun!amdcad!dgcad!dg-rtp!siberia!hamilton From: hamilton@siberia.rtp.dg.com (Eric Hamilton) Newsgroups: comp.arch Subject: Re: Atomic operations (Was Re: Living With Old Baggage) Keywords: 68040 CAS2 Message-ID: <1991May13.140634.17669@dg-rtp.dg.com> Date: 13 May 91 14:06:34 GMT References: <336@scorpio.gtephx.UUCP> <12741@pt.cs.cmu.edu> <14628@encore.Encore.COM> <1991Apr22.175410.9840@decvax.dec.com> <1991May2.201917.15062@dg-rtp.dg.com> <1991May6.113149.14531@decvax.dec.com> Sender: hamilton@siberia (Eric Hamilton) Organization: Data General Corporation, Research Triangle Park, NC Lines: 83 In article <1991May6.113149.14531@decvax.dec.com>, kenton@abyss.zk3.dec.com (Jeff Kenton OSG/UEG) writes: |> In article <1991May2.201917.15062@dg-rtp.dg.com>, |> hamilton@siberia.rtp.dg.com (Eric Hamilton) writes: |> |> In article <1991Apr22.175410.9840@decvax.dec.com>, |> kenton@abyss.zk3.dec.com (Jeff Kenton OSG/UEG) writes: |> |> |> |> |> |> The 88K has xmem, not test and set, which is guaranteed to be an atomic |> |> |> operation (the bus is locked between the read and write cycles). This |> |> |> can be used to create locks or compare and swap without disabling |> itnerrupts. |> |> |> |> |> Now I'm curious. How does one fabricate compare-and-swap out of xmem |> |> without disabling interrupts? Xmem has essentially the same restriction as |> |> test-and-set, which is that the stored value must be a constant |> independent of |> |> the loaded value. |> |> |> |> Once you've created a lock (with xmem) you can do almost anything within the |> locked region of code without disabling interrupts. |> True, but implementing compare-and-swap is not one of those things. Two reasons, one of which is has nothing to do with interrupt disable. 1) Compare-and-swap will be atomic only with respect to other compare-and-swap operations (or other operations which honor the lock). It will not be atomic with respect to stores, nor to any non-CPU accesses, such as I/O references, ref/mod bit updates in page table entries, and the like. Note that xmem doesn't suffer from this defect. Of course, we can't remove this restriction even if we had interrupt disable. So, for present purposes, let's restrict compare-and-swap so that it is only atomic with respect to other compare-and-swap operations. Of course, this is a big restriction, and by itself may be enough to dispose of the misbegotten notion that test-and-set, exchange-memory, or the like are sufficient in an architecture. 2) Compare-and-swap is non-blocking, in the sense that it is guaranteed to complete one way or another, store or no store, succeed or fail, in a bounded time (to be useful the bound must be fairly low - a few tens of cycles is nice). The "you can do anything within the locked region" approach doesn't have this non-blocking property. Suppose one process holds the lock because it is in the middle of a compare-and-swap, and a second process tries to obtain the lock. The second process will block until the first process releases the lock. But there is no assurance that the first process will ever release the lock. It may take a time slice interrupt, be descheduled, swapped out, and languish there indefinitely. It may be killed. It may take a signal, and in its signal handler try to do another compare-and-swap, need another lock, and deadlock. Meanwhile, the second process will wait forever. The only way to guarantee the non-blocking behavior of compare-and-swap is to guarantee that whenever a process begins a compare-and-swap, it will expeditiously complete it and release the lock. And the only way to make this guarantee is to.... DISABLE INTERRUPTS WHILE THE LOCK IS HELD Note that xmem doesn't have this defect either. Xmem is non-blocking and atomic with respect to interrupts - there's no such thing as an interrupt in the middle of an xmem. The moral of this is roughly as follows: 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. Therefore, cost-benefit tradeoffs permitting, one should make an effort to include compare-and-swap or something similar in the architecture. Omitting it is a defect. -- ---------------------------------------------------------------------- Eric Hamilton +1 919 248 6172 Data General Corporation hamilton@dg-rtp.rtp.dg.com 62 Alexander Drive ...!mcnc!rti!xyzzy!hamilton Research Triangle Park, NC 27709, USA