欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

MCS锁

程序员文章站 2022-05-05 09:59:43
...

1、 为什么要引入MCS锁?

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


MCS锁
 在前一篇文章中分析了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一书):


MCS锁