列表插入，不相交n并行？

我一直在寻找并发链表实现/学术论文，允许并发插入到列表中的不相交位置。我更喜欢基于锁的方法。列表插入，不相交n并行？

不幸的是，我已经签出迄今使用基于列表的锁定，而不是一个类似于基于节点锁定的实现。

任何帮助人？

编辑1：感谢所有的初步答复。使用基于节点的锁定意味着，为了插入节点或删除节点后，我需要锁定前一个节点和下一个节点。现在完全有可能在线程1尝试锁定之前的节点时，它会在线程2中被删除。如何防范这种事故？

2010-11-15 Fanatic23

我不能建议对C做专门的库，但如果你最终做自己，你可能会避免通过重新使用少量的锁和一些“有成千上万的锁哈希“来决定为每个节点使用哪一个。如果锁的数量适当地大于少量空间开销的节点数（并且它是固定的，而不是每个节点），那么会出现很多不会发生争用的情况。

更新，为EDIT 1

您可以解决此通过具有每列表多读者，单写锁，（rwlock），在那里你获得一个“读”锁获得每前插入的节点锁，但是对于删除，您需要获得单个“写入”锁。您可以相当容易地避免不必要的读取/插入操作的同步问题，并且删除操作非常简单。（假设为删除是非常罕见，虽然比插入）

2010-11-15 18:11:29 Flexo

谢谢你，和+1。我一直在思考类似的问题，但我有我在问题中提到的问题（编辑1）。做出回应。 – Fanatic23 2010-11-15 18:15:36

添加了我对这个问题的建议。其他人推荐的无锁数据结构正变得越来越普遍，相当不错，但（正确）推出自己的数据结构非常棘手。 – Flexo 2010-11-15 18:35:08

当您正常遍历列表时，您还需要在每个列表的'rwlock'上读锁，以防止您查看的节点被删除。 – caf 2010-11-16 01:18:13

基于节点锁定麻烦的是，你通常有锁定每个插入两个节点。在某些情况下，这可能会更昂贵。

更糟的是，你得到餐饮哲学家一样死锁的可能性，你必须对待。

因此，基于列表的锁定更容易，这就是为什么你看到更多关于这些。

如果列表的性能特点基于锁是不利于你的应用程序考虑换到不是单链表不同的数据结构。

2010-11-15 18:11:51

单链表可以避免死锁吗？新节点不需要被锁定，因为没有其他人可以知道它存在，只有一个节点需要调整其“下一个”指针以使其工作。 – Flexo 2010-11-15 18:16:45

我不认为餐饮哲学家是一个担心，因为这个清单是很好的命令，而不是循环。 – 2010-11-15 18:20:18

@awoodland：如果列表单独链接，并没有提及Q，@Eric也没有提及它不是循环的。当然，你可以避免僵局，但你必须小心，这就是我所说的。 – 2010-11-16 08:14:19

你可能想看看使用无锁实现。这个想法是在插入/删除节点时使用原子测试集操作。

不幸的是，并没有很多广为人知的实现。你可能不得不推出自己的。下面是关于原子操作的支持GCC的文档：从我的身边

2010-11-15 18:12:28

回答