Re: lock-free stack with hazard list performance

You can look into win32api InterlockedPopEntrySList and
InterlockedPushEntrySList.
They solve aba problem and deletion problem is partially fixed (they still
can do a read access to a node which is popped from a list, so in case you
delete that page with the node you have a problem then).

x86 code is pretty simple. I didn't look into x64 code yet.

Alexander.

2009/4/22 Stephan Rose <[email protected]>

> On Tue, 2009-04-21 at 18:53 -0700, Nicholas "Indy" Ray wrote:
> > So, excuse if I'm missing a lot, I haven't created any lock-free data
> > structures in about 2 years, But I suspect something like the
> > following might work, It has a bit longer contention, and will have to
> > spin more often, but I suspect there are also better ways to achieve
> > the same thing.
> >
> > do
> > {
> >   node = head;
> >   if(!node) continue;
> > }
> > while(cas(head, node, 0));
> >
> > head = node->next;
> >
> > retData = node->Data;
> >
> > delete node;
>
> Nope, it definitely works, however...
>
> 1. It's not lock-free, your cas on the head to set it to 0 forms a
> lock. :)
>
> 2. It prevents other threads from peeking at the top of the stack
> without potentially locking which in my case is not only lock-free but
> also wait-free. Though honestly not sure how much of an issue that is as
> I'm not really sure how useful it really is to peek at a stack/queue
> being accessed by multiple threads. No guarantee that a following
> pop/dequeue will return the peeked item.
>
> 3. One advantage that locking algorithms do have over lock-free is that
> with the right kind of spinlock, thread starvation can be avoided by
> guaranteeing that threads will obtain their lock in the order they
> requested it. The above lock makes no such guarantees however.
>
>
> >
> > This also will also require at least one dummy node, but I don't
> > suppose that would be a huge problem.
> >
> > Anyways, when I get access to my main computer tonight or tomorrow, I
> > will check to see how my current queue manages memory, which I think
> > is more optimal.
>
> That would be awesome, I'd be most interested in seeing that.
>
> Stephan
>
>
>
>
> ------------------------------------------------------------------------------
> Stay on top of everything new and different, both inside and
> around Java (TM) technology - register by April 22, and save
> $200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
> 300 plus technical and hands-on sessions. Register today.
> Use priority code J9JMT32. http://p.sf.net/sfu/p
> _______________________________________________
> GDAlgorithms-list mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
Regards,
Alexander Karnakov

------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and 
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today. 
Use priority code J9JMT32. http://p.sf.net/sfu/p

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list