第8章对同步的硬件支持

为了保证并行程序执行的正确性和高效性，构建一个共享存储多处理器系统的硬件支持必须要解决缓存一致性、存储一致性和对同步原语的支持等问题。从软件的观点来看被广泛使用的同步原语包括锁、栅栏和点对点同步（信号量）。举例来说，锁和路障被大量使用在DOALL并行性和具有链式数据结构的应用程序上，而signal/wait同步对流水线DOACROSS并行性来说至关重要。

如今将最低级别的同步原语以原子指令的形式在硬件上实现，然后将其他所有高级别的同步原语在软件中实现。将讨论锁和栅栏的不同实现之间的权衡，并将说明达成快速但可扩展的同步不是微不足道的。通常在可扩展性（同步延迟和带宽如何随着更大数量的线程而扩展）和无竞争延迟（线程不同时尝试执行同步所带来的延迟）之间会做出权衡。对于大型系统来说，在原子指令之上实现的软件栅栏和锁可能不具有足够的可扩展性。

最后，将讨论事务内存，它在最新的多核体系结构中被支持。事务内存为协同并行执行提供了一个更高的抽象级别，在有些情况喜爱可移除对低级原语（比如锁）的需求。

8.1 锁的实现

8.1.1 对锁实现性能的评估

锁性能评价标准：
1. 无竞争获取锁延迟：当线程间没有竞争时，获取一个锁所花费的时间。
2. 通信量：总的通信量，是参与竞争锁的线程数或者处理器数的函数。通信量可以分为三个字部分，即当一个锁空闲时获取产生的通信量、当一个锁不空闲时锁获取产生的通信量；锁释放时产生的通信量。
3. 公平性：线程同其他线程相比被允许持有锁的程度。公平性的标准是在一个锁实现中，线程饥饿的情况是否可能存在，即一个线程不能够长时间地持有锁，即使这个锁在这段时间内是空闲的。
4. 存储：需要的存储空间是线程数的函数。一些锁的实现要求一个恒定的存储空间，可能与共享锁的线程数有关。

8.1.2 对原子指令的需求

软件机制并不能扩展互斥，因为执行的静态指令的数量，以及为了查看线程是否能够获取到锁而需要检查的变量的数量，都会随着线程数的增加而增加。相反，如果一个原子指令能够执行一系列的加载、比较、其他指令以及存储指令，那么可以实现一个简单的锁，其中取锁只需要依赖检测一个变量就足够了。

在当今系统中，大部分的处理器支持将一个原子指令作为最低级的原语，同时基于它还可以构建其他同步原语。一个原子指令以不可分割的方式执行一系列读、修改和写操作。

原子表达了两件事：
1. 要么整个序列的指令都被完整执行，要么其中任何一条指令都不执行。
2. 在任何给定的时间内，只有一条原子指令能够被执行。来自多个处理器的多指令序列需要被序列化。

经常使用的原子类型指令：
1. test-and-set Rx，M：读取存储在M的值，将这个值与一个常数（如0）进行比较，如果它们相匹配，那么将寄存器Rx中的值存储到存储单元M中。
2. fetch-and-op M：读取存储单元M的值，对这个值进行操作（如果增值、减值、加法、减法），然后将得到的新值存储到M中。在有些情况下，会指定额外的操作数。
3. exchange Rx，M：自动交换存储单元M中值和寄存器Rx中的值。
4. compare-and-swap Rx，Ry，M：比较存储单元M中的值和寄存器Rx中的值，如果它们匹配，将寄存器Ry中的值写到M中，然后拷贝寄存器Rx中值到寄存器Ry中。

读者可能会提出2个问题：
1. 一个原子指令如何确保原子性？
2. 一个原子指令如何被用于同步控制结构？

首先讨论第一个问题：一个原子指令本质上为程序提供了一个保障：指令锁代表的一系列操作将会被完整地执行。硬件必须提供正确的机制来保障一系列操作的原子性。

在x86指令集中，除了原子指令外，还可以通过用LOCK作为前缀来对常规的整数指令进行原子操作。

幸运的是，缓存一致性协议提供了原子性被保障的基础。举例，当遇到一个原子指令时，这个一致性协议知道需要保证其原子性。它首先会获得对存储单元M的“独家所有权”（通过将其他包含M的缓存块中的拷贝置为无效）。当获得独家所有权之后，这个协议会确保只有一个处理器能够访问这个块，而如果其他处理器在此时想要访问的话就会经历缓存缺失，接下来原子指令就可以执行了。在原子指令持续期间，其他处理器不允许“偷走”（被清理，被降级）这个块。

在一个基于总线的多处理器中，一个阻止块（在基于总线的多处理器上）被偷走的方法是锁上或者预约总线直到指令完成。因为总线是系统中的序列化介质，如果它被锁上了，则其他总线事务不可以访问总新概念，直到总线被释放。一个更加常用的解决方法（亦可用在非基于总线的多处理器系统中）不是阻止其他对总线的请求，而是使用执行原子指令的处理器的一致性控制器，来对块的其他所有请求延长响应直到原子指令完成，或者否定确认请求，这样请求者会在未来重复请求。总的来说，通过对块“独家所有权”和直到原子指令完成前被阻止“偷走”，就能够保证原子性。

8.1.3 TS锁

原子指令如何实现锁？这要依赖于原子指令的类型，下面展示test-and-set指令的锁实现。在尝试获取锁的中的第一条指令时test-and-set指令，它原子地执行下面几个步骤：
1. 从lockvar所在的存储单元读取值到寄存器R1中（使用一条独占读指令，如BusRdx或者BusUpgr），将寄存器R1中的值与0相比较。如果R1中的值是0，将数字1赋予给lockvar（说明地这是一次成功的锁的获取）。如果R1中的值不是0，那么就不把数字1赋予lockvar（说明这是一次失败的锁的获取）。
2. 分支指令，当R1中的值非0时分支回到标签lock，这样锁尝试可以被重新获取。如果R1中的值是0，就意味着当到达分支指令的时候，因为原子性，test-and-set已经成功的。锁的释放只需要将0赋给lockvar即可，而不需要使用原子指令。能够执行的原因是因为此时只有一个线程在临界区中，所以只有一个线程能够对锁进行释放，所以在所释放时不会发生冲突。

让我们评价一下test-and-set锁的实现。因为在成功获得一个锁的时候只需要一条原子指令和一条分支指令，所以无竞争获取锁延迟很低，但是通信量需求非常高。每个锁获取都试图使其他拷贝失效，而不管这个获取成功与否。举例3个线程情况，起初没有一个线程获取锁，P1执行了test-and-set指令并且成功获得了锁，引发BusRdX总线事务，因为这个块尚未存在于P1的cache中。之后，P2和P3都试图去获得锁。P2执行一条test-and-set指令，紧接着P3也执行了。都会触发一次BusRdx事务，使得其他cache的拷贝失效，并且改变lockvar缓存块的状态为M。需要注意的是，尽管实际上锁被P1持有，但P2和P3还是会不断引起总线事务使得彼此的拷贝失效，以此来尝试获取锁。这是test-and-set锁实现的一个很严重的缺点。实际中线程失败的次数远超想象。

每一次获取锁的尝试总会触发一个总线事务，而不管这个锁当前是否被持有。所以单个临界区的通信量非常高O(P^2)。因为有O(P)个处理器要进入临界区，也意味着有O(P)次锁获取和释放。

很显然，test-and-set锁引发的通信量可能会非常高，由锁获取尝试而引发的通用心里可以减缓一致性缓存缺失。实际上，如果通信量因为失败的锁获取尝试而饱和的话，临界区可能就会慢下来，延迟锁的释放，这使得通信量状况更加恶化。

一种减少通信请求的方法是使用back-off策略，即在一次失败的锁尝试之后，一个线程在执行另一次尝试之前先进行等待（或延迟）。在连续的重新尝试之前插入一段延迟，而这段在back-off策略中的延迟需要被谨慎调整：如果过小的话，大量的通信量依然存在；如果过大的话，线程可能在锁可用的时候错误请求这个锁的机会。实际上的一个指数的back-off策略，即延迟咋初始时很小，但是逐渐层指数增长的策略，能够工作得很好。

8.1.4 TTSL

另一种减少通信请求的方式是指定一种标准来检测一个锁获取请求是否会导致失败，如果可能导致失败，就推迟原子指令的执行。只有当一个获取锁的尝试有很大概率成功的时候，才尝试去执行原子指令。称为test-and-test-and-set。

加载指令和接下来的分支指令构成了一个循环，来不断地读（而不是写）lockvar所在的地址直到这个地址的值变为0。因此，当一个锁被一个处理器持有的时候，其他处理器不能执行test-and-set原子指令，这样就阻止了无用的（它们导致了失败的锁获取）重复的块的失效。只有当锁被释放，处理器才会尝试使用原子指令获取锁。由于有了额外的加载和分支指令，无竞争的锁获取延迟比test-and-set锁实现要高。然而，当锁被持有时，通信量大大地减少了。只有一小部分获取锁的尝试产生了通信量。假设3个线程例子，P1获取锁之后，P2和P3加载lockvar时，发现变量为1，说明锁被其他线程持有。所以P2和P3不停地从自身cache读取数据，等待直到lockvar的值发生变化。在它们等待的时候，没有总线事务产生，因为它们都是循环地使用加载指令而不是test-and-set指令。循环地使用加载指令的一个额外的益处是总线带宽是有限的，而在临界区的线程不经历带宽的争用。当P1释放锁，而P2是第一个发现锁被释放，P2接下来使用test-and-set指令来获取锁，这会产生2个总线事务：一个用来读取值的总线，一个用来向块中写入数据的总线。与之相反，在test-and-set锁实现中，只涉及一个总线事务。所以TTSL中锁获取引起了轻微的带宽使用的增加。

8.1.5 LL/SC锁

虽然TTSL对于TSL锁实现来说是一种进步，但是它的视线仍然存在很重大的缺陷。实现一条原子指令的方法要求一个独立的总线，它能够在一个处理器执行原子指令的时候对外宣称这一事件。这样的一个实现不够普遍，因为它只能为基于总线的多处理器工作。除此之外，只有当锁的使用频率很低时他才能工作良好。如果程序员使用细粒度的锁，同时使用很多锁变量，将会产生很多锁获取和锁释放的实例，并且很多实例在使用的时候并不相关，它们不是为了确保一个临界区，而是为了确保对一个数据结构的不同的部分“独家”访问权。如果每个锁获取都要引发一个单独的总线，那么会导致不必要的序列化。

其他的实现，比如为原子指令的整个持续时间保留一个高速缓存块的方法，则更为通用。他不需要假设存在一条特殊的总线线路，所以它可以为其他相关者一起工作。然而，为了防止高速缓存块被其他线程“偷走”，对块的请求必须要延迟或者否定确认。这样一个机制实现起来代价比较高昂。延迟请求要求一个额外的缓冲区来将这些请求排队，否定确认会浪费带宽并且在之后再次尝试请求时会引起延迟。

为了避免支持原子指令而带来的复杂性，一种选择是为一系列指令提供原子性表象，而不是真的指令原子性。需要注意的是，锁获取本质包含一条加载指令，一些其他指令比如状态分支和存储指令。原子性意味着要么这些所有指令都不执行，要么都执行。从其他处理器的角度来看，只有存储指令是可见的，因为当存储指令改变值的时候这种改变可能被他们看到。而其他指令（加载和分支）只对本地处理器的寄存器产生了影响，这些影响对其他处理器来说是不可见的。因此，对于其他处理器来说，加载指令和分支指令是否执行无关紧要。对于原子性表象来说最重要的是存储指令，

原子性表象要求存储指令有条件地执行，需要检测会破坏原子性表象的事件。这样的存储是条件存SC。需要一个块地址来监控是否被偷（即无效化）的加载指令被称为加载链接load linked或者加载锁定load lock，LL。LL/SC这一对指令是非常有用的机制，能够建立很多不同原子操作，保证了原子性表象而不需对高速缓存块的独家占有权。

一个LL指令是特殊的加载指令，不仅要读一个块到寄存器中，而且还要将块的地址记录在处理器的一个特殊寄存器中，将这个寄存器称为链接寄存器linked register。SC指令是特殊的存储指令，只有在它涉及的地址与链接寄存器中存储的地址匹配时，指令才能够成功。

LL指令和接下来的分支指令构成了一个循环，能够不断读lockvar所在位置的值，直到这个为止的值变为0。因此，当一个锁被一个处理器持有时，SC指令不能被执行。这阻止了与失败的锁获取相关的重复无用的无效。是由当锁被释放时，处理器才能够尝试使用SC指令获取锁。多处理器同时尝试执行SC时有可能得。在基于总线的多处理器上，这些SC中的一个会被赋予总线的访问权，成功执行存储指令。其余处理器侦听总线上的存储指令并且清空它们的链接寄存器，成为自身SC指令失败的原因。与test-and-set原子指令不同的是，当一条SC指令失败的时候，它还不会产生总线事务。

除了LL取代常规的加载、SC取代了test-and-set指令之外，生成的总线事务的顺序同TTSL实现中相同。因此，在性能方面LL/SC锁的实现表现与TTSL实现很相似，一个很小的区别表现在多处理器同时执行SC时。LL/SC只有一个总线事务，而TTSL会有多个总线事务存在。但发生概率很低，因为锁之间的指令数目很少，因此多个处理器在同一时间执行相同序列的概率非常小。

然而，使用LL/SC相比于使用原子指令来说优势是巨大的。首先，LL/SC的实现相对简单（额外的链接寄存器）。第二，它可以被用来实现很多原子指令，比如test-and-set，compare-and-swap等。因此，它被认为是相对原子指令来说更低级的原语。

然而，LL/SC锁仍然存在严重的扩展性问题。每一个锁获取或者锁释放都会导致在锁变量上自循环的共享器失效，因为锁变量被改变了。它们轮流经历高速缓存缺失，重新加载包含锁变量的块。然后，LL./SC锁实现的总通信量会随着系统的线程数呈平方增长。另外一个问题就是锁公平性，它不能保证最早尝试获取锁的线程，能够比其他线程更早地获取锁。

8.1.6 Ticket锁

Ticket锁是一种尝试在锁获取中提供公平性的锁实现，公平性的问题涉及了线程成功获取锁的顺序是否符合首次尝试获取锁的顺序。公平性问题自动地保证了一个线程不会因为竞争不过其他现场而长时间得不到锁，导致长时间的挨饿。

为了达到这样公平性，ticket锁使用队列的概念，每个尝试去获取锁的线程在队列中被赋予一个编号，这样锁的实现的顺序就取决于它们在队列中的编号。拿到最低编号的线程会在下一次被给予锁。

为了实现ticket锁，引入两个变量。第一个是now_serving，另一个是next_ticket。next_ticket的作用是反映了下一个可用的编号（或顺序位置），now_serving的作用是反映了当前锁持有者的位置。当然，next_ticket-now_serving-1得到的数字是当前队列等待获取锁的线程数，它们试图获得锁但是没有成功。为了得到锁，一个线程读取next_ticket到一个私人变量中并且原子地增加它，所以后面的现场不会取得相同的编号。接下来，线程一致等待直到now_serving的数值等于my_ticket的数值。当前持有锁的线程通过将now_serving加上1来释放锁，这样下一个队列中的线程就会发现now_serving的新值同自己的my_ticket相同，这样在队列中的线程就成功地获得了锁。锁获取和释放代码如下：

ticket锁的性能取决于fetch_and_inc原子操作是如何实现的，例如原子指令，LL/SC锁。因为有O(p)的获取和释放操作，并且每个获取和释放都会引起O(p)的失效和随之而来的高速缓存缺失，所以总共的通信量是平方级扩展，即O(p^2)。

Ticket锁的无竞争延迟相对于LL/SC来说是比较高的，因为它需要额外的指令来读并且测试now_serving变量的值。但是，ticket锁提供了公平性，这是LL/SC无法提供的。

8.1.7 ABQL（array-based queuing lock）

是否存在一种锁：它具有Ticket锁的公平性，同时还具有之前所讨论的所有的锁实现都好的扩展性。一个答案是一种称为基于数组的排队锁ABQL的锁实现。ABQL是ticket锁的升级版。在ticket锁中，因为线程正在等待锁获取的时候已经排好了队列，它们可以在特殊的内存位置上等待和自循环，而不是只针对now_serving提供的一个内存位置。这个新机制的一个类比是，锁的当前持有者将“接力棒”传给下一个线程，下一个线程将“接力棒”传给下下个线程，以此类推，每次只通知下一个线程。

为了实现ABQL，需要确保线程在特殊的内存地址自循环，因此改变now_serving为一个数组，命名为can_serve。在ticket锁实现中，每个想要获取锁的线程都有一个编号，称为x，接下来它们在循环中等待直到can_serve数组中的第x个元素排在前面的线程置为1.当编号为y的线程释放锁的时候，它将“接力棒”传给下一个线程，并且将can_seve数组中的第y+1个元素置为1。锁获取和释放的代码如下：

考虑线程释放锁的方式：它通过修改数组can_serve[my_ticket+1]中的一个元素来释放。假设数组是填充的，这样不同数组元素存储在不同的缓存块中。因为只有一个线程在元素读取的循环中自循环，这样元素值存储在一个块上。写操作只会使这个高速缓存块失效，并且只引起一次高速缓存缺失。每次释放只有O(1)的通信量产生。

8.1.8 各种锁实现的量化比较

比较不同锁的实现，包括无竞争延迟、一次单独的锁释放后带来的通信量、当锁被一个处理器持有时等待所带来的通信量、存储开销和是否提供公平性保证。

简单锁实现，比如test-and-set、TTSL和LL/SC的无竞争延迟最低。Ticket锁和ABQL实现了更多的指令，所以它们的无竞争延迟要高一点。

在一次单独的锁释放后的通信量方面，假设所有其他线程都等待着获得下一次的锁。test-and-set、TTSL、TT/SL和ticket锁拥有着最高的通信量。这是因为所有的线程都在同一个变量上自循环，所以它们可能都缓存了同一个块，每次锁释放都会使得其他所有处理器的块的拷贝失效，导致缓存缺失，只能重新加载该数据块。另一方面，对于ABQL来说，一次锁释放只会导致一个其他高速缓存块失效，所以只会造成一次高速缓存缺失。

在锁被一个线程持有时产生的通信量方面，test-and-set表现得不好，因为所有的线程在持续不断地使用原子指令尝试获取锁，即使是一次失败的尝试。也会造成所有共享者的失效，并且会导致共享者的后续尝试。另一方面，TTSL、LL/SC、ticket和abql使用加载指令不断自循环，因此，只要有一个线程发现锁被持有了，它就不会再尝试执行原子指令了。

在存储需求方面，所有锁都使用一个或两个共享变量，所以存储需求在多个处理器之间是恒定的。只有abql因为需要维持can_serve数组，所以它的存储需求是根据处理器数量的多少而变化的。

从公平性来说，只有ticket和abql因为使用了队列而提供了这个保障。其他实现可能出现一个线程持续获取和释放锁，而代价是其他线程获取锁的能力。也可能是总线逻辑偏袒某些请求者（本地存储和远端存储）。还需要注意保障公平性会带来性能上的风险。如果一个已经在队列中等待获取锁的线程进行了上下文切换，那么即使这个锁可用了，这个线程可能也灭有尝试去获取它。其他线程也不可能获取这个锁，因为它们必须等待那个进行上下文切换的线程获取并且释放锁。因此，所有线程的性能都因为这个进行上下文切换的线程而整体下降了。所以，必须要保证在使用ticket和abql实现时不能发生上下文切换。

对于高度锁竞争的软件来说，abql提供更好的可扩展性。但可能面临可扩展性问题。

8.2 栅栏的实现

在循环级并行中，栅栏通常被用在一个并行循环的结尾，以确保所有线程在计算移动到下一步之前已完成它们负责的计算部分。

栅栏可以用软件实现，也可以直接用硬件实现。软件栅栏的实现很灵活，但是往往是低效的；硬件栅栏的实现限制了灵活性和可移植性，但是效率往往最高。最简单的软件栅栏被称为翻转感应全局栅栏。主要使用的机制是让所有线程进入栅栏，然后这些线程在一个位置上进行自循环，最后一个进入栅栏的线程将会设置此位置的值，并释放所有的等待线程。代价就是这个被写位置会涉及大量的无效化，限制了可扩展性。一个更加复杂但是扩展性更好的栅栏的实现是组合数栅栏。在此实现中，栅栏中涉及的线程被组织成树形。树种一个特定层的线程在一个只与它的兄弟节点共享的位置自循环。因为线程在不同的位置进行自循环，所以这种方法限制了无效化的数量。最后，将会探讨一个在拥有上千处理器的大机器上实现硬件栅栏。

评价栅栏性能的标准如下：
1. 延迟：进入一个栅栏和离开一个栅栏所花费的时间，在栅栏中的延迟应该尽可能的小。
2. 通信量：处理器之间交流产生的字节数的量，是处理器数量的函数。

与锁实现不同的是，其公平性和存储开销不是很重要的问题，因为栅栏是涉及很多线程的全局结构。

8.2.1 翻转感应集中式栅栏

一个软件栅栏的实现仅仅假设系统提供了锁获取和锁释放原语（通过软件、硬件以及软件和硬件的结合）。

从程序员的角度来看，一个栅栏必须和简单。也就是说，一个栅栏不应该请求任何传递给它的参数，包括变量名、处理器数量或者线程数量。

基本栅栏实现如下：barCounter追踪到目前为止一共有多少个线程到达了栅栏。barLock是一个锁变量，用来保护临界区中共享变量的修改。canGo是一个标志变量，线程在这个变量上自循环以得知自己是否能通过此栅栏。因此，最后一个到达的现场将设置为canGo的值，并释放所有的线程通过栅栏。不幸的是，当通过多于一个栅栏时，该栅栏就会失效。即在最后一个线程通过栅栏时，剩余线程可能存在加载的canGo是0情况，一直停留在当前栅栏。而最后一个线程却一直在等待被卡在之前栅栏的线程到来，造成死锁。

之前讨论一个针对这种死锁的解决方法，那就是使用两步释放。在第一个线程进入栅栏并初始化canGo变量之前，它要先等待其他所有的线程从前一个栅栏中释放。适应这个解决方法需要另一个标记变量、拎一个计数器和其他代码，代价比较昂贵。幸运的是，针对由于第一个进入下一个栅栏的线程重置canGo而导致了一些错误情况，提出了一种更简的解决方法。如果避免了重置，那么进入下一个栅栏的线程就不会阻塞其他线程从上一个栅栏中释放出来。为了避免重置canGo的值，在第二个栅栏中，线程等待最后一个进入第二个栅栏的线程把canGo的值变会0。canGo在第一个栅栏中转化为1的时候代表了释放，而在第二个栅栏中转化为0才代表释放，以此类推，交替出现。

集中式（全局）栅栏实现在栅栏程序中使用临界区，所以当线程的数目递增时候，通过栅栏的时间会线性增加。很可能以超线性方式增长。另外，通信量可能很高，因为每个线程都需要递增变量numArrived，使得所有块的共享者失效，这会导致接下来的高速缓存和块的重新加载。一共有O(p)递增，每个递增又会导致O(p)的高速缓存缺失，所以栅栏实现的总的通信量随着处理器个数的增加而呈平方增长。所以可扩展性很差。

8.2.2 组合树栅栏

在可扩展的栅栏中，避免了所有线程共享同一个位置并在单一位置自循环barCount或canGo。它们以分层组织屏障，以避免在单一位置进行自循环，被分在同一个组的线程在每个组内保持同步。每个组中选出一个线程来进行下一轮，并且同其他被选出的线程组成一个新组。以此类推，直到最后一个组完成在栅栏的同步。比如，组合树栅栏、比赛栅栏和散播栅栏。

组合树栅栏将节点（线程）分成很多组，每一组有k个成员。每组的线程将同步一个简单的线程计数器，如要求每个线程原子性地递增计数器并且等待，直到组内所有线程到达栅栏（计数器达到k）。之后，每组的第一个线程构成一个新的线程组，同样含有k个成员（代表一个父节点），再次达成同步。这样重复直到剩下一个组代表数的根节点，最后这个根节点通过设置一个所有线程监控的标记来释放所有的线程。

组合树栅栏需要与树的大小相同的存储空间，即O(p)空间，通信量随着节点的数目的增加，即O(p)。延迟会增加，因为为了得知所有线程都已经到达栅栏，需要遍历树，在树的不同级别上需要O(logp)栅栏参与，而集中式栅栏只需要O(1)。

8.2.3 硬件栅栏实现

硬件栅栏实现因为它的低延迟和可扩展性而备受瞩目。在软件栅栏中，不得不执行很多的指令来实现栅栏原语，并且依赖缓存一致性机制来传播原语所做的修改。缓存一致性目前还无法扩展到成千上万个处理器上。反之，硬件的实现依赖与在专用线路上传播的信号。对于大型处理器系统，硬件栅栏时实现真正可扩展性栅栏的唯一方法。

在基于总线的多处理器上，最简单的一个硬件栅栏实现是实现了逻辑“与”的特殊总线线路。每一个到达栅栏的处理器都对这个栅栏线路执行一个断言assert。因为这个栅栏实现了一个逻辑“与”，所以只有在所有的线程都到达栅栏并执行了断言后，这个总线才是高电平。每个处理器都监控这个栅栏总线来检测它的信号值。当处理器察觉到栅栏总线变高时，它们就知道所有的处理器都已到达此屏障。

从概念上看，硬件栅栏网络很简单，它需要收集到达栅栏的每个处理器的信号，直到来自所有处理器的信号被收集，接着它需要向所有处理器广播一个栅栏完成信号。所有这些都需要在尽可能短的时间内完成。信号不可能被一个节点收集，因为它需要非常大的连通性。有限的连通性要求用于栅栏信号传播的线路形成网络。具有有限节点连接的可扩项的网络一个例子是树。对一个k分支树而言，从n个处理器中收集信号需要花费的步骤是logkN，步骤的数量决定了收集和广播栅栏信号的延迟。使用日志函数的话，延迟的增长比系统大小的增长慢，使网络称为可扩展的栅栏的实现。

8.3 事务内存

在并行编程的环境中，事务内存TM的目的是提供更高级别的编程抽象，来将程序员从处理低级线程并行结构（比如锁）中解脱出来。一段代码被包装成一个事务，被完全执行或者完全不执行（原子性），不被其他线程锁干扰（隔离性）。

有3种方法支持TM：
1. 使用软件来实现，硬件只提供原子指令来支持基本的原语--这些原子指令已经被用来支持其他同步原语。即软件事务内存STM。一个特别有用的原子指令是CAS指令。在一个STM中，一个数据结构被另一个对象包装，其中包含指向原始对象的指针。如果一个对象需要被原子性地被修改。这个修改在提交之前对于其他线程来说是不可见的，当修改完成后，它通过CAS指令来改变指令使得指针指向对象的新副本。STM作为一个库，特定于库提供的特定的数据结构，由于对对象元数据的维护和记录，STM在没有争用的情况下都需要很大的开销。
2. 硬件事务内存HTM，即由硬件来直接提供事务。可以把LL/SC看做HTM的原始形式。LL/SC提供了原子性表象。任何在LL/SC指令之间的代码都完全执行或者完全不执行。一个硬件事务对任意一个代码区域提供了相同的原子性表象。事务的原子性表象需要很多元素。首先，它要求一个机制来检测冲突，即可能违背原子性表象的条件。其次，如果一个冲突被检测到了，它需要一个机制来撤销事务所产生的所有影响，或者它需要一个缓冲和提交机制，使事务所做的改变被缓冲和限制（其他线程不可见），直到提交更改的提交时间。与LL/SC不同的是，事务必须封装几乎所有类型的指令，包括存储指令。因为存储改变内存的值，所以需要一个更复杂的机制来缓冲被改变的值，直到提交时间。

回想一下可串行性概念：如果一组操作或者原语的并行执行结果与按照某一次串行的执行时的结果相同，称之为可串行化。

当两个事务中重叠的读集和写集时，它们的并行执行可能产生非串行化结果。在T1提交时，T2发现T1的写集合和自己的读集x和写集z都有所重叠。因此，一个可串行化冲突被检测到，而正确的操作是终止T2，丢弃它的结果（很简单，因为它们被缓冲了，且没有在缓冲区之外进行传播），并且在将来重试。

首先讨论一种将投机值进行缓冲直到提交时间的方法。问题在于这些值如何被缓冲，以及应该在那里被缓冲。因为缓冲区中的值对于其他线程来说是不可见的，所以硬件必须提供一个空间来保存这些值，并且不触发缓存一致性而引起的写操作的传播。缓冲结果的例子有存储队列、L1和L2cahce。每个缓冲区的选择都会影响到事务的带下和性能。缓冲区离处理器越远，缓冲投机值的能力就越强。处理器制造商还不确定需要为一个事务提供多大的最大容量，因为商业程序还没有大量使用事务来进行写入或者移植。

一种可能的用于保存投机值的缓冲区是高速缓存。使用缓存来缓冲投机值的结果是追踪投机值相当于在高速缓存行的粒度上跟踪数据值。这会产生假冲突的可能性。使用高速缓存缓冲投机值的另一个问题在于事务的大小限制更依赖于高速缓存的关联性，而不是容量。原因在于，一旦任何单独的高速缓存容纳了与缓存关联一样多的投机块，那么事务就会立刻溢出高速缓存。有人建议让投机缓存值溢出到主存中，以提供一个无边界的事务大小，但是这并不容易实现。更何况，现在并没有证据说明内存在事务大小很大的时候仍然保持很高的可扩展性。

考虑使用cache来容纳投机值的实现。每个cache多加一个写为（为了追踪读集，也加一个读位）。每当一个事务开始执行并写入一个数据项时候，该数据被加载到cache，然后它的写数据位被置位。使得块可以作为事务的写集的一部分被追踪。另外，写数据位将块“钉”在cache，使其在提交之前不能被置换。读数据位作用是标志事务中的读集和将块“钉”在缓存中直到事务提交。如果一个事务读和写了很多数据，那么cache可能被填满并且无法找到一个可置换的块。处理这种情况的朴素方法是终止事务。

事务的提交一定是原子性的，即同时只有一个事务可以提交。因此需要一种机制来仲裁可能同时进行的事务提交尝试。首先它必须确定在事务开始直到它想要提交的这段时间内，是否有其他提交的事务的写集和自己的读写集重叠了。如果有重叠，那么会产生冲突，这个事务必须被终止然后重新尝试。通过回到事务开始之前处理器的执行状态来实现终止。同时它必须恢复寄存器状态到之前的位置，并且将读集和写集中的数据全部置位无效。一旦它被允许提交了，他就可以公布它的写集。公布写集的一种方式是通过对其写集中的所有块宣布失效。写集的公布可能会引起其他事务的终止。一个事务的写集中失效的块也会立刻传播它的写操作，这样它们对于其他线程就可见了。