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

[Yann Guidon <whygee@f-cpu.org>]

hello,

Christophe wrote:
> > We could easily do this kind of operation in hardware, btw.
> Oh fine.

just a question : "how" ?

> > [...]
> > > A CAS2 is in fact two atomic CAS :
> > >
> > > int CAS (int *pointer1,int *pointer2,int requested_value1,int
> > > requested_value2,int new_value1,int new_value2) {
> > >     if ((requested_value1 == *pointer1) && (requested_value2 == *pointer2)) {
> > >         *pointer1 = new_value1; *pointer2 = new_value2; return true;
> > >     }
> > >     return false;
> > > }

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.

> > > Examples :
> > >
> > > How to push a element in a stack :
> > >
> > > 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'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" ?

> 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 ?

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.

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

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 ?

have a nice day,

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