¶AQS 队列同步器(二)

¶概述：

​ 在《AQS队列同步器(一)》中对AQS的概念和基本属性了解了一下，对独占式和共享模式竞争释放锁的过程进行了了解。通过继承AQS类，JDK实现了一些很好的共享或者独占式同步工具类，包括 ReentrantLock,CountDownLatch,Semaphore,CyclicBarrier等，接下来通过它们各自的同步器实现过程，了解AQS的实际运用。

¶辅助类：

• 描述： 在了解AQS的方法时，有两个类出现的机率很频繁—LockSupport 和 Unsafe，LockSupport 类的park和unpark方法用来在竞争锁失败时阻塞线程和释放锁时唤醒线程；Unsafe类提供了一系列基于底层实现的CAS操作，用来对同步器的队列头尾节点，节点状态，锁状态进行设置。在了解具体同步工具类实现之前，先了解一下这两个类。

• LockSupport :

  • 类说明：摘自 JDK1.8.0_191版本

    • 用来创建锁和其他同步工具类的阻塞原语—操作系统中原始的不可分割的操作单元

    • 该类与使用它的每一个线程都关联一个许可，当这个许可可用时，park方法会立刻返回，在线程中消费这个许可，否则会阻塞线程；相对的，unpark方法会释放许可，让许可变成可用状态。

    • 很容易联想到 Semaphore 同步工具类，初始化一组许可，每次线程执行之前先请求许可，许可用完就阻塞后来线程，直到前面的线程释放许可。

    • park和unpark方法提供了高效的阻塞和释放线程的方法，由于许可的存在，同时进行park和unpark并不会导致死锁。park方法响应中断而且也提供了超时的重载方法，不过也有可能在任意时刻“毫无原因”地返回，所有在返回之前必须在循环中重复检查条件状态是否满足。在这个场景下，park方法表现得像优化版本“忙等待”，没有太多的自旋时间，但是必须要和unpark方法一起使用才会生效。

    • park和unpark的系列方法，是为构建高性能并发模块服务的，例如 park方法在这种结构下使用：

      while(!process()){ LockSupport.park(this) };

    • 只允许一个线程获取一个许可，其他任何非标准用法可能回导致非预期的结果。

  • 方法说明：

    • unpark(): 释放许可，唤醒线程

      • 代码：

        1 2 3 4 5 6 7

        //取消线程的阻塞状态，使许可变成可用 //但是当线程没有启动时，可能不会生效 public static void unpark(Thread thread) { if (thread != null) //unsafe类的unpark方法 UNSAFE.unpark(thread); }

        • 逻辑很少，判断线程非空，调用 UNSAFE.unpark(thread) 方法

        • //TODO

¶《JAVA 并发编程实战学习笔记 二》

¶概述

• 《学习笔记一》从线程安全的定义，常见的线程安全错误，导致错误发生的原因，安全的对象发布，不可变对象，同步容器类等描述了并发编程中问题发生的原因，场景，解决方式和一些良好实践以及工具类(关于同步工具类的详解部分可以在《AQS队列同步器中(二)》看到)，也是并发编程实战的第一部分，现在学习第二部分结构化并发应用程序的内容。

¶任务执行：

• 概述：在正常负载的情况下，服务器应用程序应该表现出良好的吞吐量和快速的响应性–能够快速地处理很多的任务，从应用程序提供方来说希望能够支持更多的用户，节约成本；用户则需要更好的使用体验。而且当程序负载过高时，正确的表现不应该是直接失败，而是降低处理任务的速率。

• 串行任务：书中列举了一个简单串行WEB服务器例子，以一次用户请求作为任务边界：

  1 2 3 4 5 6 7 8 9

  class SingleThreadWebServer{ public static void main(String[] args)throws IOException{ ServerSocket socket = new ServerSocket(80); while(true){ Socket connection = socket.accept(); handleRequest(connection); } } }

  • 它的问题在于，当接受了一个用户请求之后，使用当前线程去处理这个任务，在任务处理完成之前如果还有其他线程请求这个服务器，只能等待当前的任务处理完成。在只使用了一小部分系统资源的情况下，却不能同时处理多个独立任务，在性能和效率来说是比较差的。

¶AQS 队列同步器(一)

¶概述：

​ 接触并发编程的同步机制时，会了解到一个实现的比较好的同步器，例如 原子类(AtomicInteger)，信号量(Semaphore)，CountDownLatch等，他们都是基于AQS构建的同步器，用来协调多线程对于共享资源的访问策略，再不同的硬件水准的情况下对并发吞吐量性能做了极大的提升，还保证的线程安全性。因此了解AQS对于更好地理解这些优秀同步器的设计有很大帮助。

¶AQS抽象类简介：

• 类简介(摘自 JDK 1.8 源代码中对此类的介绍)：

• 基于FIFO的等待队列提供了一个用来实现阻塞锁和相关同步器的框架，这个类设计为实现各种同步器的基础，通过使用一个原子的 AtomicInteger 变量 state 来代表当前锁的状态。子类必须重写 protected 类型的方法，用来改变这个状态，还需要定义当调用请求锁和释放锁的方法时，这个state字段的含义。

• 通过提供这些保证，AQS的其他方法才能具备队列性和同步性结构。子类也可以增加其他的代表状态的字段，但只有在通过 getState,SetState,CompareAndSetState这些方法原子更新状态值，才是维持了同步的概念。

• 子类需要通过自己的内部类继承 AQS 类的属性来构建同步器，AQS 本身没有实现任何同步接口，相应地它提供了一些将锁和同步器关联地公共方法用以被实现。

• AQS 类支持独占(exclusive) 和 共享(shared) 模式地锁获取。独占锁模式下，当锁被占有时，其他调用请求锁的线程会失败；共享锁模式下，多个线程请求获取锁可能都会成功。在共享锁模式中，当一个线程获取锁成功，下一个线程是否获取锁取决于它本身。在不同锁模式下处于等待状态的线程节点，位于同一个FIFO队列，因此共享模式的锁获取并不意味着一定成功。AQS 的子类可以自行决定是否需要支持独占或者共享模式，或者两者都支持，例如读写锁(ReadWriteLock)和可重入锁(ReentrantLock)。当子类只支持一种锁模式时，不需要实现另一种锁模式的相关方法。

• AQS 定义了一个嵌套类 ConditionObject 可以作为 Condition 对象被支持独占锁模式的子类实现，Condition 对象是条件对象，用来关联锁以决定是否能够去请求获取锁。ConditionObject 也是独占模式下方法 isHeldExclusively,release,getState,acquire等方法正确语义的实现一部分。如果这些方法的约束条件不存在，就不要使用ConditionObject 对象。ConditionObject 对象的语义也取决的于AQS的子类实现。

• AQS 为内部的队列提供了检查和监视队列状态的代码，类似于ConditionObject 方法。这些方法可以根据同步器的子类同步器结构实现需要导出到类中。

• AQS 类的序列化只会保存底层的原子状态变量值，所以反序列化的AQS会包含一个空的队列。通常需要序列化的子类需要定义或者实现一个readObject 方法保存把这些信息作为初始状态进行反序列化。

• 以上这些比较简洁地说明了AQS的正确继承和实现方式以及一些使用时的注意点，接下来是一些方法的使用方式。

• 将AQS 作为同步器实现基础使用时，需要自定义这些方法的实现 :tryAcquire(独占式获取锁)，tryRelease(独占式释放锁)，tryAcquireShared(共享式获取锁)，tryReleaseShared(共享式释放锁)，isHeldExclusively(是否独占式持有锁)，通过 getState() 方法查询锁状态，setState() 和 conpareAndSatState()等方法来设置锁状态。

• 上述需要自定义实现的方法都抛出了 UnsupportedOperationException ，上述方法的实现大体上需要简短且非阻塞，实现这些方法是使用AQS的唯一途径。

• AQS还继承了AbstractOwnableSynchronizer 抽象类，用来设置当前拥有锁的线程对象，通过它的方法实现可以帮助用户监控和判断哪个线程持有锁。

• 虽然AQS是基于内部的FIFO队列实现的，它并不会自动地执行队列地先进先出规则，独占式的同步发生在获取锁的时候。因为在非公平的同步器中，检查能否获取锁发生在等待线程进入队列之前，所以当一个新的线程请求锁时，它可能会请求成功而不会进入队列，因此队列中的其他线程需要继续阻塞或等待。

• 如果实现了一个公平锁，所有的线程都会先进入等待队列，然后按照某种排序规则，依次去请求锁。在公平锁的实现中，如果 hshQueuedPredecessors方法返回 true ,可以让 tryAcquire方法立刻返回 false 表示获取锁失败。

• 默认的线程调度算法虽然具备相当的吞吐量和扩展性，但却不保证线程公平性和避免线程饥饿，排在队列前面的线程总是排在后面的线程更早地竞争锁，而且每次都是公平地和进入线程竞争锁。一般，获取锁的方法没有自旋；通常情况下，在多个线程处于竞争状态时， tryAcquire方法会被多次调用，直到其他线程阻塞。当锁被短暂持有时，这会带来比自旋更好的收益，不会白白耗费CPU资源。

• AQS 提供了高效且有扩展性的同步实现方式，当它不能满足的你要求时，你可以i通过一种相对底层一点的方式，使用原子类，自定义队列和阻塞方法等构建自己的同步器。

¶《JAVA 并发编程实战》学习笔记(一)

¶一.概述

​ 在JAVA基础中比较重要的一些知识体系有：NIO，同步容器和并发容器，并发编程等，学习《JAVA 并发编程实战》可以了解到关于线程安全，对象发布，多线程编程，并发模型，线程池构建原理以及同步器构建等相关的内容。

¶二.基本概念

• 线程安全：

  • 理解线程安全性，需要先明白正确性的概念。程序在按照一定的逻辑组织起来之后，在单线程环境下的运行结果如预期一样，即"所见即所知",那就可以称之为单线程下的正确性。

  • 在此基础上定义线程安全性：当多个类访问某个类时，这个类始终能表现出如单线程下一样的正确行为–逻辑没有被破坏–，那么就称这个类是线程安全的。

  • 无状态的对象是线程安全的：对象无状态意味着没有可以被共享处理的信息，例如书中的例子：一个无状态的Servlet,它的 service 方法使用的局部变量并不会逸出到当前线程之外的地方，因此也就不存在竞争的可能性，所以它是线程安全的。

¶写一个链表

¶一.概述

​ 前面已经了解了 Collection 中一些常用数据结构的实现，现在实现简单版本的链表系列结构，包括单链表，双链表，循环链表，以此为基础构建不同类型的队列数据结构。

¶二.单链表

• 单链表的数据结构特点是元素存储有序，增删效率高，存储可以物理不连续

• 实现的基础可以是具备 next 的Node 结构，Node 是一个自包含的结构

  ---

  Node:

  ​ 用 java 实现一个简单的 Node 类 ：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  //实现比较简单 public class Node<E>{ //代表Node值的E E e; //代表下一个节点的next Node next; //无参构造 public Node(){} //不指定next节点的构造 public Node(E e){ this.e=e; this.next=null; } //指定next节点的构造 public Node(E e,Node next){ this.e=e; this.next=next; } }

  • 主要需要实现值存储和持有后续节点引用
  • 这里提供了三个构造函数，其实不指定使用默认构造也可以

¶Map

¶一.概述

​ 在JAVA的常用数据结构中除了Collection族，还有Map—映射，在Map族中，顶层的Map接口规定了子类的基本行为，先看一下整体的类结构图：

​

• 仔细看的话，会发现 Map,HashMap,LinkedHashMap 之间的结构和 Set,HashSet,LinkedHashSet 比较类似，都是由一个类继承基本接口和实现骨架的抽象类，然后另一个Linked类直接继承Hash类实现顺序存储的功能
• HashMap 的 put(K,V) 方法有两个版本：一个是以默认的链表结构存储时调用的 putVal(K,V) 方法，会构造新的 Node 节点插入 ； 另一个是内部类 TreeNode 的 putTreeVal(K,V) ，会构造新的 TreeNode 节点插入红黑树结构中
• Map 存储的是键值对，也就是它的内部类:Entry,同时从Map 的 keySet() 方法返回 key 值的 Set 集合和其他基于 key 进行的操作来看，Map 是不允许键重复的，在 Map 中键是作为唯一索引一样存在的

¶Collection(三)

¶一.概述

• 接下来了解一下 Collection 的重要实现之一Set 接口，可能听得最多的Set 的实现特点就是不存储重复元素和元素存取无序，接下来会解释那这些是如何实现的.

¶二. Set: 无序集合

• 先看一下继承关系图

  

• 和List 的实现最大的区别是没有新增任何自定义的方法，都是直接从 Collection 接口继承的方法也看不出它的一些特点

• 现在从最常用的实现 HashSet 开始了解它的实现细节

  ---

¶三.HashSet: 存取无序，不可存储重复元素的集合

• 先看一下继承图

  

• HashSet 实现了 Set 接口，继承了 AbstractSet抽象类

• 从属性可以猜测一下 HashSet 实现内部元素存储的容器会不会是个 HashMap 映射？

¶Collection(二)

¶一. 概述

• 在 Collection(一) 中简单地从 Collection的数据结构和主要实现接口描述了它们各自定义的的特点，以及能够实现什么样的集合数据结构，接下来将按照 List<E>,Set<E>,Queue<E> 这样的顺序来了解它们以及各自实现类的特点，包括一些重要方法的源码理解分析等。

  ---

¶二 、List: 顺序集合，支持扩容操作

​

• 继承 Collection 结构，增加了支持下标的增删方法,意味着它的实现类既支持直接通过指定元素进行添加删除，也支持下标位置添加删除
• 而通过元素确定下标位置的方法，在接触过的更基本的数据结构中，可以想到数组也具备这个功能
• 它的迭代器是自己的内部类，继承了 Iterator 接口的 ListIterator

¶三. ArrayList: 可扩容的顺序泛型集合

• 先看一下继承图

  

  • 继承了 AbstractList 类并且实现 List 接口，抽象类提供的是容量检查，克隆，对象锁相关的方法，对象相关的方法从Object中继承而来，让ArrayList具备了线程安全编程的能力

¶Collection(一)

¶一. 简述

• 本文是关于 Java Collection 的一一些个人学习概括，先从 Collection 的类结构开始，了解 Collection 包结构设计等。

¶二. 类结构

• 先从整体的Collection UML 图看起:

​ 图 1. Collection 部分类图结构

• 由上图可以看出Collection 接口最主要的几个实现结构都比较类似:抽象类规定的继承自Collection的迭代和继承自Object的通用对象方法，再加上List,Set,Queue等各自数据结构的基本定义，组合成了ArrayList,LinkedList,HashSet,TreeSet这些常用的数据结构。

• 而且从 LinkedList 的设计实现来看，假设要扩充一个循环链表实现的List，只需要增加一个类似Dequeue的CycleQueue定义循环列表所必须的基本方法，再结合继承AbstractList的某个子类就能实现，具有很好的扩展性。

• 比较明显的一个特点是贯穿类结构全程的泛型参数和返回值，Collection接口的泛型设计使得它更具备了通用性，而且也为类型检查提供了遍历，尽可能地避免了不安全转型导致的错误。

• 上图中还可以看到一个直接继承HashSet并实现Set接口的LinkedHashSet,它本身除了构造都是继承过来的方法，实现了和基本的HashSet不同的有序LinkedHashSet,HashSet本身是使用HashMap<K,V>来存储数据的，关于这个会在后续的HashSet笔记中说明。