ACM通信

实践

事务性内存并行编程

由乌尔里希Drepper
ACM通信，2009年2月，第52卷第2期，38-43页
10.1145/1461928.1461943
评论

随着单个核心的速度不再以我们过去几十年喜欢的速度增长，程序员不得不寻找其他方法来提高越来越复杂的应用程序的速度。CPU制造商提供的功能是增加执行单元或CPU内核的数量。

要使用这些额外的核心，程序必须并行化。多个执行路径必须一起工作，以完成程序必须执行的任务，并且尽可能多的工作必须并发进行。只有这样才有可能加速程序(即减少总运行时)。阿姆达尔定律表示:

这里P是程序中可并行化的部分，S是执行单元的数量。

回到顶部

同步问题

这是理论。让它成为现实是另一个问题。简单地编写一个普通的程序本身就是一个问题，这可以从无休止的程序bug修复中看出。试图将一个程序分成多个可以并行执行的部分会增加额外的问题:

• 除非程序从一开始就由多个独立的部分组成，并且应该在一开始就作为独立的程序编写，否则各个独立的部分必须协作。这通常采取共享内存或辅助存储中的数据的形式。
• 对共享数据的写访问不能以不受控制的方式发生。在任何时候都必须避免允许程序看到不一致的，因而是意外的状态。如果状态由多个内存位置的内容表示，这就会出现问题。处理器不能原子地修改任意数量(在大多数情况下甚至不能修改两个)的独立内存位置。
• 为了处理多个内存位置，“传统的”并行编程不得不求助于同步。在互斥(互斥)指令的帮助下，程序可以确保自己在执行互斥对象保护的操作时是独立的。如果对受保护状态的所有读或写访问都是在持有互斥锁的情况下执行的，那么可以保证程序永远不会看到不一致的状态。今天的编程环境(例如，POSIX)允许任意数量的互斥锁共存，并且有一些特殊类型的互斥锁允许多个读取器并发访问。后者是允许的，因为读访问不会改变状态。如果使用正确，这些机制允许合理的可伸缩性。
• 但是，锁定互斥锁会带来全新的麻烦。在大多数情况下，使用单个程序范围的互斥锁会通过减少可并行运行的程序部分(公式中为P)而显著地损害程序性能。使用更多的互斥锁不仅会增加P，还会增加与锁定和解锁互斥锁相关的开销。如果关键地区的竞争并不激烈(这是应该的)，这就特别成问题。处理多个互斥锁也意味着可能会出现死锁。如果重叠互斥锁被多个线程以不同的顺序锁定，就会发生死锁。这是一个非常容易发生的错误。互斥锁的使用通常隐藏在库函数中，不是立即可见的，这使整个问题复杂化。

回到顶部

程序员的困境

程序员陷入了两个问题:

• 增加程序中可并行执行的部分(P)。
• 增加程序代码的复杂性，从而增加出现问题的可能性。

一个功能不正确的程序可以以您让它运行的速度运行，但它仍然是无用的。因此，并行化只能做到不引入第二类问题的程度。并行度的多少取决于程序员的经验和知识。多年来，已经开发了许多尝试自动捕获与锁定相关的问题的项目。没有一个能成功地解决现实世界中出现的大小程序的问题。静态分析既昂贵又复杂。动态分析必须依赖于启发式和测试用例的质量。

对于复杂的项目，不可能一次转换整个项目以允许更多的并行性。相反，程序员迭代地添加更细粒度的锁定。这可能是一个漫长的过程，如果中间步骤的测试不够彻底，就可能出现不是由最近添加的更改集引起的问题。而且，正如经验所表明的，有时要摆脱大锁是非常困难的。例如，查看Linux内核邮件列表上关于BKL(大内核锁)的讨论。BKL是在20世纪90年代中期Linux第一次获得SMP(对称多处理)支持时引入的，到2008年我们仍然没有摆脱它。

人们已经得出结论，锁定是解决一致性问题的错误方法。对于那些不熟悉并行编程的所有问题的程序员(这意味着几乎所有人)来说尤其如此。

回到顶部

看其他地方

一致性问题在计算机世界中并不新鲜。事实上，在一个特定的领域，它一直是整个解决方案的核心:数据库。由许多表和相关索引组成的数据库必须进行原子更新，原因已经说明过:数据的一致性。绝不能发生执行更新的一部分而不执行其他部分的情况。也不能出现这样的情况:两个更新交错在一起，以至于最后每个修改只有部分可见。

数据库世界中的解决方案是事务。数据库程序员显式声明哪些数据库操作属于事务。事务中执行的操作可以按任意顺序执行，直到事务提交后才真正生效。如果事务中存在冲突(也就是说，同时存在修改相同数据集的其他操作)，则事务将被回滚并必须重新启动。

事务的概念从大多数编程任务中很自然地消失了。如果作为事务的一部分所做的所有更改都是一次性原子地可用的，那么将更改添加到事务中的顺序并不重要。不需要按特定顺序执行操作，这非常有帮助。所需要做的就是记住，修改数据集总是作为事务的一部分，而不是以一种快速、肮脏、直接的方式。

回到顶部

事务内存

事务的概念也可以转移到在程序中执行的内存操作。当然，我们可以将程序保存在内存中的数据视为与数据库中的数据相对应的表，然后实现相同的功能。但是，这是相当有限的，因为它迫使程序员极大地改变他们编写程序的方式，而系统编程不能忍受这样的限制。

幸运的是，这是不需要的。事务性内存(TM)的概念是在没有这种限制的情况下定义的。Maurice Herlihy和J. Eliot B. Moss在他们1993年的论文中写道²描述一个可以在现有的缓存一致性协议上实现的硬件实现。¹

论文中的描述是泛泛的。首先，不需要要求在硬件中实现事务内存，无论是完全实现还是部分实现。对于本文标题中提到的目的(无锁数据结构)，硬件支持可能是必不可少的。但这通常是不正确的，我们很快就会看到。其次，必须将描述转移到当前可用的硬件上。这包括实现细节，例如缓存一致性协议的可能重用和事务的粒度，事务的粒度很可能不是一个单词，而是一条缓存线。

对TM的硬件支持本身对于实现无锁数据结构最感兴趣。例如，要实现将新元素插入双链表而不锁，就必须原子地更新四个指针。这些指针在三个列表元素中找到，这意味着不可能使用简单的原子操作实现它。硬件TM (HTM)提供了一种实现操作于多个内存字的原子操作的方法。为了在原子数据结构之外为事务内存提供更通用的支持，需要软件支持。例如，任何硬件实现都会限制事务的大小。这些限制对于重要的程序可能太低，或者在不同的实现之间可能有所不同。软件可以而且必须完成HTM支持，以扩展用于一般编程的TM实现的范围。

这已经更进一步。因为现在的硬件大多缺乏HTM支持，所以软件TM (STM)是目前大多数研究项目所使用的。使用基于stm的解决方案，可以提供TM功能的接口，稍后可以在混合TM实现，如果可能的话使用硬件。这允许程序员使用TM提供的简化编写程序，即使硬件中没有HTM支持。

回到顶部

告诉我问题所在

为了让读者相信TM值得这么麻烦，让我们看一个小例子。这不是为了反映现实的代码，而是说明了在真实代码中可能发生的问题:

假设这段代码必须是线程安全的。这意味着多个线程可以并发地执行任何函数，并且这样做一定不会产生任何无效的结果。后者在这里定义为不属于一起的返回计数器和时间戳值。

当然可以定义一个单独的互斥锁，并要求在四个函数中都使用这个互斥锁。很容易验证这将产生预期的结果，但性能可能远远不是最优的。

假设大多数时候只有函数f1 _ 1而且f2 2 _使用。在这种情况下，这些函数的调用者之间永远不会有任何冲突:f1 _ 1而且f2 2 _可以和平共存。这意味着使用单个锁会不必要地降低代码的速度。

那么，使用两个锁。但是如何定义它们呢?语义必须分别是“当使用counter1和timestamp1时”和“当使用counter2和timestamp2时”。这可能适用于f1 _ 1而且f2 2 _，但它对其他两个函数不起作用。这里，对counter1/timestamp2和对counter2/timestamp1一起使用。所以我们必须再向下一层，为每个变量分配一个单独的锁。

假设我们这样做，我们很容易就会写出这样的东西(这里只提到两个函数;另外两个是镜像):

的代码w1 _ 2在这个例子中是错误的。我们不能拖延l _ timestamp1锁定，因为它可能产生不一致的结果。尽管它可能会慢一些，但我们总是需要获得锁:

这是一个简单的改变，但结果也是错误的。现在我们尝试锁定所需的锁w1 _ 2在不同的顺序f1 _ 1．这可能会导致僵局。在这个简单的例子中，很容易看出情况就是这样，但是对于稍微复杂一点的代码来说，这种情况是非常常见的。

这个例子表明:很容易陷入这样一种情况:需要许多单独的互斥锁来允许足够的并行;正确使用所有互斥锁本身就相当复杂。

从本文的主题可以看出，在这种情况和许多其他情况下，TM将能够帮助我们。

回到顶部

重写使用TM

前面的例子可以使用TM重写如下。在本例中，我们使用了C语言的非标准扩展，这些扩展以某种形式出现在支持tm的编译器中。这些扩展很容易解释。

在本例中，我们所做的只是将操作用块标头括起来tm _原子。的tm _原子关键字表示下面块中的所有指令都是事务的一部分。对于每一次内存访问，编译器都可以生成如下所示的代码。调用函数是一个挑战，因为被调用的函数也必须是事务感知的。因此，可能需要提供两个版本的编译函数:一个支持事务，另一个不支持事务。如果任何传递调用的函数使用tm _原子块本身，嵌套必须处理。以下是一种方法:

1. 检查同一个内存位置是否属于另一个内存位置。
2. 如果是，则中止当前事务。
3. 如果没有，则记录当前事务引用了内存位置，以便其他事务中的步骤2可以找到它。
4. 根据它是读访问还是写访问，要么加载内存位置的值(如果变量还没有被修改过)，要么从本地存储加载它(如果变量已经被修改过);或者将它写入变量的本地存储中。

如果事务之前访问了相同的内存位置，步骤3就会消失。对于第二步，有其他选择。事务可以一直执行到最后，然后更改才被撤消，而不是立即中止。这被称为延迟中止/延迟提交方法，与典型数据库事务中的急切/急切方法相反(前面描述过)。

现在需要的是对工作的定义，当结束tm _原子块(即，事务被提交)。具体工作如下:

1. 如果当前事务已经中止，请重置所有内部状态，延迟一段时间，然后重试，执行整个块。
2. 将在事务中修改的内存位置的所有值存储在本地存储中，并为其放置新值。
3. 重置关于作为事务一部分的内存位置的信息。

描述很简单;真正的问题是如何有效地执行每件事。在我们讨论这个问题之前，让我们简单看看这一切是否正确并满足所有要求。

回到顶部

正确性和忠诚

假设一个正确的实现(当然)，我们能够确定一个内存位置当前是否被用作另一个实现的一部分。这意味着读还是写访问并不重要。因此，很容易看出，我们从未产生过不一致的结果。只有当所有的内存访问内部tm _原子阻塞成功并且事务不被中止，事务将被提交。然而，这意味着就内存访问而言，线程是完全独立的。我们已经将代码减少到没有锁的初始代码，这显然是正确的。

关于正确性的唯一剩下的问题是:如果使用这种TM技术的线程不断地相互中止，它们真的会终止吗?说明这一点在理论上当然是可能的，但在本文中，它应该足以指出一个类似的问题。在基于ip的网络中(与令牌环网络不同)，所有连接的机器都可以同时开始发送数据。如果有多台机器发送数据，就会产生冲突。此冲突将自动检测到，并在短时间等待后重新启动发送尝试。IP定义了网络堆栈必须实现的指数备份算法。考虑到我们生活在一个由基于ip的网络主导的世界里，这种方法肯定是有效的。结果可以直接转移到TM问题上。

还有一个问题。之前我们拒绝了使用单个锁的解决方案，因为它会阻止并发执行f1 _ 1而且f2 2 _．这里看起来怎么样?很容易看出，用于这两个函数的内存位置集是分离的。这意味着事务中的内存位置集f1 _ 1而且f2 2 _是中断以及，因此检查并发内存使用在f1 _ 1将永远不会因为执行而导致中止f2 2 _反之亦然。因此，使用TM解决这个问题确实是不太可能的。

---

一致性问题在计算机世界中并不新鲜。事实上，在一个特定的领域，它一直是整个解决方案的核心:数据库。

---

再加上描述事务的简洁方式，TM如此吸引人的原因就显而易见了。

回到顶部

TM今天在哪里?

在每个人都对TM的前景过于兴奋之前，我们应该记住，它在很大程度上仍是一个研究课题。第一个实现已经开始可用，但我们还有很多东西要学习。例如，VELOX项目(http://www.velox-project.eu/)的目标是全面分析操作系统中可以使用TM技术的所有地方。这从操作系统内核中的无锁数据结构扩展到应用服务器中的高级用途。分析包括有和没有硬件支持的TM。

该项目还将研究应该添加到高级编程语言中的TM原语的最有用语义。在前面的例子中，它是一个简单的tm _原子关键字。这并不一定是正确的形式;所描述的语义也不需要是最优的。

目前有许多自包含的STM实现可用。人们可以选择TinySTM (http://tinystm.org)来获得经验。它提供了TM所需的所有原语，同时具有可移植性、小型和仅依赖于宿主系统上可用的少数服务。

基于TinySTM和类似的实现，我们很快就会看到诸如tm _原子出现在编译器。有几个专有编译器提供支持，GNU编译器的第一个补丁也可以获得(http://www.hipeac.net/node/2419)。有了这些改变，就有可能在现实环境中收集使用TM的经验，从而找到剩余问题的解决方案，而剩下的问题还有很多。以下是其中的一些:

记录交易。在上面的解释中，我们假设记录了事务中使用的每个内存位置的确切位置。但是，这可能是低效的，特别是对于HTM支持。记录每个内存位置的信息意味着每个使用的内存位置都有几个字的开销。与CPU缓存(理论上也可以缓存单个单词)一样，这通常构成了过高的代价。相反，现在的CPU缓存一次处理64字节的缓存行。这意味着对于TM实现，我们描述中的第2步不必记录额外的依赖项，以防内存位置位于已经记录的块中。

但这也带来了问题。假设在最后的示例代码中，所有四个变量都在同一个块中。这意味着我们的假设f1 _ 1而且f2 2 _独立可执行是错误的。这种类型的块共享导致了高中止率。这与错误共享的问题有关，在这种情况下，错误共享也会发生，因此无论如何都应该纠正。

但是，这些错误的中止(我们可能希望这样称呼它们)不仅仅是性能问题。不恰当的变量放置实际上可能会导致永远不会取得任何进展的问题，因为它们总是在不经意间终止彼此。这可能是因为几个不同的事务同时进行，恰巧接触到缓存内存块，但地址不同。如果使用阻塞，这是一个必须解决的问题。

处理中止。前面描述的另一个细节是处理中止的方式。所描述的是所谓的惰性中止/惰性提交方法(简称lazy/lazy)。事务即使已经中止，也会继续工作，只有当整个事务成功时，事务的结果才会写入真正的内存位置。

不过，这并不是唯一的可能性。另一个恰恰相反:eager/急切的方法。在这种情况下，事务将被尽早确认为已终止，并在必要时重新启动。商店指示的效果也会立即生效。在这种情况下，内存位置的旧值必须存储在事务本地的内存中，以便在事务必须中止的情况下，可以恢复以前的内容。

还有很多其他的方法来处理这些细节。结果可能是没有一种方法是充分的。这很大程度上取决于单个事务的中止率。编译器和TM运行时很可能会同时实现多种不同的方式，如果这似乎提供了优势，就可以在它们之间切换以实现单个事务。

语义。的语义tm _原子块(或它最终将是什么)必须被指定。有必要将TM集成到其余的语言语义中。例如，TM必须与c++的异常处理集成。其他问题是对嵌套TM区域的处理和对局部变量的处理(它们不需要成为事务的一部分，但仍然必须在中止时重置)。

的性能。性能也是一个主要问题。编译器可以并且应该执行大量的优化，所有这些都需要研究。还有一些实际问题。如果在有竞争和无竞争的情况下使用相同的程序代码(例如，在单线程程序中)，通过TM引入的开销就太高了。因此，可能有必要为每个函数生成两个版本:一个支持TM，另一个不支持TM。然后，TM运行时必须确保尽可能频繁地使用不支持TM的版本。一侧的故障意味着性能损失，另一侧的故障意味着程序不能正确运行。

回到顶部

结论

TM承诺使并行编程更加容易。事务的概念已经出现在许多程序中(从业务程序到动态Web应用程序)，事实证明，对于程序员来说，它相当容易掌握。我们现在可以看到第一个实现的出现，但所有这些还远远没有准备好。还有很多研究要做。

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.

---

没有发现记录