multithreading - 高效的多线程算法来处理一个没有死锁的对列表

Question

假设我们有从 0 到 n-1 的整数(假设我们有 n 图像并使用此索引识别它们) 和一个包含这些整数对的向量。我们如何创建这些对在这里并不是很重要，但只是为了形象化问题，我们可以说对是那些具有公共(public)区域的图像。

我们的任务是使用多线程处理所有可用的对。如果要求只是每一对可以被一个线程占用，那么任务就很简单:我们可以为带有对的向量的每个元素使用互斥锁。但在我的例子中，情况更加困难:如果某个线程处理一对 (m,n)，另一个线程不能使用任何由 m 或 组成的对>n.

为每个图像使用互斥锁的简单解决方案是有缺陷的。例如，假设我们有图像 0,1,2,3 和对 (0,1), (1,2) , (2,3), (3,0)。如果算法对一对使用互斥量，然后对每个图像使用两个互斥量，则可能会出现死锁:th_0 将处理对 (0,1)，th_1 - 对 (1,2)、th_2 - 对 (2,3) 和 th_3 - 对 (3,0)。然后每个线程将为单个图像使用互斥体。

th_0: lock 0, lock 1
th_1: lock 1, lock 2
th_2: lock 2, lock 3
th_3: lock 3, lock 0

th_0 将锁定图像 0，th_1 将锁定图像 1，但是 th_0 将停止，因为它将尝试锁定已锁定的图像 1。所有其他线程也会发生同样的情况。

似乎为了达到目的，每个线程都必须成对地锁定整个向量以避免死锁，这似乎不是一个很好的解决方案。这是正确的吗？这个问题有更好的解决方案吗？我想到的唯一解决方案是对图像使用互斥锁以及线程优先级信息。例如，如果第二张图像被锁定，线程将检查锁定线程的线程 ID 是否更高，然后它应该释放对第一张图像的锁定并继续。它会起作用还是我会再次面临僵局？

Answer 1

当持有资源 R1 的线程 T1 试图获取 R2 而持有 R2 的线程 T2 试图获取 R1 时，就会发生死锁。正是您的情况。

打破僵局的常用方法是始终以相同的顺序获取资源(如果可能的话)。

在您的情况下，“相同顺序”是一个简单的解决方案:首先锁定 min(first, second) 然后锁定另一个。因此，您永远不会陷入持有“较大”资源同时试图锁定“较小”资源的情况。

虽然这个解决方案很简单，但它可能不是最优的，当您的图像处理需要很长时间并且线程经常相互等待时，这取决于争用。