首页  思维导图  详情

004 - 同步容器类

2022-03-08 09:36:22   0  举报





AI智能生成

同步容器类,系统性总结

java

AQS

作者其他创作

大纲/内容

同步容器主要包括两类

本来就线程安全实现的容器

这类容器有Vector、Hashtable、Stack

这类容器的方法上都加了synchronized锁， 是线程安全的实现。

Vector、Hashtable、Stack这些容器，现在几乎都不在使用

因为这些容器在多线程环境下的效率不高。

由Collections.synchronizedxxx实现的非线程安全的容器

要不为啥要称Collections为集合工具类呢？

Collections会把这些容器类的状态封装起来， 并对每个同步方法进行同步，使得每次只有一个线程能够访问容器的状态。

同步容器将所有对容器状态的访问都串行化，以实现他们之间的线程安全性。

用Collections.synchronized会把它们封装起来编程线程安全的容器

其中每个synchronizedxx都是，相当于创建了一个静态内部类

汇总

举出两个例子

Collections.synchronizedList

Collections.synchronizedMap

可以通过Collections源码可以看出这些线程安全的实现

这些线程安全的实现

某些情况下需要额外的客户端加锁，来保证一些复合操作的安全性

虽然同步容器类都是线程安全的，但是在某些情况下需要额外的客户端加锁来保证一些复合操作的安全性

这些复合操作在没有客户端加锁的情况下是线程安全的，但是当多个线程并发修改容器时，可能会表现出意料之外的行为。

例如

如果线程A在包含这么多元素的基础上调用getVector方法， 会得到一个数值， getVector只是取 得该元素， 而并不是从vector中移除， removeVector方法是得到一个元素进行移除， 这段代码的不 安全因素就是， 因为线程的时间片是乱序的， 而且getVector和remove Vector并不会保证互斥， 所以 在removeVector方法把某个值比如6666移除后， vector中就不存在这个6666的元素， 此时 getVector方法取得6666， 就会抛出数组越界异常。

为什么是数组越界异常呢?可以看一下vector的源码

vector的源码

如果用图表示的话，则会是下面这样

所以，从系统的层面来看，上面这段代码也要保证线程安全性才可以，也就是在客户端加锁实现，

只要让复合操作使用一把锁，那么这些操作就和其他单独的操作一样都是原子性的。

如下面例子所示

也可以通过锁住.class来保证原子性操作， 也能达到同样的效果。

子主题

在调用size和get之间， Vector的长度可能会发生变化， 这种变化在对Vector进行排序时出现， 如下所示

子主题

这种迭代的操作正确性取决于运气， 即在调用size和get之间会修改Vector， 在单线程环境中， 这种 假设完全成立， 但是再有其他线程并发修改Vector时， 则可能会导致麻烦。

仍旧可以通过客户端加锁的方式来避免这种情况

子主题

这种方式为客户端的可靠性提供了保证，但是牺牲了伸缩性，而且这种在遍历过程中进行加锁，也不是我们所希望看到的。

什么是复合操作？

有两个及以上的方法组成的操作

比如最典型的就是，若没有则添加，用伪代码表示则是

若没有则添加

比如可以用来判断Map中是否有某个key， 如果没有则添加进Map中。

客户端加锁的讲解

fail-fast机制

诞生背景

客户端加锁，对可靠性提供了保证，但是牺牲了伸缩性，而且这种在遍历过程中进行加锁，不是希望看到的

什么是fail-fast/快速失效系统/快速失败机制

在系统设计中，快速失效系统一种可以立即报告任何可能表明故障的情况的系统。

快速失效系统通常设计用于停止正常操作，而不是试图继续可能存在缺陷的过程。

这种设计通常会在操作中的多个点检查系统的状态，因此可以及早检测到任何故障。

快速失败模块的职责是检测错误，然后让系统的下一个最高级别处理错误。

其实，这是一种理念，说白了就是在做系统设计的时候先考虑异常情况，一旦发生异常，直接停止并上报。

很多集合类都提供了一种fail-fast机制、集合类中的fail-fast

通常说的Java 中的fail-fast 机制，默认指的是Java 集合的一种错误检测机制。

当多个线程对部分集合进行结构上的改变的操作时，有可能会产生fail-fast 机制，

这个时候就会抛出ConcurrentModificationException（后文用CME 代替）。

因为大部分集合内部都是使用Iterator进行遍历， 在循环中使用同步锁的开销会很大，

 而Iterator的创建是轻量级的， 所以在集合内部如果有并发修改的操作， 集合会进行快速失败， 也就是fail-fast

抛出ConcurrentModificationException异常（CME）

代码中为什么抛出了CMException？

明明自己的代码并没有在多线程环境中执行，

为什么会抛出这种并发有关的异常呢？

这种情况在什么情况下才会抛出呢？

子主题

CMException，当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常。

当发现容器在迭代过程中被修改时， 会抛出ConcurrentModificationException异常

这种快速失败不是一种完备的处理机制，而只是意的捕获并发错误。

ConcurrentModificationException的注解

抛出的原则由两种

造成这种异常的原因是由于多个线程在让历集合的同时对集合类内部进行了修改， 这也就是fail-fast机制

该注解还声明了另外一种方式

这个问题也是很经典的一个问题

使用ArrayList来举例子

该段代码会发生异常， 因为在ArrayList内部， 有两个属性

 一个是modCount， ，

一个是expectedModCount

ArrayList在remove等对集合结构的元素造成数量上的操作会有 checkForComodification的判断， 如下所示， 这也是这段代码的错误原因。

checkForComodification的判断

ConcurrentModificationException异常复现

在Java 中， 如果在foreach 循环里对某些集合元素进行元素的remove/add 操作时，就会触发fail-fast 机制，进而抛出CMException。

如以下代码：

以上代码，使用增强for 循环遍历元素，并尝试删除其中的Hollis 字符串元素

运行以上代码，会抛出以下异常：

子主题

同样的，可以尝试下在增强for 循环中使用add 方法添加元素，结果也会同样抛出该异常。

把foreach 进行解语法糖

看一下foreach 具体如何实现的。

使用jad 工具，对编译后的class 进行反编译，得到以下代码：

子主题

可以发现，foreach 其实是依赖了while 循环和Iterator 实现的。

ConcurrentModificationException异常原理

通过以上代码的异常堆栈，我们可以跟踪到真正抛出异常的代码是：

java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)

该方法是在iterator.next()方法中调用的。

我们看下该方法的实现：

我们看下该方法的实现：

如上，在该方法中对modCount 和expectedModCount 进行了比较，如果二者不想等，则抛出CMException。

那么，modCount 和expectedModCount 是什么？是什么原因导致他们的值不想等的呢？

modCount 

是ArrayList 中的一个成员变量。

它表示该集合实际被修改的次数。

List<String> userNames = new ArrayList<String>() {{ add("Hollis"); add("hollis"); add("HollisChuang"); add("H"); }}; 当使用以上代码初始化集合之后该变量就有了。初始值为0。

expectedModCount

是ArrayList 中的一个内部类——Itr 中的成员变量。

Iterator iterator = userNames.iterator();

以上代码，即可得到一个Itr 类，该类实现了Iterator 接口。

表示这个迭代器预期该集合被修改的次数。

其值随着Itr 被创建而初始化。

只有通过迭代器对集合进行操作，该值才会改变。

userNames.remove(userName);方法里面做了什么事情，为什么会导致expectedModCount 和modCount 的值不一样。

通过翻阅代码，我们也可以发现，remove 方法核心逻辑如下：

可以看到，它只修改了modCount，并没有对expectedModCount 做任何操作。

简单画一张图描述下以上场景：

子主题

简单总结一下，

之所以会抛出CMException 异常，是因为代码中使用了增强for循环

而在增强for循环中， 集合遍历是通过iterator进行的， 但是元素的add/remove 却是直接使用的集合类自己的方法。

这就导致iterator在遍历时，会发现有一个元素在自己不知不觉的情况下就被删除/添加了，就会抛出一个异常，用来提示用户，可能发生了并发修改！

所以，在使用Java 的集合类时，如果发生CMException，优先考虑fail-fast有关的情况

实际上这里并没有真的发生并发，只是Iterator 使用了fail-fast 的保护机制，只要他发现有某一次修改是未经过自己进行的，那么就会抛出异常。

举一个最简单的fail-fast 的例子/fail-fast 理念的实际应用

public int divide(int divisor,int dividend){     if(dividend == 0){         throw new RuntimeException("dividend can't be null");      } return divisor/dividend; }

上面的代码是一个对两个整数做除法的方法

在divide 方法中，对被除数做了个简单的检查，如果其值为0，那么就直接抛出一个异常，并明确提示异常原因。

这其实就是fail-fast 理念的实际应用。

使用fail-fast的好处，可以预先识别出一些错误情况

一方面，可以避免执行复杂的其他代码，

另外一方面，这种异常情况被识别之后也可以针对性的做一些单独处理。

为什么说fail-fast 会有坑呢？

原因是Java 的集合类中运用了fail-fast 机制进行设计，

一旦使用不当，触发fail-fast 机制设计的代码，就会发生非预期情况。

为什么禁止在foreach 循环里进行元素的remove/add 操作

fail-safe机制

是什么？

Java中的一种安全失败机制

它表示的是，在遍历时，不是直接在原集合上进行访问，而是先复制原有集合内容，在拷贝的集合上进行遍历。

为了避免触发fail-fast 机制，导致异常，可以使用Java 中提供的一些采用了fail-safe 机制的集合类。

这样的集合容器在遍历时，不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

fail-safe 集合的所有对集合的修改都是先拷贝一份副本，然后在副本集合上进行的，并不是直接对原集合进行修改。

并且这些修改方法，如add/remove 都是通过加锁来控制并发的

JUC包下的容器都是安全失败的， 可以在多线程条件下使用，并发修改。

JUC包下的容器都是fail-safe 的，可以在多线程下并发使用，并发修改。同时也可以在foreach 中进行add/remove 。

不会触发ConcurrentModificationException

由于迭代时，是对原集合的拷贝，进行遍历

所以在遍历过程中，对原集合所作的修改，并不能被送代器检测到

所以不会触发ConcurrentModificationException。

比如CopyOnWriteArrayList

拿CopyOnWriteArrayList 这个fail-safe 的集合类来简单分析一下

一种fail-safe机制的集合，它就不会出现异常

ArrayList的一种线程安全的变体

所有可变操作都是通过对数组进行全新复制来实现的。

（比如add和set等）

迭代器在迭代的过程中，不需要做fail-fast 的并发检测。

（因为fail-fast 的主要目的就是识别并发，然后通过异常的方式通知用户）

CopyOnWriteArrayList的使用代码1

以上代码，使用CopyOnWriteArrayList 代替了ArrayList，就不会发生异常。

CopyOnWriteArrayList的使用代码2

源码

虽然基于拷贝内容的优点是避免了CME，但同样地，迭代器并不能访问到修改后的内容。

CopyOnWriteArrayList的使用代码3

子主题

得到CopyOnWriteArrayList 的Iterator 之后，通过for 循环直接删除原数组中的值，最后在结尾处输出Iterator，结果发现内容如下：

迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

操作系统级别的并发工具

什么是操作系统级别的并发工具

讲到并发容器，就不得不提操作系统级别实现了哪些进程/线程间的井发容器

其实就是数据结构的设计

信号量

是什么？

E.W.Dijkstra在1965年提出的一种方法

它使用一个整形变量来累计唤醒次数， 以供之后使用。

在他的观点中， 有一个新的变量类型称作信号量（semaphore）

一个信号量的取值

不需要任何唤醒

任意正数

唤醒次数

信号量有两个操作

down

用sleep来表示

用wakeup来表示

原理

down这个指令的操作，会检查值是否大于0

如果大于0， 则将其值减11若该值为0， 则进程将睡眠， 而且此时down操作将会继续执行。

检查数值、修改变量值以及可能发生的睡眠操作均为一个单一的、不可分割的原子操作（atomic action）完成

互斥量

是什么？

mutex(互斥量)

如果不需要信号量的计数能力时， 可以使用信号量的一个简单版本

互斥量是一个处于两种状态之一的共享变量

解锁(unlocked)

0表示解锁

加锁(locked)

其他所有的值表示加锁

比1大的值表示加锁的次数。

只需要一个二进制位来表示它， 不过一般情况下， 通常会用一个整型(integer) 来表示

mutex使用两个过程

当一个线程(或者进程) 需要访问关键区域时， 会调用mutex_lock进行加锁

如果互斥锁当前处于解锁状态(表示关键区域可用)，则调用成功，并且调用线程可以自由进入关键区域。

另一方面， 如果mutex互斥量已经锁定的话， 调用线程会阻塞直到关键区域内的线程执行完毕并且调用了mutex_unlock.

如果多个线程在mutex互斥量上阻塞， 将随机选择一个线程并允许它获得锁

说明

优势

在一些共享资源和一段代码中保持互斥

由于互斥的实现既简单又有效，这使得互斥量在实现用户空间线程包时非常有用。

Futexes

诞生背景

随着并行的增加， 同步和互斥对于性能来说是非常重要的。

有效的同步(synchronization)

互斥/锁定(locking)

如果进程等待时间很短， 那么自旋锁(Spinlock) 是非常有效：

但是如果等待时间比较长， 那么这会浪费CPU周期。

如果进程很多， 那么阻塞此进程， 并仅当锁被释放时，让内核解除阻塞是更有效的方式。

不幸的是，这种方式也会导致另外的问题：它可以在进程竞争频繁的时候运行良好

但是在竞争不是很激烈的情况下，内核切换的消耗会非常大，而且更困难的是，预测锁的竞争数量更不容易。

Futex

Linux中的特性

有一种有趣的解决方案是把两者的优点结合起来， 提出一种新的思想

把两者的优点结合起来

或者是快速用户空间互斥(fast userspace mutex)

特点

实现了基本的锁定(很像是互斥锁) 

而且避免了陷入内核中， 因为内核的切换的开销非常大， 这样做可以大大提高性能

由两部分组成

内核服务

提供了一个等待队列(wait queue) 允许多个进程在锁上排队等待

除非内核明确的对他们解除阻塞，否则它们不会运行。

用户库

图解Futex

Pthreads中的互斥量与条件变量

Pthreads提供的两种同步机制（Pthreads提供了一些功能用来同步线程）

互斥量（mutex）

最基本的机制是使用互斥量变量， 可以锁定和解锁， 用来保护每个关键区域，

希望进入关键区域的线程，首先要尝试获取mutex.

如果mutex没有加锁， 线程能够马上进入并且互斥量能够自动锁定， 从而阻止其他线程进入。

如果mutex已经加锁， 调用线程会阻塞，直到mutex解锁。

如果多个线程在相同的互斥量上等待， 当互斥量解锁时， 只有一个线程能够进入并且重新加锁。

这些锁并不是必须的，程序员需要正确使用它们。

与互斥量有关的重要的pthread函数调用

与互斥量有关的函数调用

和想象中的一样， mutex能够被创建和销毁， 扮演这两个角色的分别是

Phread_mutex_init

Pthread_mutex_destroy

mutex也可以通过Pthread_mutex_Lock来进行加锁， 如果互斥量已经加锁， 则会阻塞调用者。

还有一个调用Pthread_mutex_try Lock用来尝试对线程加锁

当mutex已经被加锁时，会返回一个错误代码而不是阻塞调用者。

这个调用允许线程有效的进行忙等。

最后， Pthread_mutex_unlock会对mutex解锁并且释放一个正在等待的线程。

条件变量(condition variables)

互斥量（mutex），可以很好的允许或阻止对关键区域的访问

条件变量(condition variables)，允许线程由于未满足某些条件而阻塞

注意

条件变量(不像是信号量)不会存在于内存中。

如果将一个信号量，传递给一个没有线程等待的条件变量，那么这个信号就会丢失

重新认识一下生产者和消费者问题

下面进一步来研究线程、互斥量、条件变量之间的关联

一个线程将东西放在一个缓冲区内，由另一个线程将它们取出。

如果生产者发现缓冲区没有空槽可以使用了，生产者线程会阻塞起来直到有一个线程可以使用。

生产者使用mutex来进行原子性检查从而不受其他线程干扰。

但是当发现缓冲区已经满了以后， 生产者需要一种方法来阻塞自己并在以后被唤醒。

这便是条件变量做的工作。

与条件变量有关的重要的pthread函数调用

表中给出了一些调用用来创建和销毁条件变量。

条件变量上的主要属性是

Pthread_cond_wait

Pthread_cond_signal

Pthread_cond_broadcast用来唤醒多个阻塞的、需要等待信号唤醒的线程。

管程

目的

编写更加准确无误的程序

是什么？

一个更高级的同步原语叫做管程(monitor)

Brinch Hansen和Hoare提出

一个很重要的特性

在任何时候管程中只能有一个活跃的进程

 这一特性使管程能够很方便的实现互斥操作。

原理

管程是编程语言的特性，所以编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法，来处理对管程的调用

通常情况下，当进程调用管程中的程序时，该程序的前几条指令会检查管程中是否有其他活跃的进程

如果有活跃的进程，调用进程将被挂起，直到另一个进程离开管程才将其唤醒。

如果没有活跃进程在使用管程，那么该调用进程才可以进入。

为什么需要引入条件变量以及相关操作？

即使管程提供了一种简单的方式来实现互斥，但在我们看来，这还不够.

因为还需要一种在进程无法执行被阻塞，

在生产者-消费者问题中，

很容易将针对缓冲区满和缓冲区空的测试放在管程程序中，

但是生产者在发现缓冲区满的时候该如何阻塞呢?

解决的办法是引入条件变量(condition variables) 以及相关的两个操作wait和signal

当一个管程程序，发现它不能运行时(例如， 生产者发现缓冲区已满) ， 它会在某个条件变量(如full) 上执行wait操作。

这个操作造成调用进程阻塞， 并且还将另一个以前等在管程之外的进程调入管程。

在前面的pthread中我们已经探讨过条件变量的实现细节了，

<div class="mind-clipboard">另一个进程， 比如消费者可以通过执行signal来唤醒阻塞的调用进程。</div>

优势

程序员无需关心

进入管程中的互斥由编译器负责， 但是一种通用做法是使用互斥量(mutex) 和二进制信号量(binary semaphore)

由于编译器而不是程序员在操作， 因此出错的几率会大大降低

在任何时候，编写管程的程序员都无需关心编译器是如何处理的。

他只需要知道将所有的临界区转换成为管程过程即可。

更容易保证并行编程的正确性。

通过临界区自动的互斥，管程比信号量更容易保证并行编程的正确性。

绝不会有两个进程，同时执行临界区中的代码。

缺点

大多数编程语言都没有管程

管程是一个编程语言的概念

编译器必须要识别管程，并用某种方式，对其互斥作出保证

C、Pascal以及大多数其他编程语言，都没有管程，所以不能依靠编译器来遵守互斥规则。

不适用于分布式系统

与管程和信号量有关的另一个问题是， 这些机制都是设计用来解决访问共享内存的一个或多个CPU上的互斥问题的。

<div class="mind-clipboard">通过将信号量放在共享内存中并用TSL或XCHG指令来保护它们， 可以避免竞争，</div>

但是如果是在分布式系统中

同时具有多个CPU的情况

每个CPU都有自己的私有内存

它们通过网络相连，那么这些原语将会失效，

信号量太低级了

管程在少数几种编程语言之外无法使用

所以还需要其他方法

消息传递

上面提到的其他方法就是消息传递(messa age passing)

这种进程间通信的方法使用两个原语send和receive

它们像信号量而不像管程， 是系统调用，而不是语言级别

如果没有消息，接受者可能被阻塞，直到接收一条消息或者带着错误码返回，

实例如下

send(destination, &message)

send方法用于向一个给定的目标发送一条消息

receive(source, &message)

receive从一个给定的源接收一条消息。

消息传递系统问题和设计难点

说明

消息传递系统现在面临着许多信号量和管程所未涉及的问题和设计难点，尤其是对那些在网络中不同机器上的通信状况

常见问题

如何保证消息不被网络丢失？重发机制

为了防止消息丢失，发送方和接收方可以达成一致：

一旦接受到消息后， 接收方马上回送一条特殊的确认(acknowLedgement) 消息，

 如果发送方在一段时间间隙内未收到确认，则重发消息。

如何保证返回给发送者的确认消息不丢失？

现在考虑消息本身被正确接收，而返回给发送着的确认消息丢失的情况。

发送者将重发消息，这样接受者将收到两次相同的消息。

图解

对于接收者来说，如何区分新的消息和一条重发的老消息是非常重要的。

通常采用在每条原始消息中嵌入一个连续的序号来解决此问题。

如果接受者收到一条消息，它具有与前面某一条消息一样的序号，就知道这条消息是重复的，可以忽略。

如何命名进程的问题

以便在发送或接收调用中清晰的指明进程。

身份验证（ authentication) 也是一个问题

比如客户端怎么知道它是在与一个真正的文件服务器通信

 从发送方到接收方的信息有可能被中间人所篡改。

屏障

是什么？

屏障(barrier)

一种同步机制

屏障可用于一组进程同步

最后一个同步机制是准备用于进程组，而不是进程间的生产者-消费者情况的。

实现原理

在某些应用中划分了若干阶段，并且规定，

除非所有的进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段，

可以通过在每个阶段的结尾安装一个屏障来实现这种行为。

当一个进程到达屏障时， 它会被屏障所拦截，直到所有的屏障都到达为止。

图解屏障

图a，有四个进程接近屏障，这意味着每个进程都在进行运算，但是还没有到达每个阶段的结尾。

图b，过了一段时间后，A、B、D进程都到达了屏障，各自进程被挂起，但此时还不能进入下个阶段，因为进程B还没有执行完毕，

结果，当最后一个C到达屏障后，这个进程组才能够进入下一个阶段。

避免锁：读-复制-更新

最快的锁是根本没有锁。

问题在于没有锁的情况下，是否允许对共享数据结构的并发读写进行访问，答案当然是不可以。

假设进程A正在对一个数字数组进行排序，而进程B正在计算其平均值，而此时你进行A的移动，会导致B会多次读到重复值，而某些值根本没有遇到过。

然而，在某些情况下，可以允许写操作来更新数据结构，即便还有其他的进程正在使用，窍门在于确保每个读操作要么读取旧的版本，要么读取新的版本

例如下面的树

上面的树中，读操作从根部到叶子遍历整个树。

加入一个新节点X后，为了实现这一操作，要让这个节点在树中可见之前使它*恰好正确*：

对节点X中的所有值进行初始化，包括它的子节点指针。然后通过原子写操作，使X称为A的子节点。

所有的读操作都不会读到前后不一致的版本

在上面的图中，我们接着移除B和D，首先，将A的左子节点指针指向C。所有原本在A中的读操作将会后续读到节点C，而永远不会读到B和D。、

也就是说，它们将只会读取到新版数据。同样，所有当前在B和D中的读操作将继续按照原始的数据结构指针并且读取旧版数据。

所有操作均能正确运行，不需要锁佳任何东西，而不需要锁住数据就能够移除B和D的主要原因就是RUC， 将更新过程中的移除和再分配过程分离开。

读-复制-更新（Ready-Copy-Update， RCU)

传统同步容器

同步容器主要包括两类

本来就线程安全实现的容器

Vector

Hashtable

Stack

由Collections.synchronizedxxx实现的非线程安全的容器

Collections.synchronizedList

Collections.synchronizedMap

原理：同步容器将所有对容器状态的访问都串行化，以实现他们之间的线程安全性。

这种方法的代价是严重降低了并发性能，当多个线程争抢容器锁的同时，产重降低吞吐量。

Java并发工具包JUC综述

并发容器

JDK 1.5提供了许多种并发容器，来改进同步容器的性能

Java 5.0中

新增加了用来替代基于散列的Map容器

ConcurrentHashMap

用来替代基于散列的Map容器

在并发集合中的位置（继承关系）

子主题

ConcurrentHashMap继承了AbstractMap接口，并实现了ConcurrentMap和Seralizable接口

AbstractMap和ConcurrentMap都是Map的实现类， 只不过AbstractMap是抽象实现。

和Hashtable的构造非常相似，但是原理大不相同

所有访问Hashtable的线程都想获取同一把锁

只不过Hashtable容器在激烈竞争的场景中，会表现出效率低下的现象

Hashtable 类（因性能差的线性安全被弃用）

HashTable底层采用数组+链表存储键值对， 由于被弃用， 后人也没有对它进行任何改进

它是一个线程安全的集合，一个线程安全的Map，所有的操作都是线程安全的

 它被淘汰的原因也主要因为两个字：性能

与新的集合实现不同，Hashtable是线程安全的， 但是因为这个线程安全， 它就被淘汰掉了

它所有的方法都被加上了synchronized关键字， 也是因为这个关键字，它注定成为了时代的弃儿。

 如果容器里面有多把锁，并且每一把锁都只用来锁定一段数据，

所有访问Hashtable的线程都想获取同一把锁

那么，当多个线程访问不同的数据段时，就不存在竞争关系。

ConcurrentHashMap采用的分段锁实现

在这种锁实现中， 任意数量的读取线程可以并发的访问Map，

执行读取操作的线程和执行写入的线程可以并发的访问Map， 并且在读取的同时，也可以并发修改Map。

图解ConcurrentHashMap采用的分段锁实现

底层原理：采用的分段锁实现

实现带来的结果是

 在并发环境下，可以实现更高的吞吐量

在单线程环境下，只损失非常小的性能

它是一种弱一致性的集合，能够容忍并发修改

HashMap

具有fail-fast机制

它是一种强一致性的集合

在数据不一致的情况下，会抛出ConcurrentModificationException异常

ConcurrentHashMap

一种弱一致性的集合

在并发修改其内部结构时， 它不会抛出ConcurrentModificationException异常， 弱一致性能够容忍并发修改。

标准方法如size、empty、containsKey等方法被弱化

HashMap

一般使用的size、empty、containsKey等方法都是标准方法

其返回的结果是一定的， 包含就是包含， 不包含就是不包含

可以作为判断条件

ConcurrentHashMap

这些方法只是参考方法， 它不是一个精确值，

size、empty、containsKey等方法

这些方法在并发场景下用处很小， 因为返回值总是在不断变化，所以这些操作的需求就被弱化了。

图解

ConcurrentHashMap图解

没有实现对Map加锁，从而实现独占访问

在线程安全的Map实现都实现了独占访问， 因此只能单个线程修改Map， 

如Hashtable

如Collections.synchronizedMap

ConcurrentHashMap

在ConcurrentHashMap中，没有实现对Map加锁从而实现独占访问

ConcurrentHashMap与这些Map容器相比， 具有更多的优势和更少的劣势

使用场景

只有当需要独占访问的需求时，才会使用Hashtable或者是Collections.synchronizedMap，

 否则其他并发场景下， 应该使用Concurrent HashMap.

ConcurrentHashMap（高性能的HashMap）

HashMap 和ConcurrentHashMap 的区别？

实现方式

ConcurrentHashMap 和HashMap 的实现方式不一样，虽然都是使用桶数组实现 的，但是还是有区别，ConcurrentHashMap 对桶数组进行了分段，而HashMap 并没有。

锁机制与线程安全

ConcurrentHashMap 在每一个分段上都用锁进行了保护。HashMap 没有锁机制。 所以，前者线程安全的，后者不是线程安全的。

ConcurrentMap

一个接口

它继承了Map接口并提供了Map接口中四个新的方法

四个新的方法

这四个方法都是原子性方法， 进一步扩展了Map的功能

ConcurrentNavigableMap

java.util.concurrent.Concurrent Navigable Map类是java.util.NavigableMap的子类

图解

子主题

它支持并发访问，并且允许其视图的并发访问

什么是视图呢?

视图就是集合中的一段数据序列

ConcurrentNavigableMap中支持使用headMap、subMap、tailMap返回的视图

与其重新解释一下NavigableMap中找到的所有方法，不如看一下

ConcurrentNavigableMap中添加的方法

headMap方法：headMap方法返回一个严格小于给定键的视图

tailMap方法：tailMap方法返回包含大于或等于给定键的视图

subMap方法：subMap方法返回给定两个参数的视图

ConcurrentNavigableMap接口,包含一些可能有用的其他方法

descendingkeySet()

descendingMap()

navigableKeySet()

ConcurrentSkipListMap

线程安全的有序的哈希表

适用于高并发的场景

继承关系

底层数据结构是基于跳表实现的。

ConcurrentSkipListMap可以提供Comparable内部排序或者是Comparator外部排序， 具体取决于使用哪个构造函数。

ConcurrentSkipListSet

线程安全的有序的集合

适用于高并发的场景

底层是通过ConcurrentNavigableMap来实现的， 它是一个有序的线程安全的集合。

有序的， 基于元素的自然排序或者通过比较器确定的顺序

线程安全的

新增加了分别替代ArrayList和Set接口实现类

CopyOnWriteArrayList

替代ArrayList接口实现类

是ArrayList的变体，

CopyOnWriteArrayList就是ArrayList的一种线程安全的变体

每次并发写操作，都会创建新的副本

每次并发修改，CopyOnWriteArrayList都相当于重新创建副本

其内部有一个指向数组的引用， 数组是不会被修改的

CopyOnWriteArrayList中的所有可变操作（比如add和set等）都是通过对数组进行全新复制来实现的。

这个过程存在一定的开销，所以，一般在规模很大时，读操作要远 mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-bidi-font-family: 宋体;color:black">远多于写操作时， mso-bidi-font-size:11.0pt;font-family:宋体;mso-fareast-font-family:宋体; mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin;mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;color:black"> 宋体;mso-fareast-theme-font:minor-fareast;mso-bidi-font-family:宋体;color:black">为了保证线程安全性， mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family: Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;color:black"> 宋体;mso-fareast-theme-font:minor-fareast;mso-bidi-font-family:宋体;color:black">会使用Copy mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family: Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;color:black"> On Wrte ArrayList.

它就是一种fail-safe机制的集合

它就不会出现异常

一种fail-safe机制的，它不会抛出Concurrent Modification Exception异常，

并且返回元素与迭代器创建时的元素相同。

CopyOnWriteArrayList案例代码

比如CopyOnWriteArrayList案例

图解CopyOnWriteArrayList继承关系

图解CopyOnWriteArraySet继承关系

CopyOnWriteArraySet

替代Set接口实现类

类似的， CopyOnWriteArraySet的作用也相当于替代了Set接口。

还新增加了两种容器类型， 分别是

Queue

队列

它有一些实现分别是

ConcurrentLinkedQueue

传统的先进先出队列

ConcurrentLinkedQueue是一个先入先出的队列

它的操作不会阻塞， 如果队列为空，那么获取元素的操作会返回空值，

PriorityQueue

并发优先级队列

PriorityQueue扩展了Queue， 增加了可阻塞的播入和获取等操作

如果队列为空， 那么获取元素的操作将一直阻塞，直到队列中出现一个可用的元素为止

如果队列已满，那么插入操作则一直阻塞，直到队列中有可用的空间为止。

BlockingQueue

是什么？

阻塞队列，关键字是阻塞，先理解阻塞的含义，

译为阻塞队列

它是JDK 1.5添加的新的工具类

 它继承于Queue队列， 并扩展了Queue的功能

在检索元素时，会等待队列变成非空， 并在存储元素时，会等待队列变为可用

阻塞队列中，线程阻塞两种情况

当队列中没有数据的情况下，消费者端的所有线程都会被自动阻塞（挂起），直到有数据放入队列。

图1 线程阻塞情况1

当队列中填满数据的情况下，生产者端的所有线程都会被自动阻塞（挂起），直到队列中有空的位置，线程被自动唤醒。

图2 线程阻塞情况2

继承关系

BlockingQueue的继承关系

有四种实现形式， 以不同的方式来处理

第一种是抛出异常

特殊值：第二种是根据情况会返回null或者false

阻塞：第三种是无限期的阻塞当前线程直到操作变为可用后

超时：第四种是给定一个最大的超时时间，超过后才会放弃

不允许添加null元素

在其实现类的方法add、put或者offer后时，添加null会抛出空指针异常。

有容量限制

在任意时间内， 它都会有一个remainCapacity，

超过该值之前， 任意put元素都会阻塞。

一般用于实现生产者-消费者队列

如下图所示

一般用于实现生产者-消费者队列

阻塞队列的主要方法

方法类型

抛出异常：抛出一个异常；

特殊值：返回一个特殊值（null或false,视情况而定）

阻塞：在成功操作之前，一直阻塞线程

超时：放弃前只在最大的时间内阻塞

插入操作

1：public abstract boolean add(E paramE)：将指定元素插入此队列中（如果立即可行且不会违反容量限制），成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。如果该元素是NULL，则会抛出NullPointerException异常。

2：public abstract boolean offer(E paramE)：将指定元素插入此队列中（如果立即可行且不会违反容量限制），成功时返回 true，如果当前没有可用的空间，则返回 false。

3：public abstract void put(E paramE) throws InterruptedException： 将指定元素插入此队列中，将等待可用的空间（如果有必要）

4：offer(E o, long timeout, TimeUnit unit)：可以设定等待的时间，如果在指定的时间内，还不能往队列中加入BlockingQueue，则返回失败。

获取数据操作：

1：poll(time):取走BlockingQueue里排在首位的对象,若不能立即取出,则可以等time参数规定的时间,取不到时返回null;

2：poll(long timeout, TimeUnit unit)：从BlockingQueue取出一个队首的对象，如果在指定时间内，队列一旦有数据可取，则立即返回队列中的数据。否则直到时间超时还没有数据可取，返回失败

3：take():取走BlockingQueue里排在首位的对象,若BlockingQueue为空,阻断进入等待状态直到BlockingQueue有新的数据被加入。

4.drainTo():一次性从BlockingQueue获取所有可用的数据对象（还可以指定获取数据的个数），通过该方法，可以提升获取数据效率；不需要多次分批加锁或释放锁。

Java中的阻塞队列BlockingQueue有多种实现

阻塞队列家族

ArrayBlockingQueue

一个用数组实现的有界队列，和ArrayList对应

比同步List具有更好的并发性能

FIFO先入先出队列，此队列顺序按照先入先出的原则对元素进行排序。

默认情况下不保证线程公平的访问队列

公平访问队列是什么？

阻塞的线程，可以按照阻塞的先后顺序访问

即先阻塞线程先访问队列

非公平性访问队列是什么？

对先等待的线程是非公平的

有可能先阻塞的线程，最后才访问队列。

由数组结构组成的有界阻塞队列。

用数组实现的有界阻塞队列。

此队列按照先进先出（FIFO）的原则对元素进行排序。

默认情况下，不保证访问者公平的访问队列，

（公平、非公平）

所谓公平访问队列是指阻塞的所有生产者线程或消费者线程，当队列可用时，可以按照阻塞的先后顺序访问队列，即先阻塞的生产者线程，可以先往队列里插入元素，先阻塞的消费者线程，可以先从队列里获取元素。

通常情况下为了保证公平性会降低吞吐量。

使用以下代码创建一个公平的阻塞队列： ArrayBlockingQueue fairQueue = new ArrayBlockingQueue(1000,true);

LinkedBlockingQueue

继承关系

FIFO先入先出队列

一种BlockingQueue的实现，和LinkedList对应

比同步List具有更好的并发性能

它是一种基于链表的构造、先入先出的有界阻塞队列

队列的head也就是头元素是在队列中等待时间最长的元素； 

队列的tail也就是队尾元素是队列中等待时间最短的元素。

新的元素会被插入到队尾中，检索操作将获取队列中的头部元素，

链表队列通常比基于数组的队列具有更高的吞吐量，但是在大多数并发应用程序中，可预测的性能较差。

由链表结构组成的有界阻塞队列。

基于链表的阻塞队列

同ArrayListBlockingQueue类似，此队列按照先进先出（FIFO）的原则对元素进行排序。

（两个独立锁提高并发）

而LinkedBlockingQueue之所以能够高效的处理并发数据，还因为其对于生产者端和消费者端分别采用了独立的锁来控制数据同步，这也意味着在高并发的情况下生产者和消费者可以并行地操作队列中的数据，以此来提高整个队列的并发性能。 

LinkedBlockingQueue会默认一个类似无限大小的容量（Integer.MAX_VALUE）。

PriorityBlockingQueue

一个优先级排序的阻塞队列，一个支持优先级的阻塞队列

注意：不能保证同优先级元素的顺序

如果你希望按照某种顺序，而不是FIFO处理元素时，这个队列将非常有用。

正如其他有序的容器一样， PriorityBlockingQueue

自然排序

既可以按照自然顺序来比较元素， 

默认情况下的元素采取自然顺序生序或者降序，

自定义排序

也可以使用Comparator比较器进行外部元素比较。

也可以自己定义Comparator进行外部排序。

支持优先级排序的无界阻塞队列

PriorityBlockingQueue（compareTo排序实现优先）

是一个支持优先级的无界队列。

默认情况下元素采取自然顺序升序排列。

可以自定义实现compareTo()方法来指定元素进行排序规则，或者初始化PriorityBlockingQueue时，指定构造参数Comparator来对元素进行排序。

需要注意的是不能保证同优先级元素的顺序。

DelayQueue

一个支持延时获取元素的无阻塞队列

其中的元素只能在延迟到期后才能使用

队列头是延迟最长时间的元素， 如果没有延迟， 则没有head头元素， poll方法会返回null

判断依据

getDelay(TimeUnit.NANOSECONDS) 方法返回一个值小于或者等于0，就会发生过期.

使用优先级队列实现的无界阻塞队列

DelayQueue（缓存失效、定时任务 ）

是一个支持延时获取元素的无界阻塞队列。

队列使用PriorityQueue来实现。

队列中的元素必须实现Delayed接口，在创建元素时可以指定多久才能从队列中获取当前元素。

只有在延迟期满时才能从队列中提取元素。

可以将DelayQueue运用在以下应用场景

缓存系统的设计：

可以用DelayQueue保存缓存元素的有效期，

使用一个线程循环查询DelayQueue

一旦能从DelayQueue中获取元素时，表示缓存有效期到了。

定时任务调度

使用DelayQueue保存当天将会执行的任务和执行时间

一旦从DelayQueue中获取到任务就开始执行

比如TimerQueue就是使用DelayQueue实现的。

SynchronousQueue

它的每个insert操作必须等待其他相关线程的remove方法后才能执行，反之亦然，

它维护的是一组线程而不是一组队列， 实际上它不是一个队列， 

不存储元素的阻塞队列

SynchronousQueue（不存储数据、可用于传递数据）

是一个不存储元素的阻塞队列。

每一个put操作必须等待一个take操作，否则不能继续添加元素。

SynchronousQueue可以看成是一个传球手，负责把生产者线程处理的数据直接传递给消费者线程。

队列本身并不存储任何元素，非常适合于传递性场景,比如在一个线程中使用的数据，传递给另外一个线程使用

SynchronousQueue的吞吐量高于LinkedBlockingQueue 和 ArrayBlockingQueue。

TransferQueue

继承于BlockingQueue

它是一个接口， 一个BlockingQueue是一个生产者可能等待消费者接受元素

Transfer Queue则更进一步， 生产者会一直阻塞，直到所添加到队列的元素被某一个消费者所消费， 新添加的transfer方法用来实现这种约束。

Transfer Queue有下面这些方法

两个tryTransfer方法

一个是非阻塞的

另一个是带有timeout

参数设置超时时间的

两个辅助方法

hasWaitingConsumer

getWaitingConsumerCount

LinkedTransferQueue

由链表结构组成的无界阻塞队列

这个队列对任何给定的生产者进行FIFO排序

 head是队列中存在时间最长的元素， tail是队列中存在时间最短的元素，

一个无界的基于链表的TransferQueue

是一个由链表结构组成的无界阻塞TransferQueue队列。

相对于其他阻塞队列，LinkedTransferQueue多了tryTransfer和transfer方法。

transfer方法

如果当前有消费者正在等待接收元素（消费者使用take()方法或带时间限制的poll()方法时）

transfer方法可以把生产者传入的元素立刻transfer（传输）给消费者。

如果没有消费者在等待接收元素，

transfer方法会将元素存放在队列的tail节点，并等到该元素被消费者消费了才返回。

transfer方法是必须等到消费者消费了才返回。

tryTransfer方法

则是用来试探下生产者传入的元素是否能直接传给消费者。

如果没有消费者等待接收元素，则返回false。

tryTransfer方法无论消费者是否接收，方法立即返回。

对于带有时间限制的tryTransfer(E e, long timeout, TimeUnit unit)方法，

试图把生产者传入的元素直接传给消费者，但是如果没有消费者消费该元素则等待指定的时间再返回，

如果超时还没消费元素，则返回false，

如果在超时时间内消费了元素，则返回true。

LinkedBlockingDeque

由链表结构组成的双向阻塞队列

LinkedBlockingDeque

是一个由链表结构组成的双向阻塞队列

所谓双向队列指的你可以从队列的两端插入和移出元素。

双端队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。

相比其他的阻塞队列，LinkedBlockingDeque多了addFirst，addLast，offerFirst，offerLast，peekFirst，peekLast等方法

以First单词结尾的方法，表示插入，获取（peek）或移除双端队列的第一个元素。

以Last单词结尾的方法，表示插入，获取或移除双端队列的最后一个元素。

另外插入方法add等同于addLast

移除方法remove等效于removeFirst

但是take方法却等同于takeFirst，不知道是不是Jdk的bug，使用时还是用带有First和Last后缀的方法更清楚。

在初始化LinkedBlockingDeque时可以设置容量防止其过渡膨胀。另外双向阻塞队列可以运用在“工作窃取”模式中。

Java 6.0

还引入了分别作为同步的SortedMap和SortedSet的并发替代品

ConcurrentSkipListMap

ConcurrentSkipListSet

与BlockingQueue相对的，还有

Deque

JDK 1.6被提出

Deque是一个双端队列

而双端队列适用于工作密取

在工作密取的设计中，每个消费者都有各自的双端队列

如果一个消费者完成了自己双端队列的任务，就会去其他双端队列的末尾进行消费。

密取方式要比传统的生产者-消费者队列具有更高的可伸缩性

因为每个工作密取的工作者都有自己的双端队列，不存在竞争的情况。

分别实现了在队列头和队列尾的插入

Deque的实现有

ArrayDeque

底层实现

Deque的可动态调整大小的数组实现

ArrayDeque的数据结构：数组， 并提供头尾指针下标对数组元素进行操作

使用数组实现的双端队列， 它是无界的双端队列，

一个更完善，可靠性更强的LIFO栈操作，

由Deque接口和他的实现 提供

特点

在日常使用得不多

禁止空元素，

ArrayDeque作为栈时比Stack性能好， 作为队列时比LinkedList性能好

应该优先选择使用ArrayDeque实现栈

这个类作为栈使用时要比Stack快， 

Deque<Integer> stack = new ArrayDeque<Integer>()

它与LinkedList的对比

LinkedList

采用链表实现双端队列

ArrayDeque

作为queue使用时，要比LinkedList快。

ArrayDeque不是线程安全的

如果没有外部加锁的情况下， 不支持多线程访问。

ArrayDeque具有fail-fast的特性

 如果创建了迭代器之后， 却使用了迭代器外部的remove等修改方法， 

那么这个类将会抛出ConcurrentModificationException异常。

时间复杂度大部分都稳定在0(1)

由于双端队列只能在头部和尾部操作元素，所以删除元素和插入元素的时间复杂度大部分都稳定在0(1)，

除了remove、removeFirstOccurrence、removeLastOccurrence、contains、interator、remove外，

大部分的ArrayDeque都以恒定的开销运行。

内部没有容量限制，会根据需要进行增长

除非在扩容时会涉及到元素的批量复制操作，但是在大多数情况下，使用它时应该指定一个大概的数组长度，避免频繁的扩容。

链表的插入、除操作涉及到指针的操作

数组下标的移动要比指针的操作要廉价，而且数组采用连续的内存地址空间，

而链表元素的内存地址是不连续的，所以数组操作元素的效率在寻址上会比链表要快。

最小的容量是8(JDK 1.8) ， JDK 11，默认容量已经是16

最小的容量是8(JDK 1.8) ， 在JDK 11看到它默认容量已经是16了。

优点

该数据结构更加完善、可靠性更好

依靠队列也可以实现LIFO的栈操作

ConcurrentLinkedDeque

双向链表的无界并发队列

JDK 1.7引入

它与ConcurrentLinkedQueue的区别是：ConcurrentLinkedDeque同时支持FIFO和FILO两种操作方式，即可以从队列的头和尾同时操作(插入/删除}

支持happen-before原则

不允许空元素

LinkedBlockingDeque

BlockingDeque

JDK 1.6被提出

对Queue和BlockingQueue做了扩展

继承关系

继承关系：对Queue和BlockingQueue做了扩展

BlockingDeque的实现

LinkedBlockingDeque

阻塞模式一般用于生产者-消费者队列，

一个由链表结构组成的双向阻塞队列

即可以从队列的两端插入和移除元素

双向队列，因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争

把初始容量和构造函数绑定， 这样能够有效过度拓展。

初始容量如果没有指定，就取的是Integer.MAX_VALUE， 这也是Linked Blocking Deque的默认构造函数。

JUC

Atomic（原子操作）

诞生背景

在多线程程序中，诸如++i 或 i++等运算不具有原子性，是不安全的线程操作之一。

通常会使用synchronized将该操作变成一个原子操作，

但JVM为此类操作特意提供了一些同步类，使得使用更方便，且使程序运行效率变得更高。

AtomicInteger：一个提供原子操作的Integer的类

首先说明，此处AtomicInteger，一个提供原子操作的Integer的类，常见的还有AtomicBoolean、AtomicInteger、AtomicLong、AtomicReference等

实现原理相同，区别在与运算对象类型的不同。

还可以通过AtomicReference<V>将一个对象的所有操作转化成原子操作。

相关资料显示，通常AtomicInteger的性能是ReentantLock的好几倍。

原子包 java.util.concurrent.atomic（锁自旋）

JDK1.5的原子包：java.util.concurrent.atomic这个包里面提供了一组原子类

其基本的特性就是在多线程环境下，当有多个线程同时执行这些类的实例包含的方法时，具有排他性

即当某个线程进入方法，执行其中的指令时，不会被其他线程打断，

而别的线程就像自旋锁一样，一直等到该方法执行完成，才由JVM从等待队列中选择一个另一个线程进入

这只是一种逻辑上的理解。

getAndIncrement采用了CAS操作，每次从内存中读取数据然后将此数据和+1后的结果进行CAS操作，

如果成功就返回结果，否则重试直到成功为止。

而compareAndSet利用JNI来完成CPU指令的操作。

由于一般CPU切换时间比CPU指令集操作更加长， 所以J.U.C在性能上有了很大的提升。

CAS算法

什么是CAS（比较并交换-乐观锁机制-锁自旋）

概念及特性

CAS（Compare And Swap/Set）比较并交换

相对于对于synchronized这种阻塞算法，CAS是非阻塞算法的一种常见实现。

CAS操作是抱着乐观的态度进行的(乐观锁)，它总是认为自己可以成功完成操作。

当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败。

失败的线程不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。

基于这样的原理，CAS操作即使没有锁，也可以发现其他线程对当前线程的干扰，并进行恰当的处理。

CAS算法的过程

CAS需要有3个操作数

内存地址V

旧的预期值A

即将要更新的目标值B

CAS指令执行时，当且仅当内存地址V的值与预期值A相等时，将内存地址V的值修改为B，否则就什么都不做。

它包含3个参数CAS(V,E,N)

V表示要更新的变量(内存值)，E表示预期值(旧的)，N表示新值。

当且仅当V值等于E值时，才会将V的值设为N，

如果V值和E值不同，则说明已经有其他线程做了更新，则当前线程什么都不做。

最后，CAS返回当前V的真实值。

CAS是一种更新的原子操作

整个比较并替换的操作是一个原子操作。

CAS操作是一条CPU指令，不会被打断，所以是原子操作

CAS是一种更新的原子操作，比较当前值跟传入值是否一样，一样则更新，否则失败。

ABA问题

CAS会导致“ABA问题”。

存在CAS的ABA问题

CAS算法实现一个重要前提需要取出内存中某时刻的数据，而在下时刻比较并替换，那么在这个时间差类会导致数据的变化。

举例1

如果内存地址V初次读取的值是A，并且在准备赋值的时候检查到它的值仍然为A，但可能期间它已经被修改过了

通常将 CAS 用于同步的方式是从地址 V 读取值 A，执行多步计算来获得新值 B，然后使用 CAS 将 V 的值从 A 改为 B。

如果 V 处的值尚未同时更改，则 CAS 操作成功。

举例2

比如说一个线程one从内存位置V中取出A，这时候另一个线程two也从内存中取出A，并且two进行了一些操作变成了B，然后two又将V位置的数据变成A，

这时候线程one进行CAS操作发现内存中仍然是A，然后one操作成功。

尽管线程one的CAS操作成功，但是不代表这个过程就是没有问题的。

解决ABA问题

使用AtomicStampedReference的版本号机制来管理

部分乐观锁的实现是通过版本号（version）的方式

乐观锁每次在执行数据的修改操作时，都会带上一个版本号

一旦版本号和数据的版本号一致就可以执行修改操作并对版本号执行+1操作，否则就执行失败。

因为每次操作的版本号都会随之增加，所以不会出现ABA问题，因为版本号只会增加不会减少。

JDK增加了LongAdder等四个类，高并发时效率更高，但是消耗空间更多

对数据进行操作时(使用CAS来保证)可以保证原子性

通过unsafe实现的包装类

Unsafe底层实际上是调用C代码，C代码调用汇编，最后生成出一条CPU指令cmpxchg，完成操作

CompareAndSwap...()

Locks（并发锁）

AQS

什么是 AQS（抽象的队列同步器）

AbstractQueuedSynchronizer类如其名，抽象的队列式的同步器，

一个抽象的队列式的同步器，定义了一套多线程访问共享资源的同步器框架（实现锁的框架），

AQS定义了一套多线程访问共享资源的同步器框架，

许多同步类实现都依赖于它，本质上其实就是对于state的获取和释放

ReentrantLock/ReentrantReadWriteLock /Semaphore/ CountDownLatch的实现都依赖于它

AQS只是一个框架，具体资源的获取/释放方式交由自定义同步器去实现

AQS这里只定义了一个接口，具体资源的获取交由自定义同步器去实现了

（通过state的get/set/CAS)

之所以没有定义成abstract，是因为独占模式下只用实现tryAcquire-tryRelease，而共享模式下只用实现tryAcquireShared-tryReleaseShared。

如果都定义成abstract，那么每个模式也要去实现另一模式下的接口。

不同的自定义同步器争用共享资源的方式也不同。

自定义同步器在实现时只需要实现共享资源state的获取与释放方式即可，至于具体线程等待队列的维护（如获取资源失败入队/唤醒出队等），AQS已经在顶层实现好了

自定义同步器实现时主要实现以下几种方法

1． isHeldExclusively()：该线程是否正在独占资源。只有用到condition才需要去实现它。 

2． tryAcquire(int)：独占方式。尝试获取资源，成功则返回true，失败则返回false。

3． tryRelease(int)：独占方式。尝试释放资源，成功则返回true，失败则返回false。 

4． tryAcquireShared(int)：共享方式。尝试获取资源。负数表示失败；0表示成功，但没有剩余可用资源；正数表示成功，且有剩余资源。 

5． tryReleaseShared(int)：共享方式。尝试释放资源，如果释放后允许唤醒后续等待结点返回true，否则返回false。

同步器的实现是ABS核心（state资源状态计数）

同步器的实现是ABS核心

以ReentrantLock为例，state初始化为0，表示未锁定状态。A线程lock()时，会调用tryAcquire()独占该锁并将state+1。此后，其他线程再tryAcquire()时就会失败，直到A线程unlock()到state=0（即释放锁）为止，其它线程才有机会获取该锁。当然，释放锁之前，A线程自己是可以重复获取此锁的（state会累加），这就是可重入的概念。但要注意，获取多少次就要释放多么次，这样才能保证state是能回到零态的。

以CountDownLatch以例，任务分为N个子线程去执行，state也初始化为N（注意N要与线程个数一致）。这N个子线程是并行执行的，每个子线程执行完后countDown()一次，state会CAS减1。等到所有子线程都执行完后(即state=0)，会unpark()主调用线程，然后主调用线程就会从await()函数返回，继续后余动作。

数据结构

它维护了一个volatile int state（代表共享资源）和一个FIFO线程等待队列（多线程争用资源被阻塞时会进入此队列）。

这里volatile是核心关键词，具体volatile的语义，在此不述。

共享资源  volatile int state

默认实现了FIFO线程等待队列,底层是双向链表

state的访问方式有三种:

getState()

setState() 

compareAndSetState()

线程模式（AQS定义两种资源共享方式）

独享模式

tryAcquire(int)/tryAcquireShared(int )

Exclusive独占资源-ReentrantLock

Exclusive（独占，只有一个线程能执行，如ReentrantLock）

共享模式

tryRelease/tryReleaseShared(int)

Share共享资源-Semaphore/CountDownLatch

Share（共享，多个线程可同时执行，如Semaphore/CountDownLatch）。

ReentrantReadWriteLock实现独占和共享两种方式

一般来说，自定义同步器要么是独占方法，要么是共享方式，只需实现tryAcquire-tryRelease、tryAcquireShared-tryReleaseShared中的一种即可。

但AQS也支持自定义同步器同时实现独占和共享两种方式，如ReentrantReadWriteLock。

既可独占，也可共享（ReentrantReadWriteLock）

图解AQS

ReentrantLock

NonfairSync

tryAcquire

acquireQueued

CAS

FairSync

hasQueuedPredecessors

如果是当前持有锁的线程可重入

AbstractQueuedSynchronizer

入队出队

头结点设计

共享和独享的实现

CAS

什么是CAS（比较并交换-乐观锁机制-锁自旋）

实际应用

存在的问题

cpu开销

只能保证一个共享变量原子操作

AtomicReference

ABA

标志位  时间戳

ReentrantReadWriteLock

ReadLock

WriteLock

StampedLock锁支持工具

ReentrantReadWriteLock

特点

state的变量高16位是读锁，低16位是写锁。

读锁不能升级为写锁

写锁可以降级为读锁

当访问方式是读取操作时，使用读锁即可，当访问方式是修改操作时，则使用写锁

内部类

ReentrantReadWriteLock默认实现在sync中(sync继承了AQS)

NonfairSync

FairSync

WriteLock（实现Lock接口）

ReadLock（实现Lock接口）

Tools（同步工具）

什么是同步工具类

同步工具类可以是任何一个对象

只要它根据自身状态来协调线程的控制流

多种类型的同步控制类、同步工具类

阻塞队列

信号量(Semaphore)

什么是Semaphore？

信号量

翻译过来就是信号量

它其实就是一种信号， 在操作系统中， 也有信号量的这个概念

在进程间通信时，就会谈到信号量进行通信

在Linux操作系统，采取中断时，也会向进程发出中断信号，根据进程的种类和信号的类型判断是否应该结束进程。

在Java中的Semaphore(信号量)

用来控制同时访问特定资源的线程数量， 它通过协调各个线程，以保证合理的使用公共资源。

Semaphore管理着一组许可(permit) ， 许可的初始数量由构造函数来指定。

在获取某个资源之前，应该先从信号量获取许可(permit)， 以确保资源是否可用

当线程完成对资源的操作后， 会把它放在池中并向信号量返回一个许可，从而允许其他线程访问资源，这叫做释放许可。

如果没有许可的话，那么acquire将会阻塞直到有许可(中断或者操作超时) 为止。release方法将返回一个许可信号量，

可以用来实现流量控制

例如常用的数据库连接池， 线程请求资源时，

如果连接池不为空时，解除阻塞

如果数据库连接池为空，则阻塞线程，直接返回失败，

Semaphore（信号量）

Semaphore（信号量）

翻译成字面意思为 信号量

控制同时访问的线程个数

一种基于计数的信号量。

它可以设定一个阈值，基于此，多个线程竞争获取许可信号，做完自己的申请后归还，超过阈值后，线程申请许可信号将会被阻塞。

应用场景

Semaphore可以用来构建一些对象池，资源池之类的，比如数据库连接池

实现互斥锁（计数器为1）

创建计数为1的Semaphore，将其作为一种类似互斥锁的机制，这也叫二元信号量，表示两种互斥状态。

例子：若一个工厂有5台机器，但是有8个工人，一台机器同时只能被一个工人使用，只有使用完了，其他工人才能继续使用。通过Semaphore来实现

可以用于做流量控制，特别是公用资源有限的应用场景，比如数据库连接

Semaphore可以控制同时访问的线程个数，通过 acquire() 获取一个许可，如果没有就等待，而 release() 释放一个许可。

可以控制同时访问的线程个数，它维护了一组"许可证"。

acquire()

消费一个许可证。如果没有许可证了，会阻塞起来

release()

添加一个许可证

Semaphore类中比较重要的几个方法

public void acquire(): 用来获取一个许可，若无许可能够获得，则会一直等待，直到获得许可。

public void acquire(int permits):获取permits个许可

public void release() { } :释放许可。注意，在释放许可之前，必须先获获得许可。

public void release(int permits) { }:释放permits个许可

上面4个方法都会被阻塞，如果想立即得到执行结果，可以使用下面几个方法

public boolean tryAcquire():尝试获取一个许可，若获取成功，则立即返回true，若获取失败，则立即返回false

public boolean tryAcquire(long timeout, TimeUnit unit):尝试获取一个许可，若在指定的时间内获取成功，则立即返回true，否则则立即返回false

public boolean tryAcquire(int permits):尝试获取permits个许可，若获取成功，则立即返回true，若获取失败，则立即返回false

public boolean tryAcquire(int permits, long timeout, TimeUnit unit): 尝试获取permits个许可，若在指定的时间内获取成功，则立即返回true，否则则立即返回false

availablePermits()方法得到可用的许可数目。

Semaphore其实和锁有点类似，它一般用于控制对某组资源的访问权限。

Semaphore 与ReentrantLock

Semaphore基本能完成ReentrantLock的所有工作，使用方法也与之类似，通过acquire()与release()方法来获得和释放临界资源。

经实测，Semaphone.acquire()方法默认为可响应中断锁，与ReentrantLock.lockInterruptibly()作用效果一致，也就是说在等待临界资源的过程中可以被Thread.interrupt()方法中断。

此外，Semaphore也实现了可轮询的锁请求与定时锁的功能，除了方法名tryAcquire与tryLock不同，其使用方法与ReentrantLock几乎一致。

Semaphore也提供了公平与非公平锁的机制，也可在构造函数中进行设定。

Semaphore的锁释放操作也由手动进行，因此与ReentrantLock一样，为避免线程因抛出异常而无法正常释放锁的情况发生，释放锁的操作也必须在finally代码块中完成。

闭锁(Latch)

闭锁(Latch) 是一种同步工具类

它可以延迟线程的进度以直到其到达终止状态

闭锁的作用相当于是一扇门，

在闭锁达到结束状态前，门是一直关着的，没有任何线程能够通过。

<div class="mind-clipboard">当闭锁到达结束状态后，这扇门会打开井且允许任何线程通过，然后就一直保持打开状态。</div>

通过闭锁来启动一组相关的操作，使用闭锁来等待一组事件的执行。

闭锁是一种一次性对象，一旦进入终止状态后，就不能被置

CountDownLatch

闭锁的一种实现

它可以使一个或者多个线程等待一组事件的发生

闭锁有一个计数器， 闭锁需要对计数器进行初始化， 表示需要等待的次数

闭锁在调用await处进行等待， 其他线程在调用countDown把闭锁count次数进行递减， 直到递减为0， 唤醒await。

如下代码所示

略

栅栏(Barrier)

Barrier的特点和闭锁也很类似， 它也是阻塞一组线程直到某个事件发生。

栅栏与闭锁的区别在于，所有线程必须同时到达栅栏的位置，才能继续执行

图解

ABCD四条线程， 必须同时到达Barrier， 然后手牵手一起走过幸福的殿堂。

当线程到达Barrier的位置时，会调用await方法， 这个方法会阻塞直到所有线程都到达Barrier的位置，

如果所有线程都到达Barrier的位置， 那么Barrier将会打开使所有线程都被释放， 而Barrier将被重置以等待下次使用.

如果调用await方法导致超时， 或者await阻塞的线程被中断， 那么Barrier就被认为被打破， 所有阻塞的await都会抛出BrokenBarrierException.

如果成功通过栅栏后，await方法返回一个唯一索引号， 可以利用这些索引号选举一个新的leader， 来处理一下其他工作

CountDownLatch（线程计数器 ）

CountDownLatch类位于JUC包下，利用它可以实现类似计数器的功能

只有一个构造方法只会被赋值一次

另外，CountDownLatch是不能够重用的，

CountDownLatch一般用于某个线程A等待若干个其他线程执行完任务之后，它才执行

没有别的方法可以修改 count

CountDownLatch允许一个或多个线程等待其他线程完成操作

countDown()

count数减1

await()

线程阻塞直到count等于0

应用场景

开启多个线程分块下载一个大文件，每个线程只下载固定的一截，最后由另外一个线程来拼接所有的分段。

应用程序的主线程希望在负责启动框架服务的线程已经启动所有的框架服务之后再执行。

确保一个计算不会执行，直到所需要的资源被初始化。

比如有一个任务A，它要等待其他4个任务执行完毕之后才能执行，此时就可以利用CountDownLatch来实现这种功能了。

CyclicBarrier（回环栅栏）

等待至barrier状态再全部同时执行

字面意思回环栅栏，通过它可以实现让一组线程等待至某个状态之后再全部同时执行。

叫做回环是因为当所有等待线程都被释放以后，CyclicBarrier可以被重用。

我们暂且把这个状态就叫做barrier，当调用await()方法之后，线程就处于barrier了。

当cyclicBarrier的count数等于0的时候，阻塞的线程都继续执行

CyclicBarrier（int ），参数表示屏障拦截的线程数量，每个线程调用await方法告诉CyclicBarrier我已经到达了屏障，然后当前线程被阻塞。

CyclicBarrier中最重要的方法就是await方法

它有2个重载版本

public int await()：用来挂起当前线程，直至所有线程都到达barrier状态再同时执行后续任务；

public int await(long timeout, TimeUnit unit)：让这些线程等待至一定的时间，如果还有线程没有到达barrier状态就直接让到达barrier的线程执行后续任务。

应用场景

多线程计算

CyclicBarrier一般用于一组线程互相等待至某个状态，然后这一组线程再同时执行；

CyclicBarrier是可以重用的。

而CyclicBarrier是可以重用的。

CountDownLatch和CyclicBarrier的区别

CountDownLatch和CyclicBarrier都能够实现线程之间的等待，只不过它们侧重点不同；

CountDownLatch的计数器只能使用一次，而CyclicBarrier的计数器可以使用reset()方法重置

CountDownLatch.await一般阻塞主线程，而CyclicBarrierton一般阻塞工作线程

CountDownLatch主要用于描述一个或者多个线程等待其他线程执行完毕

CyclicBarrier主要用于描述多个线程之间相互等待

Exchanger

与Barrier相关联的还有一个工具类就是Exchanger

Exchanger是一个用于线程间协作的工具类。

Exchanger用于进行线程间的数据交换.

它提供一个同步点， 在这个同步点两个线程可以交换彼此的数据。

这两个线程通过exchange方法交换数据， 如果第一个线程先执行exchange方法， 它会一直等待第二个线程也执行exchange， 

当两个线程都到达同步点时，这两个线程就可以交换数据，将本线程生产出来的数据传递给对方，因此使用 Exchanger的重点是成对的线程使用exchange) 方法， 当有一对线程达到了同步点， 就会进行交换数 据。

因此该工具类的线程对象是成对的。

图解

Exchanger

Exchanger用于进行线程间的数据交换。

它提供一个同步点，在这个同步点，两个线程可以交换彼此的数据。

这两个线程通过exchange方法交换数据，如果第一个线程先执行exchange()方法，它会一直等待第二个线程也执行exchange方法，当两个线程都到达同步点时，这两个线程就可以交换数据，将本线程生产出来的数据传递给对方。

Collections（并发容器）

ConcurrentHashMap

数据结构

JDK1.7

segment

继承了ReentrantLock

一个concurrentHashMap包含了一个segment数组

一个segment包含了一个hashEntry链表

hashEntry

链表结构的元素

hashEntry的成员变量除了value都定义为final

为了维护链表结构，防止并发问题

JDK1.8

Node数组

链表

红黑树

常用方法底层实现(JDK1.7)

put()

流程

1.首先Hash定位到Segment

2.对当前Segment加锁，如果Segment中元素的数量超过了阈值，则需要进行扩容并且进行rehash

3.再定位到链表头部

get()

不用加锁，是非阻塞的

因为共享变量都定义为了volatile

根据java内存模型的happen before原则，对volatile字段的写入操作先于读操作，即使两个线程同时修改和获取volatile变量，get操作也能拿到最新的值，这是用volatile替换锁的经典应用场景

volatile能够保证内存可见性

需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部

定位到链表头部之后根据key取出对应的value值

如果取出的value是null,则对取出value这一过程进行加锁（lock()）

取出的value是null的原因是可能现在正在进行put操作

如果不是value,则直接返回value值

remove()

因为HashEntry中的next是final的，一经赋值以后就不可修改，所以在定位到待删除元素e的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去。尾结点指向e的下一个结点。e后面的结点不需要复制，它们可以重用。e之前的元素在remove()之后为remove之前的逆置

size()

size()操作涉及到多个segment

size操作就是遍历了两次Segment，每次记录Segment的modCount值，然后将两次的modCount进行比较，如果相同，则表示期间没有发生过写入操作，就将原先遍历的结果返回，如果不相同，则把这个过程再重复做一次，如果再不相同，则就需要将所有的Segment都锁住，然后一个一个遍历了

特点

key和value都不可以为null

get()方法不加锁，是非阻塞的

是线程安全的

JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。并且 JDK 1.8 的实现也在链表过长时会转换为红黑树。

ConcurrentLinkedQueue

ConcurrentSkipListMap 和ConcurrentSkipListSet

ConcurrentSkipListMap

一个内部使用跳表，并且支持排序和并发的一个Map

是线程安全的

一般很少会被用到，也是一个比较偏门的数据结构。

跳表

跳表是一种允许在一个有顺序的序列中进行快速查询的数据结构。

在普通的顺序链表中查询一个元素，需要从链表头部开始一个一个节点进行遍历，然后找到节点。

跳表可以解决这种查询时间过长，其元素遍历的图示

跳表是一种使用”空间换时间”的概念，用来提高查询效率的链表。

两个Copy-On-Write机制实现的并发容器

从JDK1.5 开始Java 并发包里提供了两个使用Copy-On-Write机制实现的并发容器, 

它们是CopyOnWriteArrayList 和CopyOnWriteArraySet。

CopyOnWriteArrayList（线程安全的ArrayList）

疑问？

它的add/remove 等方法都已经加锁了，还要copy 一份再修改干嘛？多此一举？

同样是线程安全的集合，这玩意和Vector 有啥区别呢？

Copy-On-Write是什么？

Copy-On-Write

简称COW

是一种用于程序设计中的优化策略

Copy-On-Write的基本思路

从一开始大家都在共享同一个内容，当某个人想要修改这个内容时，才会真正把内容Copy 出去形成一个新的内容然后再改，

这是一种延时懒惰策略。

CopyOnWrite 容器

CopyOnWrite 容器即写时复制的容器。

CopyOnWrite 容器非常有用，可以在非常多的并发场景中使用到。

通俗的理解是

当往一个容器添加元素时，

不直接往当前容器添加，

而是先将当前容器进行Copy，复制出一个新的容器，

然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

CopyOnWrite 并发容器的使用场景

适合多读少写的场景

CopyOnWrite 并发容器用于读多写少的并发场景。

比如白名单，黑名单，商品类目的访问和更新场景。

写方法是需要加锁的

CopyOnWriteArrayList 中add/remove 等写方法是需要加锁的，

目的是为了避免Copy 出N 个副本出来，导致并发写。

注意：CopyOnWriteArrayList 的整个add 操作都是在锁的保护下进行的。也就是说add 方法是线程安全的。

读方法是没有加锁的

public E get(int index) { return get(getArray(), index); }

这样做的好处是我们可以对CopyOnWrite 容器进行并发的读，当然，这里读到的数据可能不是最新的。

因为写时复制的思想是通过延时更新的策略来实现数据的最终一致性的，并非强一致性。

CopyOnWriteArrayList和Vector的本质区别

所以CopyOnWrite 容器是一种读写分离的思想，读和写不同的容器

而Vector 在读写时，使用同一个容器，读写互斥，同时只能做一件事儿。

支持高效率并发且是线程安全的

因为通常需要复制整个基础数组，所以可变操作的开销很大

（add()、set() 和remove() 等等）

迭代器，

支持hasNext(), next()等不可变操作

但不支持可变remove()等操作

使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。

在构造迭代器时，迭代器依赖于不变的数组快照。

CopyOnWriteArrayList的特点总结

和ArrayList基本一模一样，但它是线程安全的

CopyOnWriteArrayList 相当于线程安全的ArrayList

CopyOnWriteArrayList 使用了一种叫写时复制的方法

当有新元素add 到CopyOnWriteArrayList 时，先从原有的数组中拷贝一份出来，然后在新的数组做写操作，写完之后，再将原来的数组引用指向到新数组。

任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，这样就不会影响COWIterator中的数据了，不会抛ConcurrentModificationException异常(对set,add没有作用，因为set,add本来就要加锁)，修改完成之后改变原有数据的引用即可。

读操作不加锁，写操作加锁，在进行add,set等操作时，会通过ReentrantLock进行加锁

CopyOnWriteArrayList的缺点

1.复制的数组会消耗内存

2.不能读取实时性的数据

3.会产生大量的对象

CopyOnWriteArraySet

Executor（并发框架）

Future和FutureTask

常见的创建多线程的方式有两种

继承Thread类

实现Runnable接口

创建多线程还有其他三种方式