列表插入,不相交n平行?

我不能特别推荐任何为C执行此操作的库,但是如果您最终自己执行此操作,您可以通过重新使用少量锁和一些“散列”来决定每个节点使用哪个锁,从而潜在地避免拥有数千个锁。如果锁的数量适当地大于节点的数量,并且空间开销很小(而且是固定的,而不是每个节点),那么就会出现很多没有争用的情况。

更新,用于编辑1

你可以通过一个列表多个读卡器,一个写锁来解决这个问题。( rwlock ,在获取插入的每个节点锁之前获取“读取”锁,但对于删除,需要获取单个“写入”锁。对于读/插入操作,您可以相当容易地避免不必要的同步问题,删除也足够简单。(假设是删除比插入要少得多)

您可能希望看到使用无锁实现。其思想是在插入/删除节点时使用原子测试集操作。

不幸的是,并没有很多广为人知的实现。你可能得自己滚。以下是关于原子操作支持的GCC文档:

http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html

基于节点的锁定的问题在于,通常每次插入都必须锁定两个节点。在某些情况下,这可能会更贵。

更糟糕的是,你会让吃饭的哲学家一样陷入僵局,你不得不去治疗。

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

如果基于列表的锁定的性能特征不利于应用程序,请考虑更改为与单个链接列表不同的数据结构。