wch的个人主页

# 并发编程（一）：并行计算概念

# 何去何从的并行计算

# 并行存在的意义

与串行程序不同，并行程序的设计和实现异常复杂，不仅仅体现在程序的功能分离上，多线程间的 协调性、乱序性，都会成为程序正确执行的阻碍。但是与一般的用户终端程序相比，服务端程序需要承受更重的用户访问压力，面对复杂的业务模型，并行程序会比串行程序更容易适应业务需求，更容易模拟我们的现实世界。

# 硬件的推波助澜

就目前的科技水平而言，CPU 的计算性能已经到达极限。我们已经不再追求单核的计算速度，而是着迷于如何将多个独立的计算单元整合到单独的 CPU 中，也就是我们所说的 多核CPU。由此，并行计算就会很自然的推广开来。如何让多个 CPU 有效并且正确的 协调工作？多线程间如何保证 线程安全？如何正确理解线程间的 无序性、可见性，如何尽可能提高并行程序设计，如何将串行程序改造为并行程序？而对并行计算的研究，也就是希望在这片黑暗中带来光明。

# 并行计算基本概念

# 同步和异步

同步和异步通常用来形容一次方法调用。

  • 同步方法调用：一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。
  • 异步方法调用：更像是一个消息传递，一旦开始，方法调用就会立即返回，调用者可以继续后续的操作，而异步方法通常会另在另一个线程中 真实地执行，如果需要返回结果，那么当异步调用真实完成时，则会通知调用者。

# 并发与并行

  • 并发：偏重于多个任务，交替执行，多个任务之间可能还是串行的。
  • 并行：是真正意义上的同时执行。

# 临界区

用来表示一种 公共资源，或是共享数据，一旦临界区资源被某个线程占用，其他线程想要使用这个资源就必须 等待。

# 阻塞和非阻塞

通常用来形容多线程间的相互影响，

  • 阻塞：如一个线程占用的临界区资源，那么其他需要这个资源的线程就必须在这个资源的临界区中进行等待。等待会导致线程挂起，这种情况就是阻塞。
  • 非阻塞：强调没有一个线程能够妨碍其他线程执行。

# 死锁

多个线程持有彼此需要的资源不肯释放。

# 饥饿

线程因为种种原因无法获得其所需的资源，导致一直无法执行。

  • 线程 优先级 过低，其它高优先级线程一直占有资源。
  • 某一个线程一直占用关键资源不肯释放。

# 活锁

多个线程秉持 谦让 的原则，主动将资源释放给对方使用，导致资源不断在多个线程之间跳动，没有一个线程能同时拿到所有资源而正常执行。

# 并发级别

  • 阻塞：在所需资源被释放前，当前线程无法继续执行。
  • 无饥饿：锁是 公平 的，满足先来后到，不允许高优先级线程插队优先获取资源。
  • 无障碍：允许多个线程进入临界区，无障碍的线程一旦检测到数据修改冲突，则对自己的修改进行 回滚，确保数据安全，进行重试。如果没有发生数据竞争，则可以完成修改操作。
  • 无锁：CAS (Compare And Set)，线程可能会通过一个无线循环来尝试修改变量，如果没有冲突则修改成功，否则继续尝试修改。

# 无等待

无等待要求所有线程在有限步内完成。通过限制步骤上限来避免饥饿问题。

# CPU 高速缓存

CPU 执行速度很快，而从内存读取数据和向内存写入数据的过程跟 CPU 执行指令的速度比起来要慢的多。CPU 高速缓存的出现是为了缓解 CPU 和内存之间速度不匹配的问题（CPU - cache - memory）。 当程序运行时，会将需要的数据从主存中复制一份到 CPU 的高速缓存中，当 CPU 执行指令时直接在缓存中存取数据，在之后的某个时间点，再将缓存中的数据刷新到主存中。 CPU高速缓存

# Java 内存模型（JMM）

为了应对并发程序下一致性和安全性挑战，JMM (Java Memory Model) 定义了在并行机制下多个线程间有效、正确协同工作的规则。

# 原子性

原子性指一个操作是不可中断的，即使在多线程的情况下也不会被干扰。

# 可见性

可见性指当一个线程修改了一个共享变量的值，其它线程是否能够知道这个修改。CPU缓存优化 （CPU 高速缓存）、 指令重排 等都可能导致数据修改不能立刻被其它使用的线程察觉。

# 有序性

程序在执行时，有可能会进行指令重排，CPU 指令执行的顺序不一定和程序的顺序一致。指令重排保证 串行语义一致 （即重排后执行的指令与程序真正执行顺序的语义一致），但不保证多线程语义一致。

# 为什么要指令重排

指令执行是分多个步骤的：

  • 取值 IF
  • 译码和取寄存器操作数 ID
  • 执行和有效地址计算 EX
  • 存储器访问 MEM
  • 写回 WB

在 CPU 实际工作时，可能使用不同硬件来执行这些步骤，为了提升执行性能，通过流水线执行： CPU指令执行流水线 执行取值操作的硬件 m 在指令 A 中取值完成后，由硬件 n 执行指令 A 的译码，而硬件 m 接着去执行指令 B 的取值。 流水线操作可以高效提升性能，但是如果发生中断，所有硬件设备会进入一个停顿期，严重影响性能： CPU指令流水线中断 类似一个 A = B + C 的操作，LW 表示 load，如 LW R1 B 表示将 B 的值加载到 R1 寄存器，ADD R3 R2 R1 表示把 R2、R1 的值相加，并放到 R3 中。SW 表示 store，SW A R3 就是把 R3 寄存器的值保存到变量 A 中。ADD 操作在执行时由于 LW R2 C 指令没有执行完成，R2 中的数据没有准备好，所以发生了停顿，后面的指令因此都慢了一个节拍。

指令重排后的CPU流水线

而通过对 CPU 指令顺序进行重排，即有可能 在不影响程序语义的情况下消除停顿。由此可见，指令重排对提高 CPU 处理性能是十分必要的。

# Happens-Before 规则

并非所有指令都可以进行重排，指令重排有一定的规则：

  • 程序顺序原则，一个线程内保证语义的串行性。
  • volatile 原则：volatile 变量的写，先发生于读，保证了变量的可见性。
  • 锁规则：解锁，必然发生于随后的加锁前
  • 传递性，a 先于 b，b 先于 c，那么 a 必然先于 c
  • 线程的 start() 方法先于它的每一个动作
  • 线程的所有操作先于线程的终结（Thread.join()）
  • 线程的中断先于被中断线程的代码
  • 对象的构造函数执行、结束，先于 finalize() 方法

# Java 并行程序基础

# 进程

进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在面向进程设计的计算机结构中，进程是程序的基本执行实体；在面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。

# 线程

线程（Thread）是轻量级进程，是程序执行的最小单位。因为线程间切换和调度的成本远小于进程，所以使用多线程去进行并发程序设计。

# 线程状态

  • NEW：线程创建，还没开始执行。
  • RUNNABLE：线程执行状态，此时所需的一切资源都已经准备好了。
  • BLOCKED：线程在执行过程中遇到 synchronized 同步块，进入阻塞状态，线程暂停执行，直到获取请求的锁。
  • WAITING：线程进入无时间限制的等待。
  • TIMED_WAITING：线程进入有时限的等待。
  • TERNIMATED：线程结束。

线程状态转换

# 线程创建

  • 继承 Thread 类
  • 实现 Runnable 接口
  • 实现 Callable 接口

# 线程停止

使用线程的 stop() 方法可以立即停止线程，但是是在线程执行过程中停止，容易造成数据不一致的问题，不建议使用。

# 线程中断

使用线程的 interrupt() 方法通知线程中断，收到中断通知的线程不会立即退出，而是由线程自行决定退出时机，为了避免造成数据不一致的问题，通过 isInterrupted() 方法获取线程的中断状态。wait()、sleep() 等方法被中断会抛出 InterruptedException 异常，此异常会清除线程的中断标记。

# 等待（wait）和通知（notify）

Object 类提供了 wait() 和 notify() 方法，意味任何对象都能调用这两个方法， wait() 方法必须包含在 synchronized 语句块中，只有获取了目标对象的监视器，才能调用这两个方法。当在一个对象实例上调用 wait() 方法，当前线程就会进入目标对象的等待队列，此队列可能会包含多个等待目标对象的线程，当 notify() 方法被调用，就会从等待队列中随机唤醒一个线程，继续执行。当对象的 notifyAll() 方法被调用，等待队列中的所有对象都会被唤醒。

# wait() 和 sleep() 的区别
  • wait() 方法可被唤醒，sleep() 方法只能一直休眠到指定时间。
  • wait() 方法会释放目标对象的锁，sleep() 方法不会释放任何资源。

# 挂起（suspend）和继续执行（resume）

使用线程的 suspend() 方法会使线程暂停，但是并不会释放任何锁资源，直到执行此线程的 resume() 方法，如果 resume() 方法先于 suspend() 方法执行，那么线程就无法被唤醒从而继续执行，也不会释放占有的锁资源，而从线程状态上看，居然还是 RUNNABLE，所以不建议使用挂起的方式去操作线程。

# 等待结束（join）

在某些时候，一个线程的输入可能会依赖其它线程的输出，这就需要通过使用被依赖线程的 join() 方法加入当前线程，等待被依赖线程执行结束。

# 谦让（yield）

使用线程的 yield() 方法会使线程让出 CPU，但不是暂停执行，线程还会进行 CPU 的争夺。如果一个线程不那么重要，或者对应任务的优先级非常低，或者不希望它占用过多的资源，就可以使用 yield() 方法给予其它线程更多的执行机会。

# 线程组

使用线程组可以对线程进行分组，从而方便管理。

ThreadGroup tg = new ThreadGroup("tg");
Thread t1 = new Thread(tg, "T1");

# 守护线程（daemon）

守护线程是一种特殊的线程，是系统的守护者，在后台默默完成一些系统性的服务，如垃圾回收、JIT 等。如果用户线程全部结束，那么整个应用程序也应该结束，守护线程也会退出。

Thread t = new Thread();
// 必须在执行 start() 方法之前设置为守护线程
t.setDaemon(true);
t.start();

# 线程优先级

Java 中的线程可以有优先级，优先级高的线程在竞争资源时会更有优势。线程优先级的范围为 1~10 ，数字越大优先级越高。

/**
 * The minimum priority that a thread can have.
 */
public final static int MIN_PRIORITY = 1;

/**
 * The default priority that is assigned to a thread.
 */
public final static int NORM_PRIORITY = 5;

/**
 * The maximum priority that a thread can have.
 */
public final static int MAX_PRIORITY = 10;

# volatile

使用 volatile 关键字可以通知虚拟机不能随意变动、优化目标指令，被此关键字修饰的变量被修改后，应用程序范围内所有的线程都能“看到”这个改动。volatile 关键字主要作用包括：

  • 保证可见性：对修饰变量的修改能为其它线程所知，但是写冲突仍可能导致错误。
  • 保证有序性：不能随意变动、优化指令。

# synchronized

当多个线程同时写一个数据时，容易产生写冲突，Java 提供了用于线程间同步的关键字 synchronized ，它的作用是对同步代码进行加锁，使得每次只能有一个线程进入同步代码块，从而保证线程间的安全性，synchronized 关键字有多种用法：

  • 指定加锁对象：对给定对象加锁，进入同步代码块前需要获取给定对象的锁。
  • 直接作用于实例方法，相当于对当前实例加锁，进入同步代码块前需要获取当前实例的锁。
  • 直接作用于静态方法：相当于对当前类加锁，进入同步代码块前需要获取当前类的锁。 synchronized 限制每次只有一个线程可以访问同步代码块，因此即使进行指令重排，串行语义是不会改变的，被 synchronized 限制的多个线程又可看做是顺序执行的，能够保证可见性和有序性。

← 并发编程（二）：JDK支持 →