Effective Synchronization on Linux/NUMA Systems
要在基于Itanium的大型NUMA系统上获得令人满意的性能，必须进行有效的锁定。
当前，在Linux内核中，NUMA计算机上并行执行流的同步是通过多种机制实现的，这些机制包括原子操作，锁定和内存访问排序。
各种同步方法也可以组合以提高性能。
演讲提出了Linux onItanium上基本同步的实现，然后研究了更复杂的锁定方案。
当前的Linux锁定机制严重依赖于简单的自旋锁实现，该锁可能适用于最多8个处理器的系统。
但是，如果更多处理器争用锁，则自旋锁会导致过多的高速缓存行反弹。
提出了迄今为止解决争用问题的一些方法，然后建议使用Linux的实现，该实现是ZoranRadovic最初提出的方法，他称之为“HierarchicalBackoff Locks”。
1. 简介
计算行业似乎已经通过提高处理器的时钟频率来提高处理器速度方面遇到了障碍。
当前的技术导致高时钟速率下的温度问题。
散热问题现在有效地限制了增加处理器可以处理的周期数的能力。
进一步提高处理器计算速度的方法是通过并行处理。
安腾指令集在设计时就已经考虑了这种并行化。
但是，主流计算机使用与IA32兼容的硬件，并且是为未针对并行化而优化的指令集设计的。
并行处理的最佳解决方案是将多个处理器放在一个芯片上。
英特尔和AMD现在已经开始交付多核处理器。
Itanium多核芯片也有望在2005年晚些时候上市。
多核处理器对操作软件的设计具有重要意义，因为可以合理预期将来会售出大量系统配备多核处理器。
多核处理器通常具有NUMA系统的特性，这是因为处理器芯片上的内核之间（可能是直接连接到一个内核的内存）之间的通信比与其他处理器以及其他方式连接的内存的芯片外通信更为有效。
AMD多核设计使用特定于内核的内存和I/O控制器，从而导致内存访问时间的变化，具体取决于处理器中使用哪个内核访问内存。
1这些特性是NUMA系统的典型特征。芯片上的处理器数量可能会迅速增加。
IBM已经有一个带有9个（某种）处理器的芯片，其他供应商似乎正在计划具有4个和8个内核的处理器。
在NUMA系统上运行良好的有效同步算法可能成为操作系统中的重要核心要求。
因此，SGI一直存在的问题可能会在将来的标准硬件中发生。
在这里，我们将讨论现有的Itanium处理器同步机制，以及它们如何用于实现Linux中可用的各种锁定机制。
这将首先包括对Itanium系统上原子操作的性质的讨论，然后是对用于实现锁定的各种原语的研究，对Linux内核锁定机制的实现的描述，以及为了提高性能而对各种锁定技术的高级组合的讨论。
将基于使用页面错误处理程序完成的性能基准测试结果来讨论当前锁定方案的性能含义。
结果是当前算法仅对多达4个处理器有效。
自旋锁竞争成为大型配置的可伸缩性问题。
在最后一节中，我们研究了ZoranRadovic首次提出的处理HBO锁的新方法。
性能测试表明，他的算法可以以更有效的方式解决具有大量处理器的NUMA系统中出现的争用问题，同时在不竞争的情况下保留现有代码的效率。
2. 基本的原子性（Basic Atomicity）
NUMA系统基本上是具有硬件高速缓存一致性方案的多处理器系统。
通过专为高速节点间通信而设计的NUMA互连提供对非本地设备和内存的访问，但是根据通过NUMA互连和设备或内存的特定硬件特性，因此NUMA表示非统一内存体系结构（Non-Uniform Memory Architecture）。
NUMA链接使用硬件高速缓存一致性协议为所有处理器提供整个系统中一致的内存视图。
硬件一致性协议允许访问缓存线块中的内存。
在Itanium上，此缓存行大小通常为128字节。
下图显示了具有MESI类型的硬件高速缓存一致性协议的多处理器系统的概念。
请注意，此模型已简化，因此我们可以专注于对锁定很重要的特性。
存在获得NUMA一致性的协议的多种实现方式，但是我目前知道的所有NUMA系统都违反了我们在此使用的基本原理。
典型的NUMA系统包含具有各种资源的节点。
一个节点通常包含一些处理器，一些内存以及可能的I/O设备。
从本地处理器到本地内存的访问非常快。
通过NUMA互连可以访问其他节点中的内存，但速度较慢，因为流量必须流经总线。
通过硬件高速缓存一致性协议管理所有内存访问，以确保系统中所有处理器的内存一致性视图。
通过确保使用的内存是本地内存，可以优化在NUMA系统上运行的程序。
但是，如果程序大于单节点上可用的内存，或者程序使用的处理器多于一个节点上的可用处理器，则必须通过互连进行操作。
程序对互连的使用越多，NUMA互连的速度和有效使用对于系统的整体性能就越重要。
2.1 缓存行
每个处理器可以通过高速缓存一致性协议获得对高速缓存行的选择的访问。
然后，可通过节点中缓存行的缓存在本地获得缓存行的内容。
可以将高速缓存行作为仅允许读取访问的共享高速缓存行来获取，也可以作为独占高速缓存行来获取。
专用高速缓存行是资源密集型的，因为必须保证当一个处理器拥有高速缓存行的所有权时，不会对该高速缓存行进行任何其他访问。
写访问只能在以独占访问保留的高速缓存行上进行，否则可以将多个更新同时提交到内存。
这可确保跨硬件一致性域进行写入的缓存行级原子性。
因此，以适合高速缓存行的方式组织数据结构非常有用。
然后，处理器可以获取一条高速缓存行，并且可以从同一高速缓存行处理所有相关数据，而无需任何其他内存操作。
确保代码使用尽可能多的共享缓存行是有利的，因为然后多个节点可以本地缓存在数据中，从而允许同时访问相同的数据。
专用高速缓存行可能需要协商并通过NUMA链接进行传输，然后才能访问数据。
- Drawing 2 MESI type cache control algorithm
Drawing 2 MESI type cache control algorithm
共享模式和独占模式之间的高速缓存行的转换成本很高，因为共享行可能由多个处理器持有。
如果一个处理器要将该行保留为排他性，则必须使其他处理器保留的副本无效。
这意味着如果其他处理器需要再次访问高速缓存行中的数据，则它们将不得不执行其他操作以重新获取高速缓存行。
如果两个处理器继续读取和写入同一条缓存行，则必须一次又一次重新协商对缓存行的独占访问。
高速缓存行的所有权和高速缓存行的内容似乎在多个处理器之间来回跳动，这称为取消缓存行。
不断重新协商高速缓存行的所有权可能会导致NUMA链路上的大量通信，这可能会成为性能瓶颈。
高速缓存行的原子读/写循环可以潜在地用于内存的原子更改，因为必须先保留高速缓存行以进行独占访问，然后才能进行任何写操作。
但是，处理器必须有意执行这种原子读取修改写入周期，这需要使用特殊的原子信号量指令。
这些绕过了处理器执行的大多数典型优化。
如果没有原子信号量操作，则高速缓存行可能会在正常处理流程中随时更改。
2.2 处理器操作的原子性质
处理器以确保某些操作的原子性的方式与高速缓存连接。
对于Itanium，可以保证对64位的操作（正确对齐的内存位置）是原子操作，无需任何其他特殊措施。
这意味着，如果多个处理器尝试将64位值存储到正确对齐的64位内存位置，则内存位置稍后将包含由一个或另一个处理器存储到该位置的值，但将不包含来自一个处理器的几位和来自另一处理器的几位。
再次注意，只有在8位边界上对齐64位值时，才能保证此行为，未对齐的64位存储区不保证是原子的。
并发存储可能会产生一个处理器设置的一些字节，而另一个处理器会设置一些字节。
请注意，Itanium能够处理长于64位的数据结构（例如10字节浮点数或16字节存储）。这些通常也是原子性的，但在某些情况下可能适用于这些特殊注意事项（如果启用了写回缓存，则不能保证原子性）。
如果未遵循这些限制，则可能会从多个CPU同时存储两个10字节的浮点数（在某些情况下）。极少数情况）产生两者的混合。
2.3 利用操作原子性进行列表处理
如上所述，64位值的加载和存储是原子的。
地址是Itanium上的64位实体。
这意味着可以安全地替换地址或从内存中读取地址，而无需采取其他措施（这一点都不奇怪，但是周围的处理器在这一领域面临挑战）。
Linux内核包含一组RCU列表功能，这些功能利用加载和存储的原子性来实现列表的无锁（lock-less）管理。
为了说明它是如何工作的，这是仅通过利用64位操作的原子性质将元素插入到以SMP安全方式完成的线性列表中。
请考虑以下具有两个条目的列表。
- Drawing 3 Lockless insertion of a list element via an atomic store
这些条目通过指向下一个条目的指针链接在一起，并且存在一个全局变量，该变量包含一个指向列表开头的指针。
必须始终安全地扫描列表，以确保无锁实现是可行的。
编写者首先准备要放入列表中的新元素，然后将下一个指针指向列表的第一个元素。
此时，扫描列表将不会到达该新元素。
然后编写器将新元素的地址存储到指向列表开头的全局变量中。
此操作是64位存储且是原子的，因此，如果其他处理器看到旧的起始指针，则扫描列表的其他处理器将扫描两个列表元素，或者在其他处理器看到新的起始指针之后，扫描三个列表元素。
从任何扫描列表的处理器的角度来看，列表本身都不会不一致。
请注意，这仅适用于一位编写者和多个读者。 必须存在某种机制，以确保多个编写者不会同时操作列表。
ps: 实际上就是读写锁的问题。
2.4 障碍和获取/释放(Barriers and acquire / release)
上面给出的示例只有在设置一些障碍以确保以正确的顺序显示内存更改时才有效。
Itanium处理器从内存读取或写入内存的顺序不确定，以允许处理器优化内存访问。
在此处的示例中，我们需要确保新条目（包含指向列表开头的旧指针！）在其他指向列表开头的指针可见之前对其他处理器可见。
我们需要在新条目的设置和指针的更新之间存在写障碍。
写屏障可确保屏障之前的所有写入在屏障之后的任何写入之前对其他处理器可见。
如果没有写顺序，新的起始指针值可能在新条目的内容之前对其他处理器可见。
该结构可能对另一个处理器似乎包含完全无效的数据，从新条目到下一个条目的指针可能看起来为NULL（在这种情况下，扫描列表的处理器只会在列表中找到一个元素，而不是三个！）或垃圾，可能导致无效的内存访问。
有一种类似的机制称为区域屏障（aread barrier）。
它确保在屏障之前的读取操作之后，实际上检索到屏障之后读取的数据。
两种类型的障碍都要求编译器生成其他代码以从内存中重新加载数据或确保将数据写入内存。
读写屏障是Linux函数，它们映射到相同的Itanium内存篱笆指令（fence instruction）。
但是，它们的功能在其他平台上可能会有所不同，因此尽管Itanium处理器没有做任何不同的事情，但我们仍需要保持区别。
某些屏障行为可以在Itanium上的内存引用中进行编码。
在这种情况下，称加载或存储具有获取或释放语义。
具有获取语义的存储操作将确保在所有后续访问之前访问是可见的。
释放语义意味着所有先前的内存访问在指令中的内存访问之前都可见。
这些语义显然不会影响通过编译器生成的代码缓存在寄存器中的值。
这意味着在这些情况下，编译器还必须配合以发挥适当的作用。
Linux的障碍确保了这种情况的发生。
如果使用汇编，则需要确保编译器以某种方式知道必须如何生成代码。
Linux提供了一系列列表操作，这些操作允许对称为RCU列表（在 include/linux/list.h中定义）的双向链接列表进行无锁处理。
图4显示了list_add_rcuusing障碍和原子存储的实现。
- Drawing 4 RCU add_list implementation
新元素的上一个和下一个指针设置为指向上一个和下一个元素。
这样可以确保遇到新元素的列表的任何扫描都可以继续。
然后是写屏障，以确保在对列表进行任何更改之前新元素中的指针是可见的。
通过将next和prev元素指针指向newitem来更改列表。
列表的其他阅读器将扫描不带元素或带元素的列表。
如果另一个处理器遇到新元素，则可以保证新项目的指针也可见。
还有其他一些操作，这些操作可以减少从列表（list_del_rcu）中删除元素的次数，并减少列表的扫描（list_for_each_entry_rcu）。
从列表中删除锁的过程并非没有困难，因为无法保证所有处理器不再看到要删除的列表元素的链接。
必须推迟释放真正的元素，直到知道没有人再浏览列表为止。
为此，存在两个功能来跟踪列表的并发扫描
rcu_read_lock()
rcu_read_unlock()
这些不是真正的锁定操作。
该功能用于维护活动阅读器数量的计数器。
如果读取器的数量达到零，则可以保证不再存在与list元素的链接，并且可以最终定位释放的list元素。
如果使用RCU类型列表，则在任何一次只能有一个写入器处于活动状态。
为了确保单个编写器需要附加锁定。
屏障和常规加载和存储（原子的）是NUMA系统中同步的最有效方法，因为它们不需要慢速的原子信号指令。但是，到目前为止讨论的控制原子性的元素不能保证单个处理器知道只有它自己才导致内存位置状态改变。
例如，不可能确保一个处理器是唯一一个将一个内存位置的零替换为1的处理器。
我们没有办法确保只有一个处理器写入一个内存位置。
小结
感觉最核心的还是需要编译器生成对应的读写屏障，这个个人理解就是指令。
感觉这种原理性的东西还是很枯燥的，希望自己可以坚持把这一系列翻译完成。
