正在尝试实现linkedlist

Question

public void Push(Node newNode)
{
while (true)
{
Node tmp = this.head;
newNode.next = tmp;
if (Interlocked.CompareExchange(ref this.head, newNode, tmp) == tmp)
{
break;
}
}
}
public Node Pop()
{
Node pop=null;
while (this.head != null)
{
pop = this.head;
var oldcount = this.popcount;
var newcount = oldcount + 1;
if (Interlocked.CompareExchange(ref this.popcount, newcount, oldcount) == oldcount)
{
pop = Interlocked.CompareExchange(ref head, head.next, head);
break;
}
pop = null;
}
return pop;
}
//---------------------------------------------------------
while (count < 10000) // 4 thread run this code
{
for (int i = 0; i < 2; i++)
{
Node temp;
if (freelist.head != null)
{
temp = freelist.Pop();
headlist.Push(temp);
}
}
for (int j = 0; j < 1; j++)
{
Node temp;
if (headlist.head != null)
{
temp = headlist.Pop();
freelist.Push(temp);
}
}
count++;
Console.WriteLine(count);
}

我正在尝试实现无锁链表。我添加popcount是为了避免aba问题。并利用CAS实现了Push和Pop。当我运行这个代码时，它并没有像我想的那样工作。

class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
}
}

当我运行代码时，Node.next会指向自己。例如，Node.data=99720和Node.next = Node因此，当我转到Node.next时，它仍然是99720节点。不知道为什么会发生。。。

Answer 1

看起来您正在尝试构建一个无锁堆栈。我不确定你用什么(伪(代码作为实现的基础，但你试图用popcount解决ABA问题是行不通的。当您使用版本标记来防止ABA时，它必须与指针组合，即指针和标记必须在单原子操作中更新。Java提供AtomicStampedReference正是为了这个目的，但不幸的是，.NET没有提供任何类似的功能。

然而，由于您使用.NET，您可以使用垃圾收集器，因此只要不重用节点，就不必担心ABA问题。

BTW：你的pop函数缺少一个循环。