c# - 无锁列表帮助!

Question

嗨，我正在尝试编写一个无锁列表，我认为添加部分可以正常工作，但是从列表中提取对象的代码效果不佳:(

这个列表不是一个普通的列表..我有接口(interface) IWorkItem

interface IWorkItem
{
    DateTime ExecuteTime { get; }
    bool Cancelled { get; }
    void Execute(DateTime now);
}

好吧，我有一个列表，我可以在其中添加这个 :P 我的想法是当我运行 Get();在列表上它应该循环它直到它找到一个 IWorkItem

If (item.ExecuteTime < DateTime.Now)

并将其从列表中删除并返回.. 我已经在我的双核 cpu 上用许多线程进行了测试，到目前为止，Add 似乎从未失败过，但是 Get 函数丢失了一些工作项，有些地方我不知道出了什么问题......

ps 如果我得到这个工作，任何人都可以免费使用代码 :) 好吧，你是任何方式，但我不明白它的错误 :P

代码在这里http://www.easy-share.com/1903474734/LinkedList.zip如果您尝试运行它，您会发现它有时无法获得与它放入列表中一样多的工作项...

编辑:我有一个无锁列表，它比使用 lock(obj) 语句更快，但我有一个使用 Interlocked 的锁对象，它仍然优于无锁列表，我将尝试制作一个无锁数组列表，并且如果我在那里得到相同的结果，当我做错了上传结果在这里..

Answer 1

问题在于您的算法:考虑以下事件序列:

线程 1 调用 list.Add(workItem1)，它完全完成。

状态是:

first=workItem1, workItem1.next = null

然后线程 1 调用 list.Add(workItem2) 并到达第二个 Replace 之前的位置(您有注释“//lets try”)。

状态是:

first=workItem1, workItem1.next = null, nextItem=workItem1

此时线程 2 接管并调用 list.Get()。假设 workItem1 的执行时间是现在，那么调用成功并返回 workItem1。

此状态后为:

first = null, workItem1.next = null

(在另一个线程中，nextItem 仍然是 workItem1)。

现在我们回到第一个线程，它通过设置 workItem1.next:=workItem2 完成 Add()。

如果我们现在调用 list.Get()，我们将得到 null，即使 Add() 已成功完成。

您可能应该查找真正的同行评审的无锁链表算法。我认为标准的是 this由约翰瓦卢瓦。有一个 C++ 实现 here . This关于无锁优先级队列的文章也可能有用。