NUMA 与 SMP

SMP（Symmetric Multi-Processor，对称多处理器）结构指服务器中多个 CPU 对称工作，每个 CPU 访问内存地址所需时间相同。其主要特征是共享，包含对 CPU、内存、I/O 等资源进行共享。SMP 的优点是能够保证内存一致性；缺点是这些共享资源很可能成为性能瓶颈。随着 CPU 数量的增加，每个 CPU 都要访问相同的内存资源，可能导致内存访问冲突，进而造成 CPU 资源的浪费。常用的 PC 机就属于这种架构。

NUMA（Non-Uniform Memory Access，非一致存储访问）将 CPU 分为多个 CPU 模块，每个模块由多个 CPU 组成，并且具有独立的本地内存、I/O 槽口等。模块之间可以通过互联模块相互访问，访问本地内存的速度将远远高于访问远地内存（系统内其它节点的内存）的速度，这也是“非一致存储访问”名称的由来。NUMA 的优点是可以较好地解决原来 SMP 系统的扩展问题；缺点是由于访问远地内存的延时远远超过本地内存，因此当 CPU 数量增加时，系统性能无法线性增加。

CLH 算法实现

CLH 队列中的结点 QNode 中含有一个 locked 字段：该字段若为 true，表示该线程需要获取锁且未释放锁；若为 false，表示线程已释放锁。结点之间通过隐式的链表相连。之所以称为“隐式链表”，是因为这些结点之间没有明显的 next 指针，而是通过 myPred 所指向结点的变化情况来影响 myNode 的行为。CLHLock 上还有一个尾指针 tail，始终指向队列的最后一个结点。CLHLock 的类图如下所示：

1336057027_8106.jpg

当一个线程需要获取锁时，会创建一个新的 QNode，将其中的 locked 设置为 true 表示需要获取锁。然后线程对 tail 域调用 getAndSet 方法，使自己成为队列的尾部，同时获取一个指向其前驱的引用 myPred。随后，该线程就在前驱结点的 locked 字段上进行自旋（Spin），直到前驱结点释放锁。

当一个线程需要释放锁时，将当前结点的 locked 域设置为 false，同时回收前驱结点。如下图所示，线程 A 需要获取锁，其 myNode 域为 true，此时 tail 指向线程 A 的结点；然后线程 B 也加入到线程 A 后面，tail 指向线程 B 的结点。接着线程 A 和 B 都在它的 myPred 域上自旋，一旦它的 myPred 结点的 locked 字段变为 false，它就可以获取锁并执行临界区代码。显然，线程 A 的 myPred locked 域为 false，此时线程 A 获取到了锁。

1336185963_4905.jpg

整个 CLH 的代码如下。其中用到了 ThreadLocal 类，将 QNode 绑定到每一个线程上；同时用到了 AtomicReference，对尾指针的修改正是调用它的 getAndSet() 操作来实现的，它能够保证以原子方式更新对象引用。

public class CLHLock implements Lock {
    AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode());
    ThreadLocal<QNode> myPred;
    ThreadLocal<QNode> myNode;

    public CLHLock() {
        tail = new AtomicReference<QNode>(new QNode());
        myNode = new ThreadLocal<QNode>() {
            protected QNode initialValue() {
                return new QNode();
            }
        };
        myPred = new ThreadLocal<QNode>() {
            protected QNode initialValue() {
                return null;
            }
        };
    }

    @Override
    public void lock() {
        QNode qnode = myNode.get();
        qnode.locked = true;
        QNode pred = tail.getAndSet(qnode);
        myPred.set(pred);
        while (pred.locked) {
            // 自旋等待
        }
    }

    @Override
    public void unlock() {
        QNode qnode = myNode.get();
        qnode.locked = false;
        myNode.set(myPred.get());
    }
}

从代码中可以看出，lock 方法中有一个 while 循环，这是在等待前驱结点的 locked 域变为 false，这是一个自旋等待的过程。unlock 方法很简单，只需要将自己的 locked 域设置为 false 即可，并将前驱结点回收供下次使用。

CLH 优缺点

CLH 队列锁的优点是空间复杂度低。如果有 n 个线程，L 个锁，每个线程每次只获取一个锁，那么需要的存储空间是 O(L+n)（n 个线程有 n 个 myNode，L 个锁有 L 个 tail）。CLH 的一种变体被应用在了 Java 并发框架中（例如 AQS 内部实现）。

唯一的缺点是在 NUMA 系统结构下性能很差。在这种系统结构下，每个线程有自己的内存，如果前驱结点的内存位置比较远，自旋判断前驱结点的 locked 域，性能将大打折扣。但是在 SMP 系统结构下，该算法还是非常有效的。一种解决 NUMA 系统结构问题的思路是使用 MCS 队列锁。

参考资料

说明：本文内容主要基于 CLH 锁的理论模型与经典实现原理。在实际的 Java 并发包（java.util.concurrent）中，AQS（AbstractQueuedSynchronizer）使用了 CLH 队列的变体来实现锁机制，具体实现细节可能有所优化。