`
海浪儿
  • 浏览: 271861 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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一书):



 

  • 大小: 56.7 KB
  • 大小: 81.6 KB
1
0
分享到:
评论
1 楼 0704681032 2015-02-17  
帮助很大,谢谢!

相关推荐

Global site tag (gtag.js) - Google Analytics