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实现:
[java] view plaincopyprint?
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)会跳出循环,紧接着执行下面的两句代码:
[java] view plaincopyprint?
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
高性能自旋锁 MCS Spinlock 的设计与实现
The Art of Multiprocessor Programming
分享到:
相关推荐
此为本人开始学习单片机的一些笔记,可方便初学者阅读学习
基于C语言编程MCS-51单片机原理与应用
基于c语言编程mcs-51单片机原理与应用
mcs-51 单片机 编程(学习资料2) mcs-51 单片机 编程(学习资料2) mcs-51 单片机 编程(学习资料2)
MCS-51单片机C语言编程100例配套C程序源代码 主要以STC15F2K60S2为主讲解STC单片机的编程及应用,C程序+仿真程序,MDK编程环境,方便大家使用和学习。
mcs-51 单片机 编程(资料) mcs-51 单片机 编程(资料) mcs-51 单片机 编程(资料)
适合大学生学习MCS-51单片,可以借鉴一下,拓展自己的编程能力。
基于单片机MCS_51的智能密码锁设计,pdf格式,相当棒的资料!!
mcs51 电子密码锁
适用于STC89c58单片机学习,适用于STC89c58单片机学习,适用于STC89c58单片机学习,适用于STC89c58单片机学习,适用于STC89c58单片机学习
MCS51入门教程和编程实例,一共30篇,可供初学者参考学习,非常实用!
单片机MCS-51汇编语言编程-汇编语言程序设计
MCS-51单片机C语言编程100例,MCS-51单片机C语言编程100,——
MCS51单片机学习,可用于课程设计。矩阵按键识别技术。
51中断函数学习笔记 51中断函数学习笔记 word
MCS单片机指令系统及编程举例PPT教案学习.pptx
07-Java基础(数组-常见问题)
普罗格 intplog MCS控制系统mcs JAVA项目源码 @Autowired private InterfaceLogService interfaceLogService; @Autowired private McsPlcLogService mcsPlcLogService; //1F分拣口 public void Distribution1F...
本书是在第3版《MCS:51单片机应用设计》一书的基础上,从应用的角度,详细地介绍了MCS:51单片机的硬件结构、指令系统、各种硬件接口设计、各种常用的数据运算和处理程序、接口驱动程序以及MCS:51单片机应用系统的...