我对多线程的概念相当陌生，并且为了获得更好的想法正在探索一些有趣的问题。我们如何在使用链表时使用多线程
我的一个朋友建议如下：
“这是相当直接的有一个链接列表，并做定期插入，搜索和删除操作，但你会如何，如果多个线程执行这些操作。需要在同一个列表上工作 最少需要多少个锁，我们需要多少个锁来优化链表功能？
给我一些想法，我觉得一个锁应该足以应付。我们获取每个读写操作的锁定。我的意思是，当我们访问列表中的一个节点数据时，我们获得了锁。当我们插入/删除元素时，我们获取整个系列步骤的锁定。
但是我无法想象使用更多锁的方式会给我们更多的优化性能。
任何帮助/指针？
“每个列表一个锁定”的逻辑扩展将是“每个项目一个锁定”。
这种情况很有用，例如，如果你经常只修改列表中的单个项目。
但是，对于删除和插入，获取正确的锁定会变得更加复杂。你必须获得该项目前后的锁，并且必须确保始终以相同的顺序获取它们（以防止死锁）。当然，如果根元素必须被修改（也可能是双链表或循环链表），也会考虑特殊情况。由更复杂的锁定逻辑导致的这种开销可能会导致您的实现再次变慢，特别是如果您经常需要从列表中插入和删除。 所以我只会考虑如果大多数访问是修改单个节点。
如果您正在寻找某个特定用例的峰值性能，那么最终归结为实现这两种性能，并且在典型场景下运行性能比较。
我不确定我是否完全理解。所以每个项目一个锁就意味着每当我对一个项目进行操作时，我都会单独获取锁并在完成时释放它。如何才能锁定一组特定的元素？从我所了解的情况来看，锁只能用于特定的代码段而不是元素。 – Akshya11235
您只需要在写入时锁定，并且说通常只有一次写入，因此请尝试读取/写入锁定。
您绝对需要至少一个信号量/锁来确保列表的完整性。
但是，大概是列表上的任何操作最多可以更改两个节点：正在插入/更改/删除的节点以及指向它的相邻节点。所以你可以在每个节点的基础上实现锁定，为一个给定的操作最多锁定两个节点。当不同的线程访问列表时，这将允许一定程度的并发，尽管您需要区分读锁和写锁以充分利用这种方法。
如果您不熟悉多线程，请接受这样一个概念，即过早优化是浪费时间。链接列表是非常直接的数据结构，您可以通过在所有读写操作中放置关键部分来使其成为线程安全的。这些将在执行读取/插入/删除操作期间将线程锁定到CPU中，并确保线程安全。它们也不会消耗互斥锁的开销，或更复杂的锁定机制。
如果您想在事实后进行优化，那么只能使用有效的分析工具来提供原始数据。链表操作永远不会成为应用程序减速的最大来源，并且它可能永远不值得您加入正在讨论的节点级锁定。
对整个列表使用一个锁将首先完全击败多线程的大多数原因。通过锁定整个列表，您可以确保一次只有一个线程可以使用该列表。
这样做肯定是安全的，因为您不会遇到死锁或竞争，但由于您序列化访问整个列表，因此它非常幼稚而且效率低下。
更好的方法是为列表中的每个项目锁定一个锁定，另一个锁定为列表本身。当追加到列表时，后者是需要的，这取决于列表是如何实现的（例如，如果它保持节点计数与节点本身分离）。
但是，根据多种因素，这可能也不尽如人意。例如，在某些平台上，在实例化互斥体时，互斥体的资源和时间可能会很昂贵。如果空间非常重要，另一种方法可能是在需要访问项目时使用固定大小的互斥锁池进行绘制。这些互斥体会拥有某种所有权标志，表明它们被分配给哪个节点，因此不会同时为该节点分配其他互斥体。
另一种技术是使用读/写锁，它允许对任何线程进行读取访问，但只能访问其中一个，这两者是互斥的。然而，在文献中已经提出，在许多情况下，使用读/写锁实际上比简单地使用普通互斥锁效率低。这将取决于您的实际使用模式以及锁的实施方式。
每个节点的锁，例如？ –
@JoeZ：是的，这是一个常见的实现，并且通常会导致* hand over hand *遍历。 –
感谢您的回复。目前我正在使用单个链接列表实现一个实现。我假设像'temp = temp-> next;'这样的操作也将被视为已读并且需要锁。 – Akshya11235