选择性地强制执行同步以促进最大并发性

Question

以下是我尝试用Java:做的事情

while(writeSetsIntersect()) {
    wait();
}    
doStuff    
notifyAll();

这就是我的难点：如果两个线程写入不同的变量，即它们具有不相交的写入集，那么doStuff可以同时执行。如果写入集相交，则线程需要交替。因此，我不能简单地将doStuff放在同步块中，因为它并不总是（也可能永远不会）是必要的。

我可以锁定写集中的项目，但如果具有交叉写集的两个线程在同一个锁上等待，则可能会发生死锁。例如：

Lock[] locks = new Lock[allAvailableVariables.length];
public void getLocks() {
    for(i = 0; i < allAvailableVariables.length; i++)
        if(i is in writeSet)
            locks[i].lock();
}

避免这种情况的最简单方法（就我所能想到的而言）是同步获取写集中的锁。但是，如果具有交叉写入集的两个线程竞争进入同步块，则具有与其他两个不相交的写入集的线程将不得不等待，直到它们离开同步块。

我想我可以有一个旋转锁，但如果可能的话，我想避免这种情况，因为评估写集是否相交可能会很昂贵。

这有意义吗？

Answer 1

看起来您想要使用锁排序。

将锁按某种自然顺序排序。然后依次锁定每个。

假设您使用a < b锁定了a和b。如果两个线程都想锁定a和b，它们将首先锁定a。因此，不可能出现这样的情况：一个线程锁定了b并在a上被阻止，而另一个线程已锁定a在b上被阻止。