这里有一个算法问题。系统中有10个线程,给定一个包含10K个元素的链表。如何进行线程同步(添加、删除等操作)以优化性能?在列表上使用互斥锁不可取,因为它会降低性能。
这里有一个算法问题。系统中有10个线程,给定一个包含10K个元素的链表。如何进行线程同步(添加、删除等操作)以优化性能?在列表上使用互斥锁不可取,因为它会降低性能。
如果所有位置的访问频率相同,且您可以修改列表节点,则可以为每个节点添加一个互斥锁:
typedef struct node{
char* data;
struct listNode *next;
pthread_mutex_t lock;
} listNode ;
这也取决于节点数据的大小。如果非常小,由于互斥锁的存储、创建和删除,可能会造成开销。
如果存在开销或者无法修改节点,则可以将列表拆分为(例如)100个100元素的组,并为每个组使用一个互斥锁。
我发现 Evans 的答案是正确的。但是我建议使用自旋锁而不是互斥锁。在低并发和锁持有时间短的情况下,自旋锁更高效。
typedef
struct ListNode {
void * data;
struct ListNode * next;
pthread_spinlock_t lock;
}
ListNode;
您可以使用Linux系统调用futex进行同步。
这取决于您想在链接列表上执行的操作以及列表是否已排序。
适当的解决方案在很大程度上取决于您要同步的对象(在您的情况下是列表)的操作频率。容器的操作包括容器创建、容器修改、容器遍历和项目修改。例如,如果列表大多数被遍历和读取,则可能列表不是最适合该工作的容器。也许您真正需要某种映射(也称为字典),如果您有一个键值,则提供非常快速的读取访问。在这种情况下,根本没有遍历,整个映射容器的同步可能是最有效的,仅仅因为我们更改了容器的类型。
只要开始时的两个假设成立,这种方法就非常有效。而且这意味着不需要互斥锁或锁定,您的主列表仅在所有线程都加入到主线程后由单个线程更新。