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: Tuesday, March 19, 2002 2:26 AM
Subject: Re: spinlocks (was Re: [f-cpu] another DATE report)


> Without conflict, best case:
>
> time     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> CPU A    R--------------W
> CPU B                    R--------------W

Sorry, it should be :
CPU A    CR--------------W
CPU B                               CR--------------W


> With conflict (first write attempt on CPU B fails), worst case:
>

CPU A    R--------------W
CPU B                   R--------------R--------------W

That's true.

> The final (succeeding) operations, counted from the initial read, will
> never overlap. The same is true for the spinlock variant, except that
> the `worst case' situation is much better (less delay in case of
> failure):
>
> Spinlock, worst case:
>
> time     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> CPU A    LR--------------WU
> CPU B                      LR--------------WU
>

I don't agree on one point : if you use a CAS for spinlock so we have something
like it :


CPU A    L-----R-------------------WU
CPU B          L-----L-----L-----L-----L-----R------------------>WU

So it is an illusion to think spinlock is shorter in worst case because you
forget that L (locking) is in fact a CAS and so have the same default as CAS2
in worst case since CPU B read should not happen until CPU A unlocks !

But anyway preemption-safe locking and non-blocking (free-lock) primitives are
those who give best results, so I think we nearly agree indeed.

> The letters mean: R(ead), W(rite), L(ock), U(nlock)
>
> [...]
> > 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.
>
> Things like push/pop operations on a stack happen all the time, not once
> in a millenium :)

Do you think to use push and pop a billion times per second !? I don't think
so. Allocation and releasing ressources shared between processors and tasks
should not be done a billion times per second. We should not abuse the
synchronisation if not necessary.

> > But okay, if long_computation is undeterministic, I wouldn't use CAS nor
CAS2 !
>
> I wouldn't use a spinlock either, then. Never block if you have no idea
> how long the block will persist.

So we are definately blocked :)

> > 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.
>
> Semaphores are slightly different, and usually not present in hardware.
> When a task requests a semaphore that is in use, it is suspended (there
> will be a task switch). As soon as the semaphore is freed, the first
> process waiting for it is woken up, or maybe all of them, and probably
> another task switch is performed.

Yes I know, it is why I asked for Yann not to use the semaphore term which
leads to a misunderstanding since F-CPU has no way to determine hardwardly
which tasks to stop or wake up.

> A simple semaphore can be written using CAS:
>
> down(struct sem *sem) {
> while (!CAS(&sem->count, 1, 0)) {
> wait_on_semaphore(sem); // does a task switch
> /* we come back here when the task is woken up again */
> }
> }

Not a semaphore for me but a mutex indeed :). Oh by the way, what happens if a
task switch occurs just before wait_on_semaphore and another task releases this
mutex ? :)

>
> up(struct sem *sem) {
> sem->count = 1;
> }

!? How do you wake up tasks waiting for mutex releasing !?

> A real semaphore (with an initial count > 1) is a little harder...
> We'd need another instruction in order to implement that efficiently,
> like `atomic test-for-zero-and-decrement-otherwise'.

something like :
int test_and_dec (int *counter) {
    do {
        old = *counter;
        if (!old)
            return old;
    } while (! CAS (counter,old,old-1));
    return old;
}

I suppose ? well, it is not enough too... for the same reason as in mutex.



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