MCS锁

1、 为什么要引入MCS锁？

         在NUMA架构体系下，访问remote memory的速度要远远慢于访问local memory的速度。如下图所示（引自Companion slides for The Art of Multiprocessor Programming by Maurice Herlihy & Nir Shavit）：

 在前一篇文章中分析了CLH算法，由于每个线程都在其前驱线程的QNode节点的locked域自旋，在NUMA体系下，即每个线程都在其前驱线程的remote memory位置自旋，因此性能上会打折扣。

那么在NUMA体系下，如果每个线程自旋的位置都能固定在自己的local memory中，则性能相比于CLH算法，应该会有一定的提升。MCS锁就是基于这种理念设计出来的。

 

2、MCS锁介绍

       同CLH锁一样，每个申请锁的线程通过一个QNode对象表示，QNode中有一个volatile boolean类型的成员变量locked，locked为true，则表示对应的线程已经获取到了锁或者正在等待获取锁；locked为false，则表示对应的线程已经释放了锁。

       锁则由多个QNode节点组成链表标示，与CLH锁不同的是，MCS中的锁不是虚拟链表，而是实际链表，每个QNode节点都有一个next域指向其后继结点。

 

public class QNode {
	public volatile boolean locked = false;
	public QNode next = null;
}

       而链表的尾节点则通过锁AtomicReference<QNode>类型的tail成员变量指向，即tail指向加入到申请锁的队列中的最近一个线程。

 

 

public class MCSLock implements Lock {
	private AtomicReference<QNode> tail;
	private ThreadLocal<QNode> myNode;

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

	public void lock() {
		QNode qnode = myNode.get();
		QNode pred = tail.getAndSet(qnode);
		if (null != pred) {
			qnode.locked = true;
			pred.next = qnode;
		}
		while (qnode.locked) {
		}
	}

	public void unlock() {
		QNode qnode = myNode.get();
		if (null == qnode.next) {
			if (tail.compareAndSet(qnode, null)) {
				return;
			}
			while (null == qnode.next) {
			}
		}
		qnode.next.locked = false;
		qnode.next = null;
	}
}

       当一个线程申请锁时：

a)首先会实例化一个QNode节点，并将其设置为自己的本地线程变量myNode；

b)然后通过调用AtomicReference的getAndSet()方法，将myNode设置为队列的最后一个节点，并返回其前驱节点

c)接着判断前面是否已经有其他线程加入到锁的等待队列中，即前驱节点是否为空。如果前驱节点为空，则说明自己是第一个加入到锁的等待队列中的线程，执行自旋，由于locked域初始值为false，所以能立即退出自旋，获取到锁；

d)如果前驱节点非空，则首先将myNode的locked域设置为true，表明自己正在等待获取锁；同时将前驱结点的next域指向myNode。

e)最后该线程一直在自己节点的locked域自旋，直到locked域变为false，即前驱节点释放了锁。

 

        当一个线程释放锁时，会处于以下三种情况之一中：

a)此刻没有其它线程正在申请锁，即当前节点的next域指向null，且tail指向当前节点：此种情况通过调用AtomicReference的compareAndSet()方法，将tail指向null；然后直接返回。

b)此刻有其他线程正在申请锁，而且已更新tail域，但还未将前驱节点的next域指向它。即当前节点的next域指向null，且tail不是指向当前节点：此种情况则一直等待其他线程设置前驱节点的next域后，才将后继节点的locked域设置为false，以便后继节点退出自旋，从而获取到释放的锁。

c)此刻有其他线程正在申请锁，而且已更新tail域，而且已将前驱节点的next域指向它。即当前节点的next域非空：此种情况则直接将后继节点的locked域设置为false，以便后继节点退出自旋，从而获取到释放的锁。

 

       下图阐述了MCS算法中锁的获取和释放过程（引自The art of Multiprocessor Programming一书）：