高效的多线程算法,用于处理没有死锁的对列表

Question

假设我们有整数从0到n-1(让我们说,我们有n图像,并使用该指数识别它们),并与对这些整数的向量.在这里我们如何创建这些对并不是很重要,但只是为了可视化问题,我们可以说对是那些具有共同区域的图像.

我们的任务是使用多个线程处理所有可用对.如果要求只是每个对都可以被一个线程占用,那么任务就很简单:我们可以使用互斥对象的每个元素.但在我的情况下,情况更加困难:如果某些线程处理一对(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而T2持有R2试图获取R1时,发生死锁.完全是你的情况.

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

在您的情况下,"相同的顺序"是一个简单的解决方案:首先锁定min(first, second)然后锁定另一个.因此,当您在尝试锁定"较小"时保留"更大"资源时,您将永远不会结束.

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