摘要
因为多核和多芯片计算机的快速增长，非一致性内存访问(NUMA)架构在主流计算机系统中的地位越来越重要。为了在这些新系统上获取最好的性能，我们需要重新修改当前程序组成部分的并发算法和同步原语。这篇论文重新设计了很关键的同步原语——读写锁。
据我们所知，本文论述的读写锁是第一个专门为NUMA架构设计的，以及这个读写锁的变种。这些变种考虑了在高并发读的情况下的读和写的公平性以及在同一个NUMA节点上让写批量运行。我们的算法利用群组所技术来处理写者之间的同步，比较适合NUMA架构，同时使用二进制标志来协调读者和写者，利用简化的读者计数器，可以在NUMA上使读者间取得更好的并发性。最经过我们的基准程序测试之后，这些简单的NUMA锁算法竟然比目前比较出色的读-写锁的效率还高出10倍以上。为了了评估在真实环境中我们算法的效率，我们也提供了用基准程序 kccachetest测试的结果。Kccachetest属于Kyoto-Cabinet 发行版，这是一个开源的数据库使用了大量的 pthread 线程库的读写锁。跟最好的锁比，我们的锁也把kccachetest的效率提升了40%。
1.介绍
因为微处理器的厂商不断的追求多核和多芯片系统(Intel的Nahalem 和Oracle Niagara平台是比较典型的例子)，计算机工业界正在快速采用分布式和缓存一致性的NUMA架构。这些系统都包含有多个节点，每个节点都有自己的内存，缓存和多核处理器。这些系统呈现了一个统一的编程模型，内存全局可见和缓存一致。在节点间的缓存一致性通信通道被称为外部互联。跟节点内的通道相比，这些节点间的链路一般延迟比较大且带宽比较低。为了降低延迟和少用占用互联带宽，NUMA策略鼓励节点内通信而不是节点间。
在NUMA架构上编写一个高效的软件是非常有挑战的意见事情，因为这类系统对内存和处理器之间的关系抽象的比较初级和“扁平化”，为程序员隐藏了真是的拓扑模型。程序员必须参阅架构手册和使用系统相关的库函数才能知道系统的拓扑结构。不考虑NUMA的多线程程序会有不少效率问题，主要是节点间的内存一致性的通信和节点间带宽引起。而且节点间互联通道是共享资源， 对其竞争和延迟，会导致有一个线程产生的缓存一致性通信会影响另外一个不相关的线程。在移植到NUMA架构之前，目前多线程程序中的并发数据和同步结构都需要仔细的设置。很重要的同步结构是读写锁。
读写锁放宽传统互斥锁的限制，允许多个读线程同时拥有锁。写线程仍需互斥访问。读写锁的使用范围非常广泛，包括操作系统内核，数据库，高端科学计算软件，软件内存事务中[6]。
读写锁已经被研究了几十年了[1,2, 11, 13–16],有简单的计数器和信号灯的方案[2]，利用中心等待队列[14,16]，也有用类似可伸缩的非零指示器（SNZI）[15]等更高级的数据结构。在所有这些方案中，SNZI依赖于中心数据结构来协调各个线程，所以会遇到可升缩性问题[15]。SNZI算法通过把读者放到SNZI树的叶子节点上来追踪写者（请求读锁的线程）。通过把SNZI树的叶子节点分到不同的NUMA节点，读线程就可以知道自己在NUMA上哪个节点了。而写线程依旧忽略NUMA，所以会有伸缩性问题。
Hsieh，Weihl和Vyukov独自提出了一种简单分布式的方式来实现读写锁。每个分布式的读写锁包括N（N是系统处理器个数）个读写锁。每一个读者分配一个读写锁，在执行读临界区之前必须获取这把读锁。通过强制的加锁次序来避免写者之间的死锁。这个方法可以用到NUMA架构上，把N限制为系统中NUMA节点的个数，每个读者分配节点专属的锁。我们把这个变化了的算法称作DV，一定程度上感知了NUMA，跟SNZI读写锁类似 。在没有写者的情况下，在各个节点上的读者在获取和释放读权限时不会产生任何节点间的写一致性交互。 然而每一个节点上的写者在获取写权限时都会潜在的产生大量的节点间一致性交互。所以随着写次数的增加，DV的效率也会显著下降。由于使用加锁次序来避免死锁，在后加锁的节点上的读者比先加锁节点上的读者更有效率优势，这是不公平的。
这篇论文展示了一组转为NUMA设计的读写锁，相比之前的读写锁算法具有更好的性能和伸缩性。我们从三方面入手来设计我们的锁。第一，跟DV类似，我们维护了一个分布式的数据结构用来存储读者元数据，读者通过更新他们节点的位置信息来说明自己的意愿。通过读指示器来更新减少了节点间一致性的交互。第二，写者优先把访问权限交给跟自己同一节点的其它已经阻塞的写者，可以增强节点内部缓存的锁和临界区中要访问的数据局部性。最后，我们的算法为读者和写者维护了一个非常紧凑的执行路径，减少了获取和释放操作带来的延迟。
我们的读写锁算法基于目前刚开发的群组所技术，他允许创建NUMA的互斥锁。简单说，写者使用群组所来同步同时维护写者之间的互斥。使用群组所方式，写者正在释放的锁会优先交给跟自己同节点的处于阻塞的写者，因此可以减少锁在节点间的转移。
我们的读写锁也包括了分布式的读指示器，这个数据结构可以追踪读者。读者获取锁时会在读指示器中记录，释放锁会从读指示器中去除。写者查询读指示器来发现并发的活跃读者。由于读指示器是分布式的，读者只需要访问他们所在节点的锁的元数据就可以了。我们还额外使用了一个简单的标识变量用来协调读者和写者。这个简单的算法是的NUMA上的读写锁的效率远比之前很出色的算好要好。
我们提供的不同的读写锁可以用公平性这个属性来区分。我们也展示了不同的“优先”策略：读者优先，写者优先，中性策略。读者优先策略是尽快让读者获取锁，而不管到达的次序。而写者优先策略对于写者本身没有偏向性。具体一点说，这些优先策略允许读
