无锁列表帮助！

Question

您好，我正在尝试编写一个无锁列表，我认为添加部分可以正常工作，但从列表中提取对象的代码不能很好地工作:(

嗯，这个列表不是一个普通的列表..我有接口 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前右到达现场（你有注释“//让我们尝试”）。

状态是：

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

此时线程2接管并调用list.Get()。假设workItem1的executionTime现在，因此调用成功，并返回workItem1。

在此状态是：

first = null, workItem1.next = null

（以及在其他线程，nextItem仍然是workItem1）。

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

如果我们现在称之为list.Get()，我们将得到null，即使Add()成功完成。

您或许应该看看一个真正的同行评议的无锁链表算法。我认为标准之一是这通过约翰·瓦卢瓦。有一个C ++实现这里。 这对无锁的优先级队列的文章也可能是使用的

Answer 2

可以使用数据结构一个时间戳协议就好，从数据库世界镜像这个例子：

并发

但明确的是，每个项目都需要一个读取和写入时间戳记，并确保遵循算法规则明确。

有虽然链表实现这个的一些额外的困难，我想。该数据库的例子就是对，你知道你想要的数组索引矢量被罚款。然而，在一个链表，你可能需要走在三分球 - 而且当你在搜索列表的结构可以改变！我想你可以解决通过某种细微差别（或者，如果你只是想穿越“新”的名单，因为它是，什么都不做），但由此带来的问题。尝试去解决它，而不会引入，使得它不是锁定列表更糟一些回滚条件！

Answer 3

所以，你确定它必须是无锁？根据您的工作负载的无阻塞解决方案有时会慢一些。看看这个 MSDN文章多一点。也证明无锁数据结构是正确的可以是非常困难的。

Answer 4

我绝不是该主题的专家，但据我所知，您需要使 IWorkItem 实现中的 ExecutionTime 字段变得易失（当然可能已经是这样）或插入一个 记忆屏障 在设置 ExecutionTime 之后或在读取它之前。