IBM

Java 理论与实践

IBM 社区的作品看起来不错。对于个人的眼界提升帮助比较大。

本文记录一下学习笔记与心德，便于回顾查阅。

Volatile

聊聊并发（一）深入分析Volatile的实现原理

在多线程并发编程中 synchronized 和 Volatile 都扮演着重要的角色， Volatile 是轻量级的 synchronized(不会引起线程上下文的切换和调度)，它在多处理器开发中保证了共享变量的可见性。 可见性的意思是当一个线程修改一个共享变量时，另外一个线程能读到这个修改的值。

一、术语表

本表用于查阅，后面的实现原理会使用到。仅供查阅。

术语 英文单词 描述
共享变量   在多个线程之间能够被共享的变量被称为共享变量。共享变量包括所有的实例变量，静态变量和数组元素。他们都被存放在堆内存中，Volatile只作用于共享变量。
内存屏障 Memory Barriers 是一组处理器指令，用于实现对内存操作的顺序限制。
缓冲行 Cache line 缓存中可以分配的最小存储单位。处理器填写缓存线时会加载整个缓存线，需要使用多个主内存读周期。
原子操作 Atomic operations 不可中断的一个或一系列操作。
缓存行填充 cache line fill 当处理器识别到从内存中读取操作数是可缓存的，处理器读取整个缓存行到适当的缓存（L1，L2，L3的或所有）
缓存命中 cache hit 如果进行高速缓存行填充操作的内存位置仍然是下次处理器访问的地址时，处理器从缓存中读取操作数，而不是从内存。
写命中 write hit 当处理器将操作数写回到一个内存缓存的区域时，它首先会检查这个缓存的内存地址是否在缓存行中，如果存在一个有效的缓存行，则处理器将这个操作数写回到缓存，而不是写回到内存，这个操作被称为写命中。
写缺失 write misses the cache 一个有效的缓存行被写入到不存在的内存区域。

二、底层原理

处理器为了提高处理速度，不直接和内存进行通讯，而是先将系统内存的数据读到内部缓存（L1,L2或其他）后再进行操作，但操作完之后不知道何时会写到内存， 如果对声明了 Volatile 变量进行写操作，JVM 就会向处理器发送一条 Lock 前缀的指令，将这个变量所在缓存行的数据写回到系统内存。但是就算写回到内存， 如果其他处理器缓存的值还是旧的，再执行计算操作就会有问题，所以在多处理器下，为了保证各个处理器的缓存是一致的，就会实现缓存一致性协议， 每个处理器通过嗅探在总线上传播的数据来检查自己缓存的值是不是过期了，当处理器发现自己缓存行对应的内存地址被修改，就会将当前处理器的缓存行设置成无效状态， 当处理器要对这个数据进行修改操作的时候，会强制重新从系统内存里把数据读到处理器缓存里。

Synchronized

一、术语表

术语 英文 说明
CAS Compare and Swap 比较并设置。用于在硬件层面上提供原子性操作。在 Intel 处理器中，比较并交换通过指令cmpxchg实现。比较是否和给定的数值一致，如果一致则修改，不一致则不修改。

二、锁的基础

Java SE1.6中的Synchronized

Java 中的每一个对象都可以作为锁。

  • 对于同步方法，锁是当前实例对象。

  • 对于静态同步方法，锁是当前对象的Class对象。

  • 对于同步方法块，锁是 Synchonized 括号里配置的对象。

当一个线程试图访问同步代码块时，它首先必须得到锁，退出或抛出异常时必须释放锁。那么锁存在哪里呢？锁里面会存储什么信息呢？

三、各种锁的对比

锁会依次递增，且不会回退。(为了避免无用的自旋)

锁 优点 缺点 适用场景
偏向锁 加锁和解锁不需要额外的消耗，和执行非同步方法比仅存在纳秒级的差距 如果线程间存在锁竞争，会带来额外的锁撤销的消耗 适用于只有一个线程访问同步块场景
轻量级锁 竞争的线程不会阻塞，提高了程序的响应速度 如果始终得不到锁竞争的线程使用自旋会消耗CPU 追求响应时间。同步块执行速度非常快
重量级锁 线程竞争不使用自旋，不会消耗CPU 线程阻塞，响应时间缓慢 追求吞吐量。同步块执行速度较长

ReentrantLock

JDK 5.0 中更灵活、更具可伸缩性的锁定机制

ConcurrentHashMap

深入分析ConcurrentHashMap

ConcurrentHashMap 实现在 JDK 1.6/1.7/1.8 中差异较大。

一、术语

术语 英文 解释
哈希算法 hash algorithm 是一种将任意内容的输入转换成相同长度输出的加密方式，其输出被称为哈希值
哈希表 hash table 根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址

二、线程不安全的 HashMap

Atomic

原子操作的实现原理

一、术语

术语名称 英文 解释
缓存行 Cache line 缓存的最小操作单位
比较并交换 Compare and Swap CAS操作需要输入两个数值，一个旧值（期望操作前的值）和一个新值，在操作期间先比较下在旧值有没有发生变化，如果没有发生变化，才交换成新值，发生了变化则不交换。
CPU流水线 CPU pipeline CPU流水线的工作方式就象工业生产上的装配流水线，在CPU中由5~6个不同功能的电路单元组成一条指令处理流水线，然后将一条X86指令分成5~6步后再由这些电路单元分别执行，这样就能实现在一个CPU时钟周期完成一条指令，因此提高CPU的运算速度。
内存顺序冲突 Memory order violation 内存顺序冲突一般是由假共享引起，假共享是指多个CPU同时修改同一个缓存行的不同部分而引起其中一个CPU的操作无效，当出现这个内存顺序冲突时，CPU必须清空流水线。

二、处理器如何实现原子操作

  • 处理器会自动保证基本的内存操作的原子性

  • 第一个机制是通过总线锁保证原子性

所谓总线锁就是使用处理器提供的一个 LOCK＃ 信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住,那么该处理器可以独占使用共享内存。

  • 第二个机制是通过缓存锁定保证原子性

Fork/Join

Fork/Join框架介绍

Fork 就是把一个大任务切分为若干子任务并行的执行，Join 就是合并这些子任务的执行结果，最后得到这个大任务的结果。

比如计算 1+2+…＋10000，可以分割成 10 个子任务，每个子任务分别对 1000 个数进行求和，最终汇总这 10 个子任务的结果。

工作窃取算法

工作窃取（work-stealing）算法是指某个线程从其他队列里窃取任务来执行。

工作窃取算法的优点是充分利用线程进行并行计算，并减少了线程间的竞争，其缺点是在某些情况下还是存在竞争。

框架简介

如果让我们来设计一个 Fork/Join 框架，该如何设计？

1、分割任务。首先我们需要有一个 fork 类来把大任务分割成子任务，有可能子任务还是很大，所以还需要不停的分割，直到分割出的子任务足够小。

2、执行任务并合并结果。分割的子任务分别放在双端队列里，然后几个启动线程分别从双端队列里获取任务执行。子任务执行完的结果都统一放在一个队列里，启动一个线程从队列里拿数据，然后合并这些数据。

Fork/Join 使用两个类来完成以上两件事情：

ForkJoinTask：我们要使用 Fork/Join 框架，必须首先创建一个 ForkJoin 任务。它提供在任务中执行 fork() 和 join() 操作的机制， 通常情况下我们不需要直接继承 ForkJoinTask 类，而只需要继承它的子类，Fork/Join 框架提供了以下两个子类：

  • RecursiveAction：用于没有返回结果的任务。

  • RecursiveTask ：用于有返回结果的任务。

ForkJoinPool ：ForkJoinTask 需要通过 ForkJoinPool 来执行，任务分割出的子任务会添加到当前工作线程所维护的双端队列中，进入队列的头部。 当一个工作线程的队列里暂时没有任务时，它会随机从其他工作线程的队列的尾部获取一个任务。

例子

  • CountTask.class
public class CountTask extends RecursiveTask {

    private static final int THRESHOLD = 2; //阈值

    private int start;

    private int end;

    public CountTask(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    protected Integer compute() {
        int sum = 0;

        //如果任务足够小就计算任务
        boolean canCompute = (end - start) <= THRESHOLD;

        if (canCompute) {
            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();

            //等待子任务执行完，并得到其结果
            Integer leftResult = (Integer) leftTask.join();
            Integer rightResult = (Integer) rightTask.join();

            //合并子任务
            sum = leftResult + rightResult;
        }

        return sum;
    }

}
  • main()
public static void main(String[] args) {
    ForkJoinPool forkJoinPool = new ForkJoinPool();

    //生成一个计算任务，负责计算1+2+3+4
    CountTask task = new CountTask(1, 4);

    //执行一个任务
    Future result = forkJoinPool.submit(task);

    try {

        System.out.println(result.get());

    } catch (InterruptedException | ExecutionException e) {
        e.printStackTrace();
    }
}

Copy-On-Write

Copy-On-Write简称 COW，是一种用于程序设计中的优化策略。

通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

优点：可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。

缺点：

  • 内存占用问题

  • 数据一致性问题

只能保证数据的最终一致性，不能保证数据的实时一致性。

生产者消费者模式

生产者消费者模式是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯，而通过阻塞队列来进行通讯，所以生产者生产完数据之后不用等待消费者处理， 直接扔给阻塞队列，消费者不找生产者要数据，而是直接从阻塞队列里取，阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。