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

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

> and don't tell me "We could easily do this kind of operation in hardware,
btw." !
> there are 2 pointers and 4 values with CAS2 ! Unless you use several
instructions,
> the instruction itself would require at least 36 bits for the operands.
>

Yes i know for CAS2 is not very easy... using pairs of Rn and Rn+1 maybe ? Or
using pairable CAS, dunno.

Anyway the single CAS wouldn't be a problem since you need only three operands.

> > > I'm not sure whether the latency will be better than with a simple
> > > spinlock around the update operation:
> >
> > well, there is a problem with the spinlock version : what happens if a task
> > switch occurs between the locking and the unlocking ? especially if other
tasks
> > will try to acquire the same spinlock, they all shall be blocked until the
> > owner task may release the spinlock, which - not speaking about the invert
> > priority problem of tasks - is in fact a real degradation. Such a thing
cannot
> > happen with CAS2 because the first to be serviced is the first to write,
not
> > the first to read - the other tasks would just need a retry - which takes
> > basically less time to execute than waiting for owner task to unlock.
>
> I do not doubt that what you say is true, here.
> the problem is still : "how do you think it can be implemented in the
existing framework" ?

I'm sure you would find a solution if you wanted to storm your brain ;-).

> > Indeed, to avoid this problem when task switching, the usual workaround is
to
> > disable interrupts before acquiring and after releasing the spinlock. But
such
> > a thing is acceptable if time is very short between locking and unlocking,
that
> > is, not using a blocking function in-between.
>
> huh ? if CAS2 requires the task to turn off IRQs, then i don't see why it is
superior
> to CAS. Are you sure there is no such routine that does what you describe
with a
> series of simple CAS and without touching the IRQs ?

!?!? what is this absurdity !? noooooooooo !!! I never told that !!!! Im not
speaking about CAS2 !!!! but the SPINLOCK as a replacement for CAS2 as PROPOSED
by M.Rieppe !!!!!!!

Please reread above : "well, there is a problem with the spinlock version".  So
the problem comes from spinlock not from CAS2 since i stated : "Such a thing
cannot happen with CAS2".

by the way, spinlock is a BLOCKING synchronisation and CAS/CAS2 is a
non-blocking synchronisation. indeed, I explain how to make a spinlock with a
CAS, that is turning a non-blocking synchronisation in a preemption-safe lock
(if we disable interrupts too in the loop).

in M.Rieppe version, no task switching must occur (because of the problem
above) so unless using a more complicated preemption-safe mechanism, we disable
all interrupts - even the IRQs which are not concerned by this synchronisation
:

void atomic_push (struct stack *stack,struct stack_node *element) {
    disable_interrupts ();
    while (!CAS(&stack->spinlock, 0, 1)); // unknown delay
    element->link = stack->top;
    stack->top = element;
    stack->version++;
    stack->spinlock = 0;
    enable_interrupts ();
}

In my CAS version, a task switch can occur without any problem and all IRQs can
run freely too.

void atomic_push (struct stack *stack,struct stack_node *element) {
    struct stack_node *requested_top;
    int requested_version;
    do
        {
            requested_top = stack->top;
            requested_version = stack->version;
            element->link = requested_top;
        }
    while (CAS2
(&stack->top,&stack->version,requested_top,requested_version,element,requested_
version+1));
}

I use the name "atomic_push" but I should have chosen "safe_push" or
"consistent_push" indeed.

>
> later, Christophe wrote:
> >
> > > Indeed, to avoid this problem when task switching, the usual workaround
is to
> > > disable interrupts before acquiring and after releasing the spinlock. But
such
> > > a thing is acceptable if time is very short between locking and
unlocking, that
> > > is, not using a blocking function in-between.
> >
> > ... is to disable interrupts JUST before acquiring and to ENABLE interrupts
> > JUST after releasing the spinlock.

Stop it ! where the heck can you see I disable interrupts in my CAS2 primitive
!? i'm speaking about the spinlock version of M.Rieppe, not my CAS2 version. If
you use a spinlock you need to disable interrupts to avoid degradation as i was
speaking above. In the CAS2 version, we don't need to do so. 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.

Spinlocks are used when you need to update consistently larger data than
non-blocking primitives like CAS or CAS2 can do.

> Now i think : you enter a critical section (playing with the IRQ enable bit
is
> nothing else, i guess). This means that you request ownership of the data.
> A simple "semaphore" (sorry, i know you don't lile this word) would do the
trick, no ?
>   * acquire semaphore
>   * swap stack top (or any operation, whatever the complexity)
>   * release semaphore

berrrrrk ! when contention it degrades too much you F-CPU performance, because
you need to use a kernel trap to make your task waiting or awaken.

>
> You say that CAS2 is the best of all but i don't understand this statement if
> you need to call the kernel to enter in a critical section. what did i miss ?

What can I say more ? my examples should be enough to understand what you
stated here is absurd... sure you miss a lot.

:-)







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