我有一个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个线程和大约250000000次操作的情况下，我很快就遇到了两个线程同时执行相同的"它被锁定了吗"的情况，问题随之而来。这里的聪明人会看到这一点：-）
我研究过一些锁定算法，比如Dekker和Peterson的，但它们似乎更像是"锁定这段代码"，而我想要的是"锁定这个变量"。我怀疑，如果我锁定了代码的"使用列表"部分，一切都会变慢，因为只有一个线程可以工作（尽管我还没有尝试过）。从本质上讲，每个工人的工作都局限于做一些数学运算和填充这些列表。顺便说一句，每个线程都想同时处理同一个列表的情况很少见——在2.5亿次操作中只有几千次，但它们确实会发生。
有没有一种算法或方法可以在许多变量上实现锁，而不是在代码段上实现锁？这是C（在Linux上，如果这很重要的话），所以Java/C#/等中的同步数组列表等不可用。
了解更多关于应用程序的组织方式会很有用，但这里有一些关于如何处理这个问题的想法。
-
"同步"对象的常见解决方案是为每个对象分配一个互斥对象。在处理对象之前，线程需要获取对象的互斥；完成后，它会释放互斥对象。这既简单又有效，但如果你真的有1600万个可锁定的对象，那就需要大量的开销。更严重的是，如果两个任务真的试图同时处理同一个对象，其中一个最终会休眠，直到另一个释放锁。如果任务可能在做其他事情，那么机会就失去了。
-
第一个问题（1600万个互斥量的开销）的一个简单解决方案是使用一个小的互斥量向量和一个散列函数，该函数将每个对象映射到一个互斥量。如果你只有四个任务，并且你使用了一个向量，比如1024个互斥，你偶尔会发现一个线程在不必要地等待另一个线程，但这并不常见。
-
如果锁争用确实是一个问题，并且可以改变工作的顺序，那么一个合理的模型就是工作队列。在这里，当线程想要做某事时，它会将任务从工作队列中删除，尝试锁定任务的对象（使用
trylock而不是lock），如果有效，则执行任务。如果锁定失败，它只会将任务放回工作队列并获取另一个任务。为了避免工作队列锁争用，线程通常只获取少量任务，而不是一个任务；然后每个线程管理自己的子队列。调整此解决方案中的各种参数需要至少了解一些任务的特性。（这个解决方案中有一种竞争条件，但这并不重要；这只是意味着偶尔任务会被不必要地推迟。但它们最终应该得到执行。）
您应该使用原子测试和设置操作。不幸的是，如果编译器没有内置的程序集例程，那么您可能需要使用程序集例程。请参阅本文：
http://en.wikipedia.org/wiki/Test-and-set
如果你被迫使用这么多列表，而你的线程很少，你可能不想锁定列表，而是允许工作线程一次声明一个列表。在这种情况下，您需要一个结构来存储当前持有的列表的编号，并且该列表不能与其他编号混叠。
由于你似乎没有使用任何库，我将添加一些伪代码来澄清我的想法：
/*
* list_number, the number of the list you want to lock
* my_id, the id of the thread trying to lock this list
* mutex, the mutex used to control locking the lists
* active_lists, array containing the lists currently held by the threads
* num_threads, size of the array and also number of threads
*/
void lock_list(int list_number, int my_id, some_mutex *mutex,
atomic_int *active_lists, size_t num_threads) {
int ok = 0;
int i;
while (true){ //busy wait to claim the lock
//first check if anyone seems to hold the list we want.
//Do this in a non-locking way to avoid lock contention
while (!ok){
ok = 1;
for (i = 0; i < num_threads; ++i){
if (active_lists[i].load() == list_number && i != my_id){
ok = 0;
/*
* we have to restart - potential to optimize
* at this point, you could delay the work on this list
* to do some other work
*/
break;
}
}
}
while(try_to_lock(mutex));
//rerun the check to see if anyone has taken the list in the meantime
// ok == 1 at this point
for (i = 0; i < num_threads; ++i){
if (active_lists[i].load() == list_number && i != my_id){
ok = 0;
break;
}
}
//this must not be set from anywhere else!
if (ok) active_lists[my_id].store(list_number);
unlock(mutex);
//if we noticed someone claimed the list, go back to the beginning.
if (ok) break;
}
}
伪类型有一些限制。some_mutex显然必须是一个互斥对象。我在这里所说的atomic_int必须以某种方式支持从主存中获取其最新值，以防止您看到缓存的旧值。存储也是如此：在写入之前，不能在本地缓存核心。使用正则int和lfence、sfence和/或mfence也可以。
这里显然有一些权衡，其中最主要的可能是内存与速度。这个例子将在用于存储锁定的列表的单个互斥体上创建争用，因此它在大量线程中的扩展性很差，但在大量列表中的扩展能力很好。如果列表很少被声明，即使在大量线程中也能很好地工作。优点是存储需求主要取决于线程的数量。您必须选择一种存储类型，它可以容纳与列表最大数量相等的数字。
我不确定你的具体情况是什么，但最近免锁定列表也获得了一些势头。随着C11和C++11中对无锁代码的高级支持的引入，出现了一些工作示例（如未显示的示例）。Herb Sutter做了一个关于如何在C++11中实现这一点的演讲。这是C++，但他讨论了编写无锁单链表的相关要点，这对普通的旧C也是如此。你也可以尝试找到一个现有的实现，但你应该仔细检查它，因为这是一种前沿的东西。然而，使用免锁定列表将完全消除锁定的需要。