锁与并发

锁的作用是保护临界区资源不会被多个线程同时访问而受到破坏。

1 对象头和锁

在Java虚拟机的实现中每个对象都有一个对象头，用于保护对象系统信息。对象头中有一个成为Mark Word的部分，它是实现锁的关键。在32位系统中，Mark Word为一个32位的数据，而在64位系统中，它占64位。它是一个多功能的数据区，可以存放对象的哈希值、对象年龄、锁的指针信息等。一个对象是否占用锁，占有哪个锁，就记录在这个Mark Word中。

2 锁在Java虚拟机中的实现和优化

在多线程中，线程之间的竞争是不可避免的，而且是一种常态，如何使用更高的效率处理多线程的竞争，是Java虚拟机一项重要的使命。如果将所有的线程竞争都交由操作系统处理，那么并发性能将是非常低下的，为此，虚拟机在操作系统层面挂起线程之前，会先耗尽一切可能在虚拟机层面上解决竞争关系，尽可能避免真实的竞争发生。同时在竞争不激烈的场合，也会试图消除不必要的竞争。

2.1 偏向锁

偏向锁是JDK 1.6提出的一种锁优化方式。其核心思想是，如果程序没有竞争，则取消之前已经取得锁的线程的同步操作。也就说，若某一锁被线程获取后，便进入偏向模式，当线程再次请求这个锁时，无需再进行相关的同步操作，从而节省了操作时间，如果在此之间有其它线程进行了锁请求，则锁退出偏向模式。JVM中使用-XX:+UseBiasedLocking来设置启用偏向锁。
当锁对象处于偏向模式时，对象头会记录获得锁的线程；这样当该线程再次尝试获得锁时，通过Mark Word的线程信息可以判断当前线程是否持有偏向锁。
偏向锁在锁竞争激烈的场合中没有太强的优化效果，因为大量的竞争会导致持有锁的线程不停地切换，锁也很难一直保持在偏向模式。此时，使用偏向锁不仅得不到性能优化，反而有可能降低系统性能。因此在竞争激烈的场合，可以尝试使用-XX:-UseBiasedLocking参数禁用偏向锁。

2.2 轻量级锁

如果偏向锁失败，Java虚拟机会让线程申请轻量级锁。轻量级锁在虚拟机内部，使用一个称为BasicObjectLock的对象实现，这个对象内部由一个BasicLock对象和一个持有该锁的Java对象指针组成，BasicObjectLock对象放置在Java栈的栈帧中。在BasicLock对象内部还维护着displaced_header字段，它用于备份对象头部的Mark Word。
轻量级锁实现流程：首先，BasicLock通过set_displaced_header() 方法备份了原对象的Mark Word。接着，使用CAS操作，尝试将BasicLock的地址复制到对象头的Mark Word。如果复制成功，那么加锁成功，否则则认为加锁失败，那么轻量级锁就有可能膨胀为重量级锁。
由于BasicObjectLock对象在线程栈中，因此该指针必然指向持有该锁的线程栈空间。当需要判断某一线程是否持有该对象锁时，也只需简单地判断对象头的指针是否在当前线程的栈地址范围内即可。同时，BasicLock对象的displaced_header字段备份了原对象的Mark Word内容。BasicObjectLock对象的obj字段则指向该对象。

2.3 膨胀锁

当轻量锁失败，虚拟机就会使用重量锁。
执行步骤：第1步是废弃前面BasicLock备份的对象头信息。第2步则是正式启用重量级锁。启用过程分为2步：首先，通过inflate() 方法进行锁膨胀，其目的是获得对象的ObjectMonitor；然后使用enter() 方法尝试进入该锁。在enter() 方法调用中，线程很可能会在操作系统层面被挂起。如果这样，线程间的切换和调度的成本就会比较高。

2.4 自旋锁

自旋锁可以使线程在没有取得锁时，不被挂起，而转去执行一个空循环（即所谓的自旋），在若干个空循环后，线程如果可以获得锁，则继续执行。若线程依然不能获得锁，才会被挂起。
在JDK 1.7后，虚拟机不再支持由用户配置自旋锁，自旋锁总是会执行，自旋的次数也由虚拟机自行调整。

2.5 锁消除

锁消除是Java虚拟机在JIT编译时，通过对运行上下文的扫描，去除不可能存在共享资源竞争的锁。通过锁消除，可以节省毫无意义的请求锁时间。这种技术称为逃逸分析技术，用来捕获到这些不可能存在竞争却有申请锁的代码段，并消除这些不必要的锁，从而提高系统性能。
逃逸分析和锁消除分别可以使用参数-XX:+DoEscapeAnalysis和-XXL:+EliminateLocks开启。

3 锁优化思路

3.1 减少锁的持有时间

对于使用锁进行并发控制的应用程序而言，在锁竞争过程中，单个线程对锁的持有时间与系统性能有着直接关系。如果线程持有锁的时间很长，那么相对的，锁的竞争程度也就越激烈。因此可以得出一个较优的解决方案是：在在必要时同步，这样就能明显减少持有锁的时间，提高系统吞吐量。典型应用：同步代码块。

3.2 减小锁粒度

这种技术的典型使用场景就是ConcurrentHashMap类的实现。对一个普通的集合对象的多线程同步来说，最常使用的方式就是对get() 和add() 方法进行同步。每当对集合进行add() 操作或者get() 操作，总是会获得集合对象的锁。
ConcurrentHashMap使用了拆分对象锁的方式提高系统吞吐量。ConcurrentHashMap将整个HashMap分成若干个段(Segment)，每个段都是一个自HashMap，目前每个table就是一个段。
如果需要在ConcurrentHashMap中增加一个新的表项，并不是将整个HashMap加锁，而是首先根据hashcode得到该表项应该被存放到哪个字段，然后对该字段加锁，并完成put操作。在多线程环境中，每个段便可并发地执行操作。
但是，减少锁粒度会引入一个新的问题，即：当系统需要取得全局锁时，其消耗的资源会比较多。例如，当试图访问ConcurrentHashMap全局信息（size）时，就会需要同时取得所有字段的锁方能顺利实施。

3.3 锁分离

锁分离是减小锁粒度的一个特例，它依据应用程序的功能特点，将一个独占锁分成多个锁，一个典型的案例就是java.util.concurrent.LinkedBlockingQueue的实现。
在JDK中，分别对插入和取出采用不同的锁，使得take() 和put() 函数独立，它们之间不存在竞争关系。

3.4 锁粗化

通常情况下，会要求每个线程持有锁的时间尽量短，即在使用完公共资源后，应立即释放锁。但是，如果一个线程不停地连续地释放锁，获取锁，那么这一过程由于每次都对锁进行操作，反而消耗了大量不必要的系统资源。
为此，虚拟机在遇到一连串地对同一个锁不断进行请求和释放的操作时，便会把所有的锁操作整合成对锁的一次请求，从而减少对锁的请求同步次数。这个操作叫做锁的粗化。

4 无锁

锁的出现，尽管为多线程安全提供了保障，但是它同时也拖慢了系统的运行速度。因此，一种称为非阻塞同步的方法被提出。这种方法不需要使用锁，但是依然能确保数据和程序在高并发环境下保持多线程间的一致性。

4.1 CAS

CAS的算法过程：它包含3个参数V，E，N。V表是要更新的变量，E表示预期值，N表示新值。仅当V值等于E值时，才会将V的值设为N，如果V值和 E值不同，则说明已经有其它线程做了更新，则当前线程不操作。最后，CAS操作返回当前V的真实值。CAS操作是抱着乐观的态度进行的，它总是认为操作可以成功执行。当多个线程同时使用CAS操作一个变量时，只有一个会胜出并成功更新变量值，其余均会失败。失败的线程不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败线程放弃尝试。

4.2 原子操作

JDK的java.util.concurrent.atomic包下，有一组使用无锁算法实现的原子操作类，主要有AtomicInteger、AtomicIntegerArray、AtomicLong、AtomicLongArray和AtomicReference等。
其内部使用一个死循环，循环内部存放着CAS操作，当操作不成功时，反复执行循环语句，直到成功。

4.3 LongAddr

上文提到的CAS在死循环中，如果不成功则会一直尝试。因此，在竞争激烈的情况下，修改失败的概率较高，且性能较差。

5 理解Java内存模型

5.1 原子性

原子操作是不可中断的，也不能被多线程干扰。比如，对int和byte等数据的赋值操作就具有原子性，而像“a++”这种操作则不具有，因为它内部实际包括读取a、计算新值和写入a的三步操作。
注意，对于long的读写操作不是原子操作。可以使用volatile解决。

5.2 有序性

现在的CPU都支持指令流水线执行。为了保证流水线的顺畅执行，在执行指令时，有可能对目标指令进行重排。目前的重排技术可以保证在不改变实际输出结果的同时，对语句的顺序进行优化。

5.3 可见性

可见性是指当一个线程修改了一个变量的值，在另外一个线程中可以马上得知这个修改。上述的指令重排就有可能使得一个线程无法立即得知另一个变量的修改。此外，由于系统编译器优化，部分变量的值可能会被寄存器或者高速缓存缓存，而每个CPU都有独立的寄存器和Cache，从而导致其它线程无法立即发现这个更改。