具有长链表的多线程

Question

我这里有一个算法问题。系统中有10个线程，您将看到一个包含10K元素的链接表。如何进行线程同步(添加、删除等)所以它是针对性能进行优化的？对列表使用互斥是不可取的，因为它会降低性能。

Answer 1

链表数据结构假定所有操作都遵循顺序规则。看一看concurrent linked list

无论您使用哪种类型的机器来实现它，接口和预期行为都隐含着顺序逻辑。

Answer 2

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

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

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

如果这是一个开销或者不能修改节点，你可以将列表分成100组，每组100个元素，并为每组使用一个互斥锁

Answer 3

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