Re: race on multi-processor solaris
From: Gavin Maltby (G_a_v_i_n.M_a_l_t_b_y_at_sun.com)
Date: 11/14/03
- Next message: Richard Gillman: "vsftpd on solaris - wont work with inetd"
- Previous message: SenderX: "Re: race on multi-processor solaris"
- In reply to: SenderX: "Re: race on multi-processor solaris"
- Next in thread: Greg Menke: "Re: race on multi-processor solaris"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Fri, 14 Nov 2003 11:24:20 +0000
SenderX wrote:
>>In an effort to keep an open mind I'll ask: what would be be your
>>lock-free suggestion for traversing a linked list?
>
>
> Use a lock-free garbage collector.
I thought so (but it was late and I had little imagination left).
Not suitable for the level I'm thinking of I think.
>
>
>
>>I'm searching a linked list from it's head looking for
>>the first match (if any) on a particular structure members.
>
>
> OK.
>
>
>
>>A number of other threads will be inserting/deleting from the
>>list
>
>
> Fine.
>
>
>
>>or making modifications to some of it's members (without
>>unlinking).
>
>
> Bzzt!
>
> The lock-free linked list protects the nodes themselvs, not the memory you
> attach to the node:
>
> typedef struct SLfNode_
> {
> /* ... */
>
> /* This is user state, we don't know anything about it.
> don't touch it at all */
> const void *pUserState;
>
> } SLfNode;
>
So what does protect the memory attached to the node? Not
a lock (obviously!). A reference count or serial number -
sounds like a lot of overhead to me.
>
>>Deleted members may be instantly reused in other
>>such linked lists, or they may be freed.
>
>
> Take a look at my 32-bit cpu garbage collector:
>
> http://intel.forums.liveworld.com/thread.jsp?forum=242&thread=6721
Will do.
> I have a 64-bit cpu collector, but I may try to patent it.
>
> This is a really simple experimental example, a real lock-free list would be
> spread over multi-buckets.
>
> But it does show how threads can traverse the list, while others are pushing
> and popping && freeing nodes with delete, all concurrently.
>
>
> However this is just a simple stack, if you want linked-list code that
> allows for pushes and pops anywhere in the list, you need the following
> x86-32 && 64-bit compatible( /w SMR and other GC's ) IBM algo:
>
> http://www.cs.tau.ac.il/~shanir/reading%20group/p73-michael.pdf
Interesting read (ok I bailed at the proof section). At first
glance I don't see why the Search algorithm (Insert/Delete are
easy and obvious) is immune to livelock. Due to list changes
occuring on other cpus there seems to be no guarantee that
the Search algorithm will ever complete since it may always
hit "list changed; try again from head" scenarios. Maybe this
is handled by hash chain ordering (which is not always
desirable). Maybe I read too quickly!
The assumption of sequentially consistent memory model is fine.
It would be nice if they indicated exactly which memory barriers
are needed where for more relaxed memory models (not trivial
to decide whether that's possible).
>
> If you have trouble coding this, I can show you my stable C++ implementation
> of the posted IBM algo.
>
> This is one of the best IBM FreeList compatible lock-free linked-list code
> currently out there.
I can manage - after some memory barrier discussions. From what I've
read this stuff will not outperform the existing implementation of
what I'm thinking of - and it will certainly add much more complexity
and likely subtle bugs. I was thinking of the Solaris virtual->physical
memory mapping hash. It it mostly a locked design now, with very low
contention. It has some lock-free aspects, however.
>
> Joe Seigh has another slick lock-free linked-list that uses his almighty
> atomic_ptr. Google for it, its worth it.
May do. Solaris has a casptr() which various things use to do this.
Mostly it used to avoid deadlock or in places where you simply cannot
block.
Gavin
Speaking for myself
- Next message: Richard Gillman: "vsftpd on solaris - wont work with inetd"
- Previous message: SenderX: "Re: race on multi-processor solaris"
- In reply to: SenderX: "Re: race on multi-processor solaris"
- Next in thread: Greg Menke: "Re: race on multi-processor solaris"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
