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一书):
相关推荐
基于单片机MCS_51的智能密码锁设计,pdf格式,相当棒的资料!!
mcs51 电子密码锁
本科毕业设计--基于mcs51单片机电子密码锁的设计.doc
学士学位论文--基于mcs51单片机电子密码锁的设计.doc
于基mcs51单片机电子密码锁的设计--本科毕业设计.doc
这个不错的哦,大家需要的下前 言 随着城市建设的不断发展,高层建筑不断增多,电梯在国民经济和生活中有着广泛的应用。电梯作为高层建筑中垂直运行的交通工具已与人们的日常生活密不可分。实际上电梯是根据外部...
328 MCS-51单片机原理及实用技术 329 位微型计算机原理·接口技术及其应用 330 单片机开发与典型应用设计 331 单片机实用系统设计技术 332 IBM PC微型计算机原理及接口技术 333 MCS-51单片机原理及接口技术 修订版 ...
基于mcs---51单片机电子密码锁的设计--大学毕业(论文)设计.doc
非常好的单片机实例,数字温度计,键盘扫描,密码锁,频率计
本文利用数字锁相频率合成技术构成收音机的电调谐部分,完成收音机的调台、选台、搜索与存储等功能。本文着重介绍了SONY公司生产的收音机集成芯片CXA1019S构成的FM调频电路、频率合成器芯片BU2614构成的锁相环电路和...
31.c51 单片机 电子锁 按键锁 例子 以及 代码 源码 仿真 模拟 32.c51 单片机 计算器 例子 以及 代码 源码 仿真 模拟 33.c51 单片机 门铃 例子 以及 代码 源码 proteus 仿真 模拟 34.c51 单片机 定时器 例子 以及 ...
锁丢失保护 开发支持 单线后台调试接口 在线调试时,实时总线捕捉在线仿真 外部设备 ADC——24通道,12位转换精度,包含2.5μs转换时钟,自动比较功能,温度传感器,内部带隙基准参考电压通道 ACMPx...
MCS- 51系列单片机应用广泛,是学习单片机技术较好的系统平台,同时也是单片机微型计算 机应用系统开发的一个重要系列。目前,单片机原理与应用教材大都采用汇编语言讲解 和设计程序实例,但汇编语言学习困难。在...
一、设计目的 1.1课题简介 如何实现防盗是很多人关心的问题,传统的机械锁由于其构造简单,被撬的事件屡见 不鲜,使人们的人身及财产安全受到很大威胁。电子密码锁是一种依靠电子电路来控制 电磁锁的开与闭的装置,...
本文所涉及的是市场占有率最高的是MCS—51系列,因为世界上很多知名的IC生产厂家都生产51兼容的芯片。到目前为止,MCS—51单片机已有数百个品种,还在不断推出功能更强的新产品。 本设计是基于单片机的密码锁设计...
[3] 何立民.MCS-51单片机应用系统设计[M].北航出版社,1990年 [4] 霍孟友,王爱群.单片机原理与应用——学习概要及题解[M].机械工业出版社,2005年 李群芳等《单片微型计算机及接口技术》,电子工业出版社
关键词 电子密码锁 STC89C52 矩阵键盘 AT24C02 目 录 1 绪 论 1 1.1 单片机及其特点 1 1.2单片机的发展及应用 1 1.2.1 单片机的发展趋势 1 1.2.2单片机的应用 2 1.3 MCS-51系列单片机 3 2系统硬件设计 5 2.1 设计...
软件设计 MCS- 51系列单片机AT89C4051采用C语言高级程序设计语言编写的程序很简易、高效。 A端工作过程: 1.上电,循环检测键盘是否按下F1,如按下F1,ALARM灯亮,进行自身初始化,等待 连接,监控中心发送create ...