std :: lock()是不明确的,不可实现的还是无用的？

Question

(注意:使用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_lock()或unlock()在每个参数.调用序列不应导致死锁,否则不会被指定.[注意:必须使用诸如try-and-back-off之类的死锁避免算法,但未指定特定算法以避免过度约束实现.- 结束注释]如果调用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界面对工程来说毫无用处.我希望被证明是错的.

Answer 1

我认为你误解了避免死锁的范围.这是可以理解的,因为文本似乎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成功锁定lock1和lock2,那么线程2个成功锁定lock3和lock4,僵局将接踵而至作为两个线程试图锁定由其他持有的资源.

那么,在回答您的具体问题时:

1 /是的,我认为你误解了标准的含义.它谈论的顺序是明确传递到个人lockables进行锁的顺序单 std::lock.

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

3 /不,没有必要避免它.我不认为我曾经发现自己处于无法进行简单的手动订购锁定的情况,但我并不打算这种可能性.如果您确实发现自己处于这种情况,这可以提供帮助(因此您不必编写自己的死锁避免代码).

关于后退和重试是一个有问题的策略的评论,是的,这是正确的.但是,你可能会丢失,这可能是点必要的,如果,例如,你不能强制执行前手锁的顺序.

它不具备对像你想象的那样糟糕.因为锁可以按任何顺序完成std::lock,所以没有什么能阻止实现在每次退避后重新排序,以使"失败"可锁定到列表的前面.这意味着被锁定的人往往会聚集在前方,这样std::lock就不太可能不必要地申请资源.

考虑通话std::lock (a, b, c, d, e, f)中f是已锁定,唯一的锁定.在第一个锁定尝试,该呼叫将锁定a通过e则"失败"的f.

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

事实上,它甚至可以通过检查所有可锁定状态来最初排序列表,以便所有当前锁定的人都在前面.这将在此过程的早期开始"趋向成功"运作.

这只是一种策略,可能还有其他策略,甚至更好.这就是为什么标准没有强制要求如何完成,有可能会有一些天才出现更好的方式.

Answer 2

如果你认为每个人都称之为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在Thread1执行之前获得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