Sofware Mutex/spinlock

TomUdale

Greetings,

Has anyone come up with some kind locking mechanism that does not use lockset/lockclr at the bottom of it? Those locks are very nice, but somewhat dear since there are only 8 of them. Perhaps someone cleverer than me has come up/knows of with an alternative algorithm that might offer similar functionality?

All the best,

Tom

Heater.

There are very few Propeller programs that actually use locks.

Data structures can be safely shared between a single "producer" process and a single "consumer" process with a simple boolean flag. Just have the producer set the flag when data is ready and have the consumer clear the flag when it has read the data. Have both producer and consumer loop checking the appropriate state of the flag prior to accessing the data.

A producer and consumer can also share a cyclic buffer (FIFO) with only manipulation of a "head" and "tail" pointer. Have a look at the FullDuplexSerial object for an example of how that is done.

Phil Pilgrim (PhiPi)

One hardware "master" lock can be used to control as many software slave locks as you want. So, in fact, eight hardware locks is an ample supply for the Propeller.

-Phil

TomUdale

Hi Phil,

Phil Pilgrim (PhiPi) wrote: »

One hardware "master" lock can be used to control as many software slave locks as you want. So, in fact, eight hardware locks is an ample supply for the Propeller.

-Phil

I thought about this but was fearing that you would wind up with contention issues for the master lock ala the global kernel locks that have plagued some OSes. I gather that has not been a problem in real systems.

Thanks and
best regards,

Tom

TomUdale

Dear Heater,

Heater. wrote: »

There are very few Propeller programs that actually use locks.

Data structures can be safely shared between a single "producer" process and a single "consumer" process with a simple boolean flag. Just have the producer set the flag when data is ready and have the consumer clear the flag when it has read the data. Have both producer and consumer loop checking the appropriate state of the flag prior to accessing the data.

A producer and consumer can also share a cyclic buffer (FIFO) with only manipulation of a "head" and "tail" pointer. Have a look at the FullDuplexSerial object for an example of how that is done.

I was actually looking for a multiple producer, single consumer system, but I gather that FullDuplexSerial can do that so I will take a look at it.

Knowing that most programs don't use locks is a good data point. I am new to the propeller and don't know many of the tricks yet. Locks are the natural answer for me, but I guess I should think outside the box in this area.

Best regards,

Tom

Heater.

Locks have the effect of serializing parts processes that otherwise run in parallel. Thus the achievable performance of your parallel processes is reduced from what it would be if they were totally independent. The performance hit rather depends on the proportion of code run when the lock is claimed compared to that run in parallel. See "Amdahl's Law". Often this performance hit is not a concern.

Now, if you have a "global lock" in your system then all the parallel processes in your system are serialized when they need exclusive access to some resource. This is a bigger overhead because interacting processes can be halted by other processes they don't interact with, except for the use of that global lock. Again this performance hit may or may not be an issue depending on your requirements.

Heater.

As far as I remember FullDuplexSerial cannot be used by more than one process at a time. Without wrapping it up with an interface that uses a lock.

ersmith

TomUdale wrote: »

Has anyone come up with some kind locking mechanism that does not use lockset/lockclr at the bottom of it? Those locks are very nice, but somewhat dear since there are only 8 of them. Perhaps someone cleverer than me has come up/knows of with an alternative algorithm that might offer similar functionality?

This isn't quite what you were asking for, since it does use lockset/lockclr of a single global lock at the bottom, but PropGCC allows an arbitrary number of software locks to be implemented. The library allocates a lock bit (the number is stored in the _C_LOCK variable) at startup time, and uses that to ensure memory access is atomic when setting/clearing a software lock. To use it do something like:

#include <sys/thread.h>
atomic_t mylock;
...
__lock(&mylock);
// do critical section stuff here
__unlock(&mylock);

The hardware lock is held only for a brief time inside the __lock() and __unlock() calls (to ensure that the read/modify/write of the "mylock" variable doesn't get interrupted by anything else).

TomUdale

Hi Eric,

Thanks for the tip. Now I don't have to consider rolling my own.

All the best,

Tom

TomUdale

Eric,

TomUdale wrote: »

Thanks for the tip. Now I don't have to consider rolling my own.

Heh, heh, of course that does not work for COG memory model. But it turns out that doing something like this:

#define my__trylock(ptr) __sync_bool_compare_and_swap(ptr, 0, 1)
#define my__lock(val) while (!my__trylock(val)) ;
#define my__unlock(val) *val = 0

at least compiles without bringing in the whole thread library without to terribly much thinking on my part.

All the best,

Tom

TomUdale

Hi All,

TomUdale wrote: »

#define my__trylock(ptr) __sync_bool_compare_and_swap(ptr, 0, 1)
#define my__lock(val) while (!my__trylock(val)) ;
#define my__unlock(val) *val = 0

Just for posterity, this does not work either. __sync_bool_compare_and_swap deadlocks immediately when called from COG code. If I replace it with my own version of __sync_bool_compare_and_swap, it all works fine. And naturally, it all works as advertised from LMM code.


Cheers,

Tom

ersmith

TomUdale wrote: »

Just for posterity, this does not work either. __sync_bool_compare_and_swap deadlocks immediately when called from COG code. If I replace it with my own version of __sync_bool_compare_and_swap, it all works fine. And naturally, it all works as advertised from LMM code.

Could you tell us what's wrong with __sync_bool_compare_and_swap in COG mode? What did you have to change in your version?

Thanks,
Eric

TomUdale

Hi Eric,

ersmith wrote: »

Could you tell us what's wrong with __sync_bool_compare_and_swap in COG mode? What did you have to change in your version?

Thanks,
Eric

It literally deadlocks the moment I call it in the COG code. I had this:

// somecog.cogc

#define cyiLockSLock(ptr) while (!__sync_bool_compare_and_swap(ptr, 0, 1)) ;
#define cyiUnlockSLock(ptr) *val = 0

int main(void* params)
{
    int lock=0;

    while(1)
    {
       cyiLockSLock(&lock);
        //toggle a pin
        OUTA&=(~CPX_HV3_MASK);
        OUTA|=CPX_HV3_MASK;
        cyiUnlockSLock(&lock);
    }
    return 0;
}

I could only see the pin toggle if I commented out the lock code. The cyiLockSLock functions worked fine in a LMM cog.

To fix it, I basically wrote my own __sync_bool_compare_and_swap function that was a straight copy of the code in propgcc which uses its own lockset/lockclr guard. So I think it is almost exactly what you are doing in the compiler.

 volatile int            slock_lock=-1;


#define AcquireLock()       while(lockset(slock_lock) == -1)
#define FreeLock()          lockclr(slock_lock)

int    p_cyi_sync_bool_compare_and_swap(volatile int* ptr,int oldval,int newval)
{
    int ret;

    AcquireLock();
    ret=( (*ptr == oldval) && ((*ptr = newval),1) );
    FreeLock();
    return ret;
}

// slock_lock is initialized elsewhere

I don't really understand why the original did not work. The only thing I could think of was that something was not linking quite right when __sync_bool_compare_and_swap was compiled (it actually compiled as a call to CMPX_something, I don't remember the exact name).

All the best,

Tom