Java小白系列(十):CLH

作者 : 开心源码 本文共2524个字,预计阅读时间需要7分钟 发布时间: 2022-05-13 共282人阅读

一、前言

本篇内容是为之后的内容AQS打下基础,AQS又称 Abstract Queued Synchronizer ,即笼统队列同步器,Java中,基于 AQS 实现了很多著名的锁,如:重入锁(ReentrantLock)、读写锁(ReadWriteLock)、共享锁(CountDownLatch)若设置为1则等同于互斥锁,等。因而,为了深入分析AQS,我将重要的内容都拆解出来,从一个一个的知识点一一击破。

二、CLH

CLH(Craig,Landin and Hagersten)是三个人,共同发明了一个可扩展、高性能、公平且基于自旋锁的链表;链表中的每个线程只在本地自旋前一个节点的状态,即该节点(线程)不断自旋获取前一个节点的状态;每个节点都有一个状态(要么自旋,要么释放锁)。

在AQS中,用到的数据结构是 CLH 的变体:

      +-------+  prev  +-------+       +-------+ head |   A   | <----- |   B   | <---- |   C   |  tail      +-------+        +-------+       +-------+

上图是AQS中CLH的变体结构,该结构是:

  1. 一个 FIFO(first-in-first-out)队列;
  2. 新的等待获取锁的线程先加入队尾(tail);
  3. 假如队列是空,则第一个新加入的节点立即取得锁;
  4. 新加入的线程本地自旋前一个节点的状态(如 C 不断自旋获取 B 的状态);
  5. (当A释放锁时,B成为第一个节点),头节点并不能保证能够取得锁,只是有优先权,假如获取失败,则重新变为等待状态;

这里的内容,我们在分析《小白三,synchronized》时,谈到过 ContentionList、EntryList,AQS的变体CLH和它们一样,没有差别。

CLH.png

三、公平与非公平

『针对第5点进行解释』
CLH是公平队列,既然是公平队列,那么当『A』释放锁时,『B』成为首节点,应该是可以取得锁的,但为什么还会失败,而重新变成等待状态呢?假如首节点还获取不到锁,那CLH不就不公平了么?

\color{red}{当『A』释放锁时,『B』被唤醒,此时又来了新的想要获取锁的线程,则会有两种情况要考虑:}

  1. 『B』节点与新来的线程竞争获取锁,新的线程竞争成功,『B』失败,因而『B』重置为自旋等待状态;
  2. 新的线程不竞争,直接加入队尾,那么,此时『B』节点就能获取到锁;

因而,这里的公平与否,主要还是要看继承AQS的锁的实现方式:新来的竞争锁的线程,是先尝试竞争一次,还是直接加入队尾。

假如采用非公平模式,则新来的线程假如竞争成功,则直接成为 first 节点,插入在 head 与 first 节点之间,而原 first 节点排在新的 first 节点之后进入等待状态并自旋。

我们在后面分析那些继承 AQS 实现的锁时,有些锁就支持非公平方式,如 ReentrantLock。

四、CLH的结构

CLH看似是个链表,但实际上并不存在,CLH中的每个节点类型为 Node,Node 中有两个索引,分别是 prev 和 next 将所有的节点串起来;在 AQS 中也只有两个索引节点,分别是 head 和 tail ,分别指向队列的头和尾;并没有一个成员变量相似 LinkedList 来管理所有的节点。

public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable {             static final class Node {        // 共享模式        static final Node SHARED = new Node();        // 独占(排它)模式        static final Node EXCLUSIVE = null;        // 线程已被取消,当首节点释放锁后,        // 开始查找下一个 waitStatus < 0 的节点,        // 假如遇到已取消的线程,则移除        static final int CANCELLED =  1;        // 当前线程的后继线程需要被unpark(唤醒)        // 后继节点处于等待状态,当前节点(为-1)被取消或者者中断时会通知后继节点,        // 使后继节点的线程得以运行        static final int SIGNAL    = -1;        // 当前节点处于等待队列,节点线程等待在Condition上,        // 当其余线程对condition执行signall方法时,        // 等待队列转移到同步队列,加入到对同步状态的获取        static final int CONDITION = -2;        // 与共享模式相关,在共享模式中,该状态标识结点的线程处于可运行状态        static final int PROPAGATE = -3;        // 当前节点的状态,默认是 0         volatile int waitStatus;        volatile Node prev;        volatile Node next;        // 等待获取锁而自旋的线程        volatile Thread thread;                // Node既可以作为同步队列节点使用,也可以作为Condition的等待队列节点使用(将会在后面讲Condition时讲到)。        // 在作为同步队列节点时,nextWaiter可能有两个值:EXCLUSIVE、SHARED标识当前节点是独占模式还是共享模式;        // 在作为等待队列节点使用时,nextWaiter保存后继节点        Node nextWaiter;        final boolean isShared() {            return nextWaiter == SHARED;        }        final Node predecessor() throws NullPointerException {            Node p = prev;            if (p == null)                throw new NullPointerException();            else                return p;        }        Node() {    // Used to establish initial head or SHARED marker        }        Node(Thread thread, Node mode) {     // Used by addWaiter            this.nextWaiter = mode;            this.thread = thread;        }        Node(Thread thread, int waitStatus) { // Used by Condition            this.waitStatus = waitStatus;            this.thread = thread;        }    }}

我们可以看到,AQS 的 Node 结构不复杂,还算比较简单,下一篇将来开始讲解 AQS。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Java小白系列(十):CLH

发表回复