c++ - 我们如何在使用链表时使用多线程

Question

我对多线程的概念相当陌生，正在探索一些有趣的问题以获得更好的想法。

我的一个 friend 提出了以下建议:

“拥有一个链表并执行常规的插入、搜索和删除操作是相当简单的。但是如果多个线程需要在同一个列表上工作，您将如何执行这些操作。最少需要多少锁。我们有多少锁才能优化链表功能？”

考虑一下，我觉得一个锁就足够了。我们为每个单独的读写操作获取锁。我的意思是，当我们访问列表中的节点数据时，我们获得了锁。当我们插入/删除元素时，我们会为整个系列的步骤获取锁。

但我无法想出使用更多锁来为我们提供更优化性能的方法。

任何帮助/指示？

Answer 1

“每个列表一个锁”的逻辑扩展是“每个项目一个锁”。

这会很有用的情况是，例如如果您经常只修改列表中的单个项目。

不过，对于删除和插入，获取适当的锁会变得更加复杂。您必须在之前和之后获取项目的锁，并且必须确保始终以相同的顺序获取它们(以防止死锁)。如果必须修改根元素(如果它是双链表或循环链表，也可能)，当然还有一些特殊情况需要考虑。这种由更复杂的锁定逻辑产生的开销可能会导致您的实现再次变慢，尤其是当您经常需要从列表中插入和删除时。因此，如果大多数访问是对单个节点的修改，我只会考虑这一点。

如果您正在寻找特定用例的最佳性能，那么归根结底是同时实现这两者，并针对典型场景进行性能比较。