PDF结构化延后：通过延后实现同步
我们根本没有可以强制互斥的同步机制。
Paul E. McKenney，IBM
开发者通常对软件设计采取积极主动的方法，尤其是那些来自重视勤奋胜过拖延的文化的人。然而，懒惰的方法已经证明了它们的价值，例如引用计数、垃圾回收和惰性求值。这种结构化延后采取了通过延后实现同步的形式，具体而言是引用计数、危害指针和RCU（读取-复制-更新）。
通过延后实现同步可以追溯到H. T. Kung和Philip Lehman 1980年的论文12，而亨利·马萨林在1992年阐述了其一般原则13。尽管这些想法已经在生产中使用了几十年9，但对许多人来说仍然陌生。本文通过下一节中描述的一个奇特的例子，介绍结构化延后。
动机示例
在这个例子中，薛定谔想构建一个内存数据库来跟踪他的动物园里的动物。出生当然会导致插入数据库，而死亡会导致删除。数据库也接受那些对薛定谔动物的健康和福祉感兴趣的人的查询。
薛定谔有许多短寿的动物，如老鼠，导致更新率很高。此外，人们对薛定谔的猫的健康状况有着惊人的兴趣19，以至于薛定谔有时怀疑是否是他的老鼠导致了大部分的查询。无论其来源如何，数据库都必须处理大量的与猫相关的查询，而不会遭受过度的争用水平。访问和更新通常都很短，涉及访问或改变内存数据结构，因此同步开销不容忽视。
然而，薛定谔也明白，不可能准确地确定给定动物的出生或死亡时间。例如，假设他的猫的死亡是通过心跳检测到的。需要几秒甚至几分钟才能确定这只可怜的猫的心脏实际上已经停止跳动。测量间隔越短，测量的不确定性就越大，因此两位检查猫的兽医可能会在死亡发生的准确时间上产生分歧。例如，一位可能会在最后一次心跳后30秒宣布死亡，而另一位可能会坚持等待整整一分钟，在这种情况下，兽医们在最后一次心跳后的半分钟内对猫的状态意见不一。
幸运的是，海森堡8教会了薛定谔如何应对这种不确定性。此外，检测到猫的死亡的延迟允许使用通过延后实现同步。毕竟，考虑到两位兽医宣布死亡的时间相隔整整30秒，那么软件延后额外的几毫秒是完全可以接受的。
下一节将通过引用计数来说明通过延后实现同步，使用这种广为人知的机制来演示结构化延后的一些不太熟悉的特性。
引用计数
薛定谔动物园的一个简单解决方案是在哈希表中每个动物的数据元素中放置一个引用计数器，并通过链式处理冲突。读者在访问动物的数据元素之前原子地增加引用计数，并在之后原子地减少引用计数。这仅在读者和更新者之间提供同步；更新者必须使用其他机制（如锁、非阻塞同步或事务内存）在彼此之间进行同步。
图1显示了移除与薛定谔可怜的猫对应的数据元素的四状态过程。初始状态（1）显示了哈希表的一个链，代表薛定谔的蟒蛇、猫和角马。正如每个框的红色所指示的那样，任何数量的读者都可能正在引用这些数据元素；因此，必须小心地执行更新以避免干扰这些读者。为了过渡到状态2，更新者将指向角马数据元素的指针存储在->next蟒蛇数据元素的指针中。这种存储必须是原子的，即任何并发的读者必须看到旧值或新值，而不是两者的混合。这种存储可以使用C11/C++11宽松原子变量2或在旧的C/C++编译器中使用volatile强制转换3来执行。请注意，猫的->next指针继续引用角马的数据元素，以容纳仍在引用猫的读者。
从此时起，没有通往猫的数据元素的路径（用黄色表示），因此新的读者无法访问它。一旦猫的引用计数达到零，过渡到状态3，所有引用猫的数据结构的读者都已释放了他们的引用，用猫的框的绿色表示。由于仍然没有通往猫的数据元素的路径，新的读者仍然无法获得引用，因此现在可以安全地过渡到状态4，通过释放已故猫的数据元素。
因此，尽管存在并发的读者，这一系列状态转换已安全地从哈希表中移除了猫的数据元素。然而，仍然存在过时引用的问题，更不用说正确性和性能了。这些将在以下章节中讨论。
过时引用
在状态2中，旧的读者仍然可以持有对猫的数据结构的旧引用，但新的读者无法获得引用。因此，这些并发的读者可能对猫是否仍然活着存在分歧，就像例子中的兽医存在分歧一样。因此，这种分歧不是错误，而是对外部现实的忠实反映。
在其他情况下，可以检测和拒绝分歧。例如，如果对给定数据元素的访问和更新受到互斥的保护，则“已删除”字段将允许读者通过表现得好像搜索失败来拒绝已删除的数据1。
最后，假设一个算法使用常见的习惯用法，即在持有锁时做出决定，然后在释放锁后依赖该决定。实际上，该算法依赖于过时的信息，因为另一个CPU可能会获取锁并更改做出决定的数据——而第一个CPU仍然依赖于其现在过时的决定。
为了了解这种习惯用法的工作原理，请考虑一个网络堆栈，它获取一个锁，做出路由决定，传输一个数据包，释放锁，然后更新统计信息。因为统计信息需要反映您实际发送数据包的位置，而不是如果您等待可能会发送的位置，所以使用“过时”的数据实际上是正确的。此外，在大多数情况下，软件实际上并没有传输数据包，而是导致硬件将数据包排队以供稍后传输。在硬件实际传输数据包时，路由决定很可能已经改变。更糟糕的是，一个数据包从其源头传输到遥远的目的地可能需要数百毫秒，这为路由决定的改变提供了更多的机会。因此，在持有锁时做出路由决定，然后在传输数据包之前释放锁是合理的——或者使用通过延后实现同步。
此外，检测硬件故障通常需要相当长的时间，导致一段时间内不确定硬件是否已发生故障。此外，许多更新都有很宽的时间窗口——例如，监管变更可能需要在90天内进行安全配置更新。在这两种情况以及许多类似的情况下，更新期间额外的几毫秒软件延后是完全可以接受的。事实上，软件延后可以使读者更快地意识到外部变化16（参考文献#16中的图17），从而减少响应时间。
简而言之，当与外部状态交互时，通过延后实现同步尤其有用。
正确性和性能
不幸的是，幼稚地使用引用计数器会导致几个问题。第一个问题是删除和读取端引用获取之间的竞争。为了说明，假设一个读者在图1的第一个状态中获取了蟒蛇的->next指针，然后被抢占。在这个读者恢复之前，更新者按顺序执行了图中的其余状态。当读者恢复时，它将原子地增加曾经是猫的引用计数器的值，但现在可能完全是其他东西，从而破坏应用程序的状态。可以通过基于比较和交换的复杂方案来避免这个问题21（由Maged Michael和Michael Scott18纠正），但这会导致糟糕的性能7。避免这个问题的另一种方法是使用垃圾回收器，以便猫的数据结构在其被引用的时间内持续存在。
如果没有垃圾回收器，另一种方法是对整个哈希链而不是单个数据元素进行引用计数。这适用于固定大小的哈希表，但如果哈希表可以调整大小，则会陷入类似的竞争条件。理论上，可以使用覆盖整个哈希表的全局引用计数器来处理调整大小，但在实践中，这增加了并发读者的连续流阻止计数器永远达到零的可能性。如果计数器永远达不到零，则无法释放从哈希表中删除的数据元素，最终导致内存耗尽而失败。
此外，如图2所示，单个变量的原子递增根本无法扩展：跨线程引用可能非常昂贵，因为电子的速度不是无限快的。如果单个线程尝试原子地递增一个变量，则在Intel Xeon Westmere-EX系统上的成本对于单个线程约为10纳秒，对于64个线程则上升到约2,500纳秒（线条斜率的变化是由硬件多线程引起的）。这意味着对于单个线程，访问次数从约1亿次下降到64个线程的约40万次。这不是薛定谔所需的可扩展性。
解决这些问题的两种方法是危害指针和RCU，这将在接下来的两节中讨论。另一种方法称为代理收集器（http://atomic-ptr-plus.sourceforge.net/），它分摊了引用计数开销，但不在本文的讨论范围之内。
危害指针
危害指针背后的关键见解是，引用计数器可以在内部实现。与其递增与给定数据元素关联的整数，不如在每个线程的危害指针列表中记录指向该数据元素的指针。给定数据元素的指针在这些列表的串联中出现的次数就是该元素的引用计数。当要释放数据元素时，释放操作将被推迟，直到没有危害指针引用它为止。批量处理释放操作，以最大限度地减少对危害指针的昂贵的跨线程引用17（其他人独立发明10，并可从多个来源获得，包括http://concurrencykit.org/）。
由于危害指针是线程本地的，因此它们避免了许多引用计数器实现所面临的性能和可扩展性问题7。它们还避免了刚刚描述的竞争条件，这可以在hp_acquire()图3的第1-14行中看到。这里的关键点是需要分配危害指针（第3行），需要避免竞争条件（第9行的重新加载和检查），以及需要击败编译器代码移动优化。编译器代码移动通过ACCESS_ONCE()在第6、7和9行上解决，它可以实现为volatile强制转换或C11/C++11 volatile宽松原子加载和存储。编译器和CPU代码移动通过第8行的内存屏障解决，它阻止重新排序第7行上的先前存储与第9行上的后续加载，因此即使在相对强排序的系统（如x86）上也是必需的。第11行的NULL返回信号通知调用者必须从头开始重新启动危害指针遍历。所有这些加在一起确保更新者将正确查看危害指针的状态。
释放危害指针很简单：只需将其设置为NULL，要么在前面加上内存屏障，要么使用C11/C++11 store-release操作；然后释放它以便可以重用，如hp_release()在图3的第16-21行中所示。hp_release()函数的唯一参数是由hp_acquire().
大多数使用显式引用计数编写的程序都可以轻松转换为使用hp_acquire()和hp_release()。但是，只需要固定数量的危害指针的算法可以静态分配它们，从而避免了hp_alloc()和hp_free的动态分配的开销，如hp_record()在图3的第23-35行中所示。请注意，这种方法在给定危害指针被重用之前不会释放该指针。在最坏的情况下，这种方法会阻止少量固定内存被释放，这通常是无害的。尽管有些算法需要无限数量的危害指针，但许多数据结构的简单搜索和遍历最多需要两个危害指针。
危害指针在许多情况下都非常有效，但它们确实存在一些缺点。
• 重试和内存屏障会导致性能下降。
• 如果需要危害指针保护链接结构中的一大组数据元素，则必须为每个数据元素获取单独的危害指针。
• 获取危害指针需要内存，这必须进行管理。尽管Michael17使用的静态分配策略在小型程序中对于某些类型的数据结构效果良好，但通常需要分配和释放。
• 危害指针不提供在释放内存时采取额外操作的规定——例如，关闭与给定数据元素关联的线程或硬件。
• 最后，在一般情况下，代码必须跟踪危害指针并在不再需要时显式释放它们。
其中一些缺点是危害指针的优势所固有的，其中包括非阻塞更新、强排序属性和减少的内存开销7。然而，在操作系统内核和大型应用程序中，危害指针的缺点可能超过其优点。下一节介绍了一种替代设计，该设计解决了这些缺点——尽管牺牲了危害指针的一些优点。教训是，为工作选择合适的工具！
读取-复制-更新
目标是生成一种引用计数方案，该方案（1）具有低（最好为零）开销；（2）在获取引用时不需要内存分配；（3）可以通过单个操作保护任意数量的数据元素；（4）允许在释放给定数据元素之前采取其他操作。满足这些目标的一种机制是RCU（读取-复制-更新）16。
为了确保实现低开销的目标，让我们将获取引用（rcu_read_lock()）和释放引用（rcu_read_unlock()）定义为不生成任何代码的空操作，从而实现最佳的性能、可扩展性、实时响应、无等待自由和能源效率。这种公认非常规的方法还具有免除内存分配的额外好处。鉴于rcu_read_lock()和rcu_read_unlock()不接受任何参数，它们无法指定特定的数据元素，因此它们也满足了保护所有数据元素的第三个目标。
怀疑论者可能会争辩说，如果rcu_read_lock()和rcu_read_unlock()不生成任何代码，它们就不能影响机器状态，因此不可能充当同步原语。尽管如此，让我们继续前进：毕竟，只有那些走得太远的人才有可能知道他们能走多远。
图1显示了如何从链表中删除元素，尽管存在并发读者，这表明薛定谔不需要互斥。然而，从状态2到状态3的过渡需要等待所有预先存在的读者完成。因此，挑战在于实现一个等待预先存在的读者的操作，即使rcu_read_lock()和rcu_read_unlock()不生成任何代码。
为了克服这个挑战，让我们首先考虑非抢占式软件环境，其中给定的线程继续执行，直到它自愿放弃CPU。非抢占式软件环境的示例包括使用CONFIG_PREEMPT=n构建的Linux内核、DYNIX/ptx和众多嵌入式系统。这种类型的环境可以强制执行一个约定，即如果线程已执行rcu_read_lock()但尚未到达匹配的rcu_read_unlock()，则禁止该线程放弃其CPU。（当持有纯自旋锁以避免死锁时，也需要相同的约定。）这样的线程被称为处于RCU读取端临界区。就像引用计数和锁定一样，如果在给定的RCU读取端临界区内获得了对给定数据元素的引用，则必须在退出该区域之前删除该引用，除非该数据元素已移交给其他一些同步机制。
现在假设更新者线程希望从图1中的状态2过渡到状态3，看到CPU 0执行上下文切换操作。鉴于RCU读者必须避免放弃他们的CPU，这种上下文切换意味着CPU 0之前的所有RCU读取端临界区都已完成——换句话说，CPU 0处于静止状态。此外，在CPU 0上运行的后续读者无法获得对薛定谔猫的引用，因为不再有通往猫的路径。因此，一旦更新者观察到每个CPU上的上下文切换，就不再可能有任何读者引用猫——换句话说，宽限期将已经过去。
这种延后程序封装在RCU原语synchronize_rcu()中，其最简单的实现只是依次在每个CPU上运行，从而确保每个CPU至少执行一次上下文切换。synchronize_rcu()的操作如图4所示，其中每个水平双端箭头表示一个RCU读取端临界区，从rcu_read_lock()开始，到rcu_read_unlock()结束，其中每个圆圈表示上下文切换。运行在CPU 3上的更新者首先使用rcu_assign_pointer()删除猫的元素，然后调用synchronize_rcu()为了等待每个CPU执行上下文切换，从而保证所有可能持有对猫的引用的预先存在的读者的完成。一旦synchronize_rcu()完成，更新者可以自由执行所需的任何其他操作（例如，关闭关联的线程或硬件），然后释放元素。生产质量的实现还提供了一个异步的对应物，call_rcu()，它在宽限期结束时调用指定的函数。在宽限期的早期，CPU很可能对猫的状态意见不一，这对于薛定谔的猫来说是恰如其分的。
简而言之，rcu_read_lock()和rcu_read_unlock()不影响机器状态，但它们不需要这样做。相反，它们作用于开发者，开发者需要遵循RCU读者不得释放其CPU的约定。因此，这种形式的RCU可以被认为是通过社会工程实现的同步。（其他同步机制也依赖于社会工程；例如，禁止数据竞争和保护给定对象所有使用的特定锁。）
“教科书式”的RCU实现非常简单，可以从图5的20行代码中看出。此外，在SC（顺序一致性）环境中，只需要rcu_read_lock(), rcu_read_unlock()和synchronize_rcu()，仅由九行代码组成。生产质量的实现规模更大，以满足严格的性能、可扩展性、响应时间和能源效率要求。用户模式RCU实现4以及可抢占内核实现5也可用。（完整的Linux内核RCU实现超出了本文的范围14。）
然而，由于没有主流计算系统是SC，因此在获取RCU保护的指针时必须使用rcu_dereference()，在改变RCU保护的指针时必须使用rcu_assign_pointer()。在SC系统中，rcu_dereference()和rcu_assign_pointer()分别简化为简单的加载和存储。在C11/C++11中，rcu_dereference()是加载-消费，rcu_assign_pointer()是存储-释放。图6显示了根据RCU原语的删除过程。
因此，RCU实现了其低开销、读取端内存分配避免、任意大的保护范围和对清理操作的支持的目标。当然，没有免费的午餐：这些目标的代价是放弃了危害指针的非阻塞、有界内存和排序属性。然而，如图7所示，RCU在Linux内核中仍然被大量使用。尽管如此，RCU是专门化的，因此锁定的使用频率大约比RCU高一个数量级。
比较
本节简要概述了危害指针和RCU在薛定谔动物园中的性能，基于该示例提供了定性和定量的比较。接下来是一些经验法则，有助于确定何时使用通过延后实现同步。
定性比较
表1比较了危害指针和RCU的属性，表明这两种同步机制代表了不同的设计要点
• 每个优势都与相应的劣势内在地交织在一起。危害指针相对于RCU的有界内存开销优势要求开发者为读者遍历的每个数据元素仔细获取危害指针。这构成了相对于RCU的能够通过单个rcu_read_lock().
保护所有数据元素的相应劣势。
• 类似地，危害指针的非阻塞优势（与有界内存相结合）要求更新者强制并发的危害指针读者重试其危害指针获取。这种重试构成了相对于RCU的相应劣势。
• 最后，危害指针的线性一致性优势需要在危害指针获取期间进行读取端内存屏障。由此导致的读取端性能降低构成了相对于RCU的相应劣势。（关于线性一致性是否普遍有用，存在一些争论6,22。）
其他差异似乎是实现选择，而不是底层机制的固有属性。例如，危害指针不提供在最终回收给定数据元素时调用清理操作的方法。这排除了关闭可能与该数据元素关联的硬件、线程或其他活动组件。然而，如果需要，可以增强危害指针的机制以提供类似RCU的清理操作的可能性。当然，提供清理操作会带来其他后果，包括禁止在遍历后不立即清理危害指针的常见用法模式。如果没有清理操作，这种用法模式是无害的，因为它只是保留了少量本来可以释放的内存。然而，在存在清理操作的情况下，这种用法模式可能会无限期地延迟清理，这将产生可能不可接受的副作用，即阻止重用相应的硬件或线程数据。
当前危害指针的实现仅在释放结构时记录结构的开头，当指针引用嵌套在其他结构中的结构时，会导致困难。这种嵌套在某些环境中非常常见，包括Linux内核。然而，扩展危害指针以处理内部指针非常简单：在释放结构时，您应该传递其大小以及其地址，从而允许正确处理指向该结构内部的危害指针。
由于危害指针仅引用特定结构，因此必须通过从头开始重新启动读取端遍历来处理与更新的竞争。这种重新启动的需求源于这样一个事实，即一旦结构被移除，更新不再更改从该结构发出的指针，因此这些指针不再可信。
对于简单的数据结构，重新启动遍历很简单，但对于具有深度嵌套的访问函数或方法的大型多链接结构，可能会构成重大的软件工程挑战。由于本文侧重于带有链式的简单哈希表，因此它不探讨这些问题。也许可以使用支持异常的语言中的异常来方便地重新启动遍历。
简而言之，危害指针和RCU之间的选择取决于工作负载的需求，包括程序中使用的其他同步机制。例如，如果程序受到内存限制，那么危害指针可能是正确的选择。相反，如果程序使用具有深度嵌套的访问函数或方法的大型多链接结构，那么RCU可能是正确的选择。
定量比较
本节介绍在受单个全局锁、每个桶锁、危害指针和RCU保护的固定大小哈希表上运行的基准测试结果。测试是在具有32个内核（64个硬件线程）的Westmere-EX x86系统上运行的，频率为2 GHz。为了便于比较，危害指针更新使用每个桶锁定进行保护。通过为每个线程提供自己的CPU来避免阻塞。
这些测试使用了来自liburcu4的基于信号的RCU变体（在许多最新的Linux发行版上可用，包括Debian、Fedora、OpenSUSE和Ubuntu）。这比前面描述的零成本（QSBR）实现要慢，但零成本实现要求每个线程定期处于静止状态。由于并非所有应用程序都以满足此要求的方式构建，并且由于危害指针不需要任何特定的应用程序结构，因此公平性决定了这些测试中使用的RCU实现也不需要任何特定的结构。为了进行比较，QSBR RCU实现的性能比基于信号的RCU实现大约好10%。
由于哈希表是简单的链接结构，因此危害指针是静态分配的，并且没有显式释放，从而消除了分配、释放和释放操作的开销。薛定谔认识到其他算法和数据结构可能需要动态分配的危害指针，这将降低它们的性能。
图8显示了仅查找测试的结果，该测试针对具有简单整数键的哈希表。此哈希表具有1,024个带有链式的桶，并且在总共2,048个元素中包含1,024个元素。随机选择查找键，以便一半的查找成功。正如预期的那样，全局锁定的性能非常差。每个桶锁定（bkt）线性扩展到大约八个CPU，然后由于随着CPU数量相对于哈希桶数量的增加，锁定和内存争用增加而下降。正如预期的那样，增加桶的数量会带来更好的可扩展性和性能。危害指针（hazptr）和RCU都几乎以极好的性能线性扩展。
图9在线性尺度上绘制了相同的数据，更清楚地显示了RCU和危害指针与每个桶锁定相比的性能和可扩展性优势。还要注意RCU在32个CPU处的拐点：危害指针比RCU更好地利用了该特定系统的双线程硬件。（使用32个或更少CPU的运行在每个核心上运行一个线程，而使用更多CPU的运行在每个核心上运行两个线程。）尽管如此，RCU在60个CPU时享有14%的性能优势，在32个CPU时享有23%的性能优势。
图10显示了薛定谔内存数据库原型的只读性能，这是一个具有1,024个桶的哈希表，带有链式，使用最多31个字符的ASCII字符串作为键。结果与整数键哈希表的结果相似，只是由于更重的键操作，RCU相对于危害指针的优势降至32个CPU时的约8%和60个CPU时的零。
图11显示了对于60个CPU，增加访问薛定谔猫的查询比例的效果。正如预期的那样，全局锁定在整个过程中表现不佳。每个桶锁定的有效性因包含猫的哈希桶上的争用级别增加而降低。当超过约50个CPU执行与猫相关的查询时，下降变得灾难性的。RCU的吞吐量不受与猫相关的查询比例的影响，但危害指针的吞吐量随着与猫相关的查询比例的增加而降低，范围从与RCU持平到大约25%的性能损失。这种下降是危害指针所需的内存屏障的结果。删除这些内存屏障可以恢复与RCU的性能均等性，但也导致了不安全的危害指针实现。这种行为提出了一个假设，即当多个CPU访问相同的内存位置时，内存屏障更昂贵，这似乎是合理的，因为访问不相交内存位置的CPU无法检测到彼此的内存访问顺序。
图12显示了与图11相同运行中获取的数据，但仅显示了与猫相关的查询的吞吐量。全局锁、危害指针和RCU结果按预期扩展：尝试的与猫相关的查询越多，完成的查询就越多。每个桶锁定表现不佳，因为随着尝试的与猫相关的查询数量的增加，猫的哈希桶上的争用也随之增加。因此，在超过约20个CPU时，每个桶锁定的性能与全局锁定相似。
当然，薛定谔需要进行更新。表2显示了包含15个线程进行更新、15个线程查询猫和30个线程查询随机动物的测试结果。所有数字都是每毫秒的事件数，与之前的数字一致。尽管猫在此测试期间始终存在，但其他动物是随机添加和删除的，因此在任何给定时间任何给定动物存在的概率为50%。因此，预计50%的非猫查询会失败，这里的情况就是这样。
正如预期的那样，全局锁定的性能很差。每个桶锁定的性能比危害指针低三倍，而危害指针的性能又比RCU低两倍。相比之下，更新（添加和删除）从每个桶锁定到危害指针减慢了10%，又从危害指针到RCU减慢了50%。这并不意外，因为危害指针和RCU都有意牺牲更新性能以换取读取端性能。与每个桶锁定相比，读取端性能的提高远大于更新端性能的降低。
这确实提出了一个问题，即每个桶锁定和危害指针的低读取端性能实际上是否是由其更快的更新速率引起的。因此，额外的测试将每个桶锁定和危害指针更新速率限制为RCU的更新速率。每个桶锁定读取端吞吐量确实响应于更新端锁争用的减少而增加，但仅增加到每毫秒约17,000次更新，这远不及危害指针的每毫秒41,011次读取，更不用说RCU的每毫秒85,906次读取（零成本RCU实现了大约每毫秒100,000次读取）。危害指针读取端吞吐量对于限制的更新速率没有显着变化。
危害指针和RCU的吞吐量都比图10所示的只读工作负载低得多。这是因为更新导致读取端缓存未命中，从而降低了吞吐量。
本节中的数据清楚地表明，通过诸如危害指针和 RCU 等拖延机制进行同步，可以显著提高读取侧的性能。RCU 的更新侧性能优势已在其他地方得到证明。4
何时应拖延？
尽管危害指针和 RCU 的读取侧性能优势可能非常显著，但这些都是专门的机制，通常与其他机制结合使用。这就引出了一个问题，即何时应使用它们。Linux 内核15 中 RCU 的广泛使用促成了以下经验法则，这些法则也可能适用于危害指针：
1. 拖延在读取为主且读者之间允许存在分歧的情况下效果极佳。“读取为主”的具体构成取决于工作负载，但 90% 读取对 10% 更新是一个不错的经验法则。
2. 拖延在读取为主且读者必须始终达成一致的情况下效果相当好。
3. 在读取和更新数量大致相等且读者必须达成一致的情况下，拖延有时效果良好。
4. 在更新为主且读者必须达成一致的情况下，拖延很少能很好地工作。目前已知此规则有两个例外：（1）为更新友好的机制提供存在性保证，以及（2）为实时使用提供低开销的无等待读取侧访问。
请注意，读取的传统定义可以推广到包括写入。薛定谔应用程序中的一个例子是，如果每个动物的数据结构都包含一个按线程缓存对齐的变量数组，用于计算对该动物的访问次数，从而使薛定谔能够评估他的猫的受欢迎程度。这是可行的，因为这些读取侧的写入不会冲突。进一步的推广不仅是可能的，而且在实践中也被大量使用——例如，允许受其他同步机制保护的冲突写入。1 这是允许的，因为引用计数器、危害指针和 RCU 都允许在其读取侧临界区中使用范围广泛的代码，包括原子操作、事务和锁定。
薛定谔的应用程序允许读取的传统定义，因此属于第一条经验法则。因此，它非常适合通过拖延进行同步。随着经验的积累，这些规则将继续完善。特别是，更新密集型情况需要更好的机制，并且在该领域已经有一些有希望的进展。11,20 最后，表 1 可能是选择危害指针和 RCU 之间经验法则的第一步。
结论
本文概述了通过拖延进行同步，讨论了一些后果，例如关于当前状态的读取侧分歧，以及这些后果如何真实地反映计算机外部的现实。这是可以预期的：根本没有任何同步机制可以对物理宇宙的任何重要部分强制执行互斥。在过去的几十年中，此处描述的两种流行的拖延机制（危害指针和 RCU）的使用有所增加，并且随着多核系统的使用增加，预计还会进一步增加。
致谢
我感谢 Steven Rostedt 将 RCU 比作薛定谔的猫（https://lkml.org/lkml/2013/3/29/248）；感谢 Maged Michael 就危害指针和 RCU 进行了多次富有成果的讨论；感谢 Arjan van de Ven、Peter Sewell 和 Susmit Sarkar 就并发和内存排序进行了讨论。我感谢 Samy Al Bahra、Eduardo Bacchi Kienetz、Seth Jennings、Wade Cline、Mathieu Desnoyers、Ram Pai、Kent Yoder 和 Phil Estes 帮助使本文更具可读性。我感谢 Jim Wasko 对这项工作的支持。
法律声明
这项工作代表了作者的观点，不一定代表 IBM 的观点。Linux 是 Linus Torvalds 的注册商标。Intel 和 Xeon 是 Intel Corporation 的注册商标。
其他公司、产品和服务名称可能是各自公司的商标或服务标志。
参考文献
1. Arcangeli, A., Cao, M., McKenney, P. E., Sarma, D. 2003. 在 Linux 2.5 内核中使用读取-复制更新技术进行 System V IPC。载于 2003 Usenix 年度技术会议论文集：297-310。
2. Becker, P. 2011. C++ 编程语言标准工作草案；http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf。
3. Corbet, J. 2012. ACCESS_ONCE(); http://lwn.net/Articles/508991/。
4. Desnoyers, M., McKenney, P. E., Stern, A., Dagenais, M. R., Walpole, J. 2012. 读取-复制-更新的用户级实现。IEEE 并行与分布式系统汇刊 23: 375-382。
5. Guniguntala, D., McKenney, P. E., Triplett, J., Walpole, J. 2008. 用于在 Linux 共享内存多处理器系统上支持实时应用程序的读取-复制-更新机制。IBM 系统杂志 47(2): 221-236。
6. Haas, A., Kirsch, C. M., Lippautz, M., Payer, H. 2012. 你的并发 FIFO 队列有多 FIFO？载于 2012 年 放松多核和众核可扩展性同步研讨会论文集。
7. Hart, T. E., McKenney, P. E., Brown, A. D., Walpole, J. 2007. 无锁同步的内存回收性能。并行与分布式计算期刊 67(12): 1270-1285。
8. Heisenberg, W. 1927. 量子理论运动学和力学的直观内容。Zeitschrift für Physik 43(3-4): 172-198。英文翻译见《量子理论与测量》。J. A. Wheeler 和 W. H. Zurek 编辑，普林斯顿大学出版社，1984 年。
9. Hennessy, J. P., Osisek, D. L., Seigh II, J. W. 1989. 多任务环境中的被动序列化。美国专利 4,809,168（已失效）。
10. Herlihy, M., Luchangco, V., Moir, M. 2002. 重复违规者问题：一种支持动态大小的无锁数据结构的机制。载于第 16 届国际分布式计算会议论文集：339-353。
11. Jacobi, C., Slegel, T., Greiner, D. 2012. 事务内存：IBM System z 的架构和实现。第 45 届年度 IEEE/ 国际微架构研讨会；http://www.microsymposia.org/micro45/talks-posters/3-jacobi-presentation.pdf。
12. Kung, H. T., Lehman, Q. 1980. 二叉搜索树的并发操作。 数据库系统汇刊 5(3): 354-382。
13. Massalin, H. 1992. Synthesis：基本操作系统服务的高效实现。博士论文，哥伦比亚大学，纽约州，纽约。
14. McKenney, P. E. 2010. RCU API；http://lwn.net/Articles/418853/。
15. McKenney, P. E., Boyd-Wickizer, S., Walpole, J. 2013. Linux 内核中 RCU 的使用：十年之后；http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf。
16. McKenney, P. E., Slingwine, J. D. 1998. 读取-复制-更新：使用执行历史解决并发问题。载于 并行与分布式计算系统：509-518。
17. Michael, M. M. 2004. 危害指针：无锁对象的安全内存回收。IEEE 并行与分布式系统汇刊 15(6): 491-504。
18. Michael, M. M., Scott, M. L. 1995. 无锁数据结构的内存管理方法校正。技术报告 TR599，罗切斯特大学，纽约州，罗切斯特。
19. Schrödinger, E. 1935. 量子力学现状。Naturwissenschaften 23: 807-812; 823-828; 844-949。英文翻译：http://www.tuhh.de/rzt/rzt/it/QM/cat.html。
20. Sutton, A. 2013. 使用 Disruptor 进行并发编程；http://lca2013.linux.org.au/schedule/30168/view_talk。
21. Valois, J. D. 1995. 使用比较并交换的无锁链表。载于 第十四届 分布式计算原理研讨会论文集：165-172。
22. Vogels, W. 2009. 最终一致性。 通讯 52: 40-44。
喜欢还是讨厌？请告诉我们 [email protected]
PAUL E. MCKENNEY 是 IBM Linux 技术中心的杰出工程师，他在该中心维护 Linux 内核的 RCU 实现，并为用户空间 RCU 做出贡献。在此之前，他曾在 Sequent 的 DYNIX/ptx 内核上工作。他于 2004 年在俄勒冈健康与科学大学获得计算机科学与工程博士学位。他于 1988 年在俄勒冈州立大学获得计算机科学硕士学位，并在俄勒冈州立大学获得计算机科学和机械工程双学士学位。他的博客地址为 http://paulmck.livejournal.com/，并致力于撰写名为“并行编程很难吗？如果是，你能做些什么？”的书籍，网址为 https://linuxkernel.org.cn/pub/linux/kernel/people/paulmck/perfbook/perfbook.html。© 2013 1542-7730/13/0500 $10.00
最初发表于 Queue vol. 11, no. 5—
在 数字图书馆 中评论本文
更多相关文章
Adam Morrison - 扩展多核程序中的同步
为现代多核处理器设计软件提出了一个难题。传统的软件设计中，线程操作共享数据，其可扩展性有限，因为对共享数据更新的同步会串行化线程并限制并行性。另一种分布式软件设计，其中线程不共享可变数据，消除了同步并提供了更好的可扩展性。但是，分布式设计使得实现共享数据结构自然提供的功能（例如，动态负载平衡和强一致性保证）具有挑战性，并且并非适用于每个程序。然而，通常情况下，共享可变数据结构的性能受到当今使用的同步方法（无论是基于锁的还是无锁的）的限制。
Fabien Gaud, Baptiste Lepers, Justin Funston, Mohammad Dashti, Alexandra Fedorova, Vivien Quéma, Renaud Lachaize, Mark Roth - 现代 NUMA 系统上内存管理的挑战
现代服务器级系统通常构建为将多个多核芯片组合在一个系统中。每个芯片都有一个本地 DRAM（动态随机存取存储器）模块；它们一起被称为一个节点。节点通过高速互连连接，并且系统是完全一致的。这意味着，程序员无需感知，内核可以向其节点的本地内存以及其他节点的内存发出请求。关键的区别在于，远程请求将花费更长的时间，因为它们会受到更长的线路延迟的影响，并且可能必须跳过多个跃点才能遍历互连。
Spencer Rathbun - 使用 Promise 进行并行处理
在当今世界，有很多理由编写并发软件。提高性能和增加吞吐量的愿望导致了许多不同的异步技术。然而，所涉及的技术通常很复杂，并且是许多细微错误的根源，特别是当它们需要共享可变状态时。如果不需要共享状态，那么可以使用称为 Promise 的更好抽象来解决这些问题。这些 Promise 允许程序员将异步函数调用连接在一起，等待每个函数返回成功或失败，然后再运行链中的下一个适当函数。
Davidlohr Bueso - 实用同步原语的可扩展性技术
在理想的世界中，应用程序有望在越来越大的系统上执行时自动扩展。然而，在实践中，不仅这种扩展不会发生，而且在更大的系统上看到性能实际恶化是很常见的。
© 保留所有权利。