Java中的公平锁和非公平锁实现详解

Wesley13
• 阅读 464

前言

Java语言中有许多原生线程安全的数据结构,比如ArrayBlockingQueueCopyOnWriteArrayListLinkedBlockingQueue,它们线程安全的实现方式并非通过synchronized关键字,而是通过java.util.concurrent.locks.ReentrantLock来实现。 刚好对这个很感兴趣, 因此写一篇博客详细分析此 “可重入锁实现原理”。 
ReentrantLock的实现是基于其内部类FairSync(公平锁)和NonFairSync(非公平锁)实现的。 其可重入性是基于Thread.currentThread()实现的: 如果当前线程已经获得了执行序列中的锁, 那执行序列之后的所有方法都可以获得这个锁。

公平锁:

  • 公平和非公平锁的队列都基于锁内部维护的一个双向链表,表结点Node的值就是每一个请求当前锁的线程。公平锁则在于每次都是依次从队首取值。
  • 锁的实现方式是基于如下几点: 
    • 表结点Node和状态statevolatile关键字。
    • sum.misc.Unsafe.compareAndSet的原子操作(见附录)。

非公平锁:

  • 在等待锁的过程中, 如果有任意新的线程妄图获取锁,都是有很大的几率直接获取到锁的。

ReentrantLock锁都**不会**使得线程中断,除非开发者自己设置了中断位。 
ReentrantLock获取锁里面有_看似_自旋的代码,但是它_不是_自旋锁。 
ReentrantLock公平与非公平锁都是属于排它锁。

ReentrantLock的可重入性分析

这里有一篇对锁介绍甚为详细的文章 朱小厮的博客-Java中的锁.

synchronized的可重入性

参考这篇文章: Java内置锁synchronized的可重入性

java线程是基于“每线程(per-thread)”,而不是基于“每调用(per-invocation)”的(java中线程获得对象锁的操作是以每线程为粒度的,per-invocation互斥体获得对象锁的操作是以每调用作为粒度的)

ReentrantLock的可重入性

前言里面提到,ReentrantLock重入性是基于Thread.currentThread()实现的: 如果当前线程已经获得了锁, 那该线程下的所有方法都可以获得这个锁。ReentrantLock的锁依赖只有 NonfairSyncFairSync两个实现类, 他们的锁获取方式大同小异。

可重入性的实现基于下面代码片段的 else if 语句

protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        ...
        // 尝试获取锁成功
    }
    else if (current == getExclusiveOwnerThread()) {
        // 是当前线程,直接获取到锁。实现可重入性。
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

此处有两个值需要关心:

    /**
     * The current owner of exclusive mode synchronization.
     * 持有该锁的当前线程
     */
    private transient Thread exclusiveOwnerThread;

     -----------------两个值不在同一个类----------------

    /**
     * The synchronization state.
     * 0: 初始状态-无任何线程得到了锁
     * > 0: 被线程持有, 具体值表示被当前线程持有的执行次数
     * 
     * 这个字段在解锁的时候也需要用到。
     * 注意这个字段的修饰词: volatile
     */
    private volatile int state;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

ReentrantLock锁的实现分析

公平锁和非公平锁

ReentrantLock 的公平锁和非公平锁都委托了 AbstractQueuedSynchronizer#acquire 去请求获取。

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}
  • 1

  • 2

  • 3

  • 4

  • 5

  • tryAcquire 是一个抽象方法,是**公平与非公平**的实现原理所在。

  • addWaiter 是将当前线程结点加入等待队列之中。公平锁在锁释放后会严格按照等到队列去取后续值,_而非公平锁在对于新晋线程有很大优势_。

  • acquireQueued 在多次循环中尝试获取到锁或者将当前线程阻塞。

  • selfInterrupt 如果线程在阻塞期间发生了中断,调用 Thread.currentThread().interrupt() 中断当前线程。

ReentrantLock 对线程的阻塞是基于 LockSupport.park(this); (见 AbstractQueuedSynchronizer#parkAndCheckInterrupt)。 先决条件是当前节点有限次尝试获取锁失败。

公平锁和非公平锁在说的获取上都使用到了 volatile 关键字修饰的state字段, 这是保证多线程环境下锁的获取与否的核心。 
但是当并发情况下多个线程都读取到 state == 0时,则必须用到CAS技术,一门CPU的原子锁技术,可通过CPU对共享变量加锁的形式,实现数据变更的原子操作。 
volatile 和 CAS的结合是并发抢占的关键。

公平锁FairSync

公平锁的实现机理在于每次有线程来抢占锁的时候,都会检查一遍有没有等待队列,如果有, 当前线程会执行如下步骤:

if (!hasQueuedPredecessors() &&
    compareAndSetState(0, acquires)) {
    setExclusiveOwnerThread(current);
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5

其中hasQueuedPredecessors是用于检查是否有等待队列的。

    public final boolean hasQueuedPredecessors() {
        Node t = tail; // Read fields in reverse initialization order
        Node h = head;
        Node s;
        return h != t &&
            ((s = h.next) == null || s.thread != Thread.currentThread());
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

非公平锁NonfairSync

非公平锁在实现的时候多次强调随机抢占:

if (c == 0) {
    if (compareAndSetState(0, acquires)) {
        setExclusiveOwnerThread(current);
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

与公平锁的区别在于新晋获取锁的进程会有多次机会去抢占锁。如果被加入了等待队列后则跟公平锁没有区别。

ReentrantLock锁的释放

ReentrantLock锁的释放是逐级释放的,也就是说在 可重入性 场景中,必须要等到场景内所有的加锁的方法都释放了锁, 当前线程持有的锁才会被释放! 
释放的方式很简单, state字段减一即可:

protected final boolean tryRelease(int releases) {
    //  releases = 1
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

ReentrantLock等待队列中元素的唤醒

当当前拥有锁的线程释放锁之后, 且非公平锁无线程抢占,就开始线程唤醒的流程。 
通过tryRelease释放锁成功,调用LockSupport.unpark(s.thread); 终止线程阻塞。 
见代码:

private void unparkSuccessor(Node node) {
    // 强行回写将被唤醒线程的状态
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
    Node s = node.next;
    // s为h的下一个Node, 一般情况下都是非Null的
    if (s == null || s.waitStatus > 0) {
        s = null;
        // 否则按照FIFO原则寻找最先入队列的并且没有被Cancel的Node
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    // 再唤醒它
    if (s != null)
        LockSupport.unpark(s.thread);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

ReentrantLock内存可见性分析

针对如下代码:

try {
    lock.lock();
    i ++;
} finally {
    lock.unlock();
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

可以发现哪怕在不使用 volatile关键字修饰元素i的时候, 这里的i 也是没有并发问题的。

CAS和volatile, Java并发的基石

volatile 是Java语言的关键字, 功能是保证被修饰的元素(共享变量):

任何进程在读取的时候,都会清空本进程里面持有的共享变量的值,强制从主存里面获取; 
任何进程在写入完毕的时候,都会强制将共享变量的值写会主存。 
volatile 会干预指令重排。 
volatile 实现了JMM规范的 happen-before 原则。

在多核多线程CPU环境下, CPU为了提升指令执行速度,在保证程序语义正确的前提下,允许编译器对指令进行重排序。也就是说这种指令重排序对于上层代码是感知不到的,我们称之为 processor ordering.

JMM 允许编译器在指令重排上自由发挥,除非程序员通过 volatile等 显式干预这种重排机制,建立起同步机制,保证多线程代码正确运行。见文章:Java并发:volatile内存可见性和指令重排

当多个线程之间有互相的数据依赖的之后, 就必须显式的干预这个指令重排机制

CAS是CPU提供的一门技术。在单核单线程处理器上,所有的指令允许都是顺序操作;但是在多核多线程处理器上,多线程访问同一个共享变量的时候,可能存在并发问题。

使用CAS技术可以锁定住元素的值。Intel开发文档, 第八章 
编译器在将线程持有的值与被锁定的值进行比较,相同则更新为更新的值。 
CAS同样遵循JMM规范的 happen-before 原则。 
JAVA CAS原理深度分析博客

公平锁和非公平锁在说的获取上都使用到了 volatile 关键字修饰的state字段, 这是保证多线程环境下锁的获取与否的核心。 
但是当并发情况下多个线程都读取到 state == 0时,则必须用到CAS技术,一门CPU的原子锁技术,可通过CPU对共享变量加锁的形式,实现数据变更的原子操作。 
volatile 和 CAS的结合是并发抢占的关键。

JSR-133编译器编写手册

JMM规范经历了多代迭代, JSR-133为较为通用的一版规范。

编译器编写手册文档见: The JSR-133 Cookbook for Compiler Writers (非官方指南)

上面小章节描述到了 volatile可以避免掉的指令重排, 那它怎么避免的呢?

在内存的读写过程中, 无非 读/写 两者操作的四种组合:

  • LoadStore
  • LoadLoad
  • StoreStore
  • StoreLoad

volatile关键字通过提供“内存屏障”的方式来防止指令被重排序,为了实现volatile的内存语义,编译器在生成字节码时,会在指令序列中插入内存屏障来禁止特定类型的处理器重排序。而大多数的处理器都支持内存屏障的指令。

  • volatile读操作的后面插入一个LoadLoad屏障。
  • volatile写操作的后面插入一个StoreLoad屏障。

那这个StoreLoad /LoadLoad有什么用处呢? 见 Intel开发文档, 第八章。 简单的说StoreLoad就是触发后续指令中的线程缓存回写到内存; 而LoadLoad会触发线程重新从主存里面读数据进行处理。

Synchronization mechanisms in multiple-processor systems may depend upon a strong memory-ordering model. Here, a program can use a locking instruction such as the XCHG instruction or the LOCK prefix to ensure that a read-modify-write operation on memory is carried out atomically. Locking operations typically operate like I/O operations in that they wait for all previous instructions to complete and for all buffered writes to drain to memory.

ReentrantLock内存可见性

在上述博客中的: ReentrantLock锁的实现分析#公平锁和非公平锁 中讲到:ReentrantLock 通过 volatile 和 CAS 的搭配实现锁的功能。

顺带的, volatile 关键字修饰的 state 字段读和后续的锁释放中的 state 字段写, 共同组成了保证ReentrantLock内存可见性的内存屏障。 此屏障保证了ReentrantLock的内存可见性

CAS的类似volatile内存屏障原理

参见文章 深入理解Java内存模型(五)——锁 
如下文档部分摘录

volatile是通过在Java编译时,添加字节码来实现内存屏障功能。

CAS通过本地JNI调用,Java代码为 Unsafe.java, 层次调用为:unsafe.cpp > atomic.cpp > atomicwindowsx86.inline.hpp。调用的代码如是:

#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

如上面源代码所示,程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果程序是在多处理器上运行,就为cmpxchg指令加上lock前缀(lock cmpxchg)。反之,如果程序是在单处理器上运行,就省略lock前缀(单处理器自身会维护单处理器内的顺序一致性,不需要lock前缀提供的内存屏障效果)。

intel的手册对lock前缀的说明如下:

  1. 确保对内存的读-改-写操作原子执行。在Pentium及Pentium之前的处理器中,带有lock前缀的指令在执行期间会锁住总线,使得其他处理器暂时无法通过总线访问内存。很显然,这会带来昂贵的开销。从Pentium 4,Intel Xeon及P6处理器开始,intel在原有总线锁的基础上做了一个很有意义的优化:如果要访问的内存区域(area of memory)在lock前缀指令执行期间已经在处理器内部的缓存中被锁定(即包含该内存区域的缓存行当前处于独占或以修改状态),并且该内存区域被完全包含在单个缓存行(cache line)中,那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定,其它处理器无法读/写该指令要访问的内存区域,因此能保证指令执行的原子性。这个操作过程叫做缓存锁定(cache locking),缓存锁定将大大降低lock前缀指令的执行开销,但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时,仍然会锁住总线。
  2. 禁止该指令与之前和之后的读和写指令重排序。
  3. 把写缓冲区中的所有数据刷新到内存中。

上面的第2点和第3点所具有的内存屏障效果,足以同时实现volatile读和volatile写的内存语义。

原文:https://blog.csdn.net/qyp199312/article/details/70598480

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
4个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这