7

I have a algorithm question here. There are 10 threads in the system and you are given a link list with 10 K elements in it. How do you do the thread synchronization (addition deletion etc.) so that it is optimized for performance? Using a mutex for the list is not advisable as it will slow down performance.

4

7 回答 7

2

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

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

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

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

于 2013-05-23T10:37:15.477 回答
1

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

无论您使用哪种机制来实现它，接口和预期行为都暗示着顺序逻辑。

于 2013-05-23T11:47:05.213 回答
0

首先假设向列表添加/删除元素不是多线程的原因（相反，确定/创建这些元素的逻辑是繁重的过程）..如果列表插入/删除时间是瓶颈，那么可能你应该重新考虑你的数据结构。

接下来，假设每个线程不会相互交互（一个线程不会删除由另一个线程插入的记录）并且每个线程都有有限的工作量。让每个线程不接触实际的链表，而是让每个线程维护两个补充列表。

它是这样工作的：

  1. 每个线程运行并创建两个补充记录列表以删除和插入

  2. 鉴于线程全部完成时线程未排序，我们可以将每个线程的“补充新项目”列表附加到现有列表的开头或结尾。

  3. 接下来对于已删除的项目，我们从每个线程中合并要删除的项目列表，然后遍历原始链表并在遇到项目时删除它们（这里可以通过使用hashtable要删除的项目列表来提高性能。

如果一开始的两个假设成立，这非常有效。这也意味着不需要互斥锁或锁，您的主列表仅在所有线程都重新加入主线程后由单个线程更新。

于 2013-05-23T12:03:03.667 回答
0

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

于 2013-05-23T10:32:11.550 回答
0

我发现埃文斯的答案是正确的。但我建议使用spinlocks而不是mutexes。自旋锁在低并发和短时间持有锁的情况下效率更高。

typedef 
struct ListNode { 
   void * data;
   struct ListNode * next;
   pthread_spinlock_t lock;
}
ListNode;
于 2013-05-23T11:07:11.560 回答
0

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

  1. 如果您担心 2 个线程会更改某个节点的值，请为每个 nore 添加互斥锁，就像这里提到的一样。
  2. 如果您担心列表操作（添加，删除）：这取决于您是否做更多的读取而不是写入 - 使用读写器锁，如果每个线程都在列表的一部分上工作，那么您只能对相关线程授予删除访问权限
于 2013-05-23T10:47:09.583 回答
0

正确的解决方案很大程度上取决于您要同步的对象（您的情况下的列表）的操作频率。对容器的操作有容器创建、容器修改、容器遍历和项修改。例如，如果列表大部分被遍历和读取，则可能是该列表是该作业的错误容器。也许你真的需要某种映射（也称为字典），如果你有一个键值，它可以提供非常快速的读取访问。在那种情况下根本没有遍历，可能整个地图容器的同步变得最有效，仅仅是因为我们改变了容器的类型。

于 2013-05-23T11:39:56.683 回答