一.CopyOnWriteArrayList

以CopyOnWriteArrayList为突破口，看一下CopyOnWrite容器的特点

1.CopyOnWrite的含义

CopyOnWrite的意思是，当容器需要被修改的时候，不直接修改当前容器，而是将当前容器进行Copy，复制出一个新的容器，然后修改新的容器，完成修改之后，再将原容器的引用指向新的容器。

2.适用场景

• 读操作可以尽可能的快,而写操作慢一些也没有关系:为了将读取的性能发挥到极致,CopyOnWriteArrayList读取是完全不用加锁的,并且写入也不会阻塞读操作,也就是说可以在写入的同时进行读取.只有写入和写入之间需要进行同步,也就是不允许多个写入同时发生,所以会更慢一些
• 读多写少:写入本身是会拷贝一份出来,会增加资源的消耗,同时多个写入之间需要进行同步,所以应该尽可能的少

3.特点

• 迭代期间允许修改集合内容:ArrayList在迭代期间如果修改集合的内容,会抛出Concurrent-ModificationException异常的;

 此处有一道经典的如何在遍历List期间删除元素的问题

 答: 迭代器在迭代过程中会检查集合是否被修改,如果检测到修改,则会抛出异常;解决:1.Iterator.remove() 2.Java8可以使用removeIf()方法

• CopyOnWriteArrayList的迭代器在迭代的时候,如果数组内容被修改, CopyOnWriteArrayList不会报ConcurrentModificationException的异常, 因为迭代器使用的依然是旧数组,只不过迭代的内容可能已经过时了

4.缺点:

CopyOnWrite容器的缺点:

• 内存占用问题:因为CopyOnWrite的写时复制机制,所以在进行写操作的时候,内存会同时驻扎两个对象的内存,这一点会占用额外的内存空间
• 数据一致性问题:由于CopyOnWrite容器的修改是先修改副本,所以这次修改对于其他线程来说并不是实时能够看到的,只有在修改完之后才能体现出来.如果希望写入的数据马上能被其它线程看到,CopyOnWrite容器是不适用的

二.ConcurrentLinkedQueue

• 实现一个线程安全的队列有两种方式:一种是使用阻塞算法,另一种是使用非阻塞算法
• 阻塞算法的队列可以用一个锁(入队和出队用一把锁)或者两个锁(入队和出队用不同的锁)等方式来实现.
• 非阻塞的实现方式则可以使用循环CAS的方式来实现

ConcurrentLinkedQueue是使用非阻塞的方式来实现的,所以ConcurrentLinkedQueue是非阻塞队列

public boolean offer(E e) {
    checkNotNull(e); // 检查元素是否为null，如果是null则抛出NullPointerException
    final Node<E> newNode = new Node<E>(e); // 创建包含新元素的新节点
    for (Node<E> t = tail, p = t;;) { // 无限循环，从尾节点开始遍历
        Node<E> q = p.next; // 获取p的下一个节点
        if (q == null) { // 如果p的下一个节点为null，说明p是尾节点
            if (p.casNext(null, newNode)) { // CAS操作：尝试将p的next设置为newNode
                if (p != t) // 如果p不是原来的尾节点
                    casTail(t, newNode); // 更新尾节点为newNode
                return true; // 添加成功，返回true
            }
            // CAS失败，说明有其他线程已经修改了p的next，重新读取next
        } else if (p == q) { // 如果p等于q，表示我们"掉出"了列表（p的next指向自己）
            // 如果tail没有改变，则需要跳到head，因为所有活动节点总是可以从head到达
            // 否则，新的tail是更好的选择
            p = (t != (t = tail)) ? t : head;
        } else {
            // 检查tail是否更新，如果tail已更新则p指向新的tail，否则p指向q
            p = (p != t && t != (t = tail)) ? t : q;
        }
    }
}

关键点解析:

1. CAS非阻塞算法：与传统的锁机制不同，这里使用CAS操作来实现线程安全，避免了线程阻塞和上下文切换的开销。
2. 自旋机制：使用无限循环(for(;;))来处理CAS失败的情况，不断尝试直到操作成功。
3. 尾节点更新：
4. tail指向队列的最后一个节点
5. 当添加新节点时，需要更新tail指向新的尾节点
6. "掉出"列表的处理：当p == q时，表示我们已经"掉出"了链表（可能是其他线程修改了链表结构），这时需要重新定位到head或新的tail。

这种适合于不需要阻塞功能，且并发不是特别剧烈的场景(如果并发过高会导致线程长时间自旋而导致大量CPU开销)

三.阻塞队列BlockingQueue

阻塞队列简介

阻塞队列是一个支持两个附加操作的队列，即支持阻塞的插入和移除方法

1. 支持阻塞的插入方法:当队列满时，队列会阻塞插入元素的线程，直到队列不满
2. 支持阻塞的移除方法:在队列为空时，获取元素的线程会等待线程变为非空

• 抛出异常:当队列满时，如果再往队列里插入元素，会抛出IllegalStateException("Queue fu")异常。当队列空时，从队列里获取元素会抛出NoSuchElementException异常。
• 返回特殊值:当往队列插入元素时，会返回元素是否插入成功，成功返回true。如果是移 除方法，则是从队列里取出一个元素，如果没有则返回nulle
• 一直阻塞:当阻塞队列满时，如果生产者线程往队列里put元素，队列会一直阻塞生产者 线程，直到队列可用或者响应中断退出。当队列空时，如果消费者线程从队列里take元素，队 列会阻塞住消费者线程，直到队列不为空。
• 超时退出:当阻塞队列满时，如果生产者线程往队列里插入元素，队列会阻塞生产者线程 一段时间，如果超过了指定的时间，生产者线程就会退出。

阻塞队列的实现原理

如果队列是空的，消费者会一直等待，当生产者添加元素时，消费者是如何知道当前队列有元素的呢?

使用通知模式实现。所谓通知模式，当消费者从空的队列获取元素时会阻塞住消费者，此时如果生产者放入一个元素入队列，则需要通知阻塞住消费者当前有元素可取。同理当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用

• 通过查看JDK源码可以发现ArrayBlockingQueue使用了Condition来实现

四.Fork/Join框架

其是一个用于并行执行任务的框架，是一个把大任务分割为若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架

Fork/Join框架内部自己实现用到了工作窃取算法

• 工作窃取(work-stealing)算法是指某个线程从其他队列里窃取任务来执行。
• 那么，为什么 需要使用工作窃取算法呢?
• 假如我们需要做一个比较大的任务，可以把这个任务分割为若干 互不依赖的子任务，为了减少线程间的竞争把这些子任务分别放到不同的队列里，并为每个 队列创建一个单独的线程来执行队列里的任务，线程和队列一一对应。
• 比如A线程负责处理A 队列里的任务。但是，有的线程会先把自己队列里的任务干完，而其他线程对应的队列里还有任务等待处理。干完活的线程与其等着，不如去帮其他线程干活，于是它就去其他线程的队列 里窃取一个任务来执行。
• 而在这时它们会访问同一个队列，所以为了减少窃取任务线程和被 窃取任务线程之间的竞争，通常会使用双端队列，被窃取任务线程永远从双端队列的头部拿任务执行，而窃取任务的线程永远从双端队列的尾部拿任务执行

使用Fork/Join框架的示例

通过一个简单的需求来使用Fork/]oin框架，需求是:计算1+2+3+4的结果使用Fork/join框架首先要考虑到的是如何分割任务，如果希望每个子任务最多执行两个 数的相加，那么我们设置分割的阈值是2，由于是4个数字相加，所以Fork/]oin框架会把,这个任 务fork成两个子任务，子任务一负责计算1+2，子任务二负责计算3+4，然后再join两个子任务 的结果。因为是有结果的任务，所以必须继承RecursiveTask，实现代码如下。

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.Future;
import java.util.concurrent.RecursiveTask;

public class CountTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 2;//阈值
    private int start;
    private int end;
    public CountTask(int start, int end) {
        this.start = start;
        this.end = end;
    }

    //必须重写compute()方法
    @Override
    protected Integer compute() {
        int sum=0;
        //如果任务足够小，则直接计算
        if(end-start<=THRESHOLD){
            for(int i=start;i<=end;i++){
                sum+=i;
            }
        }else{
            //如果任务大于阈值，则进行任务拆分
            int middle=(start+end)/2;
            CountTask leftTask = new CountTask(start, middle);
            CountTask rightTask = new CountTask(middle+1, end);
            leftTask.fork();
            rightTask.fork();
            //合并子任务
            sum=leftTask.join()+rightTask.join();
        }
        return sum;
    }
    public static void main(String[] args) {
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        //生成一个计算任务，负责计算1+2+3+4
        CountTask task = new CountTask(1, 4);
        //执行一个任务
        Future<Integer> result = forkJoinPool.submit(task);
        try {
            System.out.println(result.get());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

ForkJoinTask:ForkJoinTask与一般任务的主要区别在于它需要实现compute方法，在这个方法里，首先需要判断任务是否足够小，如果足够小就直接执行任务。如果不足够小，就必须分割成两个子任务，每个子任务在调用fork方法时，又会进入compute方法，看看当前子任务是否需要继续分割成子任务，如果不需要继续分割，则执行当前子任务并返回结果。使用join方法会等待子任务执行完并得到其结果。

Fork/Join实现原理

• ForkJoinPool由ForkJoinTask和ForkJoinWorkerThread数组组成
• ForkJoinTask数组负责将存放程序提交给ForkJoinPool的任务

compute方法里写的就是存放程序，ForkJoinPool可以看作一个线程池，compute程序经过ForkJoinTask包装之后就是一个个的任务，而ForkJoinPool里面存放的线程负责执行这一个个的任务

• 而ForkJoinWorkerThread数组负责执行这些任务