Java小白系列(十):CLH
一、前言
本篇内容是为之后的内容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的变体结构,该结构是:
- 一个 FIFO(first-in-first-out)队列;
- 新的等待获取锁的线程先加入队尾(tail);
- 假如队列是空,则第一个新加入的节点立即取得锁;
- 新加入的线程本地自旋前一个节点的状态(如 C 不断自旋获取 B 的状态);
- (当A释放锁时,B成为第一个节点),头节点并不能保证能够取得锁,只是有优先权,假如获取失败,则重新变为等待状态;
这里的内容,我们在分析《小白三,synchronized》时,谈到过 ContentionList、EntryList,AQS的变体CLH和它们一样,没有差别。
CLH.png
三、公平与非公平
『针对第5点进行解释』
CLH是公平队列,既然是公平队列,那么当『A』释放锁时,『B』成为首节点,应该是可以取得锁的,但为什么还会失败,而重新变成等待状态呢?假如首节点还获取不到锁,那CLH不就不公平了么?
- 『B』节点与新来的线程竞争获取锁,新的线程竞争成功,『B』失败,因而『B』重置为自旋等待状态;
- 新的线程不竞争,直接加入队尾,那么,此时『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