Re: [Algorithms] lock-free stack with hazard list performance

[Nicholas \Indy\ R. <ar...@gm...>]

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;

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.

Nicholas "Indy" Ray

On Tue, Apr 21, 2009 at 6:15 PM, Stephan Rose <ke...@so...> wrote:
> On Tue, 2009-04-21 at 17:23 -0700, Nicholas "Indy" Ray wrote:
>> On Tue, Apr 21, 2009 at 4:28 PM, Stephan Rose <ke...@so...> wrote:
>> > 2. Remove Node A and delete it. Major crash right there when thread 1
>> > now tries do it's CAS.
>>
>> Here is where I am confused, shouldn't the CAS be on the head pointer
>> during a dequeue so, that if the CAS is successful (assuming that
>> dequeue is the only way to get a reference to an item on the list,
>> which is how lock-free queues should be anyways) you know that you are
>> the only thread that has access to the node?
>
> To get a reference to an item on the list you're correct, you have to
> dequeue it and then it solely belongs to the thread that dequeued it and
> there are no issues. That isn't the problem.
>
> The problem are the nodes that make up the list and the references to
> them. See below for an example.
>
>>
>> > Both problems can be solved by ensuring that Node A is not recycled nor
>> > deleted until all threads release their reference to it. All lock-free
>> > implementations so far I've found have been in managed languages such as
>> > C# or Java for that reason so far as the GC ensures exactly that.
>>
>> Again, not sure why multiple threads have reference to nodes still on the queue.
>
> Well first off, the node declaration itself is simple:
>
> template <typename T>
> struct Node
> {
>  T data;
>  Node* next;
> }
>
> Simple enough, nothing fancy.
>
> Now the stack is initialized with a dummy head node that contains no
> data and initially next = 0.
>
> Now here is what happens, I'll prefix each line with the thread that's
> executing it such as T1, T2, etc. Code is simplified for clarity.
>
> T1 Wants to pop a node off the stack.
>
> T1: Node* node;
> T1: do {
> T1:   node = head->next;
>
> Next, T1 gets preempted and it's T2's turn, it also wants to pop a node
> off the stack.
>
> T2: Node* node;
> T2: do {
> T2:   node = head->next;
>
> Both T1 and T2 are now referencing the same node and are both trying to
> pop the same node off the stack.
>
> T2: } while(!cas(head->next, node, node->next);
>
> T2 is not preempted and succeeds with its CAS and now proceeds to delete
> the node.
>
> T2: delete node;
>
> T2 is now done, control returns to T1 which is still pointing at the
> very node that was just deleted.
>
> T1: } while(!cas(head->next, node, node->next);
> T1: CRASH!
>
> And it doesn't matter if this is running on 1 core, or multiple cores,
> the above will happen when multiple threads try to pop a node from the
> same stack if access to the current node is not guarded to prevent too
> early deletion.
>
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>