多线程处理长链表

Question

这里有一个算法问题。系统中有10个线程，给定一个包含10K个元素的链表。如何进行线程同步（添加、删除等操作）以优化性能？在列表上使用互斥锁不可取，因为它会降低性能。

- Adam

---

大多数操作是在列表的头部/尾部，还是通常在分布在列表上的随机元素上进行的？列表是循环的吗？列表大小的上限是10K吗？ - jxh

不，该列表未排序，因此操作不能保证在头部或尾部进行。该列表不是循环的。10K仅是一个指示性数字，表示这是一个很长的列表。 - Adam

优化代码的方式在很大程度上取决于对列表执行的所有操作。 - Dialecticus

请描述列表的使用方式。它是如何、何时以及由谁创建、读取和修改的？这些操作的相对频率是什么（哪种操作更频繁发生）？ - Dialecticus

链表数据结构假设所有操作都遵循顺序规则。 - Parag Bafna

Answer 1

如果所有位置的访问频率相同，且您可以修改列表节点，则可以为每个节点添加一个互斥锁：

typedef struct node{ 
   char* data;
   struct listNode *next;
   pthread_mutex_t lock; 
} listNode ;

这也取决于节点数据的大小。如果非常小，由于互斥锁的存储、创建和删除，可能会造成开销。

如果存在开销或者无法修改节点，则可以将列表拆分为（例如）100个100元素的组，并为每个组使用一个互斥锁。

- Evans

---

这也是我的第一反应，但在遍历列表时，您必须锁定/解锁路径中的所有互斥锁，这似乎不太高效。 - Dialecticus

Answer 2

链表数据结构假定所有操作都遵循顺序规则。请查看并发链表。

无论您使用什么样的机器来实现它，接口和预期行为都暗示着顺序逻辑。

- Parag Bafna

Answer 3

我发现 Evans 的答案是正确的。但是我建议使用自旋锁而不是互斥锁。在低并发和锁持有时间短的情况下，自旋锁更高效。

typedef 
struct ListNode { 
   void * data;
   struct ListNode * next;
   pthread_spinlock_t lock;
}
ListNode;

- stemm

Answer 4

您可以使用Linux系统调用futex进行同步。

- akhil

Answer 5

这取决于您想在链接列表上执行的操作以及列表是否已排序。

1. 如果您担心 2 个线程更改某个节点的值，请为每个节点添加像此处提到的互斥锁。
2. 如果您关注列表操作（添加、删除）：如果您进行的是更多的读取而不是写入，则使用读写锁；如果每个线程都在列表的一部分上工作，则可以仅向相关线程提供删除访问权限。

- Mzf

Answer 6

适当的解决方案在很大程度上取决于您要同步的对象（在您的情况下是列表）的操作频率。容器的操作包括容器创建、容器修改、容器遍历和项目修改。例如，如果列表大多数被遍历和读取，则可能列表不是最适合该工作的容器。也许您真正需要某种映射（也称为字典），如果您有一个键值，则提供非常快速的读取访问。在这种情况下，根本没有遍历，整个映射容器的同步可能是最有效的，仅仅因为我们更改了容器的类型。

- Dialecticus

Answer 7

首先假设将元素添加/移除到列表中不是多线程的原因（而是确定/创建这些元素的逻辑是繁琐的过程）...如果列表插入/删除时间是瓶颈的话，也许你应该重新考虑你的数据结构。

接下来，假设每个线程不会相互交互（一个线程不会删除另一个线程插入的记录），并且每个线程有一定量的工作。让每个线程不要直接操作实际的链表，而是维护两个辅助列表。

具体操作如下：

1. 每个线程运行并创建两个辅助列表，用于删除和插入记录
2. 给定线程在完成时无序，我们可以将每个线程的‘补充新项’列表追加到现有列表的开头或末尾。
3. 对于被删除的项，我们合并每个线程的要删除的项的列表，然后遍历原始链表，遇到这些项时将其删除（使用散列表来存储要删除的项列表可以提高性能）。

只要开始时的两个假设成立，这种方法就非常有效。而且这意味着不需要互斥锁或锁定，您的主列表仅在所有线程都加入到主线程后由单个线程更新。

- Seph