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

(转)MCS队列锁

阅读更多

原文: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实现:

 

  1. public class MCSLock implements Lock {  
  2.     AtomicReference<QNode> tail;  
  3.     ThreadLocal<QNode> myNode;  
  4.   
  5.     @Override  
  6.     public void lock() {  
  7.         QNode qnode = myNode.get();  
  8.         QNode pred = tail.getAndSet(qnode);  
  9.         if (pred != null) {  
  10.             qnode.locked = true;  
  11.             pred.next = qnode;  
  12.   
  13.             // wait until predecessor gives up the lock  
  14.             while (qnode.locked) {  
  15.             }  
  16.         }  
  17.     }  
  18.   
  19.     @Override  
  20.     public void unlock() {  
  21.         QNode qnode = myNode.get();  
  22.         if (qnode.next == null) {  
  23.             if (tail.compareAndSet(qnode, null))  
  24.                 return;  
  25.               
  26.             // wait until predecessor fills in its next field  
  27.             while (qnode.next == null) {  
  28.             }  
  29.         }  
  30.         qnode.next.locked = false;  
  31.         qnode.next = null;  
  32.     }  
  33.   
  34.     class QNode {  
  35.         boolean locked = false;  
  36.         QNode next = null;  
  37.     }  
  38. }  

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)会跳出循环,紧接着执行下面的两句代码:

 

  1. qnode.next.locked = false;  
  2. 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

分享到:
评论

相关推荐

    基于SMP的Linux内核自旋锁分析.pdf

    MCS Lock是一种基于队列的自旋锁机制,它使用一个队列来记录等待获取自旋锁的处理器。当一个处理器尝试获取自旋锁时,它将被添加到队列中,并等待前一个处理器释放自旋锁。 CLH Lock是一种基于链表的自旋锁机制,它...

    CPU自旋锁优化20191020-CLK-new1

    综上所述,CPU自旋锁的优化主要集中在减少数据迁移、降低锁争用以及利用NUMA架构特性,通过MCS自旋锁、CSI和NUMA-Aware Spinlock等策略,来提升多核系统中并发执行的效率和性能。这些技术对于理解和优化大规模并发...

    任哲老师 移植到MCS51的uCOC_II

    它提供了任务调度、信号量、互斥锁、消息队列、时间管理等丰富的内核服务,使得开发者能够更专注于应用程序的编写,而无需关心底层的实时调度问题。 移植过程通常包括以下几个关键步骤: 1. **硬件接口适配**:MCS...

    并发数据结构与多核编程21-22秋季1

    课程深入讲解了不同的锁机制,如测试-设置锁(TAS锁)、测试-测试-设置锁(TTAS锁)、回退锁、CLH队列锁、MCS队列锁和超时锁。这些锁机制各有特点和适用场景,对于性能的优化有着显著的影响。 除了锁机制,课程还涉及了...

    Ucos2 for 51

    UCOS2提供了任务调度、信号量、互斥锁、事件标志组、内存管理等核心功能,为开发者提供了构建复杂嵌入式应用的基础。 二、MCS51微控制器 MCS51,也称8051,是Intel公司推出的一种8位微控制器,广泛应用于工业控制、...

    字节真实面试,不多,但真实

    - **锁机制**:自旋锁、阻塞锁、乐观锁、悲观锁,以及MCS锁和CLH锁队列的应用。 - **Java线程池**:线程池的工作原理,线程数的设置考虑因素,如任务性质(计算密集型或IO密集型)。 4. **数据结构**: - **集合...

    操作系统内核实验指导书1

    2. **同步和锁**:学习原子操作、自旋锁、Ticket lock、MCS锁和读写锁的实现。 ### 第二次迭代 #### Lab 5 进程管理 深入进程创建、调度和上下文切换: 1. **创建与调度进程**:实现进程管理的基础功能。 2. **...

    ucos-II在51系列单片机上的移植源码

    1. **RTOS基础知识**:了解UCOS-II的基本架构,包括任务调度、信号量、互斥锁、事件标志组、消息队列等基本调度和通信机制。理解这些概念对于理解移植过程至关重要。 2. **MCS-51内核**:深入学习MCS-51单片机的...

Global site tag (gtag.js) - Google Analytics