原文:http://blog.csdn.net/aesop_wubo/article/details/7538934
简介
与CLH类似,MCS也是由QNode对象构成的链表,每个QNode表示一个锁持有者,表示一个线程要么已经获取锁,要么正在等待锁。它与CLH不同的是,队列是一个显示链表,是通过next指针串起来的。
实现
MCS队列锁的具体实现如下:
1、如图(a)所示,队列初始化时没有结点,tail=null;
2、如图(b)所示,线程A想要获取锁,于是将自己置于队尾,由于它是第一个结点,它的locked域为false;;
3、如果(c)所示,线程B和C相继加入队列,前面说了这个队列是由next指针串起来的,所以a->next=b,b->next=c。且B和C现在没有获取锁,处于等待状态,所以它们的locked域为true,尾指针指向线程C对应的结点;
4、如果(d)所示,线程A释放锁后,顺着它的next指针找到了线程B,并把B的locked域设置为false。这一动作会触发线程B获取锁。
从上面的实现可以看出,MSC与CLH最大的不同并不是链表是显示还是隐式,而是线程自旋的规则不同,CLH是在前趋结点的locked域上自旋等待,而MSC是在自己的结点的locked域上自旋等待。正因为如此,它解决了CLH在NUMA系统架构中获取locked域状态内存过远的问题。
下面看看MCS队列锁的JAVA实现:
- public class MCSLock implements Lock {
- AtomicReference<QNode> tail;
- ThreadLocal<QNode> myNode;
- @Override
- public void lock() {
- QNode qnode = myNode.get();
- QNode pred = tail.getAndSet(qnode);
- if (pred != null) {
- qnode.locked = true;
- pred.next = qnode;
- // wait until predecessor gives up the lock
- while (qnode.locked) {
- }
- }
- }
- @Override
- public void unlock() {
- QNode qnode = myNode.get();
- if (qnode.next == null) {
- if (tail.compareAndSet(qnode, null))
- return;
- // wait until predecessor fills in its next field
- while (qnode.next == null) {
- }
- }
- qnode.next.locked = false;
- qnode.next = null;
- }
- class QNode {
- boolean locked = false;
- QNode next = null;
- }
- }
lock方法:
若要获得锁,线程会把自己的结点放到队列的尾部,如果队列中开始有结点,就将前一个结点的next结点指向当前结点;
然后就在自己的locked域上自旋等待,直到它的前趋结点把自己的locked设置为false为止。
unlock方法:
若要释放锁,先检查自己的next域是否为null,如果为null,要么当前结点是尾结点,要么还有其他线程正在争用锁。不管是哪种情况都可以采用compareAndSet(q,null)来判断,其中q为当前结点,如果调用成功,则没有其他线程在争用锁,于是将tail设置为null返回;如果调用失败,说明另一个比较慢的线程正在试图获得锁,于是自旋等待它结束。在以上任一种情况,一旦出现有后继结点就将后续结点的locked域设置为false,然后返回。
疑点
对于unlock方法,有人会问既然qnode.next==null,说明qnode是尾结点,那么compareAndSet(q,null)为什么会失败呢?
如下图(a)所示,开始只有线程A在获取锁,A确实是队尾元素,tail指针也指向了它,多线程环境下,一切皆有可能,就在准备进行compareAndSet(q,null)操作时,突然以迅雷不及掩耳之势闯入两个线程B和C,如图(b)所示,这时如果再进行compareAndSet(q,null)操作就会失败。不过在这种情况下,while(qnode.next==null)会跳出循环,紧接着执行下面的两句代码:
- qnode.next.locked = false;
- qnode.next = null;
可见,释放锁操作在有线程闯入时也是能够正常工作的。
优缺点:
优点是适用于NUMA系统架构,缺点是释放锁也需要自旋等待,且比CLH读、写、CAS等操作调用次数多。
参考资料:
A simple correctness proof of the MCS contention-free lock
Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors
The Art of Multiprocessor Programming
相关推荐
使用xilinxFPGA时,对编译生成的bit将如何操作转成mcs可烧写文件的说明
vivado bit文件格式转mcs文件格式,console命令格式 write_cfgmem -format mcs -interface ………………
MCS51 模数转换 MCS51 模数转换
基于单片机MCS_51的智能密码锁设计,pdf格式,相当棒的资料!!
mcs51 电子密码锁
的AVR 系列单片机是一个优秀的RISC 结构单片机系列,与MCS51 相 比其有以下一些典型特点: 1 AVR 的机器周期为1 个时钟周期,绝大多数指令为单周期指令,因此每MHZ 时钟有接近1MIPS 的性能。 2 程序存贮器与数据存贮...
这是基于MCS7840的USB转四串口设计,简化了原厂的设计方案,可以根据自己的需求修改。至少做电源的隔离,也可以把地隔离也都做了,本人因为使用双层板制作,未做模拟地和数字地的隔离。设计使用cadence软件,已将...
MCS-51指令系统 MCS-51指令系统 MCS-51指令系统
本书是在第3版《MCS:51单片机应用设计》一书的基础上,从应用的角度,详细地介绍了MCS:51单片机的硬件结构、指令系统、各种硬件接口设计、各种常用的数据运算和处理程序、接口驱动程序以及MCS:51单片机应用系统的...
MCS51 循迹小车
mcs51,單片機教學
mcs51单片机软件mcs51单片机软件mcs51单片机软件
PCI-E转串口芯片MCS9900x的linux版本驱动。
新编MCS-51单片机应用设计 包括: 第1章 单片机概述 第2章 MCS—51单片机的硬件结构 第3章 MCS—51单片机指令系统 第4章 MCS—51的中断系统 第5章 MCS—51的定时器/计数器 第6章 MCS—51的串行口 第7章 MCS—51扩展...
pci转com口驱动程序,mcs9904,包含USB3.0转com等常用的转com驱动,
Motorola MCS2000维修手册,压缩包内是PDF文件,英文原版文件,里面的内容写的非常详细,
moschip串口卡驱动是一款专为MCS9835提供两个串口和一个打印机端驱动,该驱动支持多种型号卡,可以自动识别卡的类型,节省了您的很多时间,非常方便,欢迎下载使用。moschip串口卡驱动简介现在新型号的主板一般都...
MCS-51手册 MCS-51.7z.001 Part-1
MCS-51单片机
MCS96手册 Part-1 MCS96.7z.001