从软件(Java/hotspot/Linux)到硬件(硬件架构)分析互斥操作的本质

HTML5与CSS3知识点总结

先上结论:

一切互斥操作的依赖是 自旋锁(spin_lock),互斥量(semaphore)等其他需要队列的实现均需要自选锁保证临界区互斥访问。

而自旋锁需要xcmpchg等类似的可提供CAS操作的硬件指令提供原子性 和 可见性,(xcmpchg会锁总线或缓存行,一切会锁总线或缓存行的操作都会刷StoreBuffer,起到写屏障的操作)

所以,任意的互斥操作,无论是 java 层面,hotspot层面,linux层面 的根本依赖都是 xcmpchg 等硬件指令。java算是上层,需要依赖hotspot和linux嵌入的汇编完成xcmpchg的调用。

所有同步手段的根本是硬件,软件是辅助手段,软件和硬件的交界面是用于并发控制的硬件指令(如 cmpchg, 带lock前缀的指令,lwsync, sfence 等)

整个依赖链条:

1. Java 的并发工具包 JUC 中大部分同步工具类依赖 AQS 为他们提供队列服务和资源控制服务。

2. AQS 依赖 LockSupport 的 park 和 unpark 为他提供线程休眠唤醒操作

3. LockSupport 的 park 和 unpark 是依赖 JVM(此处语境讨论 Hotspot)调用操作系统的  pthread_mutex_lock 和 pthread_cond_wait , 前者是保护后者和 counter 变量的互斥锁,保证只有一个线程操作 counter 变量和 condtion 上的等待队列

4. pthread_mutex_wait 依赖于 操作系统的 futex 机制,多个用户态的线程(Java线程,即Mutator)通过用户空间相同,物理页共享,共同争抢受写屏障增强,线程可见性强的资源变量。如果抢不到,需要用 futex_wait 系统调用,具体是委托内核查看该变量是否还是 futex_wait 的入参(争抢失败后的值),如果是,则让内核将自己从 runqueue(Linux下的就绪进程队列)摘下来,并且状态设为 TASK_INTERRUABLE,表示不需要继续执行,但是可以用信号唤醒,如果不是,返回用户空间,再次争抢

5. futex_wait 和 futex_wakeup 依赖 spin_lock保护桶bucket,其实保护bucket上的一整条链表

6. 操作系统的 down , up 依赖 spin_lock 保护等待队列和资源变量

 硬件层

预备知识:

写屏障

简化微机架构(Intel X86):

 

 

 无写屏障:

  1.假设有变量var

  

 

 

   2. CPU A(进程/线程A) 修改 var = 1

  

 

  3. CPU C(进程/线程C) 读取到 var = 3, 无法立刻得到 A 的修改

  

 

有写屏障(A,B,C任意CPU在修改完某个变量后均使用写屏障):

  上面的微机架构可以简化成:

  

 

  1.A修改var

  

 

  2.C立刻可见

       

 

使用写屏障类似:

  var = 1;

  write_fence_here(); // 写屏障

作用只是将 storeBuffer中的内容马上刷出到 自己的高速缓存中,因为高速缓存有MESI缓存一致性协议,所以其他CPU读取该变量,将是一直的新值(即使穿透缓存直接读取内存也是一样一致)

 

 

 操作系统层

 自旋锁和队列锁(一般互斥量是队列锁)

1.自旋锁简化:

    while (true) {
            if (compareAndSet(期望的旧值, 新值)) {
                return;
            }
        }

自旋锁在Linux中写作 spin_lock ,spin 本身有“连轴转”的意思。自旋锁的本质是获取不到资源就一直空转。

compareAndSet : 类似下面代码,但是被包装成 一条硬件指令,所以是原子的,在他执行的中间,不能有别的CPU插手这个内存的操作。

并且CAS要么全部完成,要么不执行,不能只执行一半,因为他是一条锁了总线或缓存行的硬件指令。在SMP条件下,如果不锁总线或缓存行,指令也不是原子的,比如ADD(read-write-read),只有微操作是原子的。

比如将某个值打入某个寄存器中(write)。

    boolean compareAndSet (期望的旧值, 新值) {
        if (变量值 == 期望的旧值) {
             变量 = 新值;
             return true;
        }
        return false;
    }

 

2. 队列锁简化:

addToQueue: 将线程/进程的TCB/PCB(在linux是task_struct),放入等待队列,当持有资源的线程释放资源的时候会唤醒等待队列中线程(PCB/TCP就是代表进程/线程的结构)。

          并且将进程/线程的 状态设为非运行状态(linux中一般使用TASK_INTERRUPTABLE), 并从就绪队列上摘下来(Linux上是runqueue)

schedule :当前线程已设置为非运行状态,所以会选择其他线程占用CPU, 当前线程在此点睡眠

   while (true) {
        if (!compareAndSet(期望旧值,新值)) { // 尝试获取资源,如:compareAndSet(原资源数,原资源数 - 1)
            addToQueue(当前线程PCB/TCB); // 获取不到就进入等待队列
            schedule();// 睡眠,让出CPU
        }
    }

 

为什么说互斥量(队列锁)依赖自旋锁?

  假设有以下情况:(互斥量对应资源初始值=1)

 

 

 如此一来,明明有资源,但是线程B却无法被唤醒。

   究其原因,是因为B的 检测资源-挂入等待队列-睡眠 这三个阶段,不是原子的。线程A 可以修改资源,让资源变成1。

 线程A对资源的操作插入到了线程B的操作之中,使得B的操作集合中语句前后所处的状态不一致,即非原子的,受干扰的(区别于事物原子性)。

 

   可以使用自旋锁保护 资源,在读取资源时,其他线程不能修改资源,那么释放操作就会被放到睡眠之后:

 

 

 

 

 

 

 

   为何可以使用自旋锁? 因为自旋锁不涉及队列,如果线程无法获取自旋锁,就在CPU 上空转,直到获取为止,不需要队列去存储他们,所以不会出现多个线程修改一个队列的情况。

也不会睡眠,所以也不会出现因为睡眠而错过资源的情况,像上二张图就是错过资源的情况,自选锁一直都在争抢。

  但是自旋锁的局限性也很大,空转,无意义的CPU时间被浪费。所以只有竞争不是很激烈,以及占用锁时间不长的情况,才使用自旋锁。

  这里的对队列操作,只是简单地读取一下变量,和在链表上挂一个节点,很快。

  在Linux(3.0.7)下的实现:

  up 操作是释放互斥量资源,down 操作是获取互斥量资源

    

 

 

 

futex(fast user mutex):之所以称为 user mutex,是因为多个用户态线程通过一块共享内存存储代表资源的变量,多个用户态线程对这个资源的操作是原子性的,这是在用户态的操作。

当用户线程发现自己争抢不到资源,才委托系统调用帮自己检查一下这个变量还是不是刚才读到的变量,如果是就当前线程休眠,所以是在用户态判断是否可以获取资源,不行再使用系统调用陷入内核态。比如说,我有一块内存页,被A,B两个线程共享,这个内存页里有个变量 var ,表示资源的个数,一开始是1。线程A和B都是通过CAS型的硬件指令去设置这个资源,即操作是原子性的。假如一开始A,CAS 抢夺成功,资源var 变成 0。资源B 直接通过自己的页面映射表去到这个共享的物理页,读取一下,发现是0,那么当前表示无资源可用。B将会使用系统调用,委托操作系统检查,这个资源是不是还是0,如果是就将自己休眠,否则B退出内核态回到用户态。为什么要委托操作系统再检查一次呢?因为有可能A已经释放资源了,B只要再CAS一次就能获得资源。

 

 

dotnet cli 5.0 新特性——dotnet tool search

 

 

futex 机制的实现比较简单,基于散列表:

每一个futex_key代表一个共享变量,即资源。

每一个节点包裹着 futex_key

每一个futex_bucket代表一个hash桶,也就是hash表中的某个位置

一个 futex_bucket 的链表中,有不同节点,说明有不同资源。比如说,“萤石” 是一种资源,“红石”也是一种资源,他们的数量所代表的变量(地址)的节点会存在于下图的同一个链表上

每个bucket都有一个 锁 可以被自旋锁 锁定,锁的单位是 一个 bucket上的链表,所以当一种资源需要加锁,会锁到链表上的其他资源。

设计者这么做其实并不过分,因为一个桶中的链表长度并不是很长,而且spin_lock是短时间锁,将锁粒度控制在整个散列表一个锁和每个节点一个锁之间,是对空间和时间的权衡。

 

 

futex在 线程处于内核态 ,读取资源 之前,会用 spin_lock 锁住 bucket,读取资源后发现没有资源会把自己挂入等待队列,然后释放spin_lock 。

持有资源的线程在唤醒等待队列中线程之前,同样要用 spin_lock 锁住同样位置的 bucket。

下图是 futex 的互斥机制,可能会有疑问:获取资源不用算进去吗?

这和程序顺序有关,释放资源肯定在唤醒之前的,这是必须遵循的,因为释放完资源才会去唤醒进程去争夺

那么唤醒等待队列这个操作可能在 被自旋锁保护区域的上面或者下面。

如果在上面,那么资源在唤醒之前就释放了,保护区里肯定可以得到资源,免于睡眠。

如果在下面,那么无论资源在唤醒之前的哪个位置,就算是在保护区里也好,只要是释放了就行。因为唤醒操作在保护区之后,而保护区里,要休眠进程已经挂到等待队列。

所以唤醒操作必能唤醒要休眠进程,因为他在 入队操作之后,他能找到那些休眠的进程,从而唤醒他们。

 

再向上一层看, pthread_mutex_wait 和 pthread_cond_wait,这两个函数是 Hotspot 实现 park 函数依赖的操作系统层面接口。而park函数是 LockSupport.park 方法的本地方法实现。

其中 pthread_cond_wait 是把 Java线程(java应用线程,即Mutator)放入到一个等待队列,这个队列称为条件队列。对应LockSupport.park 方法。

还有一个与之对应的解锁方法,pthread_cond_signal ,是唤醒这个队列上的线程。那么怎么保证对这个等待队列的操作是互斥的呢?如果不互斥,就可能发生下面这钟典型的写覆盖并发问题:

 

 

依赖的是 pthread_mutex_lock, 要操作队列之前先获取互斥量,操作完释放互斥量

pthread_mutex_lock(&mutex);
pthread_cond_wait(&queue);
pthread_mutex_unlock(&mutex);

pthread_mutex_lock 依赖的是上面所说的,futex, 所以 pthread_mutex_lock 就是上面说的,先在用户态读取资源,如果没资源了,就调用 SYS futex 系统调用

 

 

jvm(hotspot)层

 

到这里,操作系统和java层面差不多要连起来了,我们再通过LockSupport向上走。

在 调用LockSupport.unpark 之后调用LockSupport.park 的话,线程不会休眠。这个点很重要,没有这个点 ,JUC中的AQS无法正常工作。

伪代码:xchg相比xcmpchg不会比较,而是直接原子设置相应内存单元的值。

park () {
        // 之前有资源,直接返回,并且把资源消耗掉
        if (xchg(&counter ,1, 0) == 1) {
            return;
        }
        // 准备操作 票据和队列
        pthread_mutex_lock();
        // 可能之前 获取 mutex 的线程给予了 资源
        // 必须要有这一句,否则可能错过释放了的资源,永远无法被唤醒
        if (counter == 1) {
            counter = 0;
            pthread_mutex_unlock();
            return;
        }
        pthread_cond_wait();
        // 这句为什么在 pthread_cond_wait 之后呢?
        // 因为这里是线程被唤醒之后的地方,其他线程给了一个资源,当前线程才被唤醒
        // 既然被唤醒了,就要去消耗这个资源,这样一唤醒(资源+1),一睡眠(资源-1)。
        // 扯平之后就是当前线程的 继续运行状态
        counter = 0;
        pthread_mutex_unlock();
    }

    unpark () {
        pthread_mutex_lock();
        counter = 1;
        writeBarrierHere();
        pthread_cond_signal();
        pthread_mutex_unlock();
    }

回到刚才的问题:为什么unpark 之后 park 不会休眠在 AQS 中起到关键作用?

 

java层

 

假设线程A是已经获取资源,要释放资源的线程

B是尝试获取资源的线程

 

 

 

 

线程A对应下面两处代码: 

 

线程B对应下面两处代码。

 

 

 

 

 极端一段假设:当线程B执行到下面的绿色处,A执行完成他 release 方法中的两处代码

 

 

 

虽然A释放了资源,但是B还是判断要休眠,于是调用LockSupport.park。于是虽然有资源但是B还是调用了park

B真的就这样休眠了吗?不会,奥秘在unparkSuccessor。

 

他会unpark 头节点的后继。B在调用 acquireQueued之前已经在队列中,所以B的线程会被调用 LockSupport.unpark(B);

 

于是B在下次调用 LockSupport.park 的时候不会休眠,可以接着争抢资源!

 

最后,JUC中的绝大多是同步工具,如Semaphore 和 CountDownLatch 都是依赖AQS的。整个JAVA应用层面到硬件原理层面的同步体系至此介绍完毕。

 

 

 

 

 

 

 

 

 

 

 

 

  

 

 

 

 

  

 

Elasticsearch从入门到放弃:浅谈算分

人已赞赏
经验教程

linux GPU上多个buffer间的同步之ww_mutex、dma_fence的使用 笔记

2021-1-26 21:50:00

经验教程

HTML5与CSS3知识点总结

2021-1-26 23:12:00

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索