36

(注意:其中大部分内容对于使用 std::lock (c++11)的大规模 CPU 负载的评论是多余的,但我认为这个主题值得拥有自己的问题和答案。)

我最近遇到了一些看起来像这样的示例 C++11 代码:

std::unique_lock<std::mutex> lock1(from_acct.mutex, std::defer_lock);
std::unique_lock<std::mutex> lock2(to_acct.mutex, std::defer_lock);
std::lock(lock1, lock2); // avoid deadlock
transfer_money(from_acct, to_acct, amount);

哇,我想,std::lock听起来很有趣。我想知道标准说它做了什么?

C++11 第 30.4.3 节 [thread.lock.algorithm],第 (4) 和 (5) 段:

模板无效锁(L1&, L2&, L3&...);

4要求:每个模板参数类型应满足可锁定的要求,[注:unique_lock类模板在适当实例化时满足这些要求。——尾注]

5效果:所有参数都通过对每个参数lock()的 一系列调用锁定。调用序列不应导致死锁,但未指定。[注:必须使用try-and-back-off等死锁避免算法,但未指定具体算法以避免过度约束实现。— 尾注] 如果调用or抛出异常,则应调用任何已被调用or锁定的参数。try_lock()unlock()lock()try_lock()unlock()lock()try_lock()

考虑以下示例。称之为“示例 1”:

Thread 1                    Thread 2
std::lock(lock1, lock2);    std::lock(lock2, lock1);

这种僵局可以吗?

对标准的简单阅读说“不”。伟大的!也许编译器可以为我订购我的锁,这会很整洁。

现在尝试示例 2:

Thread 1                                  Thread 2
std::lock(lock1, lock2, lock3, lock4);    std::lock(lock3, lock4);
                                          std::lock(lock1, lock2);

这种僵局可以吗?

再一次,标准的简单阅读说“不”。哦哦。做到这一点的唯一方法是使用某种退避和重试循环。更多关于下面的内容。

最后,示例 3:

Thread 1                          Thread 2
std::lock(lock1,lock2);           std::lock(lock3,lock4);
std::lock(lock3,lock4);           std::lock(lock1,lock2);

这种僵局可以吗?

再一次,对标准的简单解读说“不”。(如果这些调用之一中的“调用序列lock()”不是“导致死锁”,那么究竟是什么?)但是,我很确定这是无法实现的,所以我想这不是他们的意思。

这似乎是我在 C++ 标准中见过的最糟糕的事情之一。我猜它一开始是一个有趣的想法:让编译器分配一个锁顺序。但是一旦委员会咀嚼它,结果要么无法实现,要么需要重试循环。是的,这是个坏主意。

您可以争辩说“退出并重试”有时很有用。这是真的,但只有当你不知道你试图抢在前面的锁时。例如,如果第二个锁的身份取决于第一个锁保护的数据(比如因为您正在遍历某些层次结构),那么您可能需要进行一些抓取-释放-抓取旋转。但在那种情况下,你不能使用这个小工具,因为你不知道前面的所有锁。另一方面,如果您确实知道要预先使用哪些锁,那么您(几乎)总是只想简单地强加一个排序,而不是循环。

另外,请注意,如果实现只是按顺序获取锁、后退和重试,则示例 1 可以活锁。

简而言之,这个小工具在我看来充其量是没用的。只是一个坏主意。

好的,问题。(1) 我的任何主张或解释是否错误?(2) 如果不是,他们到底在想什么?(3)我们是否都同意“最佳实践”是std::lock完全避免?

[更新]

一些答案说我误解了标准,然后继续以与我相同的方式解释它,然后将规范与实现混淆。

所以,要明确一点:

在我对标准的阅读中,示例 1 和示例 2 不能死锁。示例 3 可以,但只是因为在这种情况下避免死锁是无法实现的。

我的问题的全部要点是,避免示例 2 的死锁需要一个回退和重试循环,而这样的循环是非常糟糕的做法。(是的,对这个微不足道的示例进行某种静态分析可以避免这种情况,但在一般情况下并非如此。)还要注意 GCC 将此事物实现为繁忙循环。

[更新 2]

我认为这里的很多脱节是哲学上的基本差异。

编写软件有两种方法,尤其是多线程软件。

在一种方法中,您将一堆东西放在一起并运行它以查看它的工作情况。你永远不会相信你的代码有问题,除非有人能在一个真实的系统上证明这个问题,现在,今天。

在另一种方法中,您编写的代码可以被严格分析以证明它没有数据竞争,它的所有循环都以概率 1 终止,等等。您严格在语言规​​范保证的机器模型内执行此分析,而不是在任何特定实现上。

后一种方法的拥护者对特定 CPU、编译器、编译器次要版本、操作系统、运行时等的任何演示都没有留下深刻印象。这样的演示几乎没有兴趣,也完全无关紧要。如果您的算法存在数据竞争,那么无论您运行它时发生什么,它都会被破坏。如果你的算法有一个活锁,它就会被破坏,不管你运行它时会发生什么。等等。

在我的世界中,第二种方法称为“工程”。我不确定第一种方法叫什么。

据我所知,该std::lock界面对工程学毫无用处。我很想被证明是错误的。

4

4 回答 4

45

我认为您误解了避免死锁的范围。这是可以理解的,因为文本似乎lock在两种不同的上下文中提到,“多锁”std::lock和由该“多锁”执行的单个锁(但是可锁定的实现它)。状态文本std::lock

所有参数都通过对每个参数的 lock()、try_lock() 或 unlock() 的一系列调用来锁定。调用顺序不应导致死锁

如果您调用std::lock传递十个不同的可锁定对象,则标准保证该调用不会出现死锁。如果您将可锁定对象锁定在std::lock. 这意味着线程 1 锁定 A 然后 B 可以与线程 2 锁定 B 然后 A 发生死锁。在您原来的第三个示例中就是这种情况,它具有(伪代码):

Thread 1     Thread 2
lock A       lock B
lock B       lock A

因为那不可能std::lock(它只锁定了一个资源),所以它一定是unique_lock.

根据您的第一个示例,如果两个线程都尝试在一次调用中锁定 A/B 和 B/A,则会发生死锁避免。您的第二个示例也不会死锁,因为如果已经拥有第一个锁的线程 2 需要第二个锁,线程 1 将退出。您更新的第三个示例:std::lock

Thread 1                  Thread 2
std::lock(lock1,lock2);   std::lock(lock3,lock4);
std::lock(lock3,lock4);   std::lock(lock1,lock2);

仍然有死锁的可能性,因为锁的原子性std::lock. 例如,如果线程 1 成功锁定lock1and lock2,那么线程 2 成功锁定lock3and lock4,当两个线程都试图锁定另一个持有的资源时,就会发生死锁。

因此,在回答您的具体问题时:

1/ 是的,我认为您误解了标准的含义。它所谈论的顺序显然是对传递给单个可锁定对象的锁定顺序 std::lock

2/ 至于他们在想什么,有时很难说 :-) 但我认为他们想给我们能力,否则我们必须自己写。是的,回退并重试可能不是一个理想的策略,但是,如果您需要避免死锁的功能,您可能需要付出代价。更好的实现是提供它,而不是开发人员一遍又一遍地编写它。

3/ 不,没有必要避免它。我认为我从来没有发现自己处于无法进行简单的手动订购锁的情况,但我不排除这种可能性。如果您确实发现自己处于这种情况,这可以提供帮助(因此您不必编写自己的避免死锁的东西)。


关于回退和重试是一个有问题的策略的评论,是的,这是正确的。但是您可能会忽略这一点,例如,如果您无法预先强制执行锁的顺序,则它可能是必要的。

它不必像你想象的那么糟糕因为锁定可以按任何顺序通过 完成std::lock,所以没有什么可以阻止实现在每次退避后重新排序以将“失败”锁定到列表的前面。这意味着那些被锁定的人往往会聚集在前面,这样他们std::lock就不太可能不必要地索取资源。

考虑std::lock (a, b, c, d, e, f)其中f唯一已锁定的可锁定调用。在第一次锁定尝试中,该调用将锁定a通过e然后“失败” on f

在退避(a通过解锁e)之后,要锁定的列表将更改为,f, a, b, c, d, e以便后续迭代不太可能不必要地锁定。这不是万无一失的,因为其他资源可能会在迭代之间被锁定或解锁,但它往往会成功。

事实上,它甚至可以通过检查所有可锁定对象的状态来对列表进行排序,以便所有当前锁定的对象都排在最前面。这将在流程的早期开始“趋向成功”操作。

这只是一种策略,可能还有其他策略,甚至更好。这就是为什么该标准没有规定如何完成的原因,可能会有一些天才想出更好的方法。

于 2013-08-29T21:16:03.633 回答
23

std::lock(x, y, ...)如果您将每个单独的调用视为原子调用,也许会有所帮助。它将阻塞,直到它可以锁定它的所有参数。如果您不知道先验锁定所需的所有互斥锁,请不要使用此功能。如果您知道,那么您可以安全地使用此功能,而无需订购锁。

但是,如果您喜欢这样做,请务必订购您的锁。

Thread 1                    Thread 2
std::lock(lock1, lock2);    std::lock(lock2, lock1);

以上不会死锁。其中一个线程将获得两个锁,而另一个线程将阻塞,直到第一个线程释放锁。

Thread 1                                  Thread 2
std::lock(lock1, lock2, lock3, lock4);    std::lock(lock3, lock4);
                                          std::lock(lock1, lock2);

以上不会死锁。虽然这很棘手。如果线程 2 在线程 1 之前获得了 lock3 和 lock4,那么线程 1 将阻塞,直到线程 2 释放所有 4 个锁。如果线程 1 先获得了四个锁,那么线程 2 将在锁定 lock3 和 lock4 处阻塞,直到线程 1 释放所有 4 个锁。

Thread 1                          Thread 2
std::lock(lock1,lock2);           std::lock(lock3,lock4);
std::lock(lock3,lock4);           std::lock(lock1,lock2);

是的,上面可以死锁。您可以将上述内容视为完全等同于:

Thread 1                          Thread 2
lock12.lock();                    lock34.lock();
lock34.lock();                    lock12.lock();

更新

我认为一个误解是死锁和活锁都是正确性问题。

在实际实践中,死锁是一个正确性问题,因为它会导致进程冻结。并且活锁是一个性能问题,因为它会导致进程变慢,但它仍然可以正确完成其任务。原因是活锁不会(在实践中)无限期地维持自己。

<disclaimer> 可以创建一些形式的活锁,它们是永久性的,因此等同于死锁。此答案未解决此类代码,并且此类代码与此问题无关。 </disclaimer>

这个答案中显示的产量是一个显着的性能优化,它显着减少了活锁,从而显着提高了std::lock(x, y, ...).

更新 2

经过长时间的拖延,我写了一篇关于这个主题的论文的初稿。该论文比较了完成这项工作的 4 种不同方法。它包含您可以复制并粘贴到您自己的代码中并自行测试的软件:

http://howardhinnant.github.io/dining_philosophers.html

于 2013-08-29T21:55:29.550 回答
4

您对标准语的混淆似乎是由于此声明

5效果:所有参数都通过对每个参数lock()的 一系列调用锁定。try_lock()unlock()

这并不意味着std::lock它将使用原始调用的每个参数递归调用自身。

满足 Lockable 概念的对象 §30.2.5.4 [ thread.req.lockable.req])必须实现所有 3 个成员函数。std::lock将以未指定的顺序在每个参数上调用这些成员函数,以尝试获取所有对象的锁,同时执行定义的实现以避免死锁。

您的示例 3 可能会出现死锁,因为您没有对std::lock要获取锁定的所有对象发出单个调用。

示例 2不会导致死锁,霍华德的回答解释了原因。

于 2013-08-29T21:29:39.443 回答
1

C++11 是否采用了 Boost 的这个功能?

如果是这样,Boost 的描述是有启发性的(强调我的):

效果:以未指定和不确定的顺序锁定作为参数提供的可锁定对象,以避免死锁。从具有相同互斥体(或其他可锁定对象)的多个线程以不同的顺序同时调用此函数是安全的,没有死锁的风险。如果对提供的可锁定对象的任何 lock() 或 try_lock() 操作引发异常,则该函数获取的任何锁都将在函数退出之前释放。

于 2015-04-30T12:54:55.167 回答