下载本文的PDF版本 PDF

使用事务内存的并行编程

尽管事务内存主要仍是一个研究项目，但它显示出使并行编程更轻松的希望。

Ulrich Drepper，红帽公司

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

为了使用这些额外的核心，程序必须并行化。多个执行路径必须协同工作才能完成程序必须执行的任务，并且尽可能多的工作必须同时发生。只有这样才有可能加速程序（即，减少总运行时间）。阿姆达尔定律将其表示为

 1
 __________ 
 (1-P) + P/S

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

同步问题

这是理论。将其变为现实是另一个问题。仅仅编写一个普通的程序本身就是一个问题，正如程序可用的不断涌现的错误修复所见。尝试将程序拆分成多个可以并行执行的部分，增加了一个全新的额外问题维度

程序员的困境

程序员陷入了两个问题之间

一个功能不正确的程序可以尽可能快地运行，但它仍然是无用的。因此，并行化必须适可而止，以免引入第二类问题。这种并行化程度取决于程序员的经验和知识。多年来，已经开发了许多项目，试图自动捕获与锁定相关的问题。没有一个项目成功地为真实世界中出现的程序规模解决问题。静态分析成本高昂且复杂。动态分析必须依赖于启发式方法和测试用例的质量。

对于复杂的项目，不可能一次性转换整个项目以允许更多的并行性。相反，程序员迭代地添加越来越细粒度的锁定。这可能是一个漫长的过程，如果中间步骤的测试不够彻底，则可能会弹出并非由最近添加的一组更改引起的问题。此外，正如经验所表明的那样，有时很难摆脱大锁。例如，看看Linux内核邮件列表上的BKL（大内核锁）讨论。BKL是在Linux在90年代中期首次获得SMP（对称多处理）支持时引入的，到2008年我们仍然没有摆脱它。

越来越多的人得出结论，锁定是解决一致性问题的错误方法。对于不完全熟悉并行编程的所有问题的程序员来说，尤其如此（这意味着几乎所有人）。

另寻他路

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

数据库世界的解决方案是事务。数据库程序员显式声明哪些数据库操作属于事务。在事务中执行的操作可以以任意顺序完成，并且在事务提交之前实际上不会生效。如果事务中存在冲突（即，其他操作同时修改相同的数据集），则事务将回滚并且必须重新启动。

事务的概念是大多数编程任务自然而然地产生的。如果作为事务一部分的所有更改都一次性原子地提供，则更改添加到事务中的顺序无关紧要。无需以特定顺序执行操作极大地有所帮助。所有需要做的就是记住始终将数据集修改为事务的一部分，而不是以快速而肮脏的直接方式。

事务内存

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

幸运的是，这是不需要的。TM（事务内存）的概念已在没有此限制的情况下定义。Maurice Herlihy和J. Eliot B. Moss在他们1993年的论文1中描述了一种硬件实现，该实现可以在现有缓存一致性协议之上合理地轻松实现。2

论文中的描述是通用的。首先，不需要要求事务内存完全或部分地在硬件中实现。对于论文标题中提到的目的（无锁数据结构），硬件支持很可能将是必须的。但这在一般情况下并非如此，我们稍后会看到。其次，描述必须转移到今天可用的硬件。这包括实现细节，例如缓存一致性协议的可能重用和事务的粒度，最有可能的粒度不是单个字，而是缓存行。

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

这已经更进一步。由于今天的硬件大多缺乏HTM支持，STM（软件TM）是大多数研究项目今天正在使用的。借助基于STM的解决方案，可以提供TM功能的接口，这些接口稍后可以在混合TM实现中实现，如果可能，可以使用硬件。这允许程序员即使在硬件中没有HTM支持的情况下，也可以使用TM提供的简化来编写程序。

给我看问题

为了让读者相信TM值得付出所有努力，让我们看一个小例子。这并非旨在反映实际代码，而是说明真实代码中可能发生的问题

long counter1;
long counter2;
time_t timestamp1;
time_t timestamp2;
void f1_1(long *r, time_t *t) {
	*t = timestamp1;
	*r = counter1++;
}
void f2_2(long *r, time_t *t) {
   *t = timestamp2;
   *r = counter2++;
}
void w1_2(long *r, time_t *t) {
   *r = counter1++;
   if (*r & 1)
   *t = timestamp2;
}
void w2_1(long *r, time_t *t) {
   *r = counter2++;
   if (*r & 1)
   *t = timestamp1;
}

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

当然可以定义一个单独的互斥锁，并要求在四个函数中的每一个函数中都获取此互斥锁。验证这是否会产生预期的结果很容易，但是性能可能远非最佳。

假设大多数时候只使用函数f1_1和f2_2。在这种情况下，这些函数的调用者之间永远不会有任何冲突：f1_1和f2_2的调用者可以和平共处。这意味着使用单个锁会不必要地减慢代码速度。

那么，使用两个锁。但是如何定义它们呢？语义必须在一种情况下为“当使用counter1和timestamp1时”，在另一种情况下为“当使用counter2和timestamp2时”。这可能适用于f1_1和f2_2，但不适用于其他两个函数。在这里，成对的counter1/timestamp2和counter2/timestamp1一起使用。因此，我们必须再向下深入一层，并为每个变量分配一个单独的锁。

假设我们会这样做，我们很容易受到诱惑而编写如下代码（这里只提到了两个函数；另外两个是镜像）

void f1_1(long *r, time_t *t) {
   lock(l_timestamp1);
   lock(l_counter1);
 *t = timestamp1;
 *r = counter1++;
}
void w1_2(long *r, time_t *t) {
 lock(l_counter1);

 
*r = counter1++;
   if (*r & 1) {
   lock(l_timestamp1);
   *t = timestamp2;
   unlock(l_timestamp1);
}
 unlock(l_counter1);
}

此示例中w1_2的代码是错误的。我们不能延迟获取l_timestamp1锁，因为它可能会产生不一致的结果。即使它可能较慢，我们也必须始终获取锁

void w1_2(long *r, time_t *t) {
   lock(l_counter1);
   lock(l_timestamp1);
 *r = counter1++;
   if (*r & 1) {
   *t = timestamp2;
 unlock(l_timestamp1);
   unlock(l_counter1);
}

这是一个简单的更改，但结果也是错误的。现在我们尝试以与f1_1不同的顺序锁定w1_2中所需的锁。这可能会导致死锁。在这个简单的示例中，很容易看出情况确实如此，但是对于稍微复杂一些的代码，这是一个非常常见的现象。

此示例表明：（1）很容易陷入需要许多单独的互斥锁才能允许足够并行性的情况；（2）正确使用所有互斥锁本身就非常复杂。

正如本文的主题所期望的那样，TM将能够在此和许多其他情况下为我们提供帮助。

使用TM重写

可以使用TM重写前面的示例。在以下示例中，我们正在使用C的非标准扩展，这些扩展以某种形式或另一种形式可能出现在启用TM的编译器中。这些扩展很容易解释。

void f1_1(long *r, time_t *t) {
   tm_atomic {
   *t = timestamp1;
   *r = counter1++;
   }
}
void f2_2(long *r, time_t *t) {
   tm_atomic {
   *t = timestamp2;
   *r = counter2++;
   }
}
void w1_2(long *r, time_t *t) {
   tm_atomic {
   *r = counter1++;
   if (*r & 1)
   *t = timestamp2;
   }
}
void w2_1(long *r, time_t *t) {
   tm_atomic {
   *r = counter2++;
   if (*r & 1)
   *t = timestamp1;
   }
}

在这种情况下，我们所做的只是将操作包含在名为tm_atomic的块中。tm_atomic关键字指示以下块中的所有指令都是事务的一部分。对于每个内存访问，编译器都可以生成如下所示的代码。调用函数是一个挑战，因为被调用的函数也必须是事务感知的。因此，可能有必要提供编译函数的两个版本：一个版本支持事务，另一个版本不支持事务。如果任何传递调用的函数本身使用tm_atomic块，则必须处理嵌套。以下是一种执行此操作的方法

  1. 检查同一内存位置是否是另一个事务的一部分。
  2. 如果是，则中止当前事务。
  3. 如果否，则记录当前事务引用了该内存位置，以便其他事务中的步骤2可以找到它。
  4. 根据它是读取还是写入访问，要么（a）加载内存位置的值（如果变量尚未修改）或从本地存储加载（如果已修改），要么（b）将其写入变量的本地存储。

如果事务先前访问了同一内存位置，则步骤3可以省略。对于步骤2，还有其他选择。事务可以执行到最后，然后撤消更改，而不是立即中止。这称为延迟中止/延迟提交方法，与典型的数据库事务中发现的急切/急切方法（本文前面描述）相反。

现在需要的是定义在到达tm_atomic块末尾时完成的工作

（即，事务已提交）。这项工作可以描述如下

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

描述足够简单；真正的问题是有效地实现一切。在讨论这个问题之前，让我们简要看一下所有这一切是否正确并满足所有要求。

正确性和保真度

假设实现正确（当然），我们能够确定内存位置当前是否用作另一个实现的一部分。这是否意味着读取或写入访问都无关紧要。因此，很容易看出我们永远不会产生不一致的结果。只有当tm_atomic块内的所有内存访问都成功并且事务未中止时，事务才会被提交。然而，这意味着就内存访问而言，线程完全是孤立的。我们已将代码还原为没有锁的初始代码，这显然是正确的。

关于正确性的唯一剩余问题是：如果使用此TM技术的线程不断地相互中止，它们真的会终止吗？从理论上讲，证明这一点当然是可能的，但在本文中，指出类似的问题就足够了。在基于IP的网络中（与令牌环网络不同），所有连接的机器都可能同时开始发送数据。如果多于一台机器发送数据，则会发生冲突。这种冲突会被自动检测到，并且发送尝试会在短暂的等待期后重新启动。IP定义了一种指数退避算法，网络堆栈必须实现该算法。鉴于我们生活在一个由基于IP的网络主导的世界中，这种方法肯定可以正常工作。结果可以直接转移到TM的问题上。

还有一个问题仍然存在。早些时候，我们拒绝了使用单个锁的解决方案，因为它会阻止f1_1和f2_2的并发执行。这里看起来如何？正如容易看到的那样，用于这两个函数的内存位置集是不相交的。这意味着f1_1和f2_2中事务的内存位置集也是不相交的，因此，由于f2_2的执行以及反之亦然，f1_1中对并发内存使用的检查永远不会导致中止。因此，使用TM确实可以轻松地解决此问题。

再加上描述事务的简洁方式，应该很明显为什么TM如此有吸引力。

TM的现状如何？

在大家对TM的前景过于兴奋之前，我们应该记住，它仍然是一个非常重要的研究主题。第一个实现正在变得可用，但我们仍然有很多东西要学习。例如，VELOX项目(http://www.velox-project.eu/)的目标是对操作系统中可以使用TM技术的所有位置进行全面分析。这从操作系统内核中的无锁数据结构扩展到应用服务器中的高级用途。该分析包括有和没有硬件支持的TM。

VELOX项目还将研究应添加到更高级别编程语言中的TM原语的最有用语义。在前面的示例中，它是一个简单的tm_atomic关键字。这不一定是正确的形式；所描述的语义也不一定是最佳的。

今天有许多独立的STM实现可用。人们获得经验的一个可能选择是TinySTM（http://tinystm.org）。它提供了TM所需的所有原语，同时具有可移植性，体积小，并且仅依赖于主机系统上可用的一些服务。

基于TinySTM和类似的实现，我们将很快看到诸如tm_atomic之类的语言扩展出现在编译器中。一些专有编译器具有支持，并且GNU编译器的第一个补丁也可用(http://www.hipeac.net/node/2419)。通过这些更改，可以在实际情况下收集使用TM的经验，以找到剩余问题的解决方案——并且仍然存在许多问题。以下只是一些

记录事务。 在前面的解释中，我们假设记录了事务中使用的每个内存位置的确切位置。但这可能效率低下，尤其是对于HTM支持。为每个内存位置记录信息意味着为使用的每个内存位置增加几个字的开销。与理论上也可以缓存单个字的CPU缓存一样，这通常构成了过高的代价。相反，今天的CPU缓存一次处理64字节的缓存行。对于TM实现，这意味着在我们描述中的步骤2中，如果内存位置位于已记录的块中，则不必记录额外的依赖项。

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

这些错误的中止，正如我们可能想要称呼它们的那样，不仅仅是一个性能问题。变量的不幸放置实际上可能会导致它们永远无法取得任何进展的问题，因为它们不断地无意中相互中止。这可能是由于同时进行的几个不同的事务恰好触及相同的缓存内存块，但地址不同。如果使用阻塞，这是一个必须解决的问题。

处理中止。 早先描述的另一个细节是处理中止的方式。已经描述的是所谓的延迟中止/延迟提交方法（简称为延迟/延迟）。即使事务已经中止，事务也会继续工作，并且只有当整个事务成功时，事务的结果才会被写入实际内存位置。

但这并不是唯一的可能性。另一种可能性是完全相反的情况：急切/急切方法。在这种情况下，事务将尽早被识别为中止，并在必要时重新启动。存储指令的效果也将立即生效。在这种情况下，内存位置的旧值必须存储在事务本地的内存中，以便在事务必须中止的情况下可以恢复先前的内容。

有很多其他方法可以处理细节。事实证明，没有一种方法是足够的。很大程度上取决于单个事务的中止率。很可能编译器和TM运行时将同时实现多种不同的方法，并且如果这似乎提供了优势，则在各个事务之间切换它们。

语义。 必须指定tm_atomic块（或最终将成为的任何内容）的语义。有必要将TM集成到语言语义的其余部分中。例如，TM必须与C++的异常处理集成。其他问题包括嵌套TM区域的处理和局部变量的处理（它们不必是事务的一部分，但仍然必须在中止时重置）。

性能。 性能也是一个主要问题。编译器可以并且应该执行许多优化，所有这些都需要研究。还存在实际问题。如果在有争议和无争议的情况下（例如，在单线程程序中）使用相同的程序代码，则通过TM引入的开销太高。因此，可能有必要生成每个函数的两个版本：一个版本支持TM，另一个版本不支持TM。然后，TM运行时必须确保尽可能频繁地使用不支持TM的版本。一方的失败意味着性能损失；另一方的失败意味着程序将无法正确运行。

结论

TM有望使并行编程变得更加容易。事务的概念已经存在于许多程序中（从业务程序到动态Web应用程序），并且事实证明，程序员很容易掌握它。我们可以看到第一个实现现在正在出现，但所有实现都远未达到成熟阶段。还有许多研究工作要做。

参考文献

  1. Herlihy，M.，Moss，J.E.B. 1993年。事务内存：无锁数据结构的架构支持。第20届计算机体系结构国际研讨会论文集； http://citeseer.ist.psu.edu/herlihy93transactional.html。
  2. Drepper，U. 2007年。每个程序员都应该了解的关于内存的知识； http://people.redhat.com/drepper/cpumemory.pdf。

ULRICH DREPPER是红帽公司的咨询工程师，他在该公司工作了12年。他对各种底层编程感兴趣，并且参与Linux已有近15年。

acmqueue

最初发表于Queue第6卷，第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 - 实用同步原语的可扩展性技术
在理想的世界中，应用程序有望在越来越大的系统上执行时自动扩展。但是，在实践中，不仅这种扩展不会发生，而且在那些更大的系统上看到性能实际上恶化是很常见的。



© 保留所有权利。

© . All rights reserved.