同步访问双向链表

Question

同步访问双向链表

6

我正在尝试在C语言中实现一个（特殊类型的）双向链表，使用类似原子CAS等C语言包装的同步指令来进行线程同步，而不是pthread原语。（链表的元素是固定大小的内存块，几乎不能在其中放置像pthread_mutex_t这样的东西。）我实际上并不需要完全任意的双向链表方法，只需要以下操作：

- 在列表末尾插入 - 从列表开头删除 - 根据指向要删除成员的指针，在列表中任意位置删除成员，该指针通过遍历列表之外的其他途径获得。

所以也许更好地描述这个数据结构的方式是具有从队列/先进先出中间删除项目的可能性。

是否有标准方法来同步这个数据结构？我卡在了潜在死锁问题上，其中一些可能与涉及的算法本身有关，另一些可能源于我试图在一个有其他限制的受限空间中工作。

特别是，如果要同时删除相邻对象，我就卡住了。显然，在删除对象时，你需要获取先前和下一个对象在列表中的锁，并更新它们的next/prev指针以相互指向。但如果任何一个邻居已经被锁定，这将导致死锁。我试图找出任何/所有正在进行的删除操作都可以遍历锁定的列表部分，并确定当前正在删除的最大子列表，然后锁定相邻于该子列表的节点，以便将整个子列表作为一个整体被删除，但我的头有点疼.. :-P

结论（？）：跟进一下，我确实有一些要使代码工作的代码，但我也对理论问题感兴趣。每个人的答案都非常有帮助，再加上在这里未明确表达的限制细节（你真的不想知道指向要删除元素的指针来自哪里和其中涉及的同步！），我已决定暂停使用本地锁代码并专注于：

- 使用更多小列表，每个列表都有单独的锁。 - 最小化在保持锁定期间执行指令的数量，并在获取锁定之前（以安全的方式）调用内存，以减少页面故障和缓存未命中的可能性。 - 测试在人为高负载下的争用情况，并评估此方法是否令人满意。

再次感谢给出答案的所有人。如果我的实验效果不好，我可能会回到概述的方法（特别是Vlad的方法）并重试。

- R.. GitHub STOP HELPING ICE

我相信只要你不关心列表的一致性，就可以使用双向链表来完成。根据您在列表上移动的方向，添加或删除的对象可能可见或不可见。 - Zan Lynx

1

@R：一个固定长度的缓冲区（循环使用）对您无用吗？ - Tony Delroy

很遗憾，我找不到一种方法来让它与固定长度的循环缓冲区一起工作。从一开始我就想这样做，因为这样会更简单，性能也会更好... - R.. GitHub STOP HELPING ICE

@R：你的意思是说你找不到一种方法使无锁定长循环缓冲区起作用，还是说你找不到一种方法使这样的缓冲区满足你的应用需求？ - Tony Delroy

我找不到一种方法来满足要求。我需要一种方法事先确保循环缓冲区已经被充分扩大，以满足所有可能的未来插入，直到下一个内存重新分配点（在插入点不可能）。 - R.. GitHub STOP HELPING ICE

http://en.wikipedia.org/wiki/Double_compare-and-swap - ephemient

6个回答

5

请不要认为我的回答很苛刻，但是请不要这样做。您几乎肯定会出现错误，而且非常难以找到。使用pthreads锁原语。它们是您的朋友，并由深入了解您选择的处理器提供的内存模型的人编写。如果您尝试使用CAS、原子增量和类似方法做同样的事情，几乎肯定会犯一些微妙的错误，直到为时已晚才能发现。

以下是一个小的代码示例，以帮助说明这一点。这把锁有什么问题？

volatile int lockTaken = 0;

void EnterSpinLock() {
  while (!__sync_bool_compare_and_swap(&lockTaken, 0, 1) { /* wait */ }
}

void LeaveSpinLock() {
  lockTaken = 0;
}

答案是：释放锁时没有内存屏障，这意味着在锁内执行的某些写操作可能在下一个线程进入锁之前尚未发生。哎呀！（可能还有许多其他错误，例如，该函数在自旋循环内部不执行适合平台的yield，因此浪费大量CPU周期等）。

如果将双向链表实现为带有哨兵节点的循环列表，则只需要执行两个指针分配即可从列表中删除项，并且需要四个指针分配来添加项。我相信您可以承受在这些指针分配上持有精心编写的独占锁。

请注意，我假设您不是那些深刻理解内存模型的少数人之一，仅因为世界上很少有这样的人。如果您是其中之一，则即使您无法弄清楚也应该表明它有多么棘手。 :)

我还假设您之所以提出这个问题是因为您有一些需要运行的代码。如果这只是一个学术练习，以便更多地了解线程（也许是成为深层低级并发专家的步骤），那么请无视我，并对您正在定位的平台的内存模型的详细信息进行研究。 :)

- John Doty

2

+1，因为像那样的答案，你不应该只有1个声望值。 :-) - R.. GitHub STOP HELPING ICE

3

如果您维护一组严格的锁层次结构，就可以避免死锁：如果您锁定多个节点，请始终先锁定靠近列表头部的节点。因此，要删除一个元素，首先锁定节点的前驱，然后锁定节点本身，然后锁定节点的后继，取消链接该节点，最后按相反的顺序释放锁定。

这样，如果多个线程同时尝试删除相邻的节点（例如链A-B-C-D中的节点B和C），则首先获取节点B锁定的线程将是第一个解除链接的线程。线程1将锁定A、B、C，线程2将锁定B、C、D。只有对于B存在竞争，而且线程1无法在等待线程2持有的锁定的同时保持自己持有的锁定，而线程2也在等待线程1持有的锁定（即死锁）。

- Adam Rosenfield

我喜欢这个。它很简单，我认为它符合要求。对于作为列表成员的节点，我必须制作一个二级锁（因为如我在其他评论中所描述的那样，当前节点的现有锁已经被持有，无法在删除时释放），但除此之外，实现这个似乎很直接。 - R.. GitHub STOP HELPING ICE

问题是：给定节点C，如何在不先锁定C的情况下获取并锁定B？在读取C.prev后，其他线程可能会更改它并删除B，然后您就会有一个悬空指针。 - Goswin von Brederlow

1

我注意到你需要一个双向链表的唯一原因是因为要求从列表中删除节点，而这些节点是在不遍历列表的情况下获得的。一个简单的FIFO显然可以用一个单向链表（带有头和尾指针）来实现。

你可以通过引入另一层间接性来避免从中间删除的情况 - 如果列表节点仅包含一个next指针和一个payload指针，并且实际数据指向其他地方（你说在插入点不能进行内存分配，所以你只需要在分配有效负载本身的同时分配列表节点结构）。

在从中间删除的情况下，你只需将payload指针设置为NULL并将孤立的节点留在列表中。如果FIFO弹出操作遇到这样的空节点，它只需释放它并重试。这种延迟让你使用单向链表，而无锁单向链表实现要容易得多。

当然，在这里仍然存在一个关键的竞争，即在队列中间删除一个节点 - 在决定要删除它的线程实际有机会执行之前，似乎没有任何东西能阻止该节点来到队列的前面并被另一个线程移除。这个竞争似乎超出了您问题中提供的细节范围。

- caf

1

整个列表都需要锁定，否则无法避免问题。原因如下：

向空列表插入元素

线程A和B想要插入一个对象。

线程A检查列表，发现它是空的。

发生上下文切换。

线程B检查列表，发现它是空的，并更新头和尾指针以指向其对象。

发生上下文切换。

线程A更新头和尾指针以指向其对象。线程B的对象已经丢失。

从列表中间删除项目

线程A想要删除节点X。为此，它首先必须锁定X的前驱、X本身和X的后继，因为这些节点都将受到操作的影响。要锁定X的前驱，您必须执行类似于以下内容的操作：

spin_lock(&(X->prev->lockFlag));

虽然我使用了函数调用语法，但如果 spin_lock 是一个函数，你就无法进行下去了，因为这至少涉及到三个操作才能确实拥有锁：

将锁标志的地址放置在堆栈上（或寄存器中）
调用函数
执行原子测试和设置

有两个地方可以让 A 线程被换出，另一个线程可以进入并删除 X 的前继节点而 A 线程不知道 X 的前继节点已更改。因此，您必须以原子方式实现自旋锁本身。即，您必须添加一个偏移量到 X 以获取 x->prev，然后对其进行解引用以获取 *（x->prev），并添加一个偏移量以获取 lockFlag，然后一次性完成所有原子操作。否则，在您已经承诺锁定特定节点但尚未实际锁定它之后，总会有机会让其他东西悄悄地进入。

- JeremyP

@JeremyP：关于在空列表中插入的问题。线程A必须先锁定头部，然后检查和更新它，最后才解锁。这样我们就不会遇到你所描述的问题。 - Vlad

1

@R..：确实，头和尾必须是永久的。但我会避免将它们放在同一个节点上，因为锁定头部将隐式锁定尾部，这将破坏锁定顺序。（考虑只有头、尾、两个项目和两个线程同时尝试删除这些项目的列表的情况。） - Vlad

@R..：但正如我在答案中解释的那样，列表内部的删除存在竞争条件。您首先必须定位前一个节点中锁标志的地址，然后必须应用该锁。在这两个操作之间，另一个线程可以删除前一个节点。在末尾插入时也存在同样的问题。 - JeremyP

如果一个节点的邻居被锁定，无法删除该节点怎么办？（可能需要第二个锁，而不是同一个锁。） - R.. GitHub STOP HELPING ICE

1

我不确定，我需要考虑一下。 - JeremyP

显示剩余4条评论

0

两个想法。

首先，为了避免死锁问题，我会做一些自旋锁：

锁定要删除的项
尝试锁定其中一个邻居，如果您有廉价的随机位可用，则随机选择一侧
如果这不成功，请放弃第一个锁并循环
尝试锁定另一个
如果成功删除您的项目
否则放弃两个锁并循环

由于从列表中剪切元素不是很耗时的操作，因此这不应该给您带来太多性能开销。而且，如果您真的急于同时删除所有元素，它仍然应该为您提供一些良好的并行性。

第二个想法是进行懒惰删除。标记要删除的元素，并仅在它们出现在列表末尾时有效地删除它们。由于您只对头部和尾部感兴趣，因此列表项的实际用户可以执行此操作。优点是当它们在删除时处于末尾时，死锁问题消失了。缺点是这使最终删除成为顺序操作。

- Jens Gustedt

无法进行惰性删除；这会导致内存损坏，因为一旦从列表中拉出节点，存储prev/next指针的内存就立即用于不同的目的。 - R.. GitHub STOP HELPING ICE

如果您放弃了第一个锁，然后其他线程删除了该项，那么您将拥有该项的悬空指针，并试图对其进行加锁。 - Goswin von Brederlow

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vlad · Accepted Answer

为什么不直接使用粗粒度锁？只锁定整个队列即可。

更为详细的（但不一定更高效，这取决于您的使用模式）解决方案是使用读写锁，分别用于读取和写入。

对于您的情况，使用无锁操作似乎不是一个很好的选择。想象一下，某个线程正在遍历您的队列，与此同时，“当前”项被删除了。无论您的遍历算法持有多少附加链接，所有这些项目都可能被删除，因此您的代码将没有完成遍历的机会。

使用比较并交换的另一个问题是，对于指针，您永远不知道它是否真的指向同一个旧结构，或者旧结构已被释放，并且在相同地址上分配了一些新结构。这可能对您的算法有所影响，也可能没有影响。

对于“本地”锁定的情况（即锁定每个列表项的可能性），一个想法是使锁定有序。对锁进行排序可以确保死锁的不可能性。因此，您的操作如下：

通过指针p删除先前的项：

1. 锁定p，检查（使用项目中的特殊标志）该项是否仍在列表中 2. 锁定p->next，检查它不为零且在列表中；这样您就确保p->next->next不会同时被删除 3. 锁定p->next->next 4. 在p->next中设置一个标志，指示它不在列表中 5. (p->next->next->prev，p->next->prev) = (p，null); (p->next，p->next->next) = (p->next->next，null) 6. 释放锁

插入到开头：

1. 锁定头部 2. 在新项目中设置标志，表示它在列表中 3. 锁定新项 4. 锁定头部->next 5. (head->next->prev，new->prev) = (new，head); (new->next，head) = (head，new) 6. 释放锁

这似乎是正确的，但我没有尝试过这个想法。

本质上，这使双向链表的工作方式就像单向链表一样。

如果您没有前一个列表元素的指针（通常情况下都是这样，因为几乎不可能保持这样的指针处于一致状态），可以采取以下措施：

通过指针c删除要删除的项：

锁定c，并检查它是否仍然是列表的一部分（这必须是列表项中的标志），如果不是，则操作失败
获取指针p = c->prev
解锁c（现在，c可能被其他线程移动或删除，p也可能从列表中移动或删除）[为了避免c的释放，您需要在此处拥有类似共享指针或至少对列表项进行引用计数的东西]
锁定p
检查p是否是列表的一部分（它可能在第3步之后被删除）；如果不是，请解锁p并重新开始
检查p->next是否等于c，如果不是，请解锁p并重新开始[在这里我们可以优化重启，目前不确定]
锁定p->next；在这里，您可以确定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在列表中的初始位置。当然，这种最坏情况很少发生。