ACM通信
实践
使用锁省略扩展现有的基于锁的应用程序
来源:Amazon.com
多线程应用程序利用不断增加的核心数来实现高性能。然而，这类程序通常需要程序员对多个线程之间共享的数据进行推理。程序员使用诸如互斥锁之类的同步机制来确保在多个线程访问时对共享数据进行正确的更新。不幸的是，这些机制序列化了线程对数据的访问，限制了可伸缩性。
通常，基于锁的程序无法伸缩，因为序列化导致的长块时间，以及协调同步的过多通信开销。为了减少对可伸缩性的影响，程序员使用细粒度锁定，在这种情况下，他们不是使用几个锁来保护所有共享数据(粗粒度)，而是使用许多锁来在更细的粒度上保护数据。这是一个复杂且容易出错的过程11，12这也经常会影响单线程性能。
在提高同步性能方面存在大量工作。无锁数据结构支持无互斥锁的并发操作。13这种算法通常相当复杂。
锁算法种类繁多，复杂度各不相同。11乐观锁定等其他方法可以避免同步开销，例如，通过使用序列号来保护读取共享数据和在必要时重试访问。虽然在某些条件下是有效的，但将其扩展到普遍可用是相当困难的。
事务内存5提出了简化无锁数据结构开发的硬件机制。它们依赖于锁以外的机制来向前推进，并利用底层的缓存一致性机制来检测线程之间的冲突。
锁省略15是通过在无锁快速路径中执行锁的程序来暴露基于锁的程序中的并发性的另一个提议。它使用现代处理器的硬件能力和底层缓存一致性协议来乐观地执行临界段，而不需要获取锁。只有在实际需要解决数据冲突时才会获得锁。
尽管有许多建议，但高性能同步仍然很困难:程序员必须使用事先知道的信息来确定何时序列化，而且可伸缩锁非常复杂，导致锁的位置比较保守。
最近，来自英特尔公司和IBM的商业处理器已经引入了硬件支持，以改进同步。6，7，9，17这为软件开发人员提供了一个提高软件可伸缩性的独特机会。
在本文中，重点是改进现有的基于锁的编程模型，因此，将锁省略作为主要的使用模型。
对锁省略的硬件支持
程序员必须在开发时决定如何控制对共享数据的访问，是使用粗粒度锁(用几个锁保护所有数据)，还是使用细粒度锁保护不同的数据。动态行为最终决定了共享模式。发现错误使用的同步的错误是相当困难的。
我们需要的是一种机制，它既具有粗粒度锁的可用性，又具有细粒度锁的可伸缩性。这正是锁省略提供的功能。程序员仍然必须使用锁来保护共享数据，但可以采用更粗粒度的方法。硬件动态地确定线程是否需要在临界区序列化，并尽可能地以无锁的方式执行基于锁的程序。
处理器以事务方式执行锁保护的关键部分(称为事务区域)。这样的执行只读取锁;它不获取或写入，因此暴露了并发性。因为锁被省略并且执行是乐观的，所以硬件会缓冲任何更新，并检查与其他线程的冲突。在执行期间，硬件不会让任何更新对其他线程可见。
在一个成功的事务执行中，硬件以原子的方式提交更新，以确保所有内存操作在从其他处理器查看时都是瞬间发生的。这种原子提交允许在不获取锁的情况下乐观地执行;执行不再依赖锁，而是依赖硬件来确保正确的更新。如果同步是不必要的，执行可以提交而不需要任何交叉线程序列化。
事务执行可能会因为终止条件(如与其他线程的数据冲突)而失败。当发生这种情况时，处理器将执行事务中止。这意味着处理器丢弃在该区域中执行的所有更新，恢复架构状态，就好像乐观执行从未发生过一样，并以非事务的方式继续执行。根据策略的不同，执行可以重试锁省略或跳过它并获取锁。
为了确保原子性提交，硬件必须能够检测违反原子性的情况。它通过维护事务区域的读和写集来实现这一点。读集由从事务区域内读取的地址组成;写入集由写入的地址和来自同一区域的地址组成。
如果另一个逻辑处理器读取属于事务区域的写集的位置，或者写入属于事务区域的读集或写集的位置，就会发生冲突的数据访问。这就是所谓的数据冲突．
事务终止也可能由于有限的事务资源而发生。例如，在区域中访问的数据量可能超过缓冲区容量。一些不能以事务方式执行的操作，例如I/O，总是会导致终止。
英特尔TSX
Intel事务性同步扩展(TSX)提供了两个指令集接口来定义事务区域。第一种是硬件锁省略(Hardware Lock Elision, HLE)，它使用遗留兼容的指令前缀来为现有的原子锁指令启用锁省略。另一种是受限事务内存(Restricted Transactional Memory, RTM)，它提供新的XBEGIN和XEND指令来控制事务执行，并支持显式的回退处理程序。
想要在遗留硬件上运行Intel tsx支持的软件的程序员可以使用HLE接口来实现锁省略。另一方面，对于更复杂的锁定原语或需要更大的灵活性时，可以使用RTM接口实现锁省略。
本文主要讨论TSX中的RTM接口。IBM系统提供的指令大致类似于RTM。6，9，17
回退处理程序．要使用RTM接口，程序员需要向同步例程添加一个锁省略包装器。包装器不会获取锁，而是使用XBEGIN指令，如果事务中止且重试没有成功，则会回退到锁。
Intel TSX架构(以及其他架构，IBM zSeries除外，它对有保证的小事务有有限的支持9)并不保证事务执行会成功。软件必须有回退非事务性路径，以便在事务性中止上执行。事务执行不会直接启用新算法，但会提高现有算法的性能。回退代码必须具有确保最终前进的能力;它不能只是永远地重试事务执行。
为了实现锁省略并改进现有的基于锁的编程模型，程序员将在事务性区域内测试锁，并在非事务性回退路径中获取锁，然后重新执行关键区域。这就实现了一个经典的基于锁的编程模型。
或者，程序员可以使用事务支持来改进现有的非阻塞重量级算法的性能和实现，使用快速和简单的路径来执行事务，但是如果事务执行中止，则使用更慢和更复杂的非阻塞路径。程序员必须确保两条路径之间的正确交互。
程序员还可以使用事务支持来实现新的编程模型，如事务内存。一种方法是使用硬件中的事务支持作为快速路径，并使用STM(软件事务内存)实现作为回退路径2如果STM在回退上的巨大开销是可接受的。1
实现锁elison．锁省略对现有的锁代码使用简单的事务包装器，如图1．
_xbegin ()尝试以事务方式执行临界区。如果执行没有提交，则_xbegin返回一个不同于_XBEGIN_STARTED，表示中止原因。在进行一些重试之后，程序就可以获得锁了。
在解锁时，代码假设如果锁是空闲的，那么临界区域将被省略，并提交_xend ()．(这假设程序不解锁自由锁)。否则，表示解锁正常。这是一个简化的(但实用的)示例。实际的实现可能会实现更多的优化以提高事务的成功率。GNU Compiler Collection (GCC)为这里使用的intrinsic提供了详细的文档。4GitHub有一个TSX intrinsic的参考实现。10
不断中止并转到回退处理程序的线程最终会获得锁。所有推测使用同一锁的线程都在其读集中拥有该锁，并在检测到锁变量上的写冲突时中止事务执行。如果发生这种情况，那么最终他们都会选择退路。这种回退路径和投机执行之间的同步机制对于避免竞争和保持锁定语义非常重要。
这还要求锁变量对省略包装器可见，如图2．
在现有程序中启用锁elison．大多数现有应用程序都使用同步库来实现锁。仅向这些库添加省略支持通常足以为这些应用程序启用锁省略。这可能与在现有库代码中添加一个省略包装器一样简单。应用程序不需要对此步骤进行更改，因为锁省略维护基于锁的编程模型。
我们使用Intel TSX实现了POSIX标准pthread互斥锁的锁省略，并将其集成到Linux glibc 2.18中。省略pthread读写锁的实现还没有集成到glibc中。
glibc互斥锁接口是二进制兼容的。这允许使用pthread互斥锁进行锁定的现有程序受益于省略。类似地，其他锁库也可以启用省略。
下一步是评估性能并分析事务执行。这样的分析可能会建议对应用程序进行修改，使它们更易于省略。通过避免核心之间不必要的通信，这样的更改通常也可以在不省略的情况下提高性能。
分析事务执行．显式推测的行为不同于现有的编程模型。分析事务执行的一种有效方法是使用使用硬件性能监视计数器的事务感知分析器。
Intel TSX为监视性能提供了广泛的支持，包括采样、中止速率、中止原因分析以及成功和失败事务执行的周期级分析。通常，通过对应用程序数据结构或代码的微小更改(例如，通过避免错误共享)可以显著降低中止速率。
性能监控基础设施提供了程序员不直接可见的硬件行为信息。这对于性能调优通常是至关重要的。程序员还可以利用事务区域来理解它们的行为。然而，这只提供了有限的情况，因为事务性终止会丢弃更新，或者插装本身可能会导致终止。
省略的结果
图3比较读取使用全局锁保护的共享哈希表和省略全局锁时每秒的平均操作数。测试在没有SMT的Intel Core (Haswell)四核系统上运行。elided锁提供了从1个核心到4个核心的近乎完美的扩展，而全局锁退化得很快。最近的一篇论文18分析了在大型应用中使用Intel TSX的锁省略，并报告了各种关键段类型的引人注目的好处。
埃里森什么时候来帮忙?不遇到重大数据冲突的数据结构很适合省略。一个被省略的锁可以允许多个读取器和不冲突的写入器并发执行。这是因为锁省略不会导致对锁的任何写操作，因此表现为读写锁。它还消除了锁变量的缓存行通信。因此，使用细粒度锁的程序也可以获得好处。
并不是所有的程序都能从锁的改进中受益。这些程序要么是单线程的，要么不使用争用锁，要么使用其他算法进行同步。重复冲突的数据结构看不到并发性的好处。
如果程序使用复杂的非阻塞或细粒度算法，那么更简单的事务快速路径可以提高速度。此外，一些在临界区中使用系统调用或类似不友好操作的程序会看到重复的中止。
中止的成本．并非所有事务中止都会使程序变慢。如果线程只是在等待锁，则可能会发生中止。这种事务区域也可以用于预取数据。然而，频繁、持久的中止会损害性能，开发人员必须分析中止，以减少它们发生的可能性。
自适应elison．同步库可以根据事务行为调整它们的省略策略。例如，glibc实现使用一个简单的自适应算法来根据需要跳过省略。同步库包装器检测事务中止，并在不成功的事务执行上禁用锁省略。库在一段时间后重新启用对锁的省略，以防情况发生变化。开发创新的自适应启发式算法是未来工作的一个重要领域。14，16
自适应省略与向现有同步库添加的省略包装器相结合，可以有效地无缝地为现有程序中的所有锁启用锁省略。然而，开发人员仍然应该使用分析来识别事务中止的原因，并解决代价高昂的问题。这仍然是提高性能最有效的方法。
作为在省略库中构建适应性的一种替代方法，程序员可以有选择地确定在哪些锁上应用省略。这种方法可能适用于某些应用程序，但可能需要开发人员理解程序中所有锁的动态行为，并且可能会导致错过机会。这两种方法可以结合使用。
旅鼠的效果．当事务中止发生时，同步库可以重试省略或显式跳过它并获取锁。库如何重试省略很重要。例如，当一个线程回退到显式地获取一个锁时，它会导致放弃省略相同锁的其他线程。在其他线程上的naïve实现将立即重试省略。这些线程将发现锁被持有、中止和重试省略，从而迅速达到重试阈值，而没有任何机会发现锁已被释放。因此，这些线程会快速过渡到跳过省略的执行。很容易看到所有线程最终都处于这样一种情况:在较长时间内没有线程重新尝试锁省略。这种现象就是旅鼠效应3.其中，线程进入非省略执行的延长时间。这将防止软件利用底层省略硬件。
同步库中一个简单而有效的修复方法是，仅当锁是空闲的且非事务性地旋转/等待时重试省略，并限制重试次数。有些锁算法实现了一个队列，以便在发现锁不可用时强制执行线程的顺序。队列与并行推测是不兼容的。对于这类代码，程序员必须在实际排队代码之前使用省略包装器，包括重试支持。其他缓解战略也是可能的。
一旦程序员理解了底层的行为，简单的修复可以在改进意想不到的性能行为方面大有帮助。
锁省略是现代系统中可使用的缩放工具箱中的一种新技术。它使现有的基于锁的程序能够通过少量的软件工程工作实现非阻塞同步和细粒度锁的性能优势。
致谢
感谢Noel Arnold、Jim Cownie、Roman Dementiev、Ravi Rajwar、Arch Robison、Joanne Strickland和Konrad Lai对本文的反馈和改进。
相关文章
在queue.acm.org
证明非阻塞数据结构的正确性
马修Desnoyers
http://queue.acm.org/detail.cfm?id=2490873
并行编程的Erlang
吉姆•拉森
http://queue.acm.org/detail.cfm?id=1454463
并发调试的试验和磨难
康苏-加特林
http://queue.acm.org/detail.cfm?id=1035623
参考文献
1.Cascaval, C.， Blundell, C.， Michael, M.， Cain, H. W.， Wu, P.， Chiras, S.和Chatterjee, S.软件事务性内存:为什么它只是一个研究玩具?Commun。ACM 51， 11(2008年11月)，4046。
2.Dalessandro, L.， Carouge, F.， White, S.， Lev, Y.， Moir, M.， Scott, M.L.和Spear, M.F. Hybrid NOrec:一个关于最大努力硬件事务存储器有效性的案例研究。在16年会议纪要th编程语言和操作系统体系结构支持国际会议, 2011, 3952。
3.Dice, D.， Herlihy, M.， Lea, D.， Lev, Y.， Luchangco, V.， Mesard, W.， Moir, M.， Moore, K.和Nussbaum, D.自适应事务性记忆测试平台的应用。在3个会议的会议记录理查德·道金斯美国计算机学会事务计算SIGPLAN年度研讨会, 2008年。
4.GCC。X86事务存储intrinsic, 2013;http://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/X86-transactional-memory-intrinsics.html#X86-transactional-memory-intrinsics．
5.事务内存:对无锁数据结构的架构支持。在20个会议的会议记录th计算机体系结构年度国际研讨会, 1993, 289300。
6.IBM。ISA, 2013;http://www.power.org/documentation/power-isa-version-2-07/．
7.英特尔。Intel 64 and IA-32架构软件开发人员手册， 2012年第14章，第1卷;http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html．
8.英特尔。IA优化手册，第12章，TSX优化;http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf．网络资源;http://www.intel.com/software/tsx．
9.Jacobi, C.， Slegel, T.和Dreiner, D. IBM System Z.事务性内存架构和实现45年的会议记录th年度IEEE/ACM微架构国际研讨会, 2012, 2536。
10.克林,a . 2013。TSX-tools;http://github.com/andikleen/tsx-tools．
11.并行编程很难吗?如果是这样，你能做些什么?(2013);https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html．
12.McVoy, L. SMP标度被认为是有害的，1999年;http://www.bitmover.com/llnl/smp.pdf．
13.选择非阻塞特性的平衡行为。Commun。ACM 56， 9(2013年9月)，4653。
14.Pohlack, M.和Diestelhorst, S. 2011。从轻量级硬件事务内存到轻量级锁省略。在第六届ACM SIGPLAN事务计算研讨会上。
15.拉杰瓦尔，r。古德曼，j。r。投机锁省略。在34年会议纪要th年度ACM/IEEE微架构国际研讨会, 2001, 294305。
16.Usui, T.， Behrends, R.， Evans, J.和Smaragdakis, Y.自适应锁:结合事务和锁来实现高效并发。在四人会议的会议记录th美国计算机学会事务计算SIGPLAN研讨会, 2009年。
17.Wang, A.， Gaudet, M.， Wu, P.， Amaral, J.N.， Ohmacht, M.， Barton, C.， Silvera, R.和Michael, M.评价Blue Gene/Q对事务性内存的硬件支持。在21世纪会议纪要圣国际并行体系结构和编译技术会议, 2012, 127136。
18.Yoo r.m.， Hughes, c.j.， Rajwar, R.和Lai K.用于高性能计算的Intel事务同步扩展的性能评估。在高性能计算国际会议论文集，网络，存储与分析，2013。
©2014 0001 - 0782/14/03 ACM
如果您不是为了盈利或商业利益而制作或分发本作品的部分或全部，并在第一页注明本通知和完整引用，则允许您免费制作本作品的部分或全部数字或纸质副本，供个人或课堂使用。本作品的组成部分必须由ACM以外的其他人享有版权。信用文摘是允许的。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2014 ACM股份有限公司
没有发现记录