我正在尝试在 pthreads 环境中用 C 实现一个（特殊类型的）双向链表，但仅使用 C 包装的同步指令（如原子 CAS 等）而不是 pthread 原语。 （列表的元素是固定大小的内存块，几乎肯定无法容纳pthread_mutex_t等等。）我实际上不需要完整的任意双向链表方法，只需要：
- 在列表末尾插入
- 从列表开头删除
- 基于指向要删除的成员的指针在列表中的任意点进行删除，该指针是从除遍历列表之外的源获取的。
因此，也许描述此数据结构的更好方法是队列/fifo，并且可以删除队列中的项目。
是否有一个标准方法来同步这个？我陷入了可能的僵局问题，其中一些问题可能是所涉及的算法所固有的，而另一些问题可能源于这样一个事实：我试图在一个有限的空间中工作，而我能做的事情受到其他限制。
Edit：特别是，如果要同时删除相邻对象，我该怎么办？据推测，在删除对象时，您需要获取列表中前一个和下一个对象的锁，并更新它们的 next/prev 指针以指向彼此。但如果任何一个邻居已经被锁定，这将导致死锁。我试图找出一种方法，使任何/所有发生的删除都可以遍历列表的锁定部分，并确定当前正在删除过程中的最大子列表，然后锁定与该子列表相邻的节点，以便整个子列表被整体删除，但我的头开始受伤..:-P
结论（？）：后续，我确实有一些想要运行的代码，但我也对理论问题感兴趣。每个人的答案都非常有帮助，并结合了我在这里表达的限制之外的详细信息（您really不想知道要删除的元素的指针来自哪里以及其中涉及的同步！）我决定暂时放弃本地锁定代码并专注于：
- 使用大量较小的列表，每个列表都有单独的锁。
- 最大限度地减少持有锁的指令数量，并在获取锁之前（以安全的方式）访问内存，以减少持有锁时发生页面错误和缓存未命中的可能性。
- 测量人为高负载下的争用并评估该方法是否令人满意。
再次感谢所有给出答案的人。如果我的实验进展不顺利，我可能会回到概述的方法（尤其是弗拉德的）并重试。
为什么不直接应用粗粒度锁呢？只需锁定整个队列即可。
更复杂的（但不一定更有效，取决于您的使用模式）解决方案是使用读写锁，分别用于读取和写入。
在我看来，使用无锁操作对于您的情况来说并不是一个好主意。想象一下某个线程正在遍历您的队列，同时“当前”项目被删除。无论您的遍历算法拥有多少额外链接，所有这些项目都可能被删除，因此您的代码将没有机会完成遍历。
比较和交换的另一个问题是，使用指针，您永远不知道它是否真的指向同一个旧结构，或者旧结构已被释放，并且在同一地址分配了一些新结构。对于您的算法来说，这可能是也可能不是问题。
对于“本地”锁定的情况（即，可以单独锁定每个列表项），一个想法是使锁有序。对锁进行排序可确保不会出现死锁。所以你的操作是这样的：
通过指针p删除previous item:
- 锁定 p，检查（可能使用项目中的特殊标志）该项目仍在列表中
- lock p->next，检查它是否不为零并且在列表中；这样你就可以确保 p->next->next 不会同时被删除
- 锁定 p->下一个->下一个
- 在 p->next 中设置一个标志，表明它不在列表中
- (p->下一个->下一个->上一个, p->下一个->上一个) = (p, null); (p->下一个, p->下一个->下一个) = (p->下一个->下一个, null)
- 释放锁
在开头插入：
- 锁头
- 在新项目中设置标志，表明它在列表中
- 锁定新项目
- 锁头->下一步
- (头->下一个->上一个，新->上一个) = (新，头); （新->下一个，头）=（头，新）
- 释放锁
这似乎是正确的，但我没有尝试这个想法。
本质上，这使得双链表像单链表一样工作。
如果您没有指向前一个列表元素的指针（当然通常是这种情况，因为实际上不可能使此类指针保持一致状态），您可以执行以下操作：
通过指针c删除要删除的项：
- 锁定c，检查它是否仍然是列表的一部分（这必须是列表项中的标志），如果不是，操作失败
- 获取指针 p = c->prev
- 解锁c（现在，c可能被其他线程移动或删除，p也可能从列表中移动或删除）[为了避免c的释放，您需要有类似共享指针的东西或至少一种此处列表项的重新计数]
- lock p
- 检查 p 是否是列表的一部分（可以在步骤 3 后将其删除）；如果没有，解锁p并从头开始
- 检查p->next是否等于c，如果不等于，则解锁p并从头开始重新启动[这里我们也许可以优化重新启动，不确定ATM]
- 锁定p->下一个；这里你可以确定 p->next==c 并没有被删除，因为删除 c 需要锁定 p
- 锁定 p->下一个->下一个；现在所有的锁都已被占用，所以我们可以继续
- 设置标志 c 不是列表的一部分
- 执行惯例 (p->next, c->next, c->prev, c->next->prev) = (c->next, null, null, p)
- 释放所有锁
请注意，仅拥有指向某个列表项的指针无法确保该项目不会被释放，因此您需要进行某种重新计数，以便该项目在您尝试锁定它时不会被销毁。
请注意，在最后一个算法中，重试次数是有限的。确实，新项不能出现在c的左边（插入是在最右边的位置）。如果我们的步骤 5 失败，因此我们需要重试，这只能是由于同时从列表中删除 p 造成的。这种删除最多可以发生 N-1 次，其中 N 是 c 在列表中的初始位置。当然，这种最坏的情况不太可能发生。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
