31并行处理器的其他问题
AP SHANTHI博士
本模块的目标是讨论多处理器中存在的同步问题，并介绍各种内存一致性模型。
到目前为止，我们已经讨论了用于在多处理器系统中维护缓存一致性的各种缓存一致性协议。但是，除了缓存一致性问题之外，在多处理器系统中还有其他问题需要处理。我们将在本模块中讨论它们。
在多处理器系统中，数据由多个处理器共享，我们需要提供同步以了解不同进程何时使用共享数据是安全的。在通过消息传递进行通信的情况下，与数据的传输或到达有明确的协调。然而，当通过共享地址空间进行通信时，需要额外的操作来明确协调不同处理器之间的数据共享。例如，可能需要启用标志、唤醒线程、中断处理器等。
通常，硬件提供一些同步原语，我们有基于它们构建的软件同步例程/库。在小规模系统中，硬件提供的最原始支持是不间断指令或指令序列，可以原子地检索内存位置的内容并对其进行更改。然后使用此功能构建软件同步机制。在更大规模的多处理器或高争用情况下，同步可能成为性能瓶颈，因为争用会引入额外的延迟，而且这种多处理器中的延迟可能更大。
基本硬件原语：主要硬件支持是检索和更改内存位置内容的能力。这可以通过原子 交换来实现，原子交换将寄存器中的值与内存中的值进行交换。让我们假设我们要构建一个简单的锁，其中值 0 用于表示锁空闲，使用 1 表示锁不可用。处理器尝试通过将寄存器中的 1 与与锁对应的内存地址进行交换来设置锁。如果某个其他处理器已经声明访问，则从交换指令返回的值为 1，否则为 0。在后者 在这种情况下，该值也更改为 1，以防止任何竞争交换也检索 0。
例如，考虑每个尝试同时进行交换的两个处理器。这种竞争被打破了，因为恰好有一个处理器首先执行交换，返回 0，而第二个处理器在进行交换时将返回 1。使用交换（或交换）原语实现同步的关键是操作是原子的。交换是不可分割的，两个同时交换的交换将通过写序列化机制进行排序。试图以这种方式设置同步变量的两个处理器不可能假设同时设置了该变量。
许多较旧的多处理器中存在的另一个操作是测试和设置，它测试一个值并在该值通过测试时设置它。例如，可以使用测试 0 并将值设置为 1 的操作。这类似于前面讨论的原子交换。另一个原子同步原语是fetch-and-increment。它返回内存位置的值并自动递增它。通过使用值 0 来指示同步变量未被声明，我们可以使用 fetch-and-increment，就像我们使用 exchange 一样。
然而，实现单个原子内存操作会带来一些挑战，因为它需要在单个不间断指令中进行内存读取和写入。这个要求使一致性的实现变得复杂，因为硬件不能允许读和写之间的任何其他操作，但不能死锁。另一种方法是使用一对指令，其中第二条指令返回一个值，从中可以推断出这对指令是否被执行，就好像这些指令是原子的一样。如果这对指令看起来好像任何处理器执行的所有其他操作都发生在这对指令之前或之后，则称这对指令是原子的。这对指令包括一个称为负载链接或负载锁定的特殊负载和一个特殊的商店叫做有条件的商店。这些指令按顺序使用。如果在以相同地址为条件的存储发生之前，由加载链接指定的内存位置的内容发生更改，则条件存储失败。如果处理器在两条指令之间进行上下文切换，那么条件存储也会失败。存储条件定义为如果成功则返回 1，否则返回 0。由于加载链接返回初始值，并且条件存储仅在成功时返回 1，因此以下序列在由 R1 的内容指定的内存位置上实现原子交换：
尝试： MOV R3,R4 ;mov 交换值
LL R2,0(R1) ;负载链接
SC R3,0(R1) ;存储条件
BEQZ R3,try ;branch store 失败
MOV R4,R2 ;将负载值放入R4
在这个序列的末尾，R4 的内容和 R1 指定的内存位置已经被原子交换了。每当处理器干预并修改内存中 LL 和 SC 指令之间的值时，SC 都会在 R3 中返回 0，从而导致代码序列再次尝试。
同样，下面的例子展示了我们如何实现一个 fetch &
这些指令通常通过在称为链接寄存器的寄存器中跟踪 LL 指令中指定的地址来实现。如果发生中断，或者如果与链接寄存器中的地址匹配的缓存块无效，例如，被另一个 SC，则链接寄存器被清除。SC 指令只是检查其地址是否与链接寄存器中的地址匹配。如果是，则 SC 成功；否则，它将失败。由于在另一次尝试存储到加载链接地址或出现任何异常之后，条件存储将失败，因此我们必须谨慎选择在两条指令之间插入哪些指令。特别是，只有 register-register 指令可以安全地被允许。否则，可能会造成处理器永远无法完成 SC 的死锁情况。此外，
实现自旋锁：一旦原子交换原语可用，我们就可以使用它实现自旋锁。自旋锁是一种，其中处理器为锁不断旋转，直到它变得可用。这通常用于我们期望锁只持有很短的持续时间，并且获取锁的过程本身不会消耗太多时间。否则，处理器会等待很长时间。考虑以下代码序列，假设锁变量在内存中可用：
DADDUI R2, R0, #1
lockit: EXCH R2, 0(R1) ;原子交换
BNEZ R2, lockit ;已经锁定？
在这里，我们使用原子交换指令。如果交换成功，R2 的值为 0。如果 R2 的值为 1，处理器知道没有获得锁，并再次开始旋转。
如果多处理器系统支持缓存一致性，我们可以使用一致性机制缓存锁，以保持锁值的一致性。缓存锁有两个优点。首先，旋转过程可以在本地缓存副本上完成，而不需要在每次尝试获取锁时都进行全局内存访问。第二个优点是因为锁访问经常存在局部性。也就是说，最后使用锁的处理器将在不久的将来再次使用它。在这种情况下，锁值可能驻留在该处理器的缓存中，从而大大减少了获取锁的时间。我们相应地修改了我们的自旋锁程序。读取是在本地副本上完成的，只有当处理器知道锁可用时，它才会尝试使用交换来获取锁。这避免了对共享数据的写入次数。获胜的处理器在锁定后执行代码，并在完成后将 0 存储到锁定变量中以释放锁定，从而重新开始竞争。下面的代码说明了这个想法：
锁定：LD R2, 0(R1) ; 锁负载
BNEZ R2，锁定；不可用-自旋
DADDUI R2, R0, #1; 加载锁定值
EXCH R2, 0(R1) ; 交换
BNEZ R2，锁定；如果锁不为 0 则分支
使用缓存一致性的自旋锁机制如图 35.1 所示。处理器 P0 已锁定，P1 和 P2 正在读取锁定状态。因此，锁定状态变为共享。其中一个将首先得到维修。当处理器 P0 释放锁时，它会使所有其他缓存无效。他们必须获取新值来更新他们的锁副本。一个这样的缓存首先获取未锁定值 (0) 的副本并执行交换。当满足其他处理器的缓存未命中时，他们发现变量已经被锁定，因此必须返回测试和旋转。
屏障同步：接下来我们将看看屏障同步是如何实现的。屏障是同步原语，可确保某些进程不会超过其他进程——如果进程到达屏障，则必须等到每个进程都到达屏障。当一个进程到达屏障时，它会获取一个锁并增加一个计数器来跟踪已经到达屏障的进程数。然后它旋转上一个由最后到达的进程设置的值。这确保只有当所有进程都到达屏障时才允许进程退出屏障。
Figure 35.2 shows how barrier synchronization can be implemented. The first processor entering the barrier resets the release and increments the count. As each processor enters the barrier it acquires the lock for count and increments the count value. Once count becomes equal to total, indicating that all the processes have reached the barrier, the barrier is released. Till the count is satisfied, all the processes keep spinning.
But, we have a problem here. If we have two processes, one fast and the other slow. The slow process arrives first, reads release, sees 0 and waits. The fast process arrives, sets release to 1, goes on to execute other code, comes to barrier again, resets release, and starts spinning. The slow now reads release again, sees 0 again and gets stuck. Now, both the processes are stuck and will never leave.
这可以通过计算离开的进程数或使用如图 35.3 所示的意义反转屏障来克服。第一个屏障中的释放充当第二个屏障的重置。当快速进程返回时，它不会更改 release，它只是等待它变为 0。慢进程最终看到 release 为 1，停止旋转，工作，返回，将 release 设置为 0，并且两者都前进。
还有更多可能的同步。我们只讨论了最原始的那些。
内存一致性模型简介：多处理器要处理的另一个重要问题是内存一致性。我们已经在之前的模块中概述了这个问题。缓存一致性可确保多个处理器看到一致的内存视图。但是，一个处理器何时必须看到已被另一个处理器更新的值，这是一个问题。由于处理器通过共享变量进行通信，因此处理器观察另一个处理器的数据写入的顺序很重要。由于只能通过读取来观察另一个处理器的写入，因此我们必须决定必须在不同处理器对不同位置的读取和写入之间强制执行的属性。
例如，请观察下面的代码序列。下面是来自进程 P1 和 P2 的两个代码段：
假设进程在不同的处理器上运行，而位置A和B最初是由具有0的初始值两个处理器缓存如果写入总是即时生效，其它处理器立即看到，它会为不可能既当语句来评估它们的条件为真。但是假设写入无效被延迟，并且在此延迟期间允许处理器继续；然后可能的是，P1和P2都没有看到对B和A的废票之前他们试图读取值。关于程序员的想法和实际发生的事情存在歧义。一致性模型阐明了这些问题。一致性模型定义了对不同内存位置的写入和读取的顺序。硬件保证了某种一致性模型，程序员尝试使用这些假设编写正确的程序。
最直接的内存一致性模型称为顺序 一致性。顺序一致性要求任何执行的结果都相同，就好像每个处理器执行的内存访问是有序的，不同处理器之间的访问是任意交错的。顺序一致性消除了前面示例中某些非明显执行的可能性，因为必须在启动 if 语句之前完成赋值。
实现顺序一致性的最简单方法是要求处理器延迟任何内存访问的完成，直到由该访问引起的所有失效完成。下一次内存访问必须延迟到前一次访问完成。内存一致性涉及不同变量之间的操作。必须排序的两次访问实际上是针对不同的内存位置。我们必须延迟对 A 或 B 的读取（A = 0 或 B = 0），直到前一个写入完成（B = 1 或 A = 1）。在顺序一致性下，我们不能将写入放入写入缓冲区并继续读取。
顺序一致性非常容易理解，并提供了一个非常简单的编程模型。但是，它不允许进行许多优化，因此性能会受到影响。它是最简单但最严格的一致性模型。更好的实现是处理器在它认为合适的时候发出访问，但检测并修复潜在的顺序一致性违规。
挑战在于开发一种简单且同时具有良好性能的编程模型。例如，我们可以假设程序是同步的，其中对共享数据的所有访问都按照我们之前讨论的同步操作进行排序。如果在每次可能的执行中，一个处理器对变量的写入和另一个处理器对该变量的访问（读取或写入）被一对同步操作分开，则数据引用由同步操作排序，一个在写入处理器写入之后执行，一个在第二处理器访问之前执行。如果在没有同步排序的情况下更新变量，这将导致数据竞争因为执行结果取决于处理器的相对速度，结果是不可预测的。因此，我们需要编写无数据竞争的同步程序。
程序员可以编写自己的同步机制，但这并不能保证有效，并且会导致程序出错。因此，通常所有程序员都会选择使用针对多处理器和同步类型正确和优化的同步库。此外，标准同步原语的使用确保即使架构实现了比顺序一致性更宽松的一致性模型，同步程序也将表现得好像硬件实现了顺序一致性。
松散一致性模型：松散一致性模型的关键思想是允许读取和写入无序完成，但使用同步操作来强制排序，这样同步程序的行为就好像处理器是顺序一致的。有多种放松模型，它们根据它们放松的读写顺序进行分类。可以通过以下方式放宽顺序一致性约束（允许更高的性能）：
在处理器中，读取可以在对不同内存位置的较早写入完成之前完成
在处理器中，写入可以在对不同内存位置的较早写入完成之前完成
在处理器中，读取或写入可以在对不同内存位置的较早读取完成之前完成
一个处理器可以在所有处理器看到无效之前读取另一个处理器写入的值
在写入对其他处理器可见之前，处理器可以读取自己的写入
我们通过一组 X→Y 形式的规则来指定排序，这意味着操作 X 必须在操作 Y 完成之前完成。顺序一致性需要维护所有四种可能的顺序：R→W、R→R、W→R 和 W→W。松弛模型由它们松弛的这四组排序中的哪一组定义：
放宽 W→R 排序会产生一个模型，称为总存储排序或处理器一致性。由于这种排序保留了写入之间的排序，因此许多在顺序一致性下运行的程序都在此模型下运行，而无需额外的同步。
放宽 W→W 排序会产生一个模型，称为部分存储顺序。
放宽 R→W 和 R→R 排序会产生各种模型，包括弱 排序、PowerPC 一致性模型和发布一致性，这取决于排序限制的细节以及同步操作如何强制排序。
因此，通过放宽不同的排序，处理器可能会获得显着的性能优势。
总而言之，我们已经讨论了与多处理器相关的同步问题。我们已经讨论了硬件支持的原语原子交换指令，并研究了如何使用它来构建各种同步原语，如简单锁、自旋锁和屏障同步。我们还介绍了内存一致性模型。
网页链接/支持材料
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A.Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。