[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming.threads

Lock-Free Lists

Matt Taylor

8/1/2004 3:11:00 AM

Hello, I am looking for information on lock-free lists (primarily as a means
in deadlock avoidance). Is there a list anywhere of various algorithms and
their drawbacks? I am primarily looking to replace a number of spinlocks to
minimize the chance of deadlock in my application. I've looked at a couple
algorithms already, but one is not permissive enough and the other seemed to
require the ability to atomically CAS on 2 distinct, non-contiguous words in
memory. [Aside: are there even any machines that support this? Certainly x86
does not, and that's what I'm working with.]

I am also interested in learning about garbage collection with respect to
lock-free data structures in general. Namely, what are the implications?
(Loss of performance? Memory "leaks"?) I am also very interested in knowing
the limits of data structures that do not require garbage collection since
the overhead for garbage collection is typically very high, at least with
respect to the code I am working on. Essentially I am wondering if the
garbage collector would fit into my application and whether or not it is
appropriate for me to implement one.

Any help would be appreciated. TIA!

-Matt
8 Answers

Joe Seigh

8/1/2004 1:48:00 PM

0



Matt Taylor wrote:
>
> Hello, I am looking for information on lock-free lists (primarily as a means
> in deadlock avoidance). Is there a list anywhere of various algorithms and
> their drawbacks? I am primarily looking to replace a number of spinlocks to
> minimize the chance of deadlock in my application. I've looked at a couple
> algorithms already, but one is not permissive enough and the other seemed to
> require the ability to atomically CAS on 2 distinct, non-contiguous words in
> memory. [Aside: are there even any machines that support this? Certainly x86
> does not, and that's what I'm working with.]

You must have been looking at some of Detlefs' papers. DCAS is only on some
old Motorola MC68020 and MC68030 processors. There are algorithms that only
need a double wide CAS such as cmpxchg8b for IA-32 processors or load locked/
store conditional.

What kind of list operations? Get/put or random insert and delete? You can
google for stuff by Maged Michael for a start. There's also a lock-free
stack using version that is in the appendix of the IBM Z architecture manual
(which seems to change URL's periodically so I don't have a reference for it).

>
> I am also interested in learning about garbage collection with respect to
> lock-free data structures in general. Namely, what are the implications?
> (Loss of performance? Memory "leaks"?) I am also very interested in knowing
> the limits of data structures that do not require garbage collection since
> the overhead for garbage collection is typically very high, at least with
> respect to the code I am working on. Essentially I am wondering if the
> garbage collector would fit into my application and whether or not it is
> appropriate for me to implement one.
>

Start here http://www.rdrop.com/users/paulm... for papers by Paul McKenney.
I just noticed he put his PHD dissertation online. That has a number of references
to work in this area (including an early RCU implementation :) ). Generally you
use GC to extend the range of solutions to more than just pure lock-free. Also,
they may actually scale better than some of the pure lock-free under heavy
contention.

Joe Seigh

Mouse

8/1/2004 11:08:00 PM

0

> Hello, I am looking for information on lock-free lists (primarily as a
means
> in deadlock avoidance). Is there a list anywhere of various algorithms and
> their drawbacks? I am primarily looking to replace a number of spinlocks
to
> minimize the chance of deadlock in my application.

http://portal.acm.org/citation.cfm?id=564881&dl=ACM&c...

This has a nice linked list algo and a generic gc. It blows spin-lock
per-bucket away. This list is nice because it allow you to test many
different types of garbage collectors.




> I am also interested in learning about garbage collection with respect to
> lock-free data structures in general. Namely, what are the implications?

Using a lock-free gc allows you to turn normally "static" lock-free node
storage ( ibm freelist ) into dynamic storage. They also get rid of ABA in
some areas if you don't "automatically reuse nodes". There will be no memory
leaks ( that would be a bug ), and the only impact on performance is the
latency between handing the node off to the gc, and the gc actually freeing
it. If you reuse nodes immediately and only destroy nodes when they
absolutely need to be removed, the performance penalty of using a gc is
basically washed away. Mixing ABA counters with gc'ing can get tricky,
because a flow of rapidly reused nodes will be flowing through aba prone
cas's...




> I am also very interested in knowing
> the limits of data structures that do not require garbage collection since
> the overhead for garbage collection is typically very high, at least with
> respect to the code I am working on.

The limits of lock-free collections without a gc, is that their storage has
to be static, and "any" ABA counters have to remain for the ENTIRE nodes
lifetime. That's about it.




> Essentially I am wondering if the
> garbage collector would fit into my application and whether or not it is
> appropriate for me to implement one.

If you know that the overall node count in a list would "never" reach a
certain threshold, the you could use static storage for the nodes, and a gc
would not be needed. If you have no idea how many nodes the list could have
at any one time, a gc would be appropriate. Some of the gc's require you to
have special lists and counters per-thread. Some of them need a separate
thread to check for quiescent periods.

Here is one of my old lock-free proxy gc's:

http://groups.google.com/groups?selm=bbjHc.31426%24JR4.9393%40attbi_s54&...
( pseudo code )

http://groups.google.com/groups?selm=nhGHc.50272%24a24.19496%40attbi_s03&a...
( asm code at bottom )

You should read the entire thread. My old algo needs a modification to the
Release function. The gc's aba needs to be inc'd on every cas success.




P.S.

You mentioned DCAS. There is a paper that describes an algorithm that can
actually emulate DCAS, by using MCAS...

http://www.cl.cam.ac.uk/Research/SRG/netos/papers/2004-cpwl-subm...
( a MCAS algo description, new paper )

http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/src/lockfree-...
( portable MCAS C implementation )

This algo actually works for some algorithms, but use it only when you
absolutely need to... I am concerned with the overhead of mcas. There are a
lot of cas operations...

You could try a DCAS based linked list with it. Hell, its MCAS... Why not
put a proxy reference count in the cas as well... Flexible?

Joe Seigh

8/2/2004 12:36:00 AM

0



SenderX wrote:
>
> > Hello, I am looking for information on lock-free lists (primarily as a
> means
> > in deadlock avoidance). Is there a list anywhere of various algorithms and
> > their drawbacks? I am primarily looking to replace a number of spinlocks
> to
> > minimize the chance of deadlock in my application.
>
> http://portal.acm.org/citation.cfm?id=564881&dl=ACM&c...
>

Here if you can't get it from ACM's site.

http://www.research.ibm.com/people/m/michae...

High Performance Dynamic Lock-Free Hash Tables and List-Based Sets

Joe Seigh

Mouse

8/2/2004 2:31:00 AM

0

> There will be no memory
> leaks ( that would be a bug ), and the only impact on performance is the
> latency between handing the node off to the gc, and the gc actually
freeing
> it.

I forgot to mention that extra atomic operations and/or memory barriers that
implement the gc, will have a impact on performance...

RCU is about the only one that I can think of that could need a couple of
simple loads and stores, or to inform the it of read-side critical regions.

para

8/2/2004 8:15:00 AM

0

Joe Seigh <jseigh_01@xemaps.com> wrote in message news:<410CF6D2.E8CBFB0B@xemaps.com>...
> Matt Taylor wrote:
> >
> > Hello, I am looking for information on lock-free lists (primarily as a means
> > in deadlock avoidance). Is there a list anywhere of various algorithms and
> > their drawbacks? I am primarily looking to replace a number of spinlocks to
> > minimize the chance of deadlock in my application. I've looked at a couple
> > algorithms already, but one is not permissive enough and the other seemed to
> > require the ability to atomically CAS on 2 distinct, non-contiguous words in
> > memory. [Aside: are there even any machines that support this? Certainly x86
> > does not, and that's what I'm working with.]
>
> You must have been looking at some of Detlefs' papers. DCAS is only on some
> old Motorola MC68020 and MC68030 processors. There are algorithms that only
> need a double wide CAS such as cmpxchg8b for IA-32 processors or load locked/
> store conditional.

"Managing Long Linked Lists Using Lock Free Techniques" by Mohammad
Farook and Peter Graham. The pseudocode for the TryDelete algorithm in
their paper uses DCAS on non-contiguous memory. I believe they did
everything on SGI machines, and they did make mention of load
locked/store conditional.

> What kind of list operations? Get/put or random insert and delete? You can
> google for stuff by Maged Michael for a start. There's also a lock-free
> stack using version that is in the appendix of the IBM Z architecture manual
> (which seems to change URL's periodically so I don't have a reference for it).

Generally random insert/delete. The exact piece of code I am looking
at now manages a per-thread data structure in my app. It hashes all
the structures so they can easily be retrieved by other threads. The
hash table is more accurately described as an array of lists since it
functions really as more of a cache. I don't care where in the list an
insertion takes place, but I have to be able to traverse and to delete
at any location.

I've got a few other pieces of code that manage linked lists that I
would like to replace, but for the moment the former is my primary
concern.

> > I am also interested in learning about garbage collection with respect to
> > lock-free data structures in general. Namely, what are the implications?
> > (Loss of performance? Memory "leaks"?) I am also very interested in knowing
> > the limits of data structures that do not require garbage collection since
> > the overhead for garbage collection is typically very high, at least with
> > respect to the code I am working on. Essentially I am wondering if the
> > garbage collector would fit into my application and whether or not it is
> > appropriate for me to implement one.
> >
>
> Start here http://www.rdrop.com/users/paulm... for papers by Paul McKenney.
> I just noticed he put his PHD dissertation online. That has a number of references
> to work in this area (including an early RCU implementation :) ). Generally you
> use GC to extend the range of solutions to more than just pure lock-free. Also,
> they may actually scale better than some of the pure lock-free under heavy
> contention.

That makes sense.

I looked at Paul's website. There seems to be quite a bit of
information on RCU, but I didn't see any on garbage collection. RCU
might be very optimal for me, but I'm not entirely sure. My app should
typically go through quiescent states very frequently, but I know of
degenerate cases, too.

-Matt

Joe Seigh

8/2/2004 11:31:00 AM

0



SenderX wrote:
> I forgot to mention that extra atomic operations and/or memory barriers that
> implement the gc, will have a impact on performance...
>
> RCU is about the only one that I can think of that could need a couple of
> simple loads and stores, or to inform the it of read-side critical regions.

The quiesce points in RCU require memory barriers to keep them out of the
critical regions. Normally this is not a problem with a typical RCU implementation
as the quiesce points are less frequent then the critical regions. But if you have
the quiesce point right next to a critical region then you are going to have some
extra overhead.

Joe Seigh

Ronald Landheer-Cieslak

8/2/2004 1:59:00 PM

0

Joe Seigh wrote:
>
> SenderX wrote:
>
>>>Hello, I am looking for information on lock-free lists (primarily as a
>>
>>means
>>
>>>in deadlock avoidance). Is there a list anywhere of various algorithms and
>>>their drawbacks? I am primarily looking to replace a number of spinlocks
>>
>>to
>>
>>>minimize the chance of deadlock in my application.
>>
>>http://portal.acm.org/citation.cfm?id=564881&dl=ACM&c...
>>
>
>
> Here if you can't get it from ACM's site.
>
> http://www.research.ibm.com/people/m/michae...
>
> High Performance Dynamic Lock-Free Hash Tables and List-Based Sets
An implementation of that is available in jail-ust libcontain. Sources
in CVS:
http://cvs.sourceforge.net/viewcvs.py/jail-ust/libcontain/list.c?v...

The SMR memory management algorithm is implemented in libmemory:
Sources in CVS:
http://cvs.sourceforge.net/viewcvs.py/jail-ust/...

HTH

rlc

NB: The code is GPL/BSD double-licensed. If you want to use it and you
contribute back to the project, you can get a GPL-waiver for your
troubles :)

Mouse

8/3/2004 3:39:00 AM

0

> You should read the entire thread. My old algo needs a modification to the
> Release function. The gc's aba needs to be inc'd on every cas success.

^^^^^^^^^^^^^^^^

I meant, on every one of the Release functions cas's...

DOH!