🚀 go-pugleaf

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