Re: spinlocks (was Re: [f-cpu] another DATE report)

["Christophe" <christophe.avoinne@laposte.net>]

----- Original Message -----
From: Michael Riepe <michael@stud.uni-hannover.de>
To: <f-cpu@seul.org>
Sent: Monday, March 18, 2002 9:53 PM
Subject: Re: spinlocks (was Re: [f-cpu] another DATE report)


> With a single "p", please. On the other hand, you may also call me Michael.

Sorry, Michael :-)

> With the CAS2 solution, the delay isn't known either -- you never know
> how many times the CPU has to process the retry loop.
>

For the case there is no IRQ or task switch which can disturb :

while (1) { new++; do { old = *pointer; } while (! CAS (pointer,old,new)); }

--- A : read old ---
--- B : read old ---
--- A : CAS --- HIT !
--- B : CAS --- MISS !
--- A : new++
--- B : read old ---
--- B : CAS --- HIT !
--- A : read old ---
--- A : CAS --- MISS !
...

- For 2 concurrent processors, the first processor to write always passed, so
the second do a retry and have a hit the second time because it would have time
to write before the former processor had time enough to pass a second time. So
both processors finally share their hits near 1/2.

- For n concurrent processors, the first processor to write always passed, so
others will do a retry. the unluckier would do n-1 retries at max
in fact. So both processors finally share their hits near 1/n.

Even with disturbance like IRQ or task switch, the time for each processor to
have a hit could be shorter than a delay between two task switchs or IRQ and be
enough to allow all processors finally to have a hit.

As a benefit, if one processor is interrupted by an IRQ, another processor will
hit anyway.

> At the cost of having to retry the update operation if the CAS2 fails.

for n concurrent processors, n-1 failures is the raisonnable maximum we get in
reality for the very worst case.

> [...]
> > In fact if we
> > don't need a version stamping to prevent us from the ABA problem, a CAS
would
> > be enough and more efficient than a spinlock.
> [...]
>
> Depends. Consider the following examples:

> with_cas() {
> do {
> oldx = x;
> newx = long_computation(oldx);
> }
> while (!CAS(&x, oldx, newx)); // may repeat indefinite times
> }

Why ? if cycles for long_computation are the same for both processors, both
processors would hit each after other. By the way if you don't call this
with_cas in an eternal loop so your statement "repeat indefinite times" becomes
false, because there is a time when a processor hits, it wouldn't be back until
a very long moment (at least I hope so!) so it should not be any longer a
possible contention for other processors waiting for their hits.

But okay, if long_computation is undeterministic, I wouldn't use CAS nor CAS2 !

Anyway, using CAS shouldn't be a thing which occurs at 99% of running code, so
such a situation should be avoided.

> Note that this does not mean that I don't like CAS. Au contraire -- we
> definitely need an atomic read-modify-write operation, and this one
> looks pretty good to me, although it doesn't solve all problems.

Of course, it doesn't solve all problems. But I prefer them to semaphores when
possible.

> CAS2, on the other hand, is too heavy for a hardware implementation.
> We can't handle 6 input operands, no matter how hard we try.

I know, I know.



*************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/