C++ 的前向进度保证¶
标题：Forward Progress Guarantees in C++
日期：2023/07/20
作者：Olivier Giroux
链接：https://www.youtube.com/watch?v=g9Rgu6YEuqY
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
备注：还没看，可是像 P2300 几行字就能说完的事情，他为啥能聊一个半小时？
好的， crew，准备好了吗？摄像机开拍。好的。好的。
欢迎大家来听这场关于前向进度保证（forward progress guarantees）的讲座。我们将讨论 C++ 中的前向进度保证，但实际上不仅仅是 C++。原因是，很多语言实际上（de facto）都引入了 C++ 的抽象机模型。没有多少语言会去自己定义什么是内存，很多甚至连自己的内存模型都懒得定义，同样，它们也不会定义自己的前向进度保证。很多语言的情况是，有人在 LLVM 上构建了一个前端，然后在不知不觉中，就把 C++ 的抽象机带到了他们的程序底层。
好的。所以这里的规则通常适用于各种语言，尽管 C++ 对其自身的一些设施有非常具体的措辞，我会在激活这些部分时告诉大家。
我记得很清楚，我对前向进度保证的兴趣是从什么时候开始的。当时我正在做 CUDA 的工作，我们刚刚发布了支持原子操作（Atomics）的 CUDA 1.1。我们最初的纯并行编程模型是没有任何原子操作的，没有原子操作，你就不会惹上麻烦。然后在 1.1 版本，我们做了一件非常有意义的事情：我们提供了原子操作，意图是让人们用它们来做归约（reductions），但人们立刻开始用它们来编写同步（synchronization）代码。而当时的编程系统和硬件都无法处理这种情况。
所以，如果你当时去 Stack Overflow 搜索 CUDA、锁（lock）或互斥体（mutex），你会看到满屏的搜索结果。每一个结果都是有人在说：“嘿，我用 atomicExchange 或者 atomicCAS 写了这段代码，我不明白为什么我的 GPU 死机了，然后 Windows 重启了 GPU。” 好的。那么我是谁呢？
我从事 GPU 架构师的工作已经相当长一段时间了，从 2002 年开始。你们可能都用过我参与设计的 GPU。我目前在苹果公司的平台架构部门工作，负责苹果 GPU 的编程模型。我也是 SG1 并发与并行研究组的主席。
在我们深入探讨之前……我们将毫无例外地审视 C++ 中进度的每一个方面。我们将探访每一个角落，并且我会告诉你们，目前缺陷都藏在哪里。如果有人想写论文，欢迎。好的。
但在此之前，我会给你们快速介绍一下进度理论。我的意思是，这部分内容在一篇由 Herlihy 和 Shavit 撰写的开创性论文《On the Nature of Progress》中有详细阐述。但我只会给你们一些我们需要的零碎知识，然后我会用 C++ 的例子来逐步构建说明。
好的。我们首先需要了解的术语是 “调度器”（scheduler） 这个概念。调度器是你线程运行时所依赖的抽象机的一部分。调度器对线程做出保证。术语“前向进度保证”指的就是调度器做出的那些保证。这就是我们正在讨论的内容。调度器会规定一些条件，在这些条件下，线程最终会执行其操作。调度器可以做出不止一种声明。事实上，在 C++ 中，我们有三种不同的调度器，它们的保证截然不同，这对你能编写什么样的代码有重大影响。好的。这是第一步：有一个调度器，它会做出一系列保证的声明。
“活锁”（livelock）这个术语有一个非常正式的定义。它不仅仅是“哦，我的程序挂起了，是活锁还是死锁”。活锁的正式定义是：你编写的程序的假设，超出了代码（即调度器）所做的保证。我在上面写了一个程序，其中一个线程设置一个标志，另一个线程则轮询（poll）这个标志。也就是说，它反复加载该标志。这超出了调度器的保证，因为调度器说“至少一个线程（at least one of the threads）”。它没说“所有线程（all threads）”。所以它可能会一遍又一遍地选择线程二。线程二加载标志，发现值不对。然后调度器再次选择线程二，它加载标志，值还是不对。调度器永远不选择线程一。因此，在像底部这么弱的保证下，我无法编写像我上面描述的那种代码。我得到了一个活锁。
好的。“死锁”（deadlock）则是指代码超出了“最大保证”（maximal guarantee）。确实存在所谓的最大保证。一个调度器承诺所有线程在任何时候最终都会执行它们的下一步操作。很多人喜欢认为这是唯一有效的保证。但这是最大保证。如果我写的代码超出了最大保证，那么我就有了一个死锁。
所以，举个例子，这里我有一个死锁。我的两个线程都在轮询，在看到一个标志后，它们会设置另一个标志，并且它们在哪个标志上进行操作是交叉的。这个程序永远无法完成，因为线程二永远不会设置标志 Y，所以线程一永远不会设置标志 X，因此线程二也永远无法继续。对吧？好的。这就是一个死锁。
（观众提问）“这怎么就超出最大保证了呢？” （演讲者回答）“一个提供最大保证的调度器并不会产生死锁。一个提供最大保证的调度器无法将这个程序执行到完成。并不是说这个死锁程序做了一个可能被满足的假设。它因为这个循环而无法被满足。”
（观众）“是的，因为循环。”
（演讲者）“是的，完全正确。是的。所以在同一个循环里，如果我们用 try_lock，那么死锁会转换成活锁，对吧？”
（演讲者）“嗯，这取决于你接下来做什么。如果你 try_lock 失败了，你要做什么？再试一次吗？”
（观众）“是的。”
（演讲者）“不，那仍然是死锁。是的，没有任何调度器能够解决你的程序。我的意思是，你只是在描述轮询内部发生了什么。如果我把轮询替换成所有轮询内部的代码，那并不会让它变得可执行。”
（观众）“但死锁不也意味着两个线程甚至没有任何进展吗？而活锁意味着两个线程在取得进展，它们在运行，但无法完成最终目标。”
（演讲者）“不。从前向进度保证的角度来看，而且我后面会有更多关于 C++ 如何与此关联的例子。从前向进度保证的角度来看，一个有死锁的程序在不断地执行步骤（steps）。只是这些步骤都无法让程序完成。如果你愿意等一下，我会在图上向你展示。Tony？” （另一位观众）“是的。因为那些线程确实在做它们的下一步操作。”
（演讲者）“是的。” （另一位观众）“下一步操作就是再次检查标志。”
（演讲者）“是的。所以它们在做事。它们在执行。” （另一位观众）“没错。但是没有（最终的）进展。”
（演讲者）“所以从调度器的角度看，感觉上进度应该是在推进的。但从整个算法的角度看，并没有取得进展。顺便说一下，活锁和死锁给人的感觉是一样的。就是感觉程序挂起了。就是我的程序运行到这里，然后它就一直忙着做事，但永远完不成。”
（观众）”但如果我把轮询换成互斥锁，它会睡眠而不是轮询。”
（演讲者）”不，同样的问题。当我们讲到 C++ 中阻塞（blocking）的正式定义时就会看到，阻塞……我这是在预告后面的幻灯片内容了，但我们现在就讲了吧，这样就可以继续了。阻塞被定义为‘反复尝试执行一个步骤’（repeatedly attempting to take a step）。”
（观众）“活锁和饥饿（starvation）是同义词吗？”
（演讲者）“这是个有趣的问题。我们姑且说是吧。是的。是的。好的。”
当我们在库和编程语言中拥有任务（tasking）抽象时，事情就变得相当模糊了。我刚才在谈论线程，但假设我启动了两个任务，并且我是通过某种并行 for 循环类型的库抽象来启动它们的。尽管这个库是在 C++ 调度器上运行的，尽管一个并行库可能是用线程实现的，尽管调度器给予了线程最大进度保证，但我的库抽象实际上可能会妨碍这一点。在接下来的一个小时里，我们将深入探讨这个问题。我只是告诉你们我们将要讨论的内容。
好的。这里，我启动了两个任务，任务所做的是调用一个屏障（barrier）的 arrive_and_wait。这是否会活锁，将取决于哪些保证实际上能穿透我的库。
好的。现在让我们从第一性原理（first principles）来推导 C++。我会展示一系列代码示例。总的来说，我的代码没有哪个是特别好的。这些都是幻灯片演示代码（slideware）。你不应该这么写。外面有很棒的库可以做我的代码将要做的事情。我想指出，如果代码有未定义行为（UB），我会打一个红色的叉（❌）。如果它仅仅是个糟糕的主意，我会打一个黄色的叉（🟡）。
单线程¶
好的。让我们从单线程代码开始，然后再逐步构建到线程。我们也会先构建一些糟糕的线程代码。好的。这里是我的单线程代码的试金石（litmus test）。这个试金石代表了所有曾经编写过的单线程程序。它们不包含 this，它们有其他东西。然后在 main 函数里做任何事情，但它们没有包含那些（并发相关的）东西。这是一个单线程程序。很棒。
我将用事件图（graph of events）来表示这次演讲中的所有程序。所以这是最激动人心的图之一。我调用 main，然后这“顺序前于”（sequenced before）“任何事情”的注释，而这又“顺序前于”从 main 返回。这就是我们理解单线程程序的方式。很棒。它没有竞争，没有前向进度问题，但它也没有免费的午餐。
（观众）“它有数据竞争。有吗？中断。信号。”
（演讲者）“是的，信号。是的。信号是被定义的。是的。信号是被定义的。谢谢。书呆子狙击（nerd snipe）。是的。太棒了。我……我确实想说一下单线程程序的一个好处，那就是单线程程序仍然可能在这里使用加速库。实际上，尽管我是 SG1 的主席，我在委员会做的所有事情都与线程、并发、并行、原子操作、竞争、同步等等有关，但请你们不要使用任何这些东西。如果可以不用，就别用。尽可能多地使用加速库。尤其是在今天，当硅片变得越来越异构时，供应商在领域特定的加速库上投入了更多精力。这些库的质量通常超过了你尝试自己重新实现所能达到的水平。所以，如果你使用加速库，你可以通过单线程代码获得免费的午餐。我认为这样做是完全合理的。”
（观众）“是的。而且这里的代码可以有并行执行。”
（演讲者）“在库的内部吗？”
（观众）“不，就在 main 里面，因为它可以使用向量化指令，对吧？”
（演讲者）“我的意思是，你只写一个循环。在 C++ 中，自动向量化器必须是无法感知的。它必须隐藏在‘如同’（as-if）规则之下。是的。所以我写单线程代码，这就是我需要关心的全部。好的。是的。好的。”
好了，让我们给它加点线程。我们将会用几种错误的方式来做，这样我们才能达到可以提出一个有趣问题的地步。好的。我要加一个线程。这里我只是创建了这个线程。线程做的是它有一个语句 a，它给 data 赋了 1。然后我在 b 处有另一个语句。然后我从 a 返回 data。很好。
这段代码有一堆问题。我们从图开始。有趣的是，至少它有两个线程了。所以我们有两条“顺序前于”的链，每条都从一个调用开始。我们有 main 的调用，然后顺序地是 jthread 的构造函数，jthread 的析构函数，b，虽然这些在这里可能不是顺序的。我的 jthread 构造函数到 lambda 的调用之间有一个“同步于”（synchronizes with）关系，lambda 顺序前于 a 的求值，顺序前于它的返回。很好。我们还没有前向进度问题。但是我们没有前向进度问题的原因是，我们有一堆其他问题。
（观众）“是的。在你之前的图里，它显示的是一个 jthread。哦，这里它是个 thread。”
（演讲者）“幻灯片 bug。我本意是 thread。”
（观众）“行为不同。”
（演讲者）“没错。我们会在后面的幻灯片里用 jthread。”
（观众）“析构函数行为是不同的。”
（演讲者）“你正说到我后面两张幻灯片的要点了。所以这里写的是 thread。各位，它写的是 thread。你们的眼睛在骗你们。没错。它写的是 thread。”
好的，第一个问题是，在我们的 thread 析构函数那里，我们会调用 terminate。因为它是一个未 join 也未 detach 的线程。所以它会调用 terminate。这不好。
我说未 join 未 detach。好吧，我可以 detach 它。嗯，在某种程度上这更糟了。现在我有两个问题。第一个问题是，在给 data 赋 1 和在 return 语句中读取 data 之间存在数据竞争。我还有一个问题。第二个竞争是，我有一个生命周期结束后使用（use after lifetime end）的问题，这个线程的生命周期可以超过 main。它可能会尝试解引用 data，而 data 在栈上，它的生命周期在从 main 返回时就结束了。所以那也不行。
我说未 join 未 detach。我们可以 join 它。我们可以这么做。这里是一个黄色的叉（🟡）。是的，我用了线程。但是我在两个线程上写了一个串行程序。这不太好。我在这里实际上没有得到任何并行性。所以我这样做并没有得到免费的午餐。好的。这不太好。你这是在请别人吃午饭。
是的。现在，我也可以用 jthread 做完全相同的事情，它避免了 terminate，也避免了数据竞争。这都很好。但是，你知道，jthread 实际上让我陷入了串行化的行为。所以那也不太好。
所以现在，我们终于来到了我的试金石的一种形式，在这里我们可以讨论进度保证了，我终于有了一些并发的语句。我创建了一个作用域。我的 jthread 的生命周期现在就是，我已经给它命名了，我的 jthread 的生命周期现在就是那个作用域。它在 jthread 内部有一个语句 A，在周围的作用域里有一个语句 B。这两件事是并发的。所以现在我们可以讨论并发执行了。好的。
并发进度¶
我们已经讲了错误使用线程的方式。现在我们到了可以讨论主题的地方了。让我们来谈谈并发进度保证。为此，我将给出我对“并发”（concurrent）的定义。我会说，在野外，人们使用“并发”和“并行”（parallel）有两种极性。但在 SG1 中，这是我们的极性。当有人第一次带着错误的极性来到 SG1 时，整个小组都会纠正他的极性。从此以后，我们都遵循 C++ 使用的含义。好的。
我个人的定义是，并发任务最终能观察到彼此的效果。它们实际上是在同一时间运行，并且内存模型给予了它们最终性（eventuality）的保证，即如果它们产生了一个效果，这个效果最终对另一个任务是可见的。好的。
现在问题是，我们之前有了一些并发性。现在问题是，我们这里有一个阻塞操作。那就是 jthread 的析构函数。它最终会解除阻塞吗？答案是肯定的。但这是因为它得到了并发进度保证。好的。
所以这里是修正后的图。我们有一个“同步于”的边，从 jthread 的构造函数指向 lambda 的调用。我们有一个“同步于”的边，从 lambda 的返回指向 jthread 的析构函数。现在我们将用我们的正式定义来注释这个图，这些定义将构建起并发进度保证。我们需要三个定义。我们需要知道什么是执行线程（threads of execution）。我们需要知道什么是抽象机的步骤（abstract machine steps）。我们需要知道线程何时执行步骤。
好的。第一步，我现在给它们上色了。我有两个执行线程。你可能会说，这太明显了。好的。是的。执行线程的定义，我们将在演讲的最后重新审视它，因为它并不像我马上要说的那么清晰，它的定义是：它始于一个顶层函数的调用，并包含从那一点开始的控制流。好的。所以这里我有两个执行线程。它们始于 main 的调用和 lambda 的调用，然后是各自的控制流。好的。这个例子中的“顺序前于”关系。所以这些是我们的执行线程。很棒。
抽象机的步骤。这是整个讨论中需要了解的最重要的事情之一。好的。有些特定的事情被认为是一个“步骤”（step）。
执行一个同步操作是一个步骤。
访问一个原子变量是一个步骤。
访问一个
volatile变量是一个步骤。一个控制线程的终止是一个步骤。
所以这里，你有它们全部。这里我有我的两个控制线程。我看到 jthread 的同步操作是一个步骤。return 操作是步骤。阻塞操作，是同步操作的一种，也是一个步骤。然后，正如我刚才提到的，有一条规则说，一个阻塞操作被视为执行了不确定的、可能是无限次数的内部步骤。它必须为 unique_ptr 或 matrix 系统建模。但在突然间，那里有一个解决方案问题。它被有意的元素包围，当 Baltimore 的阻塞频率或重建时。这在你的脑海中很容易记住，就好像……它可能是用高效的阻塞实现的。但是从 C++ 抽象机的角度来看，那个阻塞的互斥锁函数，就好像它在不断地做 try_lock。而那是一个步骤。
最后，它们何时执行步骤？嗯，控制线程，线程最终会执行一个步骤。所以蓝色的区域，蓝色区域内的一切，我们总是最终会执行下一步。绿色的区域内的一切，我们最终也会执行下一步。这就是我们稍后将更正式地写成“并发进度保证”的东西。
好的，这里有一个“should”（应该）。在 C++ 标准中，“should”总是应该让你感到害怕，因为它意味着我们知道我们想规定什么，但是，嗯，实际上，有时实现可能因为某些原因无法实现这个规定。所以，我们改用规范性的鼓励，也就是“should”。好的。所以这里有一个“should”，我想你可能凭直觉就能知道为什么这里是“should”。在很多操作系统上，你可以设置线程优先级。在很多操作系统上，这些优先级是会被遵守的。但并非所有地方都如此。例如，在 Windows 上，你几乎无法通过设置优先级来让 Windows 完全饿死一个线程。然而，在 Linux 上，你完全可以做到。因此，所有这些规则，当涉及到例如在 Linux 上的 C++ 实现时，意味着这在名义条件下是成立的，除非你乱动了线程优先级。
好的。所以，jthread 应该最终会解除阻塞。太好了。这就是我们的并发前向进度。
在接下来的几分钟里，我们将构建我们的前向进度保证菜单。并发前向进度保证是：线程最终会执行它们的下一步。这从线程被构造的那一刻就开始了。所以线程可能还没有执行它的第一步，但只要线程存在，它最终就会执行第一步以及所有后续的步骤。
好的。现在我们来看看错误地使用它会怎样。这是最大保证。所以我们将画一个带有死锁的图。这里我有一个信号量（semaphore），为了释放这个信号量，我需要 jthread 完成，但是 jthread 又需要获取那个信号量。好的。这是依赖关系图，从图上你可以识别出，这显然是死锁，因为有循环。
然而，从前向进度保证的角度来看，将会发生的是，调度器在不断地给这些线程执行步骤的机会，它们也确实在执行，但它们把所有的步骤都花在了阻塞操作上。好的。所以并不是说这个程序失去了前向进度保证。这就是为什么它被称为“前向进度保证”的原因，因为它无法在有前向进度保证的情况下完成。好的。这就是一个死锁。
（观众）“但它没有动啊。如果它死锁了，为什么还叫‘前向进度保证’呢？”
（演讲者）“是的。因为它不是……从实现的角度来看，实现做的一切都是对的。它在不断地调度那个线程，不断地给它机会去做事。底层的计算机，除非你只使用平台同步原语，并且只有在平台有死锁检测的情况下，通常实现是无法知道你是否死锁了的。实现为你提供了一个前向进度保证，而你用它做了一些没有用的事情。好的。好的。”
所以我们有了并发进度，即最大保证。如果我们讨论的是 C++11，那我们已经讲完了。因为 C++11 没有任何其他设施。它有 std::thread。它有运行 main 的未命名线程。在托管实现（hosted implementations）中，这两者都获得并发前向进度保证。在独立实现（freestanding implementations）中，它们获得什么保证是由实现定义的。好的。
并行进度¶
现在我们将要构建 C++17 中引入的，并且在未来我们将要添加的其他设施中仍然相关的概念。好的。让我们来谈谈并行进度。我们谈过了并发。这是我对并行的定义。并行任务永远不会观察到彼此的效果。这将是纯粹并行（pure parallelism）的定义。
（观众提问）“C++ 中的并行是纯粹的吗？”
（演讲者）“呃，不总是。其中有很多实用主义的成分。记住这个的直觉是，平行线永不相交。”
（观众）“那为什么还要创建线程呢？它们完全可以是另一个进程啊？”
（演讲者）“不，不。并行任务之间不会互相串扰，但它们从程序中获取输入，并将输出返回给程序。对吧？它们从程序状态开始，对该状态进行计算，然后产生一个输出状态，只是在并行计算阶段，线程之间不应该有写-写或读-写冲突。这是纯粹的。就像这是纯粹的并行。C++ 没有那么纯粹。我们会谈到融入其中的实用主义。是的。”
（观众）“我的问题是，这是没有保证它们会观察到，还是保证它们不会观察到？”
（演讲者）“是的。在纯粹的并行中，如果你试图在任务间通信，你就违反了编程模型，我们应该给你未定义行为（UB）。是的。好的。然而，你们都是……我直接跳到实用主义部分。你们都是务实的 C++ 程序员。你们知道计算机是在并发的基础上实现并行的。当我使用一个并行编程 API 时，它实际上是构建在线程和 CPU 核心之上的，而这些是并发的，可以观察到彼此的效果。所以我们称之为，我们给这个起了个名字，这个名字没有争议，是全行业通用的。我们称之为‘发现的并发’（discovered concurrency）。当你使用并行编程模型编写代码，并且代码在线程之间会有一定程度的通信时，即使你事先不知道哪些线程会同时运行，也有很多习语可以让你与‘在场的任何人’协同工作。是的。那被称为发现的并发。”
而且，我可以通过从图景开始来展开对并行进度保证的讨论。但我认为对于 C++ 来说，从务实的一端开始会更好。所以我们将要做的是，我们将逐步构建一个并行编程库。然后我们将问自己，这个库有什么样的进度保证？
好的。我们从一件你可能不应该做的事情开始。这里没有黄叉，但这是个坏主意。我有一些任务。现在，我说“一些”任务。任务可能是我有 10 件事情要做。任务也可能是我有 1100 万件事情要做。好的。现在我要创建一个 jthread 的 vector。你的脑子里应该响起警报了。1100 万个 jthread 可能不是个好主意。然后我将在每个元素中构造 jthread。所以在注释“并行工作”这里，就是我的并行工作内容。然后在末尾，我销毁那个 vector，这会销毁所有的 jthread，也就是 join 了所有的 jthread。好的。这是实现一个大的“分叉-汇合”（fork-join）的可爱方式。
让我们用两个任务来画图，因为我不想让图变得巨大。好的。它看起来和我们之前看到的相似，只是我们有两个 jthread，每个的创建都是一个步骤。我有两个被调用的 lambda。它们是独立的执行线程，因为执行线程是从……哦，我这里漏掉了一些“顺序前于”的边。好的。这就是我的图。
我这里有什么进度保证呢？我的测试是，我会做我之前在讲座最开始做的事情。我说，如果我做一个屏障的 arrive_and_wait 会怎么样？这被支持吗？这里的答案是肯定的，因为我使用的是完整的线程。所以如果我写屏障，两个 lambda 都到达，两个 lambda 都等待，同步于（synchronizes-with）的边交叉了，但它们没有形成一个循环。它们的方向是正确的。所以这没问题。因此，我们这个“婴儿的第一个并行编程库”——一个 jthread 的 vector——拥有并发前向进度。我们还没有发现任何新东西。
好的。我们来看看我为每个任务花了多少时间。我会得到一条曲线，随着我增加更多的线程，完成总工作量相对于串行的时间会下降。但之后我会达到一个点，我已经饱和了所有的核心。然后这条线实际上会稍微上升。这是因为一旦我把每个核心都放上一个 jthread，我只是在要求计算机在我工作的间隙做更少的有用功。对吧。它在 jthread 之间进行上下文切换。而且，我这里画的是线性的，但它可能不是线性的。而且我对小任务没有任何好处。对于大任务，这种摊销在开始时非常好。但对于小任务，我可能永远不会让情况好转多少，因为创建一个 jthread 的成本相当高。所以如果我的任务成本和创建 jthread 的成本在同一数量级，甚至更小，我只是在给计算机创造更多的工作。
现在我们进入了构建并行编程抽象的业务。为什么谈论并行编程的人不谈论启动一大堆线程呢？我们将讨论四个需要担心的事情。我们从 摊销（amortization） 开始。
好的。为 1100 万个任务每个启动一个 jthread 不是个明智的主意。那么，我们为每个硬件并发单元（原则上是核心）启动一个 jthread 怎么样？现在我将一个 for 循环推入每个任务。所以每个 jthread 将循环处理一些任务。所以如果我启动两个 jthread，我有四个任务，那么每个循环两次。是吧？说得通。好的。
这是我们的图。所以每个 lambda 调用里有两个并行工作。我的摊销现在会好得多。它会衰减。即使对于小任务它也会下降。因为如果我有 1100 万个任务和两个 jthread，那么每个做 550 万个任务。这很好。它会趋势向好。你会得到一点这种锯齿状的东西，就是一旦我给每个核心分配了一个任务，当我再给其中一个核心分配一个任务时，我就通过制造一个“尾部效应”（tail effect）使完成这件事的时间翻倍了。好的？我们现在还没担心这个，但我们很快就会担心尾部效应了。
好的。现在我还有同样的进度保证吗？这有点预示，因为答案将是否定的。如果我再把我的屏障放在这里，现在记住，我的屏障计数的是任务，不是线程。所以我创建了一个任务数量的屏障，然后在我的循环内部做 arrive_and_wait。你可以为四个任务和两个线程画出这个图。这些是所有我们必须有的“同步于”边。这里有很多问题。你可以创建很多循环，不止一个，但我只挑一个。我选可能最直观的一个，那就是我在等待其他线程的后续迭代。我们到不了那里，因为在前一次迭代中，我们正在等待。然后我们把所有的时间都花在了阻塞步骤上。
现在，这还不是一个调度器。我启动了线程。线程在我的代码里。循环在我的代码里。我使用的是操作系统的……我使用的是抽象机的并发前向进度保证。它还不是一个新的调度器，但我们快到了。所以这是一个死锁。死锁的原因我刚刚已经给出了。我们看得到线程。我们看得到循环。我们看得到依赖关系。它完全在我们的代码里。这里有一个重要的点，那就是我们判断它是活锁还是死锁，或者我们判断是否有前向进度保证问题，将取决于我们在程序和实现之间划定的那条界线。所以现在，我们开始做了一件事，如果它是一个调度器，它会有较弱的保证，但它目前还不是实现的一部分。
那么，这种任务会有什么样的保证呢？嗯，如果一个任务已经执行了一个步骤，它最终会完成它所有的步骤。因为在我的 Lambda 中，我调用一个任务，然后我调用另一个任务，但我不会在同一个 Lambda 中交错执行这些任务。我调用第一个任务，一旦我在任务中执行了一个效果，我就是在运行任务的代码。而任务的代码是在线程上运行的，所以它得到的是线程的并发前向进度。所以一旦一个任务执行了一个步骤，它最终会执行它的下一步。
并且至少 N 个任务最终会执行它们的第一步。这里的 N 是线程的数量。如果我有两个线程，那么至少有两个任务会执行它们的第一步。当一个任务完成，我降到一个，我立刻又弹回两个。当第一个 Lambda 上的任务完成时，我就接着执行下一个。
（观众）“创建一个任务也是任务的第一步吗？比如我有一个任务，然后立刻在里面 wait。那 wait 本身会是一个步骤吗？所以在这种情况下，哪一个是第一步？创建任务会是第一步，还是那个 wait？”
（演讲者）“不，不，是 wait。如果我回到一个图，让我找一个不是那么糟糕的图。这个。这个执行线程只有一个步骤。就是这个。如果并行工作内部有一个步骤，那么第一步会在这里。调用本身不是一个步骤。它不在那个列表上。是的。好的。所以，好的。”
让我们来谈谈尾部效应。那个锯齿状的东西。然后这还有另一个维度。当我串行地看我的任务时，它们可能不都是完全相同的长度。比如我想在一个 map 里搜索一个键。如果找到了，它会相对快地返回。如果没找到，我就得穷尽最大距离，你知道，才能确定。对吧？所以有时候我们有很短的任务和很长的任务。如果我只是按索引来分配任务，我可能会遇到像这样的问题。这些条上有相同数量的任务。但是有些条拿到了所有短的任务。有些拿到了所有长的任务。所以我的计算机利用率在一段时间后就下降了。一开始很好。然后我只剩下两个线程在跑。然后我只剩下一个线程在跑。我需要等待那个线程完成才能结束我的并行批处理。
所以我们要解决这个问题。这也会对我们的进度保证产生轻微的影响。我们解决这个问题的方法是，在这里，我们不再用预先确定的索引分配来分派任务，而是从一个队列中 窃取（steal） 任务。我们会说，有一个原子变量，它计算任务的数量。每个线程会反复地去原子性地递减那个计数器，得到一个唯一的数字，然后说“我正在运行那个任务”。如果一个线程拿走了所有简单的任务，那么它会更频繁地回到那个原子变量去拿更多的任务。如果一个线程拿到了所有长的任务，情况则相反。
现在，当我这样构建它时，有一件有趣的事情发生了，我想指出那个红色的箭头，就是当我这样构建它时，这个组里的线程数量现在可以完全被抹去了。这段代码用一个线程、两个线程、一万个线程都能完美工作，没关系。好的。所以我可以得到一个像这样的执行。一个慢任务，三个快任务，性能更好。而且我并不需要知道硬件并发宽度是多少才能让它工作。它可以是任何宽度。好的。
所以，因为它可以是任何宽度，那么我们就在削弱保证可能是什么了。保证可能是至少一个任务执行它的第一步。如果组里只有一个线程，那么可能只有一个任务会迈出第一步。但这仍然能完成批处理，只要它们之间没有同步。对吧？好的。
现在我要把这个概念——这个由未知数量线程组成的工作窃取集合——包装成一个线程池 API。我将想象一个线程池 API。我创建一个池子，我的线程池，我的线程池有一个 run 函数，我想运行一些任务，我传入带有并行工作的 lambda。然后当我 join 这个池子时，比如说它会 join 所有的线程。同样的事情，基本上和前几张幻灯片的代码一样，只是重新包装了一下。是的，重新包装。这开始是一个在人们代码中相当可信的并行循环库了。好的。好的。
现在，如果我像这样在本地创建我的线程池，我就会给自己造成 过度订阅（over-subscription） 的问题。在我们能把像这样的并行抽象放进 C++ 标准之前，我们需要解决这个问题。好的。好的。好的。
这里是过度订阅的例子。假设我现在有一个外部并行工作和一个内部并行工作。对于外部并行工作，我实例化我的线程池，然后调用 pool.run。这创建了一个 jthread 的 vector，大小可能和硬件并发数一样。然后在内部，我还有一些并行工作。它是一个二维的东西。好的。所以我又创建了一个线程池，为每个 jthread 创建一个新的 jthread vector。然后，我现在对 i 和 j 做一些并行工作。
这就是我刚刚做的。孤立地看，我的线程池的每一次出现都有左边的摊销策略，因为我们做得对。但是当我在我的程序中组合使用它时，我最终得到了右边的行为。所以我会得到这两种行为的混合。
所以，我想要做的是，有一个全局线程池，一个大的共享线程池，然后我把两层任务都附加到这个线程池里。现在这解决了我的过度订阅问题。然而，我给自己制造了一个 饥饿（starvation） 问题。让我们来看看那个饥饿问题可能是什么。
现在，这一个，我想我们需要花点时间来读一下。好的。这个，即使没有红叉，这里也应该有个黄叉。这是那种你为了找出哪里会出问题而写的代码，而不是为了做有用功而写的。好的。
我将从在我的代码中开始，不是在线程池里，在我的代码里，我为每个任务创建一个线程。然后我转过身，把工作推到线程池里去。我将在里面放一个屏障的 arrive_and_wait。这应该能工作吗？嗯，如果屏障的 arrive_and_wait 是在 jthread 自身内部，它能工作。但是我把它放在了池子里，而我们知道池子承诺最多只运行一个任务。结果就是，这行不通。这会挂起。至少它会挂起。我开始说我们这里要得到一个活锁了，因为我们把线程池作为实现的一部分推了出去。
但问题是，如果一个 C++ 程序本身有四个线程，每个线程都有工作，而当你在这些线程内进行局部推理时，那个工作没有死锁或活锁，那这个 C++ 程序怎么能信任一个全局线程池呢？但是当我把它组合起来，由于有一个全局线程池，它就出问题了。现在，我解决各种性能问题的方案，使得我无法对我的程序进行除了全局之外的任何推理。而全局推理是站不住脚的。所以，不可接受。
所以我们要再加一个成分，然后我们就完成了对并行前向进度保证的探索。好的，这最后一个成分，用俗语说叫做“boost blocking”。在标准里，它叫做“带有前向进度委托的阻塞”（blocking with forward progress delegation）。它的工作原理是这样的。
首先，我们引入一种方式来阻塞在一组并行的……任务上。当我给我的线程池工作时，它不能只是一个返回 void 的东西。它不能说“谢谢”，然后给我一个那么弱的进度保证。如果它给了一个非常强的进度保证，那个接口可能是可以接受的。但是因为它有一个弱的进度保证，我们将让它返回一种句柄（handle）。它会说，“这是一个句柄，用来指代你刚给我的这堆任务”。然后当我们阻塞在这个句柄上时，我们将采取一个行动。
有几种行动我们可以采取。我们可以开始抢占任务。如果我们有一个抢占式调度器，我们的调度器是一个 for 循环，它不是抢占式的。所以我们做不到。但是如果我们把它交给了一个操作系统，而操作系统为此具体化了轻量级线程，操作系统可以说：“哦，你阻塞在这个上面了。那么让我开始抢占式地进行上下文切换来升级进度保证。” 或者我们可以开始向池子里添加线程。比如当你阻塞在上面时，开始添加线程直到事情解除阻塞。有些操作系统就是这样工作的。
我们将要做的是一种叫做“子任务窃取”（child stealing）的东西，就是当创建工作的父上下文参与到任务窃取方案中时。当我们的线程将要阻塞在这个句柄上时，它将开始运行工作线程正在运行的同样的代码。所以它开始从队列中窃取，但它只窃取自己的工作。所以它把前向进度委托给了它创建的子工作。好的。
所以这在我的代码里可能看起来是这样的。我有了我的 pool.run，现在它返回某种句柄。我不会告诉你我的句柄的 API 是什么或者它的名字是什么。所以我用 auto 捕获它，但它确实有一个 drain 函数。所以我调用，我将我的任务 1 入队。然后我调用 task.drain。
这里发生的是，我可能开始时只有一个工作线程的线程池。也许我有八个任务，比方说。那么那一个工作线程只能执行一个 arrive_and_wait。但是当所有的父线程都到达阻塞点，到达 drain 时，它们会把自己贡献给线程池，但只为它们的子工作，并且只在子工作期间。所以线程池看起来将会有九个线程，和八件事情要做。
（观众）“好的。此时工作实际上已经不在线程池执行了，因为线程池所有东西都阻塞了。”
（演讲者）“是的。但是最初调度工作的那些 jthread，它们会执行它们。是的。好的。”
（演讲者）“没错。这是为了建立你对前向进度委托如何工作的直觉。在实践中，你知道，你本不应该知道 C++ 实现是如何工作的。你只是得到一个 C++ 实现。你不应该去看底层。它做什么就是什么。它可能做我提到的其他方案。但这里有一个非常直观的方式来思考，当一个并行 API 可以被阻塞，并且标准强制要求前向进度委托时，会发生什么。”
（观众）“所以这个委托是从子任务到父任务的，对吗？”
（演讲者）“是父任务将它的进度委托给子任务。父任务在这里有非常强的进度保证。它是一个 jthread。所以它有并发进度。它有最大进度。然后它的子任务没有最大进度。它有并行进度，我们稍后会得到定义。所以当父任务阻塞时，它将子任务组的进度保证提升到并发，但一次只有一个。就像它确保它们中至少有一个取得进展。”
（观众）“因为它在等待子任务完成，这意味着子任务必须执行下一步。所以除非它不做，否则父任务会一直阻塞。”
（演讲者）“没错。没错。”
（观众）“所以当我们在例子中计数时，我们把那个对象给了父任务。那为什么我们要多加一个线程呢？你说八个，然后你又说九个。它只是用父任务来做同样的事情。那我们为什么把它算作一个额外的呢？”
（演讲者）“嗯，我是说，在所有父任务都调用了 .drain 的那个点，其中一个很幸运，它的子线程实际上被调度到了一个工作线程上。对。剩下的七个没有。但是当所有八个都调用 .drain 时，它们都会让自己可用于运行它们创建的、但没有进展的工作。”
（观众）”那么下一个父级会在开始执行之前等待下一组子线程吗？”
（演讲者）”每个父级只向其子级委托进度。所以你不能让线程七去处理线程三的工作，我的意思是，你潜在地可以构建一个那样的系统。但是那样要向自己证明你正确地实现了前向进度委托会更困难。更困难。如果你把父级出现的效果限制在只对它的子级有效，会更容易。”
（观众）”那么，这里的 drain 和我们在 C 代码中看到的普通 thread_join 有什么不同？”
（演讲者）”哦是的，它不是，它不是一个 join。不，那个，嗯，最下面的那个是，但这个不是。最下面的那个是排空整个池子。那只是一个，那只是一个 join。但是，嗯，这里的这个，等待这个特定任务的。抱歉，阴影不太好。但是这里的这个，等待这个特定任务的，嗯，那不能是一个 pthread_join。那个工作可能没有线程可以运行。好的。但是，是的。所以父任务做的是，它调用了与工作线程本身为参与工作窃取方案而调用的相同的函数。所以它临时变成了一个工作线程，直到它的子任务完成。然后它返回去做它之前在做的事。”
（观众）“所以，是的，概念上，池子，呃，任务，每个任务都不会有线程可以运行。”
（演讲者）“是的。”
（观众）“所以父任务等待子任务完成。是的。在这里，呃，呃，和 join 的概念不是一对一映射的，因为 join 和线程实例非常相关。”
（演讲者）“没错。”
（观众）“呃，但概念上它仍然在等待任务。即使它不是……被……支持的……去完成。”
（演讲者）“是的，是的。”
（观众）“我很难看出现实中这个递增的保证有多大用处。因为我还是需要像所有 jthread 都去调用 drain，对吧？所以我不能只是把任意的工作放在线程池里，然后等着其他工作线程。我最终还是需要有足够多的东西可用去调用 drain，才能让它，嗯，完成。”
（演讲者）“对。嗯，对于……所以如果，如果我想象一个，一个应用程序，对吧。是的。就像任意的片段开始把东西放到线程池里，这些东西又等着线程池里必须发生的其他事情。是的。我仍然需要能够全局地推理，我永远不会在线程池里放太多东西以至于它会，会阻塞。”
（演讲الرئيسية）“不，你不需要全局推理。不。每个父任务都被保证会得到下一张幻灯片里的并行进度保证。对于它们所有的子任务，它们都会收到一个并行进度保证，无论其他人做了什么。嗯。而提供这个保证的一部分是，父任务会得到一个阻塞句柄，它们需要调用那个句柄来知道工作已经完成。在最坏的情况下，父任务在那个调用内部运行了所有的子工作。好的。”
（观众）“所以，就像，父任务必须确保，像我推送的所有工作，我都能在，像我的单个文件内完成它。”
（演讲者）“是的。然后，好的。然后我明白了。是的。是的。但是早些时候我们，我们，我们明确了，并行进度保证在极限情况下可能只有一个工作线程。对。是的。现在我说，在最坏的极限情况下，那一个工作线程实际上就是父任务。是的。”
好的。如果我们这里有一个任务调度器，那么我们已经确定了顶部的这个东西：已经执行了一个步骤的任务，最终会执行它的下一步。因为每次我调用一个任务函数，我都会在一个线程上执行那个任务函数直到它完成。
至少有一个被阻塞的任务，最终会执行它的第一步。这是我们之前的保证，现在我们说，被阻塞的那个任务，最终会执行它的第一步。好的。好的。这个保证字面上就是并行算法（parallel algorithms）所提供的。
所以在 C++17 中，这是我的，又一个丑陋的版本，不是你应该写的代码。直接用 C++17 的并行算法就行了。但是如果我自己写一个 parallel_for_each，这短短的一点代码就可以在我的线程池上实现一个 parallel_for_each。对吧？为了幻灯片的目的，我把它写得非常丑。A 和 B 是迭代器。C 是一个可调用对象。我获取 A 和 B 之间的距离。这是我需要运行的索引空间。这是任务的数量。所以我发送可调用对象。我用 A 的第 i 个下一个东西在一个 lambda 内部调用可调用对象。把它放到我的线程池里。我拿到从中出来的句柄，然后立刻在上面调用 drain。
所以，这就是 parallel_for。它拥有我们之前描述的所有属性：摊销、避免过度订阅和避免尾部效应。并且它有前向进度委托。它通过包装我们目前为止构建的东西，拥有了所有这些属性。如果你给我 1100 万个小任务，我不会启动 1100 万个线程。并且总的来说，因为我循环，比如说，我的意思是，这是我们在这一节中讨论的第一件事，对吧？所以每个任务的成本趋向于真实成本除以活动线程数。是的？
（观众）“我想你是不是漏了括号之类的？”
（演讲者）“我吗？你少了个括号。我在 .drain 前面少了个括号。是的。好的。”
所以这是我们的并行前向进度保证。这是三分之二了。幸运的是，第三个会快得多。好的。
现在我们可以再次测试我们有活锁还是死锁了。这里我用我的 parallel_for_each。我现在用的是看起来像 C++17 的东西，只是拼写不同，更丑一点。我给它传一个 iota 范围，然后调用 arrive_and_wait。这能工作吗？嗯，这不行。这是一个活锁。因为我们现在超出了调度器的保证。这是一个活锁。我们看不到线程。我们看不到循环。它不在我们的代码里。它在实现的代码里。实现给我们做了一个前向进度保证，即并行前向进度。并行前向进度只承诺启动其中一个任务，而我的屏障需要所有任务。所以那不行。那是一个活锁。但它不是一个死锁，因为如果我有最大进度，它就能工作。它会正确执行。
弱并行进度¶
好的。让我们看看弱并行进度（weakly parallel progress）。
我回到我之前的定义。并行任务永远不会观察到彼此的效果。如果你永远不能观察到彼此的效果，现在我要变得纯粹。我要变得严格。之前我说，我们都知道这是 C++，我们很务实，事情都在线程上运行，因此你可以进行各种通信。现在我要说，如果你做任何在线程间通信的尝试，你会得到未定义行为（UB）。你会从内存模型得到 UB，也会从进度模型得到 UB。好的。所以在纯粹并行下没有发现的并发。好的。
现在我们可以做一些非常强的假设了。我们可以假设所有任务都是有限的。它们最终都会结束，因为它们不被允许阻塞在任何东西上。所以有一个有限的执行步骤数，并且没有这些可能不确定的循环。好的。也没有临界区。我这里所说的临界区是，一个第一个可见的效果，它先于一个第二个可见的效果。在程序中，假设是如果你看到了第一个并等待，你最终会看到第二个。好的。所以这两个假设我们都可以做。
结果就是，我直接跳到弱并行进度的定义。我们可以只保留底部的规则，然后说至少一个被阻塞的线程最终会执行它的下一步。注意，我删掉了第一个。如果你已经迈出了一步，我不能保证你什么时候会执行下一步。好的。
所以在下面这里，我只是把所有的执行线程都归入一个黄色的虚线域里。我说，在所有这些里面，我承诺执行一个步骤。现在我可以反复选择这个而不选那个。所以在有一组弱并行进度的线程里进行同步是完全不允许的。你会得到活锁。好的。因为进度保证非常弱。而这对于 SIMD、GPU、DSP 实际上非常好。如果你要拿看起来像顺序代码的代码。比如你想把一个 for 循环映射到向量单元。你有一个 lambda。它看起来是顺序的。它是每个向量通道想做的事。但是向量通道不是完整的线程。向量通道不是抢占式调度的。它们之间没有最大进度。如果在那个函数内部，有一个 if，我想拿一个锁。如果我拿到了锁，我做这个。否则，我做别的事情。而向量化编译器调度这个的方式是，它只选择那些没拿到锁的，然后一直重试让那些失败者去拿锁。它们会一直失败。
这就是为什么我最开始提到的那个东西，CUDA 上的死锁、挂起，就是因为 CUDA 当时真正提供的是弱并行进度。而任何想写互斥锁的人，都假设了至少有并行进度。所以那些代码作者超出了调度器的保证。你知道，你从遇到一件令人沮丧的事情开始，你心想：“哦，我以为我会这样做。”然后你花了接下来 15 年的时间来理解这件事背后的理论。好的。
并行算法¶
所以我们在 C++17 中有并行算法。如果你用 std::execution::par，你得到的是并行前向进度。如果你用 std::execution::par_unseq，你得到的是弱并行前向进度。你可以用它做很多事。用 par，例如，你可以拿锁。你知道，早些时候，我不能在这里放一个屏障，因为屏障需要每个人都到达屏障才能同步。但是用锁，在你拿锁之前，你没有对谁在这里做任何假设。你可以做一个原子效应来拿锁。临界区在并行进度下是能工作的。它们只是在弱并行进度下不工作。
即使它们在弱并行进度下不工作，你仍然可以做很多事。比如在这个算法里，我在一个 map 里查找一堆键。这是我一直喜欢用的一个例子。比如你有一个巨大的 map，你想在里面查找 10000 个键，这完全合法。你没有改变 map。所以这里没有写效应。没有同步。map 在这里是常量。我只是要做一堆查找。这在弱并行进度下是完全没问题的。
（观众）“在强保证下，如果你在拿锁，一次只有一个会因为锁而前进。”
（演讲者）“是的。是的。那没关系。它没有超出调度器的保证。是那些黄色的圈。我的意思是，是的。对。我的意思是，你不想……对。再次，你不想写一个拆分在多个线程上的串行程序。但是那批并行工作，它可能有非常可观的工作量，而只有一小部分需要锁。那完全没问题。是的。好的。好的。”
悬而未决的问题¶
我还有很多悬而未决的问题（loose ends）。我们已经讲完了直到 C++23 的进度。有这三种进度保证。你通过并行算法来访问它们。当你编写将被作为这些算法的一部分调用的代码时，你需要知道你被允许假设什么样的保证，否则你就会导致活锁。当然，在库的场景下，这可能非常有趣。假设你写一个库。
（接下来是一段有点混乱的音频，大意是：作为一个库作者，你必须清楚地告诉用户你的库在哪种进度保证下工作，例如，如果你的库内部使用了并行算法，它就需要并行前向进度。用户需要知道这一点。）
好的，悬而未决的问题。你知道，作为 SG-1 的主席，我脑子里一直记着一些事，是的，我们有一个官方的缺陷报告列表，但是还有所有那些零碎的东西，哦，在一次会议上，某件事被提出来了，我们只是觉得，哦，那不清楚。然后没人提交缺陷报告，也没有关于它的论文，但它占据了我们的脑力空间，SG-1 的人占据了我们的脑力空间，记着那些规范的粗糙边缘。所以我们将讨论那些。
但我想从我最喜欢的未定义行为（UB）开始。是的，是的。因为这是我的一个朋友在我说我有一个最喜欢的 UB 时发给我的。“要是它出了什么事，那就太可惜了。”然后。我实际上会把这张图发给你。是的，这确实是我们的聊天窗口，是的。
所以，这个 UB 对于实现的多样性非常重要。让我们来谈谈它。它说的是，可以假设每个线程最终都会执行一个步骤。你们中的许多人可能知道这个 UB 是“禁止无限循环”，或者是“允许编译器优化掉无限循环”。所以，如果你写 while (1);，编译器可以移除它。为什么？因为它是 UB。为什么是 UB？因为如果你写 while (1);，你的线程就没有最终执行一个步骤。但它被要求这样做。这个要求是放在程序员身上的，因为它被声明为所有实现都可以做出的一个假设。
好的，我能用它做什么？我能用它做一些非常酷的事情。它给我，作为实现者，提供了一个我不需要证明的证明。我收到了一个证明，即 A 是有限的，B 也是有限的。为什么它们是有限的？因为它们不包含任何步骤。所以，每当我做一个不是步骤的事情，它最终都会完成。它不会有任何轮询循环之类的东西。
好的，现在我能做的是，我可以把我的执行线程切成我称之为“线程片”（threadlets）的东西。这些线程片是执行线程的片段，它们以一个步骤结束。并且我被保证可以在所有程序上这样做。所以，第一个线程片是 main 的调用到第一个步骤。然后是 B 到下一个步骤。然后 3’ 本身就是一个线程片，因为它完全由一个步骤组成。然后是最后的终止步骤。这里，这是一个步骤。lambda 的调用是一个有限的事情，但不是一个步骤。A 是有限的，也不是一个步骤。return 是一个步骤。
所以，然后我就可以构建一个实现。这在现实中是存在的。它在生产环境中，大批量地存在。在一个非抢占式计算机上实现 C++ 前向进度保证。计算机本质上可以只有协程（fibers）。如果编译器向调度器指明了步骤在哪里，它可以在那里执行一个协程切换。是的，这意味着，是的，当我做一个原子 fetch_add，那是一个步骤。它需要协程切换。如果我调用一个阻塞函数，那是一个步骤。它需要协程切换。如果它访问了所有活动的线程片，如果它访问了所有任务程序计数器所在的线程片，它最终会正确地执行程序。
（观众）“是的。我对‘步骤’的直觉还不是很强。但如果我说，如果我有一个普通的循环，每次循环迭代都是一个步骤，会怎么样？”
（演讲者）“你是说……或者这是标准法定的，它是真的吗？”
（观众）“如果标准会这么定义的话，就像……是的，但它没有，对吧？是的，是的。只是，只是假设性的。” （演讲-者）“如果它会说，那会有什么影响？因为那样的话，我们是否有 UB 就不再重要了。是的。所以如果你，你，这有点涉及到那篇论文了。如果你修改 C++ 标准说每个循环迭代都是一个步骤，那么这些在步骤处进行协程切换的实现，将会进行数量惊人的协程切换。因为……它们的性能会被摧毁。因为你真的必须在每次迭代时都做一个协程切换。在每个循环，每个地方。是的。而这些步骤实际上相当稀少和粗粒度。比如，从宏观上看，你的程序中执行的指令里，有多少比例是同步的原子操作？比如，是的。是的。对吧？”
（观众）“是的。回到上一个问题。我们所知的世界是建立在无限消息循环之上的。那些是 UB 吗？”
（演讲者）“嗯，看情况。它们是否包含一个步骤？我认为它们包含。因为如果它是一个消息循环，你就像是从一个操作系统队列里取东西。是的。你在这里做的很多事情实际上都是步骤。比如你有一些系统调用，你可以把它定义为在操作系统上阻塞。你可能有 volatile 或者原子操作。把一个东西从它来的地方弄到你的消息循环里。你没问题。你没问题。它真的只是那些在非原子数据上，没有同步、没有 volatile、没有原子操作的 for 循环……并且，如果没有这些，如果它们有一个可能达到也可能达不到的退出条件，这足以让它们不是 UB 吗？”
（观众）“因为它们可能会结束？”
（演讲者）“如果它们不结束，一个让你的程序挂起的实现是符合标准的。所以它们应该结束。实现会假设它结束。”
（观众）“所以任何同步原语都是一个步骤？”
（演讲者）“是的。是的。任何同步原语都是一个步骤。我们，我们，我们，我的意思是，我们确实把……在你程序的数万亿次操作中，我们把这个范围缩小到了，你知道的，几百或几千次，就是这些。当谈论前向进度保证时，其他所有东西，你都把它扔进一个盒子里，称之为 A，我不在乎它做什么。它可能是，你知道的，十亿行代码。不在乎。称之为 A。它是一个步骤。”
（观众）“这很有道理，因为在同步原语这一点上，我们就可以切换到下一个任务了。”
（演讲者）“没错。是的。因为我们知道至少在这一点上，我们是一致的。是的。”
（观众）“我的意思是，就像我们切换后不能有未定义行为。是的。是的。”
（演讲者）“这个未定义行为，我非常珍视。抱歉，Mike。我非常珍视。这种能力，这种允许做出非抢占式实现的许可。这非常重要。我认为对于 C++ 生态系统的多样性来说。所以，我对那篇论文有点不感冒，但它会被认真对待的。好的。”
我想谈谈与内存模型的交互。你知道，前向进度和内存模型是规范中两个独立的部分，但它们往往有点……而且它们没有很多分歧，但它们在很多地方有接触。
所以，第一个值得思考的是，进度既是数据竞争的原因，也是解决方案。如果你没有并发进行的任务，你就不会有数据竞争。同时，你用你的前向进度保证来构建同步，你用同步来消除数据竞争。哈。想想吧。想想吧。
另一件事是，标准中提到了两种“最终性”（eventuality）。标准说原子效应最终对其他线程可见。但是前向进度保证都是用“一个线程最终执行一个步骤”来定义的。那么，这两种最终性在任何方面可以被分开观察吗？我认为答案是否定的。如果我造了一台电脑，我发誓它给你最大进度，但它有一个无限大的缓存，可以无限期地持有原子效应，我想你可能会合理地得出结论，你没有前向进度保证，因为你永远无法观察到其他线程的效果。你知道吗？反过来，我可以造一台电脑，它能瞬间，零时间内让效果可见。光速的电线，没有缓存，连到无限速的 RAM。但我没给你前向进度保证。你的原子操作真的在零时间内到达内存了吗？你怎么能知道呢？感觉就像原子操作被拖延了。所以在 C++ 中有两种最终性，它们本质上是不可分割的。好的。好的。
接下来这件事更像一个缺陷，我想解释一下。在内存模型的世界里，有一个概念叫做“小强汽车旅馆”（roach motels）。等着瞧。它们本不应该是个问题。好的。但是标准没这么说。而且标准没有任何措辞来防止有问题的“小强汽车旅馆”。好的。那么什么是“小强汽车旅馆”？
首先，它是一个美国品牌的蟑螂陷阱。它们有一个广告语是：“小强住得进来，但它们出不去。”好的。在内存模型的行话里，“小强汽车旅馆”是这样的。我有一段非常简单的代码，里面有一个临界区。它以获取一个信号量开始，然后释放信号量结束。它有三个操作：A、B 和 C。临界区的真正含义是，B 的效果不能被重排到 acquire 之上，也不能被重排到 release 之下。acquire 和 release 的目的就是困住 B。好的。然而，你可以住进来。你出不去，但你可以住进来。A 和 C 可以移入临界区。好的。现在，对于计算来说，“住得进来，但它们出不去”。这就是“小强汽车旅馆”。
好的。如果我写这个程序呢？这个程序没有 bug。它没问题。我有两个信号量，有两个线程。一个 jthread 和 main。每个线程都释放一个信号量，然后等待另一个。这有并发进度，最大进度，所以这没问题。对吧？没问题。所以我把它表示成一个完全没问题的图。这里没有死锁。边不交叉。有效的程序。
现在，当你看“小强汽车旅D馆”的规则时，它说你可以把东西移到 release 上面，或者移到 acquire 下面，这里没有特殊规则说你不能对原子操作这么做。也没有特殊规则说你可以移动一个原子操作，或者你可以移动一万个原子操作，或者你可以移动不确定的，可能是无限数量的原子操作。所以，我可以像这样搞个“小强汽车旅馆”。然后当这个执行时，它活锁了。或者实际上是死锁了。
你知道，标准里没有任何措辞告诉实现者不要这么做。我为不止一个实现者工作过，我们不得不坐下来讨论，我们公司发布一个 C++ 的主要实现，我们到底该怎么办？然后我们在内部会表达一个规则，我们会说，我们只能在“假定隔离有限时间”的情况下进行优化。当你优化原子操作时，你必须想象一个理论，世界冻结了，这一个线程的操作作为一个原子单元不可分割地执行，然后世界解冻了。重要的部分是“有限”。当你有了那个规则，你就不能移动一个可能是无限数量的 acquire 操作。
（投影仪故障）
好的。现在好了。哦！你听到了吗？不，不，不。演讲者视图刚回来。我有你的幻灯片，只是等着投影仪把它们投出来。但是它们正在传给我。好了，我们继续。
所以当我们做了这个非法的“小强汽车旅馆”优化时，我们做的是移动了可能是无限数量的 acquire 操作。这是我们不应该做的。所以如果这里是 acquire 步骤。所以如果只是一个 load_acquire，一个 load_acquire，那没问题。一个 while (load_acquire != 42)，那就有问题了。好的。好的。
（观众）“为什么这被称为优化？”
（演讲者）“因为我们住进来了。所以当我们住进来时，锁的范围增加了。是的。”
（观众）“所以它不应该被称为优化。它就像……”
（演讲者）“不，它……问题是 A 和 C 可以被重排。而且如果它们……是的。是的，它们被重排了，但即使从外面看……是的，但如果有其他原子操作。嗯，原子操作的重排……有规则阻止原子操作的重排。那些规则会被遵守。但是有很多原子操作是可以被重排的。而且是的，所以……不，这是一个……这可能非常有利润。是的。它可能正在你的代码里发生。它让代码快了很多，而你不知道。是的。编译器可能对长内存延迟弧在哪里有一些概念……通过移动 acquire，更多的数据比……它可能达到50%……通过将 acquire 向上移动，它能够重叠内存延迟，你知道，结果它推断，当然，将数据 A 的加载移动到 acquire 下面实际上更好，只要它遵循所有其他规则，这是允许的。但是现在编译器需要知道 acquire 可能有这些无限数量的步骤，对吧？所以它需要理解语义。是的，嗯，所以通常它是不被允许的。通常如果它是一个外部函数，编译器不理解里面是什么，它就不会这么做。所以在很多情况下它不会。但是从抽象机的角度来看，你必须想象所有的代码都在同一个翻译单元里，它看到了所有东西，而那里的 acquire，就编译器而言，它只看到一个在 load_acquire 上的循环。这是它唯一看到的。嗯，好的。好的。我们快结束了。”
我们来简单谈谈无锁（lock-freedom）。无锁不仅仅是不包含互斥锁的程序，虽然这是其中一部分，它还包括使用无锁的原子操作。但这还不够。如果你使用的原子操作是无锁的，但表达的算法本身不是无锁的，那么你写的就不是严格意义上的无锁代码。而我说的“无锁”，是指它必须符合弱并行进度。如果你满足所有这三个条件，你写的才是无锁代码。
我真的不喜欢人们说“我在写无锁代码”，然后我看到一个循环，他们在轮询一个东西。是的，不，那不是。就像你没用互斥锁，很好。你可能用了本身每个独立步骤都是无锁的原子操作，但是那个循环，你落入了一个通常被称为“无饥饿”（starvation-free）的算法类别。
（观众）“所以大多数队列，无锁队列，都有那个 while 循环和那个 cas 条件。是的。那也不是……不不不，等一下。循环是在队列内部，比如，这取决于你的 pop 接口是什么。如果你的 pop 接口总是 try_pop，并且没有 pop，只有 try_pop，那么，还有 try_push，没有 push 没有 pop，只有 try_push try_pop，并且队列的实现里没有循环，那么这个队列是无锁的。你用它做什么可能仍然不是无锁的。比如你做 while (!push_try_push())。好的。你这里写的不是无锁代码。这段代码在弱并行下会失败，会活锁。因为你做了一个假设，它最终会成功。这是什么意思？这意味着最终某个其他线程产生了一个效果，使得这个效果成功。那个其他线程，你和它有什么前向进度关系？如果你们的关系是弱并行，那么记住那个黄色的虚线，调度器可以一直调度你的 try_push，而永远不调度另一个家伙的 pop。所以，无锁，严格来说，除了所有那些，还要符合弱并行。好的。”
（投影仪再次故障）
好的。当它显示在屏幕上时，我们会有一段代码，构建一个直方图。它在一个原子符号上无锁地构建直方图。所以它是无锁的。这没问题。这是无锁代码。我用的是无锁原子操作，而且我没有封闭循环。很好。好的。
除了……C++ 告诉我们，有时候无锁也不是无锁。为了节省时间，我不会让你们读所有这些。有这么一段含糊其辞的话说，嗯，有些使用“加载-锁定/存储-条件”（load-lock/store-conditional）的计算机，实际上如果所有线程都同时尝试加载-锁定，它们可能都无法成功。所以如果大家都在尝试做一个 fetch_add，计算机可能会卡在一个模式，谁也做不了 fetch_add，它只是在发热，无限期地产生热量。然后我们会说，那是符合标准的 C++。
现在这个属性不是无锁的。当 C++ 在那种计算机上说“无锁原子操作”时，实际的算法类别是“无阻碍”（obstruction-free）。然后如果你去读我之前提到的那篇论文《On the Nature of Progress》，你读到“无阻碍”的定义是，这些程序只有在存在一个“一致隔离历史”（uniformly isolating history）时才能工作。然后它说，你怎么做到呢？你用退避（backoff）。C++ 有这么一句含糊的话说，在你整个世界观里，可能根本没有无锁这种东西，一切都只是无阻碍的。你应该有退避循环。它没告诉你怎么做或者什么时候做。比如在这个 fetch_add 里，退避循环必须在 fetch_add 内部。我没写 fetch_add。所以，这有点棘手。我想可能未来某个时候，我们需要把这个收紧，然后说，看，从 C++ 开发者的角度看，他们不需要知道这个，这是实现者的工作去解决这个问题。祝你好运。
（观众）“这是一个答案吗？那是在 effect 内部吗？是的，嘿，那会在所有原子操作内部。如果你用加载-锁定/存储-条件试了很多次，你只是逐渐退避。是的。这不是处理器应该推动澄清的事情吗？是的，我“悬而未决的问题”部分的所有东西都像是嵌入式视角。是的，你需要知道这类事情，对吧？为什么？所以你可能无法……你可能无法满足你的要求。所以这在我看来，也可能会阻止人们在嵌入式世界里自信地使用 C++。是的，是的。我想，嗯，在嵌入式世界里，已经有一大堆你应该知道的零碎知识了。我想其中之一会是，在嵌入式领域，无阻碍就是你的无锁。你应该用 atomic_compare_exchange_weak 来表达一切，别的都别用，就用 atomic_compare_exchange_weak。然后在你所有的模拟中都有一个退避循环。那可能行得通。是的。是的。是的，我们应该澄清这个。我想当我们做的时候会是一场非常有趣的对话。嗯，好的。”
我们来快速谈谈 par_unseq 下的原子操作。我还没给你们看过在 par_unseq 下有原子操作的幻灯片，尽管原子操作技术上可以在弱并行进度下工作。原因在于，par_unseq 是弱并行进度并且是“无序的”（unsequenced）。如果你考虑标准的这一层，无锁原子操作不是 UB。它说“无序的写效应是 UB”。而这，默认情况下，我们没有写任何额外的措辞，就包含了原子操作，尽管在任何合理的实现上，无锁原子操作在 par_unseq 下都能正常工作。好的。所以我上一张幻灯片的那个例子，那个直方图的东西，它是无锁代码，因为它无锁，所以在弱并行进度下是安全的。所以原则上这应该能工作。但你必须在那里用 par，而不是 par_unseq。
结果就是，我们该怎么办呢？我们应该允许 par_unseq 下的原子操作吗？我们应该创建一个 par_weak，它只是弱并行进度但不是无序的吗？我有个想法，我们可以引入一个内存顺序，它对你能做什么有非常大的限制。比如你不允许用它来同步。然后说只有那个在 par_unseq 下是允许的。所以你可以写归约，直方图字面上就是。在所有这些情况下，你都在写一个原子操作，但你从不从另一个……是的，从另一个……没错。是的。是的。就像一个想法，你稍后在你的程序中通信，在你……是的。就像你有并发效应，但你只对最终效应感兴趣。是的。是的。好的。
简单说一下魔法静态变量（magic statics）。魔法静态变量是那些有初始化器的静态变量，并且它们在并发上下文中使用。我在这张幻灯片上没有放红叉。意思是，这个在 par_unseq 下的静态变量，根据标准的字面意思，是允许的。然而，如果我用 call_once 重写它，并且有和编译器为魔法静态变量生成的完全相同的代码，但现在我用的是 call_once，那是不允许的。而且我认为 par_unseq 的实现实际上在有魔法静态变量的情况下不能正确工作。是的，是的，它是同步。所以，魔法静态变量真的被允许吗？标准说……然后……
关于 执行线程（threads of execution） 有很多不清楚的地方。所以，什么是执行线程？早些时候我用的定义是“从顶层调用开始的控制流”。定义 A 是我最喜欢的对执行线程的定义。我们应该在所有地方都用这个。然而，标准里有些句子把执行线程等同于完整的线程，std::thread，jthread，和运行 main 的线程。里面确实有那么一句话说，你知道，它们是相同的。但是从 C++17 开始它们就不再相同了。而且它们有很多我们可能想要记录的有趣属性。好的。我快速过一下那些我们可能想谈论的属性。如果原子操作被允许，比如在 par_unseq 下，它们就重要得多。只要原子操作不被允许，你无法通信，呃，这些属性有些就不太重要了。但是一旦它们被允许，而且在 par 下它们是被允许的，这就很重要了。
所以这里有一个小的试金石，我从环境中获取线程 ID。我会得出结论说我的执行线程得到了不同的线程 ID 吗？不，我不会。首先因为我把它们按顺序放到了工作线程上，我会得到工作线程的线程 ID。所以是的，一些任务会得到相同的线程 ID，即使只是因为这个原因。但是如果它们通过原子操作通信，它们可能同时得到相同的线程 ID。尤其是在谈论 par_unseq 时，如果 par_unseq 把我的任务调度到了向量通道上，多个任务会同时得出结论，它们有相同的线程 ID。好的。
同样地，线程局部变量（thread locals），和线程 ID 一样。线程 ID 在某种程度上只是一个特殊的线程局部变量。所以所有的线程局部变量，它们可能都有同一个。当人们使用线程局部变量时，这可能是个大问题。他们被允许做的一个假设是，“我不会在这个东西上和其他线程有数据竞争”。嗯，在 par_unseq 下，你可能会。同样，在 par_unseq 下，它可能根本就不能工作。可能访问那个线程局部变量会让你的实现崩溃。好的。
栈指针（stack pointers） 呢？栈指针非常有趣，因为在很多基于 SIMD 或者在 GPU 上的实现中，栈是以完全不同的格式布局的。不是说我有一个地址，然后是一组线性的位置，我的数据就写在那里。相反，它被交错存放了。所以，通道 0 得到一个字，然后通道 1 得到一个字，通道 2 得到一个字，然后重复。对吧？编译器知道地址分配，所以编译器让你的代码正常工作。它甚至可能让它在有指针的情况下也能正常工作。但当你把一个指针在任务间传递时，它可能就不工作了，因为另一个任务不知道如何解释你的指针。你的指针只在你的上下文中有意义。好的。所以，逃逸的栈指针在 C++ 中可用吗？有一段话说，是的，在 C++ 中，你可以取栈上任何东西的地址，并与别人分享。好的。
所以，关于这些悬而未决的问题，需要明确的是，我欢迎大家就这些问题写论文。是的。而且我认为，我认为这里还有相当多的工作要做。我们可以有一个非常棒的 C++ 版本，专门为 SG1 修复这些问题，别的什么都不做。嗯，好的。
总结¶
你的代码在线程中运行。
这些线程在一个调度器上运行。
调度器对你的线程做出保证。
保证不止一种，不只是最大保证。
这些保证是：
并发前向进度 (Concurrent Forward Progress)：这是最大进度。这是你总是想假设拥有的。你从完整线程（
std::thread/jthread）和运行main的线程（在托管实现中）那里得到它。并行进度 (Parallel Progress)：我看不到……我不能保证我会启动多少个任务，但如果你阻塞它，我至少会启动一个。并且那些启动了的任务，它们将拥有最大进度直到完成。
弱并行进度 (Weakly Parallel Progress)：它把你所有的任务打包成一个袋子，然后最终在那个袋子里执行一个步骤。
好的。并且，记录你的代码假设了哪种进度是非常重要的。如果你在写一个库，尤其如此。你需要……你需要告诉开发者你假设底层是什么，以及他们可以在上层做什么样的假设。对吧？不，这个问题在于，这是……这是……这是一个关于程序所处的“环境以太”的假设，你知道吗？它不会出现在代码里。它不是静态可检查的。
（观众）“我们可以把它做成一个属性，比如函数 peg 系统的一部分。”
（演讲者）”你……你……你可以想象把它 Rust 化。是的。就是基础函数说它们假设什么进度，然后函数……所有东西都构建起来。是的。但是在 C++ 或 C 里，不行。是的。好的。”
谢谢大家。