Re: Synchronization primitives (was:Re: Where is atomicqueue?)
Re: Synchronization primitives (was:Re: Where is atomicqueue?)
- Subject: Re: Synchronization primitives (was:Re: Where is atomicqueue?)
- From: Steve Sisak <email@hidden>
- Date: Tue, 29 Apr 2008 12:22:52 -0400
At 11:11 AM -0400 4/29/08, Army Research Lab wrote:
I want to be able to use this from user space. Are there any functions that
are supported from user space and capable of all that the OSAtomic*
functions are?
I'm not sure how far back the OS* versions are declared by that name,
but there's some version of CompareAndSwap32 in every Mac OS version
since OpenTransport (Unix STREAMS) was introduced -- Mac OS 7.5, I
think.
CompareAndSwap() from <DriverServices.h> is available back to Mac OS 8.0.
OTCompareAndSwap32() from <OpenTransport.h> is available back to the
beginning of time.
As I mentioned previously, given CompareAndSwap32(), and
CompareAndSwapPtr (correct size for a pointer) you can implement
everything else.
-------
BTW, if you ever need really fast atomic queues from user space, look
at OTLifo in <OpenTransport.h>.
These just implement a singly lined list with atomic enqueue/dequeue.
To implement a fast FIFO, you use two OTLifo's (call them head and
tail) and a lock.
You enqueue (OTLIFOEnqueue()) to head and (OTLIFODequeue()) from tail.
If tail becomes empty:
if (head) is not empty:
Take the lock
retry the deque from case it's been filled while waiting
If you get nil:
Steal the contents of head (OTLIFOStealList())
If not nil:
Reverse the list you get (OTReverseList())
Set fHead of tail to the reversed list
Deque the first element as the result
Release the lock
This has the desirable attributes of:
1) enqueuing to head never blocks
2) dequeing from tail only blocks when tail is empty.
(This is part of the reason why OpenTransport was so fast -- it
didn't block much and used very clever memory allocation to avoid
copying data much)
The above can all be implemented in C given an implementation of
CompareAndSwapPtr(). (I could probably send you some code if you need
it)
Implementing this is a good interview question. :-)
Cheers,
-Steve
--
_________________________________________________________________________
Steve Sisak, CTO email@hidden
IOXperts, Inc. +1 617 876-2572
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Darwin-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden