同步对双向链表的访问
我正在尝试在pthreads环境中在C中实现一个（特殊类型的）双向链表，但是只使用C-wrapped同步指令，如primefacesCAS等，而不是pthread原语。 （列表的元素是固定大小的内存块，几乎肯定不能适合pthread_mutex_t等。）我实际上并不需要完全任意的双向链表方法，只有：
- 插入列表末尾
- 从列表的开头删除
- 基于指向要删除的成员的指针删除列表中的任意点，该指针是从遍历列表之外的源获得的。
因此，描述此数据结构的更好方法可能是队列/ fifo，可以删除队列中的项目。
是否有标准方法来同步这个？ 我陷入了可能的死锁问题，其中一些问题可能是所涉及的算法所固有的，而其他问题可能源于这样一个事实，即我正试图在一个有限的空间内工作，并对我能做的事情有其他限制。
编辑 ：特别是，如果要同时删除相邻的对象，我会坚持做什么。 大概在删除对象时，您需要获取列表中上一个和下一个对象的锁定，并更新它们的下一个/上一个指针以指向彼此。 但是如果任何一个邻居已经被锁定，这将导致死锁。 我试图找出一种方法，任何/所有发生的删除可以走在列表的锁定部分，并确定当前正在删除过程中的最大子列表，然后锁定该子列表旁边的节点，以便整个子列表整体被删除，但我的头开始受伤.. 😛
结论（？） ：为了跟进，我确实有一些我想要工作的代码，但我也对理论问题感兴趣。 每个人的答案都非常有用，并结合我在此处表达的限制之外的细节（你真的不想知道指向要移除的元素的来源和所涉及的同步！）我现在决定放弃本地锁定代码并专注于：
- 使用大量较小的列表，每个列表都有单独的锁。
- 在获取锁定之前，最小化锁定所持有的指令数量并以内存（以安全的方式）戳戳，以减少在保持锁定时页面错误和缓存未命中的可能性。
- 测量人为负荷下的争用并评估这种方法是否令人满意。
再次感谢所有给出答案的人。 如果我的实验不顺利，我可能会回到所概述的方法（特别是弗拉德），然后再试一次。
为什么不应用粗粒度的锁？ 只需锁定整个队列即可。
更精细（但不一定更有效，取决于您的使用模式）解决方案将分别使用读写锁，用于读取和写入。
对我来说，使用无锁操作似乎不是一个好主意。 想象一下，某些线程正在遍历您的队列，同时删除了“当前”项。 无论您的遍历算法包含多少其他链接，所有项目都可能被删除，因此您的代码将无法完成遍历。
比较和交换的另一个问题是，使用指针，您永远不知道它是否真正指向相同的旧结构，或者旧结构已被释放，并且在同一地址分配了一些新结构。 这可能是您的算法的问题，也可能不是。
对于“本地”锁定的情况（即，可以单独锁定每个列表项），一个想法是使锁定。 对锁进行排序可确保无法实现死锁。 所以你的操作是这样的：
通过指针p删除前一项：
- 锁定p，检查（项目中可能使用特殊标志）项目仍在列表中
- 锁定p->接下来，检查它是否为零并在列表中; 这样你就可以确保在此期间不会删除p-> next-> next
- 锁定p-> next-> next
- 在p->中设置一个标志，表示它不在列表中
- （p-> next-> next-> prev，p-> next-> prev）=（p，null）; （p-> next，p-> next-> next）=（p-> next-> next，null）
- 释放锁
插入到开头：
- 锁头
- 在新项目中设置标志，指示它在列表中
- 锁定新项目
- 锁头 – >下一个
- （head-> next-> prev，new-> prev）=（new，head）; （new-> next，head）=（head，new）
- 释放锁
这似乎是正确的，但我没有尝试这个想法。
从本质上讲，这使双链表工作就好像它是一个单链表。
如果你没有指向前一个列表元素的指针（当然通常就是这种情况，因为几乎不可能将这样的指针保持在一致状态），你可以执行以下操作：
通过指针c删除要删除的项目：
- 锁定c，检查它是否仍然是列表的一部分（这必须是列表项中的标志），否则，操作失败
- 获得指针p = c-> prev
- 解锁c（现在，c可以被其他线程移动或删除，p也可以从列表中移动或删除）[为了避免重新分配c，你需要有一些像共享指针或至少一种在这里引用列表项的计数]
- 锁定页
- 检查p是否是列表的一部分（可以在步骤3之后删除）; 如果没有，解锁p并从头重新开始
- 检查p-> next是否等于c，如果没有，解锁p并从头开始重启[这里我们可以优化重启，不确定ATM]
- 锁定p->下一个; 在这里你可以确定p-> next == c并且没有被删除，因为删除c将需要锁定p
- 锁定p-> next-> next; 现在所有的锁都被拿走了，所以我们可以继续
- 设置c不是列表的一部分的标志
- 执行习惯（p-> next，c-> next，c-> prev，c-> next-> prev）=（c-> next，null，null，p）
- 释放所有锁
请注意，只有指向某个列表项的指针无法确保该项未被释放，因此您需要进行一种引用计数，以便在您尝试锁定该项时不会销毁该项。
请注意，在最后一个算法中，重试次数是有界的。 实际上，新项目不能出现在c的左侧（插入位于最右侧的位置）。 如果我们的步骤5失败，因此我们需要重试，这只能通过同时从列表中删除p来引起。 这样的移除可以发生不超过N-1次，其中N是列表中c的初始位置。 当然，这种最坏的情况不太可能发生。
请不要严厉对待这个答案，但不要这样做。
你几乎肯定会遇到错误，并且很难发现错误。 使用pthreads锁原语。 他们是您的朋友，并且由深刻理解您选择的处理器提供的内存模型的人编写。 如果你试图用CAS和primefaces增量等做同样的事情，你几乎肯定会犯一些你不会发现的微妙错误，直到它为时已晚。
这里有一个代码示例来帮助说明这一点。 这个锁有什么问题？
volatile int lockTaken = 0; void EnterSpinLock() { while (!__sync_bool_compare_and_swap(&lockTaken, 0, 1) { /* wait */ } } void LeaveSpinLock() { lockTaken = 0; }
答案是：释放锁时没有内存屏障，这意味着锁中执行的某些写操作可能在下一个线程进入锁之前没有发生。 哎呀！ （也可能存在更多错误，例如，该函数不会在自旋循环内执行适合平台的产量，因此极大地浪费了CPU周期。＆c。）
如果将双链表实现为带有sentinal节点的循环列表，则只需要执行两个指针分配以从列表中删除项目，并且只需要四个添加项目。 我相信你能负担得起这些指针分配的写得很好的独占锁。
请注意，我假设您不是少数几个深刻理解记忆模型的人之一，因为世界上只有极少数记忆模型。 如果你是这些人中的一员，那么即使你无法弄清楚这一事实也应该表明它是多么棘手。 🙂
我也假设你问这个问题，因为你有一些你真正喜欢的代码。 如果这只是一个学术练习，以便更多地了解线程（可能作为成为深层低级并发专家的一步），那么无论如何，请忽略我，并对内存细节进行研究您要定位的平台模型。 🙂
如果您保持严格的锁定层次结构，则可以避免死锁：如果要锁定多个节点，请始终先将其锁定在靠近列表头部的位置。 因此，要删除元素，首先锁定节点的前任，然后锁定节点，然后锁定节点的后继节点，取消链接节点，然后以相反的顺序释放锁定。
这样，如果多个线程试图同时删除相邻节点（例如，链ABCD中的节点B和C），那么无论哪个线程首先获得对节点B的锁定，将首先取消链接。 线程1将锁定A，然后是B，然后是C，线程2将锁定B，然后是C，然后是D.只有B的竞争，并且在等待线程持有的锁定时线程1无法保持锁定2，而线程2正在等待线程1持有的锁（即死锁）。
没有锁定整个列表你就无法逃脱。 原因如下：
插入空列表
线程A和B想要插入一个对象。
线程A检查列表，发现它为空
发生上下文切换。
线程B检查列表，发现它为空并更新头部和尾部以指向其对象。
发生上下文切换
线程A更新头部和尾部以指向其对象。 线程B的对象已丢失。
从列表中间删除项目
线程A想要删除节点X.为此，它首先必须锁定X的前任，X本身和X的后继，因为所有这些节点都将受到操作的影响。 要锁定X的前身，你必须做类似的事情
spin_lock(&(X->prev->lockFlag));
虽然我已经使用了函数调用语法，但是如果spin_lock是一个函数，那么你已经死了，因为在实际拥有锁之前至少涉及三个操作：
- 将锁定标志的地址放在堆栈上（或寄存器中）
- 调用该函数
- 做primefaces测试并设置
有两个地方可以交换线程A，另一个线程可以进入并删除X的前任而没有线程A知道X的前身已经改变。 所以你必须以primefaces方式实现自旋锁。 即你必须向X添加偏移量以获得x-> prev然后取消引用它以获得*（x-> prev）并向其添加偏移以获得lockFlag然后在一个primefaces单元中进行primefaces操作。 否则，在您提交锁定特定节点之后但实际锁定它之前，始终有机会潜入某些东西。
我注意到你在这里需要一个双向链表的唯一原因是因为需要从列表中间删除节点，这些节点是在不走列表的情况下获得的。 显然，一个简单的FIFO可以使用单链表（带有头指针和尾指针）来实现。
你可以通过引入另一个间接层来避免从中间删除 – 如果列表节点只包含一个next指针和一个payload指针，实际数据指向其他地方（你说在内存分配是不可能的）插入点，因此您只需要在分配有效负载本身的同一点分配列表节点结构。
在delete-from-the-middle案例中，您只需将payload指针设置为NULL并将孤立节点保留在列表中。 如果FIFO弹出操作遇到这样一个空节点，它只是释放它并再次尝试。 这种延迟允许您使用单链表，而无锁单链表实现更容易实现。
当然，这里仍然存在一个必要的竞争，即在队列中间删除一个节点 – 似乎没有任何东西阻止该节点进入队列的前面，并在决定它想要的线程之前被另一个线程删除删除它实际上有机会这样做。 此竞赛似乎超出了您问题中提供的详细信息的范围。
两个想法。
首先，为了避免死锁问题，我会做一些自旋锁：
- 锁定要删除的项目
- 尝试锁定其中一个邻居，如果你有可用的便宜随机位，则随机选择一方
- 如果这没有成功放弃你的第一个锁和循环
- 试图锁定另一个
- 如果成功删除您的项目
- 否则放弃锁定和循环
由于将一个元素拼接出一个列表并不像操作那么冗长，因此不应该花费很多性能开销。 如果你真的急于同时删除所有元素，它仍然应该给你一些很好的并行性。
第二个是做懒惰删除。 标记要删除的元素，只有当它们出现在列表末尾时才有效删除它们。 由于您只对头部和尾部感兴趣，因此列表项的有效用户可以执行此操作。 优点是当它们在删除时结束时，死锁问题就会消失。 缺点是这使得最终删除成为顺序操作。