PDF使用锁省略扩展现有基于锁的应用
锁省略使现有的基于锁的程序能够以较少软件工程工作量获得非阻塞同步和细粒度锁的性能优势。
Andi Kleen，英特尔公司
多线程应用程序利用不断增加的内核数量来实现高性能。然而，此类程序通常需要程序员推理多个线程之间共享的数据。程序员使用互斥锁等同步机制来确保在多个线程访问的情况下对共享数据进行正确的更新。不幸的是，这些机制序列化了线程对数据的访问，并限制了可扩展性。
通常，基于锁的程序无法扩展，这是因为序列化导致的长时间阻塞以及协调同步的过度通信开销。为了减少对可扩展性的影响，程序员使用细粒度锁，即不使用少量锁来保护所有共享数据（粗粒度），而是使用许多锁来保护更细粒度的数据。这是一个复杂且容易出错的过程10,11，并且通常也会影响单线程性能。
关于改进同步性能的方法，已经存在大量工作。无锁数据结构支持在没有互斥锁的情况下进行并发操作。12 这种算法通常非常复杂。
存在各种复杂程度不同的丰富的锁定算法。10 其他方法（如乐观锁定）避免了同步开销，例如，通过使用序列号来保护对共享数据的读取，并在必要时重试访问。虽然在某些条件下有效，但将这些方法扩展到普遍适用非常困难。
事务内存5 提出了硬件机制，以简化无锁数据结构的开发。它们依赖于锁以外的机制来实现向前进展，并利用底层缓存一致性机制来检测线程之间的冲突。
锁省略14 是另一项提议，旨在通过在无锁快速路径中执行基于锁的程序来暴露并发性。它利用了现代处理器的硬件能力和底层缓存一致性协议，以乐观的方式执行临界区，而无需获取锁。仅在实际需要解决数据冲突时才获取锁。
尽管有许多提议，但高性能同步仍然很困难：程序员必须使用预先已知的信息来确定何时进行序列化，并且可扩展的锁定很复杂，导致保守的锁放置。
最近，英特尔公司和 IBM 公司的商用处理器引入了硬件支持以改进同步。6,7,8,16 这为软件开发人员提供了一个独特的机会来提高其软件的可扩展性。
本文重点关注改进现有的基于锁的编程模型，因此，将锁省略作为主要使用模型进行研究。
锁省略的硬件支持
程序员必须在开发时决定如何控制对共享数据的访问——是使用粗粒度锁（少量锁保护所有数据），还是使用细粒度锁来保护不同的数据。动态行为最终决定共享模式。发现错误使用的同步错误非常困难。
需要的是一种机制，它具有粗粒度锁的可用性和细粒度锁的可扩展性。这正是锁省略所提供的。程序员仍然必须使用锁来保护共享数据，但可以采用更粗粒度的方法。硬件动态地确定线程是否需要在临界区中序列化，并在可能的情况下以无锁方式执行基于锁的程序。
处理器事务性地执行受锁保护的临界区（称为事务区域）。这种执行仅读取锁；它不获取或写入锁，从而暴露并发性。由于锁被省略且执行是乐观的，因此硬件会缓冲任何更新并检查与其他线程的冲突。在执行期间，硬件不会使任何更新对其他线程可见。
在成功的事务执行中，硬件原子地提交更新，以确保从其他处理器来看，所有内存操作都瞬间发生。这种原子提交允许执行以乐观的方式进行，而无需获取锁；执行不再依赖于锁，而是依赖于硬件来确保正确的更新。如果同步是不必要的，则执行可以提交而无需任何跨线程序列化。
事务执行可能会因中止条件（例如与其他线程的数据冲突）而失败。当发生这种情况时，处理器将执行事务中止。这意味着处理器会丢弃在该区域中执行的所有更新，将架构状态恢复为好像从未发生过乐观执行一样，并以非事务方式恢复执行。根据所使用的策略，执行可能会重试锁省略，或者跳过它并获取锁。
为了确保原子提交，硬件必须能够检测到原子性违规。它通过维护事务区域的读集合和写集合来实现这一点。读集合由从事务区域内读取的地址组成，写集合由写入的地址组成，也来自事务区域内。
如果另一个逻辑处理器读取了属于事务区域写集合的位置，或者写入了属于事务区域读集合或写集合的位置，则会发生冲突的数据访问。这被称为数据冲突。
事务中止也可能由于有限的事务资源而发生。例如，区域中访问的数据量可能超过缓冲容量。某些无法以事务方式执行的操作（例如 I/O）始终会导致中止。
英特尔 TSX
英特尔 TSX（事务同步扩展）提供了两个指令集接口来定义事务区域。第一个是 HLE（硬件锁省略），它使用与传统指令兼容的指令前缀来为现有的原子锁指令启用锁省略。另一个是 RTM（限制性事务内存），它提供了新的 XBEGIN 和 XEND 指令来控制事务执行，并支持显式回退处理程序。
希望在传统硬件上运行支持 Intel TSX 的软件的程序员可以使用 HLE 接口来实现锁省略。另一方面，对于更复杂的锁定原语或需要更大灵活性时，可以使用 RTM 接口来实现锁省略。
本文重点介绍 TSX 中的 RTM 接口。IBM 系统提供的指令与 RTM 大致相似。6,8,16
回退处理程序
要使用 RTM 接口，程序员需要向同步例程添加锁省略包装器。包装器不获取锁，而是使用 XBEGIN 指令，并在事务中止且重试不成功时回退到锁。
英特尔 TSX 架构（以及其他架构，IBM zSeries 除外，后者对保证的小事务的支持有限8）不保证事务执行一定会成功。软件必须具有回退非事务路径，以便在事务中止时执行。事务执行不会直接启用新算法，但会提高现有算法的性能。回退代码必须能够确保最终向前进展；它不能只是无限期地重试事务执行。
为了实现锁省略并改进现有的基于锁的编程模型，程序员将在事务区域内测试锁，并在非事务回退路径中获取锁，然后重新执行临界区。这启用了一个经典的基于锁的编程模型。
或者，程序员可以使用事务支持来提高现有非阻塞重量级算法的性能和实现，使用快速简单的路径以事务方式执行，但如果事务执行中止，则使用较慢且更复杂的非阻塞路径。程序员必须确保两条路径之间的正确交互。
程序员还可以使用事务支持来实现新的编程模型，例如事务内存。一种方法是在硬件中使用事务支持来实现快速路径，如果回退时 STM（软件事务内存）的开销较大是可以接受的，则使用 STM（软件事务内存）实现作为回退路径2, 1。
实现锁省略
锁省略在现有锁代码周围使用简单的事务包装器，如图 1 所示。
_xbegin()尝试以事务方式执行临界区。如果执行未提交，则_xbegin返回的状态字与_XBEGIN_STARTED不同，表示中止原因。在进行一些重试后，程序可以获取锁。
在解锁时，代码假定如果锁是空闲的，则临界区被省略，并使用_xend()提交。（这假设程序不会解锁空闲锁。）否则，锁正常解锁。这是一个简化的（但功能齐全的）示例。实际的实现可能会实现更多优化以提高事务成功率。GCC（GNU 编译器集合）为此处使用的内在函数提供了详细的文档。4 GitHub 上有 TSX 内在函数的参考实现。9
不断中止并转到回退处理程序的线程最终会获取锁。所有推测同一锁的线程都在其读集合中拥有该锁，并且当它们检测到锁变量上的写冲突时，会中止其事务执行。如果发生这种情况，那么最终它们都将采用回退路径。回退路径和推测执行之间的这种同步机制对于避免竞争并保持锁定语义非常重要。
这也要求锁变量对省略包装器可见，如图 2 所示。
在现有程序中启用锁省略
大多数现有应用程序都使用同步库来实现锁。仅向这些库添加省略支持通常就足以在这些应用程序中启用锁省略。这可能就像在现有库代码中添加省略包装器一样简单。应用程序无需为此步骤进行更改，因为锁省略维护了基于锁的编程模型。
我们使用英特尔 TSX 为 POSIX 标准 pthread 互斥锁实现了锁省略，并将其集成到 Linux glibc 2.18 中。省略 pthread 读/写锁的实现尚未集成到 glibc 中。
glibc 互斥锁接口是二进制兼容的。这允许使用 pthread 互斥锁进行锁定的现有程序从省略中受益。同样，其他锁库也可以启用省略。
下一步是评估性能并分析事务执行。这种分析可能会建议更改应用程序以使其更易于省略。这些更改通常也会在没有省略的情况下提高性能，方法是避免内核之间不必要的通信。
分析事务执行
显式推测的行为与现有编程模型不同。分析事务执行的有效方法是使用硬件性能监视计数器的事务感知分析器。
英特尔 TSX 提供了广泛的支持来监视性能，包括采样、中止率、中止原因分析以及成功和不成功事务执行的周期级分析。通常，可以通过对应用程序数据结构或代码进行细微更改（例如，通过避免伪共享）来显着降低中止率。
性能监视基础设施提供了有关硬件行为的信息，这些信息对于程序员来说并非直接可见。这对于性能调优通常至关重要。程序员还可以检测事务区域以了解其行为。然而，这仅提供了一个有限的画面，因为事务中止会丢弃更新，并且检测本身可能会导致中止。
省略结果
图 3 比较了读取受全局锁保护的共享哈希表与省略全局锁时每秒的平均操作数。测试在没有 SMT 的四核英特尔酷睿 (Haswell) 系统上运行。省略锁提供了从一个内核到四个内核的近乎完美的扩展，而全局锁则迅速退化。最近的一篇论文17 分析了在更大的应用程序中使用英特尔 TSX 进行锁省略的情况，并报告了各种临界区类型的引人注目的好处。
何时省略有帮助？
没有遇到重大数据冲突的数据结构是省略的绝佳候选对象。省略锁可以允许多个读取器和非冲突的写入器并发执行。这是因为锁省略不会导致对锁的任何写入操作，因此表现得像读写锁。它还消除了锁变量的任何缓存行通信。因此，具有细粒度锁定的程序也可能会看到收益。
并非所有程序都受益于锁改进。这些程序要么是单线程的，要么不使用有竞争的锁，要么使用其他一些算法进行同步。重复冲突的数据结构看不到并发性优势。
如果程序使用复杂的非阻塞或细粒度算法，那么更简单的事务快速路径可以加快速度。此外，某些在其临界区内使用系统调用或类似不友好操作的程序将看到重复中止。
中止的代价
并非所有事务中止都会使程序变慢。中止可能发生在线程原本只是等待锁的地方。这种中止的事务区域也可能用于预取数据。然而，频繁的、持续的中止会损害性能，开发人员必须分析中止以降低其概率。
自适应省略
同步库可以根据事务行为调整其省略策略。例如，glibc 实现使用简单的自适应算法来根据需要跳过省略。同步库包装器检测到事务中止，并在不成功的事务执行时禁用锁省略。库会在一段时间后重新启用锁的省略，以防情况发生变化。开发创新的自适应启发式算法是未来工作的一个重要领域。13,15
自适应省略与添加到现有同步库的省略包装器相结合，可以有效地为现有程序中的所有锁无缝启用锁省略。但是，开发人员仍应使用性能分析来识别事务中止的原因，并解决代价高昂的原因。这仍然是提高性能的最有效方法。
作为将自适应性构建到省略库中的替代方案，程序员可以选择性地识别要将省略应用于哪些锁。这种方法可能适用于某些应用程序，但可能需要开发人员了解程序中所有锁的动态行为，并且可能会导致错失机会。这两种方法可以结合使用。
旅鼠效应
当发生事务中止时，同步库可以重试省略，或者显式跳过它并获取锁。库如何重试省略非常重要。例如，当线程回退到显式获取锁时，这会导致中止省略同一锁的其他线程。其他线程上的幼稚实现会立即重试省略。这些线程会发现锁被持有，中止并重试省略，从而快速达到其重试阈值，而没有任何机会找到空闲锁。因此，这些线程会快速过渡到它们跳过省略的执行状态。很容易看出所有线程最终都处于没有线程在更长时间内重新尝试锁省略的情况。这种现象就是旅鼠效应3，即线程进入长时间的非省略执行状态。这会阻止软件利用底层的省略硬件。
同步库中一个简单有效的修复方法是仅在锁空闲时才重试省略并以非事务方式自旋/等待——并限制重试计数。一些锁算法实现了一个队列，以便在线程发现锁不可用时强制执行线程顺序。队列与并行推测不兼容。对于此类代码， 程序员必须在实际排队代码之前使用省略包装器，包括重试支持。其他缓解策略也是可能的。
一旦程序员了解了底层行为，简单的修复就可以在很大程度上改善意外的性能行为。
锁省略是现代系统中可用的扩展工具箱中的一项新技术。它使现有的基于锁的程序能够以较少的软件工程工作量获得非阻塞同步和细粒度锁的性能优势。
致谢
感谢 Noel Arnold、Jim Cownie、Roman Dementiev、Ravi Rajwar、Arch Robison、Joanne Strickland 和 Konrad Lai 对本文的反馈和改进。
延伸阅读
英特尔。《IA 优化手册》，第 12 章，TSX 建议，描述了各种调整技术以改进锁省略； http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf。
Web 资源： http://www.intel.com/software/tsx。
参考文献
1. Cascaval, C., Blundell, C., Michael, M., Cain, H. W., Wu, P., Chiras, S., Chatterjee, S. 2008。软件事务内存：为什么它只是一种研究玩具？ 通讯 51(11): 40-46。
2. Dalessandro, L., Carouge, F., White, S., Lev, Y., Moir, M., Scott, M. L., Spear, M. F. 2011。混合 NOrec：最佳努力硬件事务内存有效性的案例研究。在第 16 届编程语言和操作系统架构支持国际会议 (ASPLOS)论文集中：39-52。
3. Dice, D., Herlihy, M., Lea, D., Lev, Y., Luchangco, V., Mesard, W., Moir, M., Moore, K., Nussbaum, D. 2008。自适应事务内存测试平台的应用。第三届 SIGPLAN 事务计算年度研讨会。
4. GCC。2013。X86 事务内存内在函数； http://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/X86-transactional-memory-intrinsics.html#X86-transactional-memory-intrinsics。
5. Herlihy, M., Moss, J. E. B. 1993。事务内存：无锁数据结构的架构支持。在第 20 届计算机架构国际研讨会 (ISCA) 论文集： 289-300。
6. IBM。2013。Power ISA； http://www.power.org/documentation/power-isa-version-2-07/。
7. 英特尔。2012。《英特尔 64 位和 IA-32 架构软件开发人员手册》，第 1 卷，第 14 章； http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html。
8. Jacobi, C., Slegel, T., Greiner, D. 2012。IBM System z 的事务内存架构和实现。在第 45 届 IEEE/ 国际微架构研讨会论文集： 25-36。
9. Kleen, A. 2013。tsx-tools； http://github.com/andikleen/tsx-tools。
10. McKenney, P. E. 2013。并行编程很难吗？如果是，您能做些什么？； https://linuxkernel.org.cn/pub/linux/kernel/people/paulmck/perfbook/perfbook.html
11. McVoy, L. 1999。SMP 扩展被认为是有害的； http://www.bitmover.com/llnl/smp.pdf。
12. Michael, M. M. 2013。选择非阻塞功能的平衡行为。 通讯 56(9): 46-53。
13. Pohlack, M., Diestelhorst, S. 2011。从轻量级硬件事务内存到轻量级锁省略。在第六届 SIGPLAN 事务计算年度研讨会中。
14. Rajwar, R., Goodman, J. R. 2001。推测性锁省略。在第 34 届 /IEEE 国际微架构研讨会论文集： 294-305。
15. Usui, T., Behrends, R., Evans, J., Smaragdakis, Y. 2009。自适应锁：结合事务和锁以实现高效并发。在第四届 SIGPLAN 事务计算研讨会中。
16. Wang, A., Gaudet, M., Wu, P., Amaral, J. N., Ohmacht, M., Barton, C., Silvera, R., Michael, M. 2012。Blue Gene/Q 硬件对事务内存支持的评估。在第 21 届并行体系结构和编译技术国际会议论文集： 127-136。
17. Yoo, R. M., Hughes, C. J., Rajwar, R., Lai, K. 2013。英特尔事务同步扩展在高性能计算中的性能评估。在高性能计算、网络、存储和分析国际会议论文集中：文章编号 19。
喜欢还是讨厌？请告诉我们
Andi Kleen 是英特尔开源技术中心的软件工程师。他从事 Linux 内核的 x86-64 端口和其他内核领域的工作，包括网络、性能、NUMA（非一致性内存访问）和错误恢复。他目前专注于性能调优、多核可扩展性和性能分析。他的职业生涯始于为媒体艺术家提供支持，然后在 SUSE 实验室工作了九年多。
© 2013 1542-7730/14/0100 $10.00
最初发表于 Queue vol. 12, no. 1—
在 数字图书馆 中评论本文
更多相关文章
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 - 实用同步原语的可扩展性技术
在理想的世界中，应用程序有望在越来越大的系统上执行时自动扩展。然而，在实践中，不仅这种扩展没有发生，而且在更大的系统上看到性能实际上变得更糟是很常见的。
© 保留所有权利。