Java并发之高级自旋锁CLH锁和MCS锁

自旋锁

自旋锁(spin lock)是一个典型的对临界资源的互斥手段,自旋锁是基于CAS原语的,所以它是轻量级的同步操作,它的名称来源于它的特性。自旋锁是指当一个线程尝试获取某个锁时,如果该锁已被其他线程占用,就一直循环检测锁是否被释放,而不是进入线程挂起或睡眠状态。由于自旋锁只不进行线程状态的改变(挂起线程),所以当线程竞争不激烈时,它的响应速度极快(因为避免了线程调度的上下文切换)。自旋锁适用于锁保护的临界区很小的情况,线程竞争不激烈的场景下。如果线程之间竞争激烈或者临界区的操作特别耗时,那么线程的自旋操作就会耗费大量的cpu资源,所以这种情况下性能就会下降明显。

现代计算机CPU的处理结构

由于自旋锁受不同的硬件处理器和架构的影响,我们来简单了解一下相关的知识,重点关注SMP和NUMA。

(1)多线程

(2)多核心

(3)SMP SMP(Symmetric Multi-Processing),对称多处理结构的简称,是指在一个计算机上汇集了一组处理器(多CPU),各CPU之间共享内存子系统以及总线结构。在这种技术的支持下,一个服务器系统可以同时运行多个处理器,并共享内存和其他的主机资源。像双至强,也就是所说的二路,这是在对称处理器系统中最常见的一种(至强MP可以支持到四路,AMD Opteron可以支持1-8路)。也有少数是16路的。但是一般来讲,SMP结构的机器可扩展性较差,很难做到100个以上多处理器,常规的一般是8个到16个,不过这对于多数的用户来说已经够用了。在高性能服务器和工作站级主板架构中最为常见,像UNIX服务器可支持最多256个CPU的系统。

(4)NUMA

NUMA即非一致访问分布共享存储技术,它是由若干通过高速专用网络连接起来的独立节点构成的系统,各个节点可以是单个的CPU或是SMP系统。在NUMA中,Cache 的一致性有多种解决方案,一般采用硬件技术实现对cache的一致性维护,通常需要操作系统针对NUMA访存不一致的特性(本地内存和远端内存访存延迟和带宽的不同)进行特殊优化以提高效率,或采用特殊软件编程方法提高效率。NUMA系统的例子。这里有3个SMP模块用高速专用网络联起来,组成一个节点,每个节点可以有12个CPU。像Sequent的系统最多可以达到64个CPU甚至256个CPU。显然,这是在SMP的基础上,再用NUMA的技术加以扩展,是这两种技术的结合。

(4)乱序执行

(4)分枝技术

(4)控制器

自旋锁的分类及特点

关于自旋锁的种类大体上有四种:

(1)简单自旋锁(非公平)

不能保证公平性

(2)基于票据的自旋锁(公平)

虽然解决了公平性的问题,但是多处理器系统上,每个进程/线程占用的处理器都在读写同一个变量serviceNum ,每次读写操作都必须在多个处理器缓存之间进行缓存同步,这会导致繁重的系统总线和内存的流量,大大降低系统整体的性能

(3)CLH自旋锁(公平)

作者:CLH:Craig,Landin and Hagersten。 锁的名称都来源于发明人的名字首字母

CLH自旋锁是一种基于隐式链表(节点里面没有next指针)的可扩展、高性能、公平的自旋锁,申请线程只在本地变量上自旋,它不断轮询前驱的状态,如果发现前驱释放了锁就结束自旋。CLH队列锁的优点是空间复杂度低(如果有n个线程,L个锁,每个线程每次只获取一个锁,那么需要的存储空间是O(L+n),n个线程有n个。myNode,L个锁有L个tail),CLH的一种变体被应用在了JAVA并发框架中。 CLH在SMP系统结构下该法是非常有效的。但在NUMA系统结构下,每个线程有自己的内存,如果前趋结点的内存位置比较远,自旋判断前趋结点的locked域,性能将大打折扣

(4)MCS自旋锁(公平)

作者:MCS:John Mellor-Crummey and Michael Scott。 锁的名称都来源于发明人的名字首字母

MCS Spinlock是一种基于显式链表(节点里面拥有next指针)的可扩展、高性能、公平的自旋锁,申请线程只在本地变量上自旋,由直接前驱负责通知其结束自旋(与CLH自旋锁不同的地方,不在轮询前驱的状态,而是由前驱主动通知),从而极大地减少了不必要的处理器缓存同步的次数,降低了总线和内存的开销。而MCS是在自己的结点的locked域上自旋等待。正因为如此,它解决了CLH在NUMA系统架构中获取locked域状态内存过远的问题。

实现CLH和MCS自旋锁

关于简单的自旋锁和基于票号的自旋锁前面的文章已经介绍过,这里不再重复介绍。

首先看CLH自旋锁的实现方式:

package concurrent.spinlock;

import java.util.concurrent.atomic.AtomicReference;

/**
 * Created by qindongliang on 2018/8/5.
 */
public class CLHLock {

     class Node{
         //false代表没人占用锁
      volatile   boolean locked=false;
    }

    //指向最后加入的线程
  final   AtomicReference<Node> tail=new AtomicReference<>(new Node());

    //使用ThreadLocal保证每个线程副本内都有一个Node对象
  final   ThreadLocal<Node> current;


    public CLHLock(){
        //初始化当前节点的node
        current=new ThreadLocal<Node>(){
            @Override
            protected Node initialValue() {
                return new Node();
            }
        };


    }


    public void lock() throws InterruptedException {

       //得到当前线程的Node节点
       Node own=current.get();
        //修改为true,代表当前线程需要获取锁
        own.locked=true;

        //设置当前线程去注册锁,注意在多线程下环境下,这个
        //方法仍然能保持原子性,,并返回上一次的加锁节点(前驱节点)
        Node preNode=tail.getAndSet(own);

        //在前驱节点上自旋
        while(preNode.locked){
            System.out.println(Thread.currentThread().getName()+" 开始自旋....  ");
            Thread.sleep(2000);
        }


    }

    public void unlock(){

        //当前线程如果释放锁,只要将占用状态改为false即可
        //因为其他的线程会轮询自己,所以volatile布尔变量改变之后
        //会保证下一个线程能立即看到变化,从而得到锁
        current.get().locked=false;

    }


    public static void main(String[] args) throws InterruptedException {

        CLHLock lock=new CLHLock();

        Runnable runnable=new Runnable() {
            @Override
            public void run() {
                try {
                    lock.lock();
                    System.out.println(Thread.currentThread().getName()+"  获得锁 ");
                    //前驱释放,do own work
                    Thread.sleep(5000);
                    System.out.println(Thread.currentThread().getName()+"  释放锁 ");
                    lock.unlock();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        };

        Thread t1=new Thread(runnable,"线程1");
        Thread t2=new Thread(runnable,"线程2");
        Thread t3=new Thread(runnable,"线程3");

        t1.start();
        t2.start();
        t3.start();




    }




}

在三个线程下面的输出结果:

线程1  获得锁 
线程3 开始自旋....  
线程2 开始自旋....  
线程3 开始自旋....  
线程2 开始自旋....  
线程2 开始自旋....  
线程3 开始自旋....  
线程1  释放锁 
线程2  获得锁 
线程3 开始自旋....  
线程3 开始自旋....  
线程3 开始自旋....  
线程2  释放锁 
线程3  获得锁 
线程3  释放锁

MCS锁的实现方式:

package concurrent.spinlock;

import java.util.concurrent.atomic.AtomicReference;

/**
 * Created by qindongliang on 2018/8/5.
 */
public class MCSLock {

    class Node{
      volatile   Node next;//后继节点
        //默认false
      volatile   boolean locked;
    }

    //指向最后加入的线程
    final AtomicReference<MCSLock.Node> tail=new AtomicReference<>(null);

    ThreadLocal<Node> current;

    public MCSLock(){
        //初始化当前节点的node
        current=new ThreadLocal<MCSLock.Node>(){
            @Override
            protected MCSLock.Node initialValue() {
                return new MCSLock.Node();
            }
        };
    }


    public void lock() throws InterruptedException {

        //获取当前线程的Node
        Node own=current.get();

        //获取前驱节点
        Node preNode=tail.getAndSet(own);

        //如果前驱节点不为null,说明有线程已经占用
        if(preNode!=null){
            //设置当前节点为需要占用状态;
            own.locked=true;
            //把前面节点的next指向自己
            preNode.next=own;

            //在自己的节点上自旋等待前驱通知
            while(own.locked){

                System.out.println(Thread.currentThread().getName()+" 开始自旋....  ");
                Thread.sleep(2000);

            }


        }

        System.out.println(Thread.currentThread().getName()+" 获得了锁....  ");

    }


    public void unlock(){
        //获取自己的节点
        Node own=current.get();
        //
        if(own.next==null){
            //判断是不是自身是不是最后一个线程
            if(tail.compareAndSet(own,null)){
                //是的话就结束
                return;
            }

            //在判断过程中,又有线程进来
            while (own.next==null){

            }

        }
        //本身解锁,通知它的后继节点可以工作了,不用再自旋了
        own.next.locked=false;
        own.next=null;// for gc


    }

    public static void main(String[] args) {

        MCSLock lock=new MCSLock();

        Runnable runnable=new Runnable() {
            @Override
            public void run() {
                try {
                    lock.lock();
                    System.out.println(Thread.currentThread().getName()+"  获得锁 ");
                    //前驱释放,do own work
                    Thread.sleep(4000);
                    System.out.println(Thread.currentThread().getName()+"  释放锁 ");
                    lock.unlock();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }


            }
        };

        Thread t1=new Thread(runnable,"线程1");
        Thread t2=new Thread(runnable,"线程2");
        Thread t3=new Thread(runnable,"线程3");

        t1.start();
        t2.start();
        t3.start();

    }








}

输出结果:

线程1 获得了锁....  
线程2 开始自旋....  
线程3 开始自旋....  
线程1  获得锁 
线程3 开始自旋....  
线程2 开始自旋....  
线程1  释放锁 
线程3 开始自旋....  
线程2 开始自旋....  
线程3 获得了锁....  
线程3  获得锁 
线程2 开始自旋....  
线程2 开始自旋....  
线程2 开始自旋....  
线程3  释放锁 
线程2 获得了锁....  
线程2  获得锁 
线程2  释放锁

详细介绍,在代码的注释里面写的很清楚了,这里再给一张图来帮助我们我们理解基于链表实现公平方式的过程:

CLH 对比 MCS

(1)从代码实现来看,CLH比MCS要简单得多。

(2)从自旋的条件来看,CLH是在前驱节点的属性上自旋,而MCS是在本地属性变量上自旋。

(3)从链表队列来看,CLH的队列是隐式的,CLHNode并不实际持有下一个节点;MCS的队列是物理存在的。

(4)CLH锁释放时只需要改变自己的属性,MCS锁释放则需要改变后继节点的属性。

(5)CLH适合CPU个数不多的计算机硬件架构上,MCS则适合拥有很多CPU的硬件架构上

(6)CLH和MCS实现的自旋锁都是不可重入的

总结

本文主要介绍了目前主流的4种自旋锁的特点和实现,此外众所周知,AbstractQueuedSynchronizer是Java并发包的基石之一,而CLH锁的原理和思想则是AbstractQueuedSynchronizer的基石之一,JDK里面的CLH锁的是增强改进后的CLH锁。理解清楚CLH锁的原理和实现对后面学习和理解AbstractQueuedSynchronizer是非常重要的。最后文中所有的代码已经上传我的github上,感兴趣的朋友可以研究学习。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-08-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

linux 内核同步机制使用

Linux 内核中的同步机制:原子操作、信号量、读写信号量、自旋锁的API、大内核锁、读写锁、大读者锁、RCU和顺序锁。 1、介绍 在现代操作系统里,同一时间...

4005
来自专栏极客编程

用Java为Hyperledger Fabric(超级账本)开发区块链智能合约链代码之部署与运行示例代码

您已经定义并启动了本地区块链网络,而且已构建 Java shim 客户端 JAR 并安装到本地 Maven 存储库中,现在已准备好在之前下载的 Hyperled...

2521
来自专栏菩提树下的杨过

spring cloud:Edgware.RELEASE版本中zuul回退方法的变化

Edgware.RELEASE以前的版本中,zuul网关中有一个ZuulFallbackProvider接口,代码如下: public interface Zu...

2436
来自专栏玩转JavaEE

Spring Cloud中Hystrix的请求合并

在微服务架构中,我们将一个项目拆分成很多个独立的模块,这些独立的模块通过远程调用来互相配合工作,但是,在高并发情况下,通信次数的增加会导致总的通信时间增加,同时...

3907
来自专栏Ryan Miao

在dropwizard中使用feign,使用hystrix

前言 用惯了spring全家桶之后,试试dropwizard的Hello World也别有一帆风味。为了增强对外访问API的能力,需要引入open feign...

41412
来自专栏Android 研究

Android系统启动——4 zyogte进程 (C篇)

我们大家都是知道"一鼎三足"和"三角形的稳定性",那么支撑Android系统的三个"足"是什么?即init进程、SystemServer进程和Zygote进程。...

3661
来自专栏JavaEE

Thymeleaf的使用前言:一、thymeleaf简介:二、thymeleaf标准方言:三、thymeleaf与springboot集成案例:总结:

最近听说thymeleaf好像也挺流行的,还说是spring官方推荐使用,那thymeleaf究竟是什么呢?spring为什么推荐用它呢?怎么用呢?本文将为你揭...

1442
来自专栏WindCoder

Spring Boot REST API错误处理指南

本来是5号来的文章,无奈最近准备换工作,一直拖着没写,今天搜索偶然看见有人已经翻译完了,由于时间原因这次就直接转载下吧,现附上英文原文及相关信息,最后再附上译文...

2262
来自专栏机器学习从入门到成神

临界区、互斥量、信号量

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

2172
来自专栏Java3y

JSP第一篇【JSP介绍、工作原理、生命周期、语法、指令、行为】

什么是JSP JSP全名为Java Server Pages,java服务器页面。JSP是一种基于文本的程序,其特点就是HTML和Java代码共同存在! 为什么...

3865

扫码关注云+社区

领取腾讯云代金券