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

Question

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

不幸的是，到目前为止我检查过的所有实现都使用基于列表的锁定，而不是类似于基于节点的锁定。

有人帮忙吗？

编辑 1:感谢大家最初的回复。使用基于节点的锁定意味着要在节点后插入或删除节点，我需要锁定前一个和下一个节点。现在完全有可能在线程 1 尝试锁定前一个节点时它在线程 2 中被删除了。如何防止此类事故发生？

Answer 1

我无法推荐任何专门为 C 执行此操作的库，但是如果您最终自己执行此操作，则可以通过重新使用少量锁和一些“散列”来潜在地避免必须拥有数千个锁"来决定每个节点使用哪个。在很多情况下，如果锁的数量适本地大于节点的数量以减少空间开销(并且它是固定的，而不是每个节点)，则不会有任何争用。

更新，用于 EDIT 1

您可以通过为每个列表设置多个读取器、单个写入锁(rwlock)来解决此问题，在获取每个节点的插入锁之前获取“读”锁，但对于删除您需要获得单个“写”锁。您可以很容易地避免读取/插入操作的不必要的同步问题，并且删除也很简单。 (假设删除比插入要少得多)