基本概念

同步(Synchronous)和异步(Asynchronous)

同步：调用方必须等到方法调用返回后才能继续下一步。
异步：调用方调用方法后不需要等待返回结果。

并发(Concurrency)和并行(Parallelism)

• 并发：多个任务交替执行。
• 并行：多个任务同时进行，只有多CPU系统才能实现并行（比如多核CPU）。

临界区

公共资源或共享数据，可以被多个线程使用，但是每一次只能有一个线程使用它，一旦临界区资源被占用，其他线程想要使用这个资源，就必须等待。

在并行程序中，临界区资源是保护的对象。

阻塞(Blocking)和非阻塞(Non-Blocking)

阻塞和非阻塞通常用来形容多线程间的相互影响。
比如：一个线程占用了临界区资源，那么所有需要这个资源的线程就必须在这个临界区中等待。等待会导致线程挂起，这种情况就是阻塞。

非阻塞与阻塞相反，强调没有一个线程可以妨碍其他线程执行。所有的线程都会尝试不端向前执行。

死锁(DeadLock)、饥饿(Starvation)和活锁(LiveLock)

都属于多线程的活跃性问题。

死锁：多个线程所需要的锁被对方占有，相互等待对方释放锁。
饥饿：一个或多个线程因为种种原因（如线程优先级太低、或某个线程一直占着关键资源不放）无法获得所需的资源，导致一直无法执行。
活锁：多个线程不断的主动将资源释放给对方使用，导致资源不断地在线程间跳动，而没有一个线程可以同时拿到所有资源正常执行。

并发级别

根据控制并发的策略，可以对并发的级别进行分类
参考文章：
无锁编程技术及实现
Lock-Free and Wait-Free, definition and examples

阻塞(Blocking)

一个线程是阻塞的，那么其他线程释放资源之前，当前线程无法继续执行。如使用synchronized关键字、可重入锁。

缺点：会存在饥饿情况。

无饥饿(Starvation-Free)

使用公平锁，按顺序获取资源，就能避免饥饿。
阻塞是悲观策略。无阻塞是乐观策略。

缺点：还是会有阻塞。

无障碍(Obstruction-Free)

最弱的非阻塞调度。都可以无限制进入临界区，一旦检测到发生并发修改数据的情况，会进行回滚，保证数据安全。

一种可行的无障碍实现：依赖一个"一致性标记"，线程操作前读取并保存该标记，操作完成后，再次读取并检查该标记是否被更改过，如果不一致，说明被更改过，需要重试操作。任何对临界区资源有修改操作的线程，在修改数据前都需要更新这个“一致性标记”。

缺点： 冲突比较多时，会不断的进行回滚，导致都无法走出临界区。

无锁(Lock-Free)

在无障碍的基础上，保证必然有一个线程能够在有限步内完成操作离开临界区。

// 如果修改不成功，那么循环永远不会停止。
while(atomicVar.compareAndSet(localVar, locaVar+1)){
    localVar = atomicVar.get();
}

缺点：会出现类似于饥饿的情况。

无等待(Wait-Free)

在无锁的基础上，要求所有的线程都必须在有限步内完成，这样就不会引起饥饿问题。如果限制步骤上限，可分为有界无等待和线程数无关的无等待，区别只是对循环次数的限制不同。
典型的无等待：++RCU(read-copy-update)++.对读线程不加限制，都是无等待的，写线程需要先取得原始数据的副本，接着只修改副本数据(所以读可以不加限制)，修改完成后在合适的时机回写数据。

Amdahl定律

加速比 = 优化前耗时/优化后耗时
加速比公式：

Tn = T1(F+\frac{1}{n}(1-F))=\frac{1}{F+\frac{1}{n}(1-F) }

n为CPU的数量，F为程序中串行执行的比例，T1为优化后耗时（只有一个CPU执行），Tn为加速后耗时。
结论：当n无限大时，F越小，加速比越大。仅仅添加CPU对性能影响不是特别大，必须加大并行比例。

Gustafson定律

串行执行时=a
并行时间=b
执行时间=a+b
串行比例=F

F=\frac{a}{a+b}

S(n)=\frac{a+nb}{a+b} = \frac{a}{a+b}+\frac{nb}{a+b}

=F+n(\frac{a+b-a}{a+b})=F+b(1-\frac{a}{a+b})

=F+n-nf 

=n-F(n-1)

结论：如果串行比例很小，那么加速比就是处理器的个数。只要不断地累加处理器，就能获得更快得速度。

Amdahl强调：当串行化比例一定时，加速比是有上限的，不管堆多少cpu都不能突破这个上限。
Gustafson强调：如果可被并行化的代码所占比重足够多，那么加速比就能随着CPU的数量线性增长。

串行化比例为1时，加速比都是1，串行化比例为0时，加速比都是n

JMM（java内存模型）

JMM是为了保证多个线程间可以有效地、正确地协同工作，定义的一组规则。
JMM的关键技术点都是围绕多线程的原子性、可见性和有序性来建立的。
参考文章 Memory Model

原子性

指一个操作是不可中断的，即使多个线程一起执行，一个操作一旦开始就不会被其他线程干扰。

在32系统中，long型数据的读写不是原子性的（因为long有64位）。

可见性

可见性是指当一个线程修改了某一个共享变量的值，其他线程是否能够立即知道这个修改。

缓存优化、编译器优化、硬件优化和指令重排都有可能导致一个线程的修改不会立即被其他线程察觉。

有序性

指令重排：为了提高CPU处理性能，指令可能会被重新排序，指令重排会保证串行语义一致性，
不会使串行的语义逻辑发生问题，遵守Happen-Before原则，但不保证多线程间的语义也一致。

//  如果不加volatile，线程ReadT已经读到ready为false，当主线程修改ready为true后，线程ReadT并不能知道，主线程将一直执行。
private static volatile boolean ready;
private static int number = 0;
public static class ReadT extends Thread{
    @Override
    public void run() {
        while (!ready);
        System.out.println(number);
    }
}
public static void main(String[] args) throws InterruptedException {
    new ReadT().start();
    Thread.sleep(1000);
    number = 42;
    ready = true;
}

volatile 可以保证可见性，不能保证原子性。能禁止指令重排序（所以能在一定程度上保证有序性），但只能保证volatile所修饰的变量之前的程序不会在该变量之后执行，该变量之后的代码不会在变量之前执行。
synchronized 可以保持原子性、可见性和有序性。

Happen-Before原则

指令重排的原则（保证指令重排不会破坏原有的语义结构）：

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