锁定一对相互引用的资源

Question

请考虑以下几点：

// There are guys:
class Guy {
    // Each guy can have a buddy:
    Guy* buddy; // When a guy has a buddy, he is his buddy's buddy, i.e:
                // assert(!buddy || buddy->buddy == this);

public:
    // When guys are birthed into the world they have no buddy:
    Guy()
        : buddy{}
    {}

    // But guys can befriend each other:
    friend void befriend(Guy& a, Guy& b) {
        // Except themselves:
        assert(&a != &b);

        // Their old buddies (if any), lose their buddies:
        if (a.buddy) { a.buddy->buddy = {}; }
        if (b.buddy) { b.buddy->buddy = {}; }

        a.buddy = &b;
        b.buddy = &a;
    }

    // When a guy moves around, he keeps track of his buddy
    // and lets his buddy keep track of him:
    friend void swap(Guy& a, Guy& b) {
        std::swap(a.buddy, b.buddy);
        if (a.buddy) { a.buddy->buddy = &a; }
        if (b.buddy) { b.buddy->buddy = &b; }
    }
    Guy(Guy&& guy)
        : Guy()
    {
        swap(*this, guy);
    }
    Guy& operator=(Guy guy) {
        swap(*this, guy);
        return *this;
    }

    // When a Guy dies, his buddy loses his buddy.
    ~Guy() {
        if (buddy) { buddy->buddy = {}; }
    }
};

到目前为止，一切都很好，但现在我希望在不同线程中使用伙伴时，这一切都能正常工作。没问题，我们把std::mutex放在Guy里吧

class Guy {
    std::mutex mutex;

    // same as above...
};

现在我只需要锁定两个人的互斥对象，然后再链接或断开他们的一对。

这就是我感到困惑的地方。下面是失败的尝试(以析构函数为例)：

1. 僵局： ~Guy() { std::unique_lock锁{mutex}；if (巴迪){ std::unique_lock buddyLock{巴迪->互斥}；巴迪->巴迪= {}；} 当两个伙伴在大约同一时间被销毁时，它们都有可能在试图锁定其伙伴的互斥对象之前锁定它们自己的互斥对象，从而导致死锁。
2. 种族状况： 好的，我们只需按一致的顺序锁定互斥对象，手动或使用std::lock： { std::unique_lock锁{mutex，std::defer_lock}；if (巴迪){ std::unique_lock buddyLock{巴迪->互斥，std::defer_lock}；std：：lock(锁，buddyLock)；巴迪->巴迪= {}；}} 不幸的是，为了访问巴迪的互斥对象，我们必须访问buddy，此时它不受任何锁的保护，并且可能正在从另一个线程(这是一个竞争条件)中被修改。
3. 不可伸缩的： 可以通过全局互斥来实现正确性： 静态std：：互斥互斥；~Guy() { std::unique_lock锁{mutex}；if (好友){巴迪->巴迪= {}；}} 但出于性能和可伸缩性的原因，这是不可取的。

那么，如果没有全局锁，这是可能的吗？多么?

Answer 1

使用std::lock本身并不是一种竞争条件，也不存在死锁的风险。

std::lock将使用无死锁算法来获得这两个锁。它们将是某种(未具体说明的)尝试撤退的方法。

另一种方法是确定任意的锁顺序，例如使用对象的物理地址。

您正确地排除了对象伙伴本身的可能性，因此不存在尝试两次lock()相同mutex的风险。

我说这本身并不是一种竞赛条件，因为该代码所做的是确保完整性，如果a有巴迪b，那么b对所有的a和b都有巴迪a。

事实是，在两个对象成为朋友之后的一分钟，它们可能被另一个线程解除为好友，这大概就是您打算或通过其他同步来解决的。

还请注意，当你是朋友，并可能解除新朋友的朋友，你需要一次锁定所有的对象。这是两个“做朋友”和他们现在的朋友(如果有的话)。因此，您需要锁定2,3或4个互斥锁。

不幸的是，std::lock没有接受数组，但是有一个版本在boost中这样做，或者您需要手动处理它。

为了澄清，我正在阅读可能的析构函数作为模型的例子。所有相关成员都需要在相同锁上同步(例如，befriend()、swap()和unfriend() (如果需要的话))。实际上，锁定2,3或4的问题适用于befriend()成员。

此外，析构函数可能是最糟糕的例子，因为正如注释中提到的，一个对象是可销毁的，但可能与另一个线程处于锁争中，这是不合逻辑的。一定要在更广泛的程序中存在一些同步，这样才不可能，此时析构函数中的锁是多余的。

事实上，确保Guy对象在销毁前没有伙伴的设计似乎是一个好主意，也是一个调试前条件，可以在析构函数中检查assert(buddy==nullptr)。遗憾的是，不能将其作为运行时异常，因为在析构函数中抛出异常会导致程序终止(std::terminate())。

事实上，真正的挑战(这可能取决于周围的程序)是如何解除朋友关系时的友谊。这似乎需要一个尝试-撤退循环：

1. 锁定a和b。
2. 找出他们是否有朋友。
3. 如果他们已经是朋友了-你就完了。
4. 如果他们有其他伙伴，打开a& b，锁定a和b以及他们的伙伴(如果有的话)。
5. 看看朋友们有没有变，如果他们再去的话。
6. 调整相关成员。

对于周围的项目来说，这是一个问题，它是否会带来实时锁定的风险，但是任何尝试撤退的方法都会遭受同样的风险。

不起作用的是std::lock() a&b，然后是std::lock()伙伴，因为这样做会导致死锁。

因此，要回答这个问题-是的，没有全局锁是可能的，但这取决于周围的程序。它可能存在于许多Guy对象中，争用很少，活性也很高。但是，可能会有少数对象被激烈竞争(可能是在大量的人口中)，从而导致问题。如果不了解更广泛的应用，就无法对此进行评估。

解决这一问题的一种方法是锁升级，这实际上是零碎地回到全局锁上。本质上，这意味着如果有太多的往返重试循环，一个全局信号量将被设置，命令所有线程进入全局锁模式一段时间。一段时间可能是一些动作或一段时间，或者直到全局锁的争用平息为止！

因此，最后的答案是“是的，这是绝对可能的，除非它不起作用，在这种情况下‘不’”。