Java并发数据结构的基础

逃离我推掉我的手 2022-04-05 18:42 168阅读 0赞

Java的并发能力的基础是Park（）和unPark（）方法、易失性变量、同步化、CAS操作和AQS队列。进入这些知识点并不容易。本节中提到的与锁相关的知识并不特别完整，还有许多细节我还没有完全理解，因此让我们稍后讨论关于锁的更多细节。

## 线程阻塞原语 ##

Java的线程阻塞和唤醒是通过不安全的类公园和不停机方法实现的。

![990913-20181213142003964-1181607441.png][]

这些方法都是本机方法，是C语言实现的核心功能。Park意味着停车，它允许当前运行的线程线程。currentThread().。unpark意味着卸载停车位并唤醒指定的线程。在底部，这两个方法是使用操作系统提供的信号量机制实现的。具体的实现过程应该深入研究C代码，这里暂时不去具体分析。Park方法的两个参数用于控制睡眠持续时间。第一个参数isAbsolute指示第二个参数是以毫秒为单位的绝对时间还是相对时间。

因为读取锁需要使用CAS操作来修改底层锁的总读取计数值，所以可以获得成功的读取锁。CAS操作获取读锁的失败仅仅意味着CAS操作在读锁之间存在竞争，并不意味着锁被其他人占用，此时无法获得。再尝试几次肯定会成功锁定，这就是自旋发生的原因。类似地，当释放读锁时，存在CAS操作的循环重试过程。

线程从启动开始一直运行，除了操作系统的任务调度策略，该策略仅在调用park时暂停。锁可以暂停线程的秘密正是因为锁调用底部的park方法。

protected final boolean tryReleaseShared(int unused) {
       ...
       for (;;) {
           int c = getState();
           int nextc = c - SHARED_UNIT;
           if (compareAndSetState(c, nextc)) {
             return nextc == 0;
           }
       }
       ...
    }

### parkBlocker ###

当线程被unpark唤醒时，此属性设置为空。不安全的。Park和unpark不能帮助我们设置parkBlocker属性。负责管理此属性的工具类是Lock.，它简单地包装Unsafe两个方法。

![990913-20181213142127203-622253568.png][]

线程对象有一个重要的属性parkBlocker，它存储当前线程停靠的用途。这就像在停车场里停很多车。这些业主来参加拍卖会，当他们拍下他们想要的照片时，就会开车离开。所以parkBlocker指的是拍卖。它是一系列冲突线程的管理员协调器，它控制哪些线程应该休眠和唤醒。

![990913-20181213142208266-2030469783.png][]

Java的锁数据结构通过调用锁支持来实现休眠和唤醒。线程对象中的parkBlocker字段的值是我们将在下面讨论的队列管理器。

## 排队管理器 ##

当锁不成功时，当前线程将自己放在等待列表的末尾，然后调用Lock.。停车睡觉。当其他线程解锁时，它们从列表头获取节点并调用Lock.。打开方舟叫醒它。

![990913-20181213142305401-1439458082.png][]

当多个线程竞争同一个锁时，必须有排队机制来串联无法将锁组合在一起的线程。当释放锁时，锁管理器选择合适的线程来占用新释放的锁。每个锁都有一个队列管理器，在其中维护等待的线程队列。ReentrantLock中的队列管理器是AbstractQueued Synchronizer。ReentrantLock中的等待队列是双向列表结构。列表中每个节点的结构如下。

![图片][1]

JDK 锁管理器的实现者是 Douglas S. Lea，Java 并发包几乎全是他单枪匹马写出来的，在算法的世界里越是精巧的东西越是适合一个人来做。

![图片][1 1]

锁管理器仅以通用双向列表的形式维护队列。数据结构很简单，但是仔细维护是相当复杂的，因为它需要仔细考虑多线程并发性，并且每行代码都非常小心地编写。

AbstractQueuedSynchronizer 类是一个抽象类，它是所有锁队列管理器的父类，由JDK中各种形式的锁队列管理器继承。它是Java并发世界的核心基石。比如 ReentrantLock、ReadWriteLock、CountDownLatch、Semaphone、ThreadPoolExecutor 内部的队列管理器都是它的子类。这个抽象类公开了一些抽象方法，每个锁都需要定制给管理器。而 JDK 内置的所有并发数据结构都是在这些锁的保护下完成的，它是JDK 多线程高楼大厦的地基。

后面我们将 AbstractQueuedSynchronizer 简写成 AQS。我必须提醒各位读者，AQS 太复杂了，如果在理解它的路上遇到了挫折，这很正常。目前市场上并不存在一本可以轻松理解 AQS 的书籍，能够吃透 AQS 的人太少太少，我自己也不算。

## 公平锁与非公平锁 ##

也许你会问，如果锁处于空闲状态，那么它如何能够具有排队线程？假设当前持有锁的线程刚刚释放了锁，并且它唤醒了等待队列中的第一个节点线程。此时，唤醒的线程只是从park方法返回，然后尝试锁定。返回锁和锁之间的状态是锁的空闲状态，非常短，可能是其他线程也在短时间内试图添加。

公平的锁确保请求和获取的顺序。如果在某个点上锁处于空闲状态，则线程将尝试锁定。公平锁还必须检查其他线程当前是否排队，但不能直接排队。想象一下，在肯德基排队买汉堡包。

其次还有一点需要注意，执行了 Lock.park 方法的线程自我休眠后，并不是非要等到其它线程 unpark 了自己才会醒来，它可能随时会以某种未知的原因醒来。我们看源码注释，park 返回的原因有四种

1.  其它线程 unpark 了当前线程
2.  时间到了自然醒（park 有时间参数）
3.  其它线程 interrupt 了当前线程
4.  其它未知原因导致的「假醒」

文档没有指定未知引起错误唤醒的原因，而是显示当park方法返回时，并不意味着锁是空闲的。在尝试检索锁失败后，被唤醒的线程将再次停驻自身。因此，锁定过程需要在循环中写入，并且可以在成功获得锁定之前进行多次尝试。

在计算机世界中，不公平的锁比公平的锁更有效，因此Java默认锁使用不公平的锁。但在现实世界中，不公平的锁似乎效率较低。例如，如果你能在肯德基一直排队，你可以想象场景会很混乱。为什么计算机世界和现实世界有区别？可能是因为在计算机世界中，线程队列不会导致其他线程抱怨。

![990913-20181213142632422-317034385.png][]

## 共享锁与排他锁 ##

ReadWriteLock中的读锁不是独占锁。它允许多个线程同时持有读锁。这是一个共享锁。Node类中的nextWaiter字段区分共享锁和独占锁。ReentrantLock的锁是独占锁，一个线程持有它们，所有其他线程必须等待。

![990913-20181213142718006-604904087.png][]

那么为什么这个字段没有被命名为模型或类型或共享呢？这是因为NextWaiter在其他场景中具有不同的用途。它作为C语言联合类型的字段，但Java语言没有联合类型。

## 条件变量 ##

至于条件变量，需要提出的第一个问题是为什么需要条件变量。锁不够？考虑以下伪代码在满足条件时执行某些操作

void doSomething() {
       locker.lock();
       while(!condition_is_true()) {  // 先看能不能搞事
         locker.unlock();  // 搞不了就歇会再看看能不能搞
         sleep(1);
         locker.lock(); // 搞事需要加锁，判断能不能搞事也需要加锁
       }
       justdoit();  // 搞事
       locker.unlock();
     }

当条件不满足时，它将在循环中重试（其他线程将通过锁定来修改条件），但是需要间隔休眠，否则由于空闲，CPU将急剧上升。这里有个问题，那就是睡眠时间不能控制。如果间隔太长，则会降低整体效率，甚至错过机会（条件立即得到满足并立即复位）。如果间隔太短，将导致CPU再次空闲。利用条件变量，这个问题可以得到解决。

![990913-20181213142809545-1218271554.png][]

waiit()方法将阻塞cond条件变量，直到被另一个线程cond调用。信号()或cond..All()方法。当waiit()块时，当前线程持有的锁将自动释放。当await()被唤醒时，它将再次尝试保持锁（并且可能需要排队），并且await()方法在锁成功之前不会返回。

![图片][1 2]

waiit()方法必须立即释放锁，否则其他线程不能修改临界状态，.\_is\_true()返回的结果也不会改变。这就是为什么条件变量必须由锁对象创建，锁对象需要保存对锁对象的引用，以便在信号唤醒后释放和重新锁定锁。创建条件变量的锁必须是独占锁。如果通过await()方法释放共享锁，则不能保证关键区域的状态可以由其他线程修改。唯一可以修改关键区域状态的是独占锁。这就是为什么ReadWriteLock的新条件方法。ReadLock类的定义如下

阻塞在条件变量上的线程可以有多个，这些阻塞线程会被串联成一个条件等待队列。当 signalAll() 被调用时，会唤醒所有的阻塞线程，让所有的阻塞线程重新开始争抢锁。如果调用的是 signal() 只会唤醒队列头部的线程，这样可以避免「惊群问题」。

![990913-20181213142903001-2026086248.png][]

利用条件变量，解决了睡眠不易控制的问题。当满足条件时，将调用.()或.All()方法，并且可以立即唤醒阻塞的线程，几乎没有延迟。

## ReentrantLock 加锁过程 ##

下面我们精细分析加锁过程，深入理解锁逻辑控制。我必须肯定 Dough Lea 的代码写成下面这样的极简形式，阅读起来还是挺难以理解的。

![990913-20181213143041822-90330240.png][]

如果判决书的取得分为三部分。tryAcquire方法指示当前线程试图锁定。如果锁不成功，则需要排队。此时，将调用addWaiter方法来对当前线程进行排队。然后调用.dQueued方法启动停车、唤醒和重试锁的过程。如果锁失败，Park的循环将重试锁。获取方法在锁成功之前不会返回。

如果在循环重试锁定期间被其他线程中断，则获取的Queued方法返回true。此时，线程需要调用selfInter.()方法来设置当前线程的中断标识符位。

[990913-20181213142003964-1181607441.png]: /images/20220405/80ff9eac033a47f2ac02b125e61ccb24.png
[990913-20181213142127203-622253568.png]: /images/20220405/6a9482e7ac9f4c4e840edc72d7e1c4a6.png
[990913-20181213142208266-2030469783.png]: /images/20220405/239bce8bffbd474093d560626035a212.png
[990913-20181213142305401-1439458082.png]: /images/20220405/0addb0abb6e04017ba5783a25276a368.png
[1]: https://user-gold-cdn.xitu.io/2018/12/10/16797297ad18159b?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[1 1]: https://user-gold-cdn.xitu.io/2018/12/10/16797297e4e415ff?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[990913-20181213142632422-317034385.png]: /images/20220405/3db7e8cb2e344dbc985248bbd6ca410e.png
[990913-20181213142718006-604904087.png]: /images/20220405/d2a17b51869c45139dfb6681747ed7e5.png
[990913-20181213142809545-1218271554.png]: /images/20220405/7c4430f668d04f43851293e89d92d8b8.png
[1 2]: https://user-gold-cdn.xitu.io/2018/12/10/16797297cc69b4b4?imageView2/0/w/1280/h/960/format/webp/ignore-error/1
[990913-20181213142903001-2026086248.png]: /images/20220405/2fa8228d91fa4c1d9d9042336112f69d.png
[990913-20181213143041822-90330240.png]: /images/20220405/0a4b1aa4ecbf471a82d3c67eed45ffc4.png