Java高并发设计(一)——几个重要的概念

飞奔的炮台

本系列博客我们将介绍Java的高并发设计，当然，在介绍高并发之前，我们可能需要先明白为什么需要高并发？高并发有什么作用？那么首先我们先看看下面两个例子：
1、图像处理：一张 1024*768 像素的图片，包含多达 78 万 6 千多个像素，我们即使将所有的像素都遍历一遍，也得花大量的时间，更何况，图像处理会涉及到大量的矩阵计算，矩阵的规模和数量都非常大，这么大密集的计算，我们该怎么去解决？
2、淘宝双十一：2014年根据淘宝的数据，在双十一当天，支付宝核心数据库集群处理了 41 亿个事务，执行了 285 亿次 SQL,生成了 15TB的日志，访问了 1931 亿次内存数据块，13 亿个物理读。如此密集的访问，我们又该如何去解决呢？
很明显，对于上面的第一个例子，我们使用单核CPU单线程也能解决，只不过会花费巨大的时间，但是对于淘宝双十一的处理，一天的时间处理这么多数据，依据目前的计算机水平，单个计算机是绝对无法解决的。因此，并行计算是目前解决问题的唯一出路。
1、摩尔定律的失效
摩尔定律是由英特尔创始人之一戈登.摩尔提出来的：集成电路上可容纳的晶体管数据，约每隔 24 个月便会增加一倍，后来英特尔首席执行官大卫.豪斯提出：每隔18个月会将芯片的性能提高一倍（更多的晶体管使其更快）。
总结来说：每隔18-24个月，计算机的性能就将翻一倍。
摩尔定律并不是经过严格的物理或数据推导得出来的，而是基于人为的观测数据后，对未来的预测，摩尔定律的有效性一直持续了半个世纪，直到2004年Intel 宣布取消 4GHz 的研发计划，因为目前的硅电路而言，制造工艺已经达到纳米级别了，而目前的科技水平，如果无法在物质分子层面以下进行工作，那么 4GHz 的芯片已经接近了理论极限。1 纳米 = 10-9米，而即使是一个水分子，它的直径也有 0.4 纳米。
因此摩尔定律在 CPU 的计算性能上可能已经失效，虽然现在Intel 已经研制出了 4GHz 的芯片，但是没有重大的技术突破，CPU 的主频提升还是遇到了很大的瓶颈。
2、多核CPU
摩尔定律的失效，意味着很难在单个CPU的技术上取得重大的性能提升了，但是这个时候多核CPU产生了，我们不在追求单核CPU的计算速度，但是我们可以将多个独立的计算单元整合到一个CPU中，也就是我们所说的多核CPU，摩尔定律在另一个侧面生效了，我们可以预测，每过18-24个月，CPU的核心数便会翻一倍，那么计算机的性能也会提高一倍。
这种情况顶级计算机科学家唐纳德.尔文.克努斯（Donald Ervin Knuth）这样评价：这种现象（并发）或多或少是由于硬件设计者已经无计可施了导致的，他们将摩尔定律失效的责任推脱给软件开发者。
硬件工程师通过将多个CPU内核塞进一个CPU的奇妙想法，并行计算就被自然的推广开来了，但是随之而来的问题也层出不穷，程序员的黑暗也随之到来，因为简化的硬件设计方案必然会带来软件设计的复杂性。换句话说，软件工程师正在为硬件工程师无法完成的工作负责。
因为如何让多个CPU正确并有效的工作，多线程如何保证线程安全，如何提高并行程序的性能等等，都是程序员在软件设计中必须考虑的问题。接下来我们将介绍并行计算中的几个重要的概念。
3、同步(Synchronous)和异步(Asynchronous)
同步：同步方法调用一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。
异步：异步方法更像一个消息传递，一旦开始，方法调用就会立即返回，调用者就可以继续后续的操作。

4、并发(Concurrency)和并行(Parallelism)
并发：指两个或多个事件在一个时间段内发生；
并行：指两个或多个事件在同一时刻发生（同时发生）。

并发和并行都可以表示两个任务一起执行，但是偏重点不同，并发偏重于多个任务交替执行，而多个任务之间有可能还是串行的；但是并行是真正意义上的“同时执行”。
5、 临界区
临界区表示一种公共资源或者说是共享数据，可以被多个线程使用。但是每一次，只能有一个线程使用它，一旦临界区资源被占用，其它线程想要使用这个资源，就必须等待。
在并行程序中，临界区资源是保护的对象。
6、阻塞(Blocking)和非阻塞(Non-Blocking)
阻塞和非阻塞通常用来形容多线程间的相互关系，比如一个线程占用了临界区资源，那么其他所有需要这个资源的线程就必须在临界区中等待。等待会导致线程挂起，这种情况就是阻塞，此时，如果占用资源的线程一直不愿意释放资源，那么其它所有阻塞在这个临界区的线程都不能工作。
非阻塞与其相反，它强调没有一个线程可以妨碍其它线程的执行，所有的线程都会尝试不断向前执行。
7、死锁(Deadlock)、饥饿(Starvation)和活锁(Livelock)
死锁：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。

上图A,B,C,D四辆小车因为互相占用了对方的车道，如果大家都不愿意释放自己的车道，那么这个状态就将永远维持下去，谁都不可能通过。
饥饿：指某一个或者多个线程因为种种原因无法获得所需要的资源，导致一直无法执行。比如它的线程优先级太低，而高优先级的线程不断抢占它需要的资源，导致低优先级线程抢不到资源无法工作。
活锁：活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败。
对于活锁，比如我们坐电梯下楼，这时候电梯到1楼了，我们正准备出电梯，但是不巧的是，门外一个人挡住了我们的去路，因为他想进来，于是，我们首先很绅士的靠左走，避让对方，但是对方也很绅士的靠右走，希望避让我们。结果我们和对方又碰上了，于是乎，我们又马上向右避让，而对方马上向左避让，结果自然是又碰上了，如果我们一直这样，谁也走不了，于是活锁就产生了。
8、并发级别
由于临界区的存在，多线程之间的并发必须受到控制，根据控制并发的策略，我们把并发的级别进行分类，大致可以分为阻塞、无饥饿、无障碍、无锁、无等待。
①、阻塞(Blocking)
一个线程如果是阻塞的，那么在其他线程释放资源之前，当前线程无法继续执行，当我们使用 synchronized 关键字时，或者重入锁（后面会讲），我们得到的就是阻塞的线程。
②、无饥饿(Starvation-Free)
如果线程之间是有优先级的，那么线程调度的时候总是会倾向于满足高优先级的线程，也就是说，对于同一个资源的分配是不公平的。下图显示了公平和非公平两种情况（五角星表示高优先级线程）



对于非公平锁，系统允许高优先级线程插队，这样会导致低优先级线程产生饥饿。但如果锁是公平的，满足先来后到，那么饥饿就不会产生，不管新来的线程优先级多高，要想获得资源，都必须排队，那么所有线程都有机会执行。
③、无障碍(Obstruction-Free)
这是一种最弱的非阻塞调度。两个线程如果是无障碍的执行，那么他们不会因为临界区的问题导致一方被挂起，大家都可以进入临界区，但是如果大家都修改临界区数据，导致数据变坏，那么对于无障碍的线程来说，它就会立即对自己所做的修改进行回滚，确保数据安全。但是如果没有数据竞争发生，那么线程就可以顺利完成自己的工作，走出临界区。
和前面讲的阻塞的控制相比，系统认为两个线程在临界区很有可能发生冲突，以保护共享数据为第一优先级，那么临界区只能存在一个线程，我们称其为悲观策略。而无障碍非阻塞的调度是一种乐观策略，它认为多个线程之间很有可能不会发生冲突，大家都可以无障碍的执行，但是一旦检测到冲突，就应该进行回滚。
从上面的描述我们可以看出，无障碍的多线程程序并不能保证程序顺畅的运行，因为当临界区存在冲突时，所有线程可能都会不断的回滚自己的操作，而没有一个线程可以走出临界区，这会影响到系统的正常执行，而我们希望的是至少能有一个线程走出临界区，保证系统不会在临界区中进行无限的等待。
解决这种问题可以依赖一个“一致性标记”来实现，线程在操作之前，先读取这个标记，在操作完成之后，再次读取这个标记，检查这个标记是否被更改过，如果两者是一致的，则说明资源访问没有冲突，如果不一致，则说明资源可能在操作过程中与其他线程冲突，需要重试操作。而任何对资源有修改操作的线程，在修改数据前，都需要更新这个一致性标记，表示数据不再安全。
④、无锁(Lock-Free)
无锁的并行都是无障碍的。在无锁的情况下，所有的线程都会能尝试对临界区进行访问，但不同的是，无锁的并发保证必然有一个线程能够在有限步内完成操作离开临界区。
在无锁的调用中，一个典型的特点是可能会包含一个无穷循环，在这个循环中，线程会不断尝试修改共享变量，如果没有冲突发生，修改成功，那么程序退出，否则继续尝试修改。但无论如何，无锁的并行总能保证有一个线程可以胜出，不至于全军覆没，至于临界区中竞争失败的线程，它们会不断的重试，直到自己获胜，如果运气不好，总是尝试不成功，则会出现饥饿的现象，线程会停滞不前。
⑤、无等待(Wait-Free)
无锁只要求有一个线程可以在有限步内完成操作，而无等待在无锁的基础上更进一步，它要求所有的线程都必须在有限步内完成，这样不会引起饥饿问题，如果限制这个步骤上限，还可以进一步分解为有界无等待和线程数无关的无等待等，他们的区别只是对于循环次数的限制不同。
9、Java内存模型（JMM:Java Memory Model）
并发程序为什么会比串行程序复杂很多？因为并发程序下数据访问的一致性和安全性很难控制，如何保证一个线程总是可以看到正确的数据？我们需要定义一种规则，保证多个线程能有效的、正确的协同工作，这就是Java的内存模型。而Java内存模型是围绕着如下几点来进行的：
①、原子性(Atomicity)
原子性是指一个操作不可中断，即使是多个线程一起执行的时候，一个操作一旦开始，就不会被其它线程所干扰。
②、可见性(Visibility)
可见性是指当一个线程修改了某一个共享变量的值，其它线程是否能够立即知道这个修改。除了缓存优化或者硬件优化（有些内存读写可能不会立即触发，而会进入一个硬件队列等待）会导致可见性问题外，指令重排以及编辑器的优化，都有可能会导致一个线程的修改不会立即被其他线程察觉。
③、有序性(Ordering)
对于一个线程的执行代码而言，我们总是习惯的认为代码的执行是从前往后，依次执行的，对于一个线程而言，确实会这样，但是对于多个线程，程序的执行可能会出现乱序，会给人一种错觉：写在前面的代码会在后面才执行。
有序性的问题原因是因为程序在执行时，可能会进行指令重排。注意，指令重排有一个基本前提是保证串行语义的一致性，指令重排不会使串行的语义逻辑发生问题。指令重排能减少CPU的流水线中断次数，因为每次中断流水线然后恢复会有比较大的性能损耗，而指令重排能减少中断次数。
所以指令重排虽然带来了乱序问题，但是对于提高CPU的性能是十分必要的。
④、Happen-Before 规则
虽然Java虚拟机和执行系统会对指令进行一些重排，但是指令重排是有原则性的，并非所有的指令都可以随便改变执行的位置，以下这些原则是指令重排不可违背的。
1、程序次序规则(Program Order Rule)：在同一个线程中，按照程序代码顺序，书写在前面的操作先行发生于书写在后面的操纵。准确的说是程序的控制流顺序，考虑分支和循环等。
2、管理锁定规则(Monitor Lock Rule)：一个unlock操作先行发生于后面（时间上的顺序）对同一个锁的lock操作。
3、volatile变量规则(Volatile Variable Rule)：对一个volatile变量的写操作先行发生于后面（时间上的顺序）对该变量的读操作。
4、线程启动规则(Thread Start Rule)：Thread对象的start()方法先行发生于此线程的每一个动作。
5、线程终止规则(Thread Termination Rule)：线程的所有操作都先行发生于对此线程的终止检测，可以通过Thread.join()方法结束、Thread.isAlive()的返回值等手段检测到线程已经终止执行。
6、线程中断规则(Thread Interruption Rule)：对线程interrupt()方法的调用先行发生于被中断线程的代码检测到中断时事件的发生。Thread.interrupted()可以检测是否有中断发生。
7、对象终结规则(Finilizer Rule)：一个对象的初始化完成（构造函数执行结束）先行发生于它的finalize()的开始。
8、传递性(Transitivity)：如果操作A 先行发生于操作B，操作B 先行发生于操作C，那么可以得出A 先行发生于操作C。