c - 百万链表+多线程的加锁策略(C)

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 8 年前。

Improve this question

我有一个 C 程序，有 1600 万多个链表和 4 个工作线程。

两个线程不应该同时在同一个链表上工作，否则它们可能会同时修改它，这会很糟糕。

我最初的简单解决方案是这样的:

int linked_lists_locks[NUM_LINKED_LISTS];
for (i=0; i< NUM_LINKED_LISTs; i++)
   linked_lists_locks[i] = 0;

然后，在每个线程工作时执行的部分中:

while ( linked_lists_locks[some_list] == 1 ) {
   /* busy wait */
}
linked_lists_locks[some_list] = 1;  // mark it locked lock it
/* work with the list */
linked_lists_locks[some_list] = 0;

然而，在 4 个线程和约 250,000,000 次操作的情况下，我很快就遇到了两个线程同时执行相同“是否已锁定”的情况，并随之而来的问题。这里的聪明人会预见到这一点:-)

我研究过一些锁定算法，例如 Dekker 和 Peterson 的锁定算法，但它们似乎更多的是“锁定这部分代码”，而我正在寻找的是“锁定此变量”。我怀疑如果我锁定代码的“使用列表”部分，一切都会变慢，因为只有一个线程可以工作(尽管我还没有尝试过)。本质上，每个 worker 的工作仅限于做一些数学计算并填充这些列表。每个线程想要同时处理同一个列表的情况很少见，顺便说一句 - 在 250M 操作中只有几千次，但它们确实发生了。

是否有一种算法或方法可以对许多变量而不是代码段实现锁定？这是 C(如果重要的话，在 Linux 上)，因此来自 Java/C#/et al 的同步数组列表等不可用。

Answer 1

更多地了解应用程序的组织方式会很有用，但这里有一些关于如何解决该问题的想法。

1. “同步”对象的常见解决方案是分配 mutex到每个对象。在对一个对象进行操作之前，线程需要获取该对象的互斥锁；完成后，它会释放互斥体。这既简单又有效，但如果您确实有 1600 万个可锁定对象，那么这是很大的开销。更严重的是，如果两个任务确实尝试同时处理同一个对象，其中一个任务最终将处于休眠状态，直到另一个任务释放锁。如果任务可能正在做其他事情，那么机会就已经失去了。

2. 第一个问题(1600 万个互斥体的开销)的一个简单解决方案是使用一个小的互斥体 vector 和一个将每个对象映射到一个互斥体的哈希函数。如果您只有四个任务，并且使用了一个 vector ，例如 1024 个互斥体，那么您偶尔会遇到一个线程不必要地等待另一个线程，但这不会很常见。

3. 如果锁争用确实是一个问题，并且可以改变工作的顺序，那么一个合理的模型是工作队列。在这里，当一个线程想要做某事时，它会从工作队列中取出一个任务，尝试锁定该任务的对象(使用 trylock 而不是 lock)，如果可行的话，执行任务。如果锁失败，它只是将任务放回工作队列并获取另一个任务。为了避免工作队列锁争用，线程通常会获取少数任务而不是一个任务；然后每个线程管理自己的子队列。调整该解决方案中的各种参数需要至少了解一些任务的特征。 (此解决方案中存在一种竞争条件，但这并不重要；它只是意味着任务偶尔会被不必要地推迟。但它们最终应该总是被执行。)