c - 如何在多线程进程中锁定矩阵单元

Question

假设我有“n”个线程。所有这些线程都在访问同一个矩阵，并且它们正在执行一些操作。

当一个线程完成它的工作时(该工作将转到二维数组中的相邻位置)，我要么锁定整个矩阵，完成它的工作，然后解锁它并让其他线程也完成它们的工作.或者，我可以锁定它们的相邻位置，在这种情况下，包括对角线在内的 8 个位置，或者我可以阻止线程想要移动的目标单元格。

我已经通过放置 pthread_t_lock() 实现了锁定整个矩阵并完成工作，然后解锁它。在本例中，我只使用了一个互斥体。它有效，但我不认为我在这种方法中受益于整个多线程支持。

在第二种方法中，我不知道如何实现8个相邻位置锁定或锁定线程要走的目标位置。我是否应该使用多个互斥量，比如整个网格的互斥量数组？即，如果我的数组是 10*10，我需要使用 100 个互斥锁并锁定其中的 8 个，并在线程想要完成其工作时为每个线程释放其中的 8 个。或者我应该使用另一种方法吗？另外，我不确定锁定 8 个互斥量是否是原子的。也许我可以使用另一个互斥体来锁定这 8 个互斥体，并在锁定 8 个互斥体时释放此锁。但同样，我不确定这会导致僵局。

编程语言是C。

提前致谢。

Answer 1

如果您想要为二维数组中的每个条目锁定，您有 2 个选择:

• 有第二个包含锁的二维数组，因此 myLocks[x][y]是条目 myArray[x][y] 的锁.

• 创建一个包含锁和值的结构，并创建这些结构的二维数组，这样 myArray[x][y].lock是 myArray[x][y].value 值的锁.

为避免死锁，您需要按特定顺序获取锁并按相反顺序释放锁。最合乎逻辑的顺序(至少对于使用英语的人来说)是“从左到右，从上到下”，但任何顺序都可以。

问题是你很可能会花很多时间获取和释放锁(相比之下做实际工作的时间太少)以至于只使用一个线程可能会更快(并避免获取和释放锁的成本)。

您希望在更多线程的好处和获取/释放锁的成本之间找到更好的折衷方案；比如只为数组的每一行加一个锁(所以你需要使用 3 个锁而不是 8 个或 9 个)，或者只为每对行加一个锁(所以你需要使用 2 个锁而不是 8 个或9).

请注意，锁的设计可以(并且应该)取决于您执行操作的顺序，而您执行操作的顺序可以(并且应该)取决于锁的设计。例如;如果你确实对数组的每一行都有一个锁，那么每个线程执行数组的整行可能是有意义的(例如，这样一个线程将获得 3 个锁，然后执行整行，然后释放 3 个锁).

另请注意，无需任何锁也可以做到这一点。例如，如果数组是 1000 * 1000 个条目并且您有 10 个线程，那么您可以将数组拆分为十个 1000 * 100 子数组(每个线程一个子数组)并让每个线程执行其子数组的上半部分-大批;然后让所有线程等待，直到所有其他线程完成其子数组的上半部分，然后再继续；让每个线程执行其子数组的下半部分。