ACM通信

研究突出了

TxLinux和MetaTM:事务性内存和操作系统

作者:克里斯托弗·罗斯巴赫，哈尼·e·拉马丹，欧文·s·霍夫曼，唐纳德·e·波特，阿迪蒂亚·班达里，埃米特·威切尔
ACM通信，2008年9月，第51卷第9期，83-91页
10.1145/1378727.1378747
评论

TxLinux是第一个使用硬件跨性内存(HTM)作为同步原语的操作系统，也是第一个在调度器中管理HTM的操作系统。TxLinux是Linux的修订版，是事务内存(TM)的第一个实际规模的基准测试。MetaTM是对x86体系结构的修改，它一般支持HTM，专门支持TxLinux。

本文描述并度量了TxLinux和支持它的HTM模型MetaTM。TxLinux从一个叫做协作事务自旋锁的新原语(cxspinlock)，它允许锁和事务保护相同的数据，同时保持这两个同步原语的优点。将TxLinux调度器与MetaTM对HTM的体系结构支持集成在一起，可以消除几个实际基准测试的优先级反转。

回到顶部

1.简介

为了提高性能，硬件制造商已经不再专注于提高时钟速度，而是专注于提高芯片上的核数。在新硬件上提高性能需要找到利用多硬件处理上下文提供的并行性的方法，这是直接放在软件程序员身上的负担。新一代的硬件不会提高用户应用程序的性能，除非采取一些措施使并发编程变得更容易，因此对并行编程的可访问方法的需求越来越迫切。

目前使用并行编程实现并发的方法严重依赖于线程。多个连续的控制流(线程)同时执行，使用锁来保护临界区。锁保证了对共享资源的互斥访问。不幸的是，使用线程和锁进行并行编程仍然非常困难，即使对于有经验的程序员也是如此。锁遭受许多众所周知的和长期以来令人遗憾的问题，如死锁、护送和优先级反转;它们的组合很差，需要复杂的排序规程来协调多个锁的使用。与锁相关的还有一个不吸引人的性能复杂度权衡。粗粒度锁定很容易推理，但牺牲了并发性能。细粒度锁定可以实现高性能，但它使代码更复杂，更难维护，因为它依赖于难以表示或执行的不变量。作为一种能够提供细粒度锁定的性能和粗粒度锁定的代码复杂度的技术，TM一直是最近研究关注的焦点。

TM是一种编程模型，可以极大地简化并行编程。程序员将可能访问共享数据的关键部分划分为交易，它们是完全执行(提交)或没有效果(中止)的内存操作序列。系统负责确保事务的执行自动(完全或完全不)，并在隔离，这意味着事务不能看到其他活动事务的效果，而且它自己的操作在提交之前在系统中是不可见的。虽然事务提供了临界区完全串行执行的抽象，但系统实际上是乐观地执行它们，允许多个事务并发进行，只要不违反原子性和隔离性。程序员受益，因为系统提供了原子性:不再需要对关键部分的部分故障进行推理。因为可以组合事务，而且不受死锁的影响，所以程序员可以基于事务自由组合线程安全的库。

HTM提供了TM的有效硬件实现，适合在操作系统中使用。操作系统受益于使用TM，因为TM提供了比锁更简单的编程模型。例如，操作系统具有锁定规程，这些规程指定了获取锁的顺序，以避免死锁。随着时间的推移，这些学科变得复杂，程序员很难掌握;事务不需要排序规程。因为许多应用程序在内核中花费了大量的运行时(通过进行系统调用，例如，读取和写入文件)，在操作系统中使用TM的另一个好处是提高了用户程序的性能，而不必修改或重新编译它们。

但是，在操作系统中管理和支持HTM需要在体系结构和操作系统方面进行创新。事务不能简单地替换或消除操作系统中的锁，主要有两个原因。首先，许多内核临界区执行I/O，实际上改变了磁盘或网卡等设备的状态。I/O对于TM来说是一个问题，因为TM系统认为，如果发生冲突，一个事务可以中止，回滚到它的开始，并重新执行。然而，当操作系统执行I/O时，它实际上改变了设备的状态(例如，通过向网络写入数据)。大多数设备在写操作完成后不能恢复到以前的状态，因此执行I/O的事务不能回滚和重新执行。第二个原因是，一些内核临界区是高度竞争的，目前对于高度竞争的临界区，锁比事务更有效。在争用情况下，事务的乐观性是没有根据的，TM系统执行的回滚和回滚会显著降低性能。

的exspinlock(协作事务自旋锁)是一种解决事务中I/O问题的新原语，它允许锁和事务协同工作，在保持各自优势的同时保护相同的数据。以前的HTM建议要求每个临界段的执行都由锁或事务保护，而cxspinlocks允许从不同临界段访问的临界段或数据结构有时由锁保护，有时由事务保护。cxspinlock动态和自动地在锁和事务之间进行选择。在默认情况下，cxspinlock试图将临界区作为事务执行，但是当处理器检测到I/O尝试时，事务将被回滚，cxspinlock将确保线程独占地重新执行临界区，从而阻塞其他事务性和非事务性线程。此外，cxspinlocks提供了一个方便的API，用于将基于锁的代码转换为使用事务。

HTM能够解决长期存在的由锁引起的优先级反转问题。当高优先级线程等待低优先级线程持有的锁时，会发生优先级反转。我们演示了TxLinux调度器和TM硬件中必要的修改，以几乎消除优先级和策略反转。此外，操作系统可以改进它的调度算法，通过利用线程的事务历史计算线程的动态优先级或取消调度冲突线程来帮助管理高争用。

本文的贡献如下:

1. 基于Linux内核创建事务操作系统TxLinux。TxLinux是使用HTM的最大的实际应用程序之一，也是第一个在内核中使用HTM的程序。
2. 在关键区域的事务同步和基于锁的同步之间进行合作的新机制。可以从事务性或非事务性线程调用协作事务自旋锁(cxspinlock)，它利用事务所支持的更大的并行性。
3. 在事务中处理I/O的新颖机制:执行I/O的事务由硬件重新启动，并在软件中获得常规锁。
4. HTM机制几乎消除了优先级反转。

回到顶部

2.HTM底漆

本节提供使用锁进行并行编程的背景知识，并概述使用HTM进行编程。

2.1.线程、同步和锁

当前的并行编程实践严重依赖于线程抽象。线程是一个顺序的控制流，具有私有程序计数器和调用堆栈。多个线程可以共享一个地址空间，允许它们使用共享变量通过内存进行通信。线程使单个逻辑任务能够利用多个硬件指令处理器，例如，通过将任务的子集移动到不同的处理上下文并并行执行它们。线程允许应用程序在等待来自磁盘驱动器或人工等慢速设备的输入时，保持对用户的响应或完成其他工作。多处理器是硬件级的并行计算资源，多线程是操作系统级的并行计算资源。

线程在共享数据或通过内存通信时需要同步，以避免竞争条件。当线程以违反数据结构不变量的方式并发访问同一数据结构时，就会发生竞态条件。例如，插入到链表中的两个线程之间的竞态条件可以在链表中创建一个循环。同步是一种消除竞争条件并维护数据结构不变量(比如每个列表都是空终止的)的协调。锁允许线程同步对数据结构的并发访问。锁通过强制保护数据结构互斥，确保每次只有一个线程可以访问该数据结构。当一个线程独占访问一个数据结构时，它保证不会看到其他线程所做的部分完成的更改。因此，锁有助于维护共享变量和资源的一致性。

锁给编程模型带来了许多挑战，比如死锁和优先级反转。但最重要的是，它们通常与程序员的实际需求和意图不匹配:临界段表示一致性约束，而锁提供排除。最终，当程序员将一组指令封装在一个临界区中时，它表示必须以原子的方式(要么完全执行，要么完全不执行)和隔离地(没有可见的部分更新)执行这些指令，以保持临界区操作的数据的一致性。HTM为这种抽象提供了硬件和软件支持:关键部分的原子的、隔离的执行。锁可以通过确保没有两个线程在临界区并发执行来保守地提供这种抽象。相比之下，TM乐观地提供了这种抽象，它允许并发执行关键部分，动态地检测隔离的违反，并在响应中重新启动一个或多个事务，如果事务没有提交，则恢复事务中所做的状态更改。结果是全局一致的事务顺序。

有很多锁的变体，比如读写锁和序列锁。这些锁变体减少了给定临界区的排除量，从而允许更多线程并发执行临界区，从而提高了性能。但是，这些变量只能在特定的情况下使用，例如当特定的关键区域只读取数据结构时。虽然锁变体可以减少锁的性能问题，但它们并不能减少复杂性，实际上还会增加复杂性，因为开发人员和代码维护人员必须继续推理特定的锁变体在特定的关键区域是否仍然安全。

2.2.同步与事务

HTM是自旋锁和序列锁等同步原语的替代品。事务比锁更容易推理。它们通过消除锁变量和与之相关的一致性缓存缺失来提高性能，并且通过允许不试图更新相同数据的线程并发执行来提高可伸缩性。

事务组成一个执行事务的线程，可以调用启动另一个事务的模块。第二个事务巢在第一位。相比之下，大多数锁实现不进行组合。如果一个函数获得一个锁，然后调用另一个函数，该函数最终尝试获得相同的锁，线程将死锁。对事务嵌套语义的研究是一个活跃的领域，^13，15，16但是平嵌套(所有嵌套事务都包含在最外层事务中)很容易实现。MetaTM使用平面嵌套，但所有事务嵌套模式都不受死锁和活锁的影响。

HTM设计具有一些关键的高级特性:用于管理事务的原语，用于检测事务之间冲突的机制，称为冲突检测，以及冲突发生时的处理机制，或争用管理．

的表格这里提供了一个HTM术语表，定义了重要的概念，并列出了MetaTM添加到x86 ISA中的基本元素。没有用斜体显示的机器说明是任何HTM设计的通用说明。斜体显示的是MetaTM专用的。的xbegin而且xend指令分别启动和结束事务。启动事务会导致硬件强制隔离对内存的读写，直到事务提交;更新在提交时对系统的其余部分可见。的xretry指令提供了显式重启的机制。

事务期间读和写的一组内存位置称为itsread-set而且写集,分别。一个冲突当一个事务的写集与另一个事务的读集和写集并集之间存在非空交集时，在两个事务之间发生。非正式地说，如果两个事务访问相同的位置，并且这些访问中至少有一个是写集，就会发生冲突。

当两个事务发生冲突时，其中一个事务将继续进行，而另一个事务将被选中以丢弃其更改并在重新启动执行xbegin:执行一个策略来选择丢失的交易是一个人的责任争用管理器．在MetaTM中，争用管理器在硬件中实现。作为争用管理决策基础的策略可能会对性能产生一级影响。²⁴争用管理中的高级问题包括不对称冲突，其中一个冲突访问是由事务外部的线程执行的。

回到顶部

3.HTM和操作系统

本节讨论在操作系统中使用TM进行同步的动机，并考虑更改基于锁的程序以使用事务的最常见方法。

3.1.为什么在操作系统中使用HTM ?

现代操作系统并行使用所有可用的硬件处理器，在多个用户进程之间并发地多路复用有限的硬件资源。操作系统将关键任务(如维护网络连接或将未使用的页面换出)委派给断断续续调度的独立内核线程。一个进程是一个或多个内核线程，每个内核线程直接由OS调度器调度。

操作系统工作的积极并行化的结果是跨内核本身内的多个线程共享内核数据结构。看似不相关的任务可能会在操作系统中创建复杂的同步。例如，考虑图1，这是Linux文件系统的简化dparent_notify函数。当访问、更新或删除文件时，调用此函数更新父目录的修改时间。如果两个不同的用户进程并发写入同一个目录中的不同文件，两个内核线程可以同时调用此函数来更新父目录修改时间，这将显示为争用，而不仅仅是dentry - > d_lock但是对于父目录p - > d_lock,p - > d_count，以及dcache - >锁)．虽然操作系统为程序员提供了涉及单个控制线程的单个顺序操作的抽象，但所有这些线程都共存于内核中。即使当操作系统管理访问不同的文件不同的程序、资源可以并发使用，操作系统必须同步自己的访问，以确保相关数据结构的完整性。

为了在这种共享模式存在的情况下保持良好的性能，许多操作系统要求程序员付出大量努力使同步变得细粒度化。，锁定只能保护尽可能少的数据。但是，同步会给操作系统编程和维护带来困难。在一项针对Linux bug的综合研究中，1025个bug中有346个(34%)涉及到同步⁷在Linux 2.5内核中发现了4个确认的死锁错误和8个未确认的死锁错误。同步的复杂性在Linux源文件中非常明显mm / filemap.c它在文件顶部有一个50行注释，描述文件中使用的锁顺序。该注释描述了文件中函数在调用深度为4处使用的锁。锁定是不可组合的;一个组件必须知道另一个组件使用的锁，以避免死锁。

TM可以帮助降低上下文中同步的复杂性dparent_notify函数。因为涉及到多个锁，所以操作系统必须遵循锁定顺序规则以避免死锁，这在TM中是不必要的。细粒度锁定由dparent_notify的发布dentry - > d_lock以及随后的收购p - > d_lock而且dcache_lock可以通过事务来省略。如果用不同的父目录中，基于锁的代码仍然强制进行一些序列化，因为dcache - >锁．然而，当事务不争夺相同的数据时，它们可以允许并发执行临界段。TM比锁更模块化，可以通过更简单/粗糙的锁提供更大的并发性;操作系统可以从中受益。

3.2.将Linux转换为Txlinux-SS

图1还说明了在基于锁的程序中引入事务的最常见范式:分别将锁的获取和释放映射到事务的开始和结束。这是在Linux中使用事务的第一个方法，称为TxLinux-SS。Linux拥有超过2000个自旋锁静态实例，TxLinux-SS中的大多数事务都是由转换自旋锁产生的。TxLinux-SS还将读写自旋锁变量和se-qlock转换为事务。根据从Syncchar工具收集的分析数据，¹⁸九个子系统中使用的锁被转换为使用事务。TxLinux-SS花了6个开发人员一年的时间来创建，并最终将Linux中大约30%的动态锁定调用转换为使用事务。

内核的TxLinux-SS转换暴露了几个严重的挑战，这些挑战阻止了像Linux这样基于锁的操作系统机械地转换为使用事务，包括锁函数的特殊使用、由于大量使用函数指针而难以遵循的控制流，以及最重要的I/O。为了确保隔离，HTM系统必须能够回滚丢失冲突的事务的影响。然而，HTM只能回滚处理器状态和物理内存的内容。另一方面，设备I/O的影响不能回滚，并且将I/O操作作为事务的一部分执行会破坏事务系统旨在保证的原子性和隔离性。这就是所谓的“输出提交问题”。⁶计算机系统无法解除导弹发射。

如果dentry_iput函数图1，执行I/O，如果事务中止，内核的TxLinux-SS事务化将无法正常工作。TM本身不足以满足操作系统的所有同步需求。受锁保护的临界区将不会重新启动，因此可以自由地执行I/O。操作系统中总是需要一些锁定同步，但是操作系统应该能够在任何可能的地方利用TM。由于事务和锁在任何现实实现中都必须共存，因此锁和事务之间的合作是必不可少的。

回到顶部

4.锁与事务之间的合作

为了在操作系统中同时允许事务锁和常规锁，我们提出了一个同步API，它提供了它们的无缝集成，称为协作事务自旋锁cxspinlocks．cxspinlock允许同一个临界区的不同执行与锁或事务同步。这种自由在可能的时候支持事务的并发性，在必要的时候加强锁的安全性。锁定可以用于I/O，用于保护硬件读取的数据结构(例如，页表)，或者用于特定数据结构的高竞争访问路径(其中事务的性能可能会因过度重启而受到影响)。cxspinlock API还提供了一个简单的升级路径，让内核使用事务来代替现有的同步。

cxspinlock仅对内核是必需的;它们允许用户编程模型保持简单。用户不需要它们，因为他们不能直接访问I/O设备(在Linux和大多数操作系统中，用户通过调用操作系统来执行I/O)。阻止用户对设备的直接访问是一个常见的操作系统设计决策，它允许操作系统在不合作的用户程序之间安全地多路复用设备。希望事务和锁共存的复杂用户程序可以使用cxspinlocks，但这不是必需的。

在事务中使用传统的Linux自旋锁是可能的，并且将保持互斥。然而，传统的自旋锁降低了事务的并发性，缺乏公平性。传统的自旋锁阻止多个事务线程并发执行关键区域。关键区域中的所有事务线程都必须读取自旋锁内存位置以获得锁，并且必须写入该位置以获得锁并释放锁。事务性线程之间的写共享将阻止并发执行，即使临界区中“实际工作”的并发执行是安全的。此外，传统的自旋锁不能帮助解决I/O问题。获得自旋锁的事务线程可以重新启动，因此它不能执行I/O。

事务性线程的进程可能被使用自旋锁的非事务性线程不公平地限制。在MetaTM中，事务性线程和非事务性线程之间的冲突(非对称冲突)总是以有利于非事务性线程的方式得到解决。为了提供隔离，HTM系统保证非事务性线程总是赢得非对称冲突(如MetaTM)，或者事务性线程总是赢得非对称冲突(如Log-TM)¹⁴)．无论是哪种约定，传统的自旋锁都会导致事务性线程和非事务性线程之间的不公平。

4.1.合作事务自旋锁

Cxspinlocks允许用锁或事务安全保护单个关键区域。非事务性线程可以在受保护的临界区内执行I/O，而不必担心在重新启动时撤消操作。许多事务线程可以同时进入保护相同共享数据的临界区，从而提高性能。MetaTM中的简单返回代码允许动态地在锁和事务之间进行选择，从而简化了程序员的推理。cxspinlock确保了一组行为，允许事务性和非事务性代码正确使用相同的临界段，同时保持公平性和高并发性:

• 多个事务线程可以进入一个临界区，而不会在锁变量上发生冲突。非事务性线程将事务性线程和其他非事务性线程排除在临界区之外。
• 方法轮询cxspinlockxtest指令，该指令允许线程检查锁变量的值，而不将锁变量输入事务的读集，使事务避免在锁被释放时重新启动(另一个线程写入锁变量)。这对于获取嵌套的cxspinlock尤其重要，其中线程在尝试获取之前已经完成了事务性工作。
• 非事务性线程使用一条指令(xcas)，由事务争用管理器仲裁。这实现了锁和事务之间的公平性，因为争用管理器可以实现多种有利于事务性线程、非事务性线程、读取器、写入器等的策略。

图2展示了API和实现。cxspinlock可以通过以下两个函数获得:cx_exclusive而且cx_optimistic．两个函数都以锁地址作为参数。

cx_optimistic是自旋锁的临时替代品，对于几乎所有在Linux内核中执行的锁都是安全的(例外是一些低级的页表锁和在线程之间传递所有权的锁，例如保护运行队列的锁)。cx_optimistic乐观地尝试使用事务保护临界区。如果临界段内的代码路径受cx_optimistic要求互斥，然后事务重新启动并独占获取锁。中的代码图1，它可能会由于裸事务的I/O而失败，使用cxspinlocks函数，利用事务的乐观性dentry_iput函数不做I/O，当它做的时候用独占访问重新尝试。

总是需要互斥的控制路径(例如，总是执行I/O的控制路径)可以通过cx_exclusive．访问同一数据结构的其他路径可能以事务方式执行cx_optimistic．允许不同的关键区域与的混合同步cx_optimistic而且cx_exclusive确保最大的并发性，同时维护安全。

4.2.将Linux转换为txlixx - cx

内核的TxLinux-SS转换用裸事务替换选定子系统中的自旋锁，而txlixx - cx则用cxspinlocks替换所有自旋锁。该API解决了操作系统上下文中事务的限制，这不仅使转换更多的锁成为可能，而且使转换更迅速成为可能:与创建TxLinux-SS所需的6年开发人员相比，tx - lixx - cx只需要一个开发人员月。

回到顶部

5.HTM知道日程安排

本节描述MetaTM如何允许操作系统将其调度优先级通信到硬件冲突管理器，这样TM硬件就不会破坏操作系统的调度优先级或策略。

5.1.优先级和策略反转

锁会颠倒操作系统调度优先级，导致高优先级线程等待低优先级线程。一些操作系统(如Solaris)具有处理优先级反转的机制，例如优先级继承，在这种机制中，等待的线程临时将其优先级捐赠给持有锁的线程。RT(实时)Linux的最新版本也实现了优先级继承。优先级继承是复杂的，虽然该技术可以缩短优先级反转的长度，但不能消除它。此外，它还需要将忙碌等待的原语(如自旋锁)转换为阻塞原语(如互斥锁)。转换到互斥锁在面对优先级反转时提供了延迟的上限，但它降低了总体响应时间，并不能消除问题。

TM的简单硬件争用管理策略可以反转操作系统调度优先级。HTM研究人员一直专注于简单的硬件争用管理，它保证不受死锁和活动锁的影响，例如，时间戳，最老的事务获胜。^20.时间戳策略不会死锁或激活锁，因为在事务重新启动期间没有刷新时间戳。事务最终将成为系统中最老的事务，并且它将成功。但是，如果一个操作系统调度程序优先级较高的进程可以在一个低优先级的进程启动一个事务之后启动一个事务，并且这些事务发生冲突，那么时间戳策略将允许低优先级的进程继续执行，而高优先级的进程将被迫重新启动。

锁和事务不仅可以反转调度优先级，还可以反转调度策略。支持软实时进程的操作系统，如Linux，允许实时线程与非实时线程同步。这样的同步会导致政策反演一个实时线程等待一个非实时线程。策略反转比优先级反转更为严重。实时进程不仅仅是具有更高优先级的常规进程，操作系统调度程序对它们的处理是不同的(例如，如果一个实时进程存在，它将总是在一个非实时进程之前调度)。正如优先级反转一样，许多争用管理策略将锁的策略反转带入事务领域。尊重操作系统调度策略的争用管理器可以在很大程度上消除策略反转。

HTM系统的争用管理器几乎可以消除策略和优先级反转。当一个事务的写集与另一个事务的读和写集的并集具有非空交集时，将调用争用管理器。如果争用管理器解决了这个冲突，有利于具有更高操作系统调度优先级的线程，那么事务将不会经历优先级反转。

5.2.使用操作系统优先级的竞争管理

为了消除优先级和策略反转，metatm为操作系统提供了一个接口，用于向硬件争用管理器通信调度优先级和策略(其他研究人员建议的一种机制)^14，22)．MetaTM实现了一种新的争用管理策略称为os_prio．的os_prio策略是争用管理策略的混合。前者更倾向于具有最大调度价值的事务而不是操作系统。由于调度优先级值的数量较少，冲突优先级中的关系并不罕见，因此os_prio下一个雇佣时间戳。这种混合争用管理策略诱导事务的总顺序，因此是无活动锁的。

MetaTM体系结构中的单个寄存器允许操作系统将其调度优先级传递给争用管理器。TxLinux将进程的动态调度优先级和调度策略编码为单个整数冲突的优先级，在调度进程的过程中写入特权状态寄存器。寄存器只能由操作系统写入，因此用户代码不能更改该值。在调度量期间，寄存器的值不会改变。例如，调度策略可能编码在冲突优先级的上位，而调度优先级编码在低位。一个8位的值足以记录Linux进程的策略和优先级值。一旦检测到冲突，os_prio争用管理器倾向于冲突优先级值最大的事务。

的os_prio策略没有死锁和活动锁，因为冲突优先级是在xbegin指令被执行，并且操作系统在事务的生命周期内从不改变冲突优先级(一些设计允许事务在多个调度量子中继续)。当优先级相等时，os_prio默认为大小，默认为时间戳当读写集大小相等时。因此,元组(冲突优先级、规模、年龄)归纳出一个总的顺序，使os_prio不存在死锁和活动锁的策略。

回到顶部

6.评价

Linux和TxLinux版本2.6.16.1运行在Simics机器模拟器版本3.0.27上。在接下来的实验中，Simics建模了一台x86 SMP机器，它有16和32个处理器，IPC为每个周期一条指令。内存层次结构使用每个处理器的分割指令和数据缓存(16 KB具有4向结合性，64字节缓存线，1周期缓存命中和16周期未命中惩罚)。第一级数据缓存具有额外的标记位来管理事务性数据。有一个统一的秒级缓存，它是4mb, 8路关联，64字节缓存线，对主内存有200个周期的缺失惩罚。一致性是通过事务性MESI窥探协议来维护的，主内存是单个共享的1gb。磁盘设备模拟了PCI带宽限制、DMA数据传输，并具有固定的5.5毫秒访问延迟。所有基准测试都是脚本化的，不需要用户交互。

6.1.工作负载

我们在许多应用程序基准测试上评估了TxLinux-SS和txlixx - cx。在哪里P表示处理器的数量，它们是:

• pmake(让- jP编译libFLAC源代码树的一部分)
• MAB(修改安德鲁基准，P实例，没有编译阶段)
• 为TeTeX的一个子集配置脚本，P实例)
• 查找78MB目录(29 dirs, 968个文件)，P实例)
• 建模web缓存的文件系统活动，P实例)
• dpunishment(一个文件系统压力测试，操作被分割P流程)

需要注意的是，这些基准测试都没有直接使用事务;基准测试运行内核，而内核又使用事务进行同步。

6.2.性能

图3显示了Linux、Tx-Linux-SS(使用裸事务)和txlixx - cx(使用cxspin-locks)在16个cpu上的同步性能，分解为在锁上旋转所花费的时间和终止和重试事务所花费的时间。Linux同步时间占内核时间的1%到6%，而TxLinux同步时间占内核时间的1%到12%。然而，TxLinux使用事务和cxspinlock分别平均减少了34%和40%的同步时间。虽然HTM通常会减少同步开销，但它会使的时间损失增加一倍以上邦尼+ +。这种损失是由于事务重新启动、退出，但继续失败造成的。自bon-nie + +单个目录中大量创建和删除小文件是否会导致文件系统代码路径中的争用，从而导致处理目录更新的文件系统代码出现病态重启行为。内核数据结构上的高争用会导致重复的回退和重新启动会有效地使一些事务挨饿。在重新启动之前使用回退作为处理这种高争用的技术对于复杂系统来说可能是不够的:事务系统可能需要对始终没有完成的事务进行排队。

在所有基准测试的平均值上，TxLinux-SS在16个cpu上比Linux慢2%，在32个cpu上比Linux快2%。的病态重新启动情况导致了16 CPU案例中的减速邦妮+ +上面讨论的基准;这种病态在32 CPU的情况下不存在，而在没有事务的情况下邦妮TxLinux-SS在16个cpu和32个cpu上的加速是一样的。txlixx - cx在16和32个cpu上的速度分别比Linux提高了2.5%和1%。这些性能增量可以忽略不计，并不能证明有决定性的性能提高。然而，在操作系统中使用HTM的理由是为了减少编程的复杂性。这些结果表明，HTM可以增强可编程性，而不会对性能产生负面影响。

6.3.优先级反转性能

图4显示了事务优先级反转在TxLinux中发生的频率。在这种情况下，优先级反转意味着默认SizeMatters争用管理政策²¹在冲突中决定获胜事务时，优先选择操作系统调度优先级较低的进程。基于时间戳的争用管理的结果类似。大多数基准测试表明，相当大比例的事务冲突导致了优先级反转，在我们测试的所有内核和CPU配置中，平均为9.5%，而在find配置中，as为25%。优先级反转随着处理器数量的增加而减少，但这种趋势并不严格。pmake和bonnie++基准测试显示处理器数量越高，性能越好。事务冲突的数量和分布是混乱的，因此改变处理器的数量可以改变冲突行为。os_prio争用管理策略在我们的基准测试中完全消除了优先级反转，性能成本低于1%。相比之下，使用锁改进优先级反转的技术(如优先级继承)只提供优先级反转的上限，并且需要将轮询锁转换为阻塞锁的性能损失。

naïve争用管理违反操作系统调度优先级的频率强烈支持一种让操作系统参与争用管理的机制，例如，通过向硬件通信提示。

回到顶部

7.相关工作

由于篇幅有限，我们建议有兴趣的读者阅读完整的讨论，^21，23并对相关文献进行简要综述。Larus和Rajwar提供了到2006年底TM研究的全面参考。¹²

HTM．病和苔藓¹⁰给出了HTM最早的设计之一;从那以后，许多建议都集中在支持HTM的体系结构机制上，^{5，8，13，14，25}以及对HTM的语言级支持。TM虚拟化的一些建议(当事务溢出硬件资源时)涉及到操作系统，^2，5但是到目前为止还没有任何建议允许操作系统本身使用事务进行同步。然而，本文研究了在操作系统中使用HTM时产生的系统问题以及操作系统对HTM的支持。拉杰瓦尔和古德曼探索投机¹⁹和事务^20.关键部分的执行。这些在违反隔离时退回到锁定的机制类似于(但不那么通用)在事务上下文中执行的cxspinlock技术，并在检测到I/O时返回到锁定。

I / O的事务．关于事务中I/O的建议分为三个基本阵营:给事务一个隔离的逃生口;¹⁵¹⁷延迟I/O直到事务提交，^8，9并保证执行I/O的线程将提交。^2，8所有这些策略都有严重的缺陷。¹¹．Escape hatch引入了限制编程模型的复杂性和正确性条件，并且在常见的编程习惯中很容易被违反。当执行I/O的代码依赖于它的结果时，延迟I/O是不可能的，例如，设备寄存器读取可能返回一个状态字，操作系统必须解释这个状态字才能完成事务。最后，保证事务将被提交会严重限制调度程序的灵活性，并且对于长时间运行或高度竞争的事务，可能会导致串行瓶颈或死锁。与保证线程冲突的其他处理器上的非事务性线程将被迫暂停，直到保证线程提交其工作。这可能会导致丢失的计时器中断和内核中的死锁。

调度．Microsoft Windows、Linux和Solaris等操作系统实现了复杂的、基于优先级的抢占式调度器，为每个类提供了不同的优先级类和各种调度技术。Linux RT补丁支持优先级继承，以帮助减轻优先级反转的影响:虽然我们的工作也解决了优先级反转，但Linux RT补丁实现将自旋锁转换为互斥锁。虽然这些机制保证了优先级反转的上限，但是os_prio策略允许竞争管理器有效地消除优先级反转，而不需要原语阻塞或涉及调度器。

回到顶部

8.结论

本文首次描述了使用HTM作为同步原语的操作系统，并介绍了支持HTM的调度和锁与事务之间的合作的创新技术。TxLinux演示了HTM提供了与锁相当的性能，并且可以简化代码，同时与现代操作系统中的其他同步原语共存。cxspinlock原语为事务中I/O的长期问题提供了解决方案，该API大大简化了从锁定原语到事务的转换。在操作系统中引入事务作为同步原语，平均而言可以减少同步浪费的时间，但在竞争非常激烈的情况下，或者临界段大到足以引起HTM虚拟化开销时，可能会导致传统锁不会出现的病态。HTM感知调度消除了我们研究的所有工作负载的优先级反转。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

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