2

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

那么这个列表不是一个普通的列表..我有接口 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 的锁对象，它仍然优于无锁列表，我将尝试制作一个无锁数组列表，如果我当我在这里完成上传结果时得到相同的结果..

4

4 回答 4

5

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

线程 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的 executionTime 是现在，所以调用成功并返回workItem1。

这个状态之后是：

first = null, workItem1.next = null

（在另一个线程中，nextItem仍然是workItem1）。

现在我们回到第一个线程，它完成了Add()by setting workItem1.next:=workItem2。

如果我们现在调用，即使成功完成list.Get()，我们也会得到。nullAdd()

You should probably look up a real peer-reviewed lock-free linked list algorithm. I think the standard one is this by John Valois. There is a C++ implementation here. This article on lock-free priority queues might also be of use.

于 2009-02-02T09:43:43.553 回答
1

那么你确定它需要无锁吗？根据您的工作负载，非阻塞解决方案有时可能会更慢。查看这篇MSDN 文章了解更多信息。同样证明无锁数据结构是正确的也非常困难。

于 2009-01-24T16:36:54.160 回答
1

您可以很好地为数据结构使用时间戳协议，从数据库世界中镜像这个示例：

并发

但是要清楚每一项都需要读写时间戳，一定要清楚地遵循算法的规则。

我认为，在链表上实现这一点还有一些额外的困难。数据库示例适用于您知道所需数组索引的向量。但是，在链表中，您可能需要沿着指针向下走——并且在您搜索时，链表的结构可能会发生变化！我想您可以通过某种细微差别来解决这个问题（或者如果您只想按原样遍历“新”列表，则什么都不做），但这会带来问题。尝试在不引入比锁定列表更糟糕的回滚条件的情况下解决它！

于 2009-02-01T21:10:39.110 回答
0

我绝不是该主题的专家，但据我所知，您需要在 IWorkItem 的实现中使 ExecutionTime-field 易失性（当然可能已经是这样），或者在您之后插入一个内存屏障设置 ExecutionTime 或在阅读之前设置。

于 2009-01-24T16:25:31.983 回答