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: Army Research Lab <email@hidden>
- Date: Tue, 29 Apr 2008 12:46:06 -0400
- Thread-topic: Synchronization primitives (was:Re: Where is atomicqueue?)
On 4/29/08 12:22 PM, "Steve Sisak" <email@hidden> wrote:
> 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. :-)
I'm not worried about implementing it, I've done it WAAAAY too many times
already (I'm an embedded systems programmer, when you don't have a C
standard library because its too big, and the OS is whatever you cook up...)
I'm just a) ignorant; I don't know much about mac programming and b) lazy;
if someone else already wrote it, I'm going to use their version of it.
BTW large chunks of OpenTransport.h are marked
AVAILABLE_MAC_OS_X_VERSION_10_0_AND_LATER_BUT_DEPRECATED_IN_MAC_OS_X_VERSION
_10_4, including various bits that have to do with OTLifo. If your code
still uses it, you may need to update it to something else.
Thanks,
Cem Karan
_______________________________________________
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