关于java:Java并发编程-锁

本文次要答复以下问题：
1. 锁是什么，有哪些类型的锁，什么时候须要锁，以及锁的实现原理；
2. 如何正确地应用锁；有哪些潜在的问题；
3. 如何晋升并发的性能（例如缩小锁竞争，JVM 的锁优化，原子类，非阻塞算法，无锁算法）；

1. 锁的类型

从不同的角度或性能来对锁进行分类，使锁的类型有很多。上面表格列出了一些常见的锁类型。

思考题：
1. 乐观锁会加锁吗？
2. 为什么 wait 和 notify 办法放在 Object 类里？

2. 加锁机制

锁的实质是什么?
锁是一种同步机制，管制并发程序对共享资源的拜访，线程持有锁时才能够对共享资源进行拜访。在锁的实现上，锁是一个数据标记。

2.1 内置锁（synchronized）的原理

每个 Java 对象都能够作为一个锁，这个锁被称为内置锁或监视器锁（Monitor Lock）。内置锁的长处是：进入 synchronized 润饰的同步代码块前会主动去取得锁，在退出（包含抛出异样退出）同步代码块时主动开释锁。

内置锁通过更改对象头里的锁状态位来加锁和开释锁（对象头的构造上面会展现）。同步的实现依赖于 monitor 对象（HotSpot 虚拟机里的 monitor 实现是 ObjectMonitor 对象），每个 Java 对象都能够有一个对应的 monitor 对象与之关联。ObjectMonitor 对象中有两个队列_WaitSet 和 _EntryList，用来保留 ObjectWaiter 对象（封装了期待的线程）列表，monitor 对象的同步形式如下：

如上图所示，新的线程会进入 EntryList，当一个持有锁的线程开释 monitor 时，在入口区（EntryList）和期待区（WaitSet）的线程都会去竞争监视器（图中 Owner 所在区域）。Monitor 对象只能有一个 owner，一个线程成为监视器的 owner 后如果须要期待某个条件而执行了 wait()办法，那么这个线程会开释锁并进入 WaitSet（第 3 步所示）。

32 位 JVM 的对象构造 ：
1. 对象头：由 MarkWord(32bit) + ClassMeta 地址(32bit) 组成。在无锁状态时 MarkWord 的存储构造为：对象 hashcode-25bit，对象分代年龄 -4bit，是否偏差锁 -1bit，锁标记位 -2bit。
32 位 JVM 的 MarkWord 和 ClassMeta 地址别离占用 32bit，64 位 JVM 的 MarkWord 和 ClassMeta 地址别离占用 64bit。
2. 实例数据；
3. 对齐填充的数据；JVM 要求对象的起始地址必须是 8 字节的整数倍。
对象头的 MarkWord 存储构造：（锁状态这列为每行的含意）

在 JDK1.6 时，虚拟机团队对 synchronized 进行了一系列的优化。在此之前，synchronized 是一个重量级锁，效率比拟低。优化后，synchronized 一开始是无锁或偏差锁（MarkWord 后三位是 001 或 101），随着锁竞争水平的加剧，才开始 锁降级：无锁 -> 偏差锁 -> 轻量级锁 -> 重量级锁。留神，锁降级是一个不可逆的过程。

synchronized 的执行过程：
1. 查看 MarkWord 里是不是以后线程的 ID，如果是，示意以后线程处于偏差锁；
2. 如果不是，则用 CAS 操作将以后线程 ID 替换进 MardWord；如果胜利则示意以后线程取得偏差锁，置偏差标记位 1；
3. 如果失败，则阐明产生锁竞争，撤销偏差锁，并降级为轻量级锁；
4. 以后线程应用 CAS 将对象头的 MarkWord 替换为栈中锁记录指针；如果胜利，以后线程取得锁；
5. 如果失败，示意其余线程竞争锁，以后线程便尝试应用自旋来获取锁；
6. 如果自旋胜利则仍然处于轻量级锁状态；
7. 如果自旋失败，则降级为重量级锁。

如果线程争用强烈，那么应该禁用偏差锁(-XX:-UseBiasedLocking)，JDK1.6 之后偏差锁是默认开启的，JDK15 偏差锁改为默认敞开(开启配置 -XX:+UseBiasedLocking)。

2.2 可重入锁（ReentrantLock）的原理

2.2.1 惯例用法

Lock lock = new ReentrantLock(false); // 参数为空时，默认创立非偏心锁

lock.lock(); 
try {operation-xx(); // 业务解决逻辑
} finally {lock.unlock(); // 放在 finally 中确保锁开释
}

2.2.2 ReentrantLock 的实现

ReentrantLock 的实现基于 AbstractQueuedSynchronizer(简写为 AQS)，可重入性能基于 AQS 的同步状态字段（也是锁标记字段）：state。state 用来示意所有者线程曾经反复取得该锁的次数。

可重入锁的原理：当某一线程获取锁后，将 state 值加 1，并记录下以后持有锁的线程标识，以便查看是否是反复获取锁，以及检测线程开释锁时是否非法；再有线程来获取锁时，判断这个线程与持有锁的线程是否是同一个线程，如果是，将 state 值再加 1；如果不是，则阻塞新来的线程。在线程开释锁时，将 state 值减 1；当 state 值减为 0 时，示意以后线程彻底开释了锁。

ReentrantLock 没有间接继承 AQS 类，而是在外部定义了一个公有外部类 Sync 来继承 AQS 类，而后把本人的同步办法的实现都委托给这个公有外部类。这种同步器实现形式也是 AQS 作者 Doug Lea 倡议的形式。ReentrantLock 的类间关系如下图所示：

2.2.3 AQS 类介绍

j.u.c 包中大部分的同步器（例如锁，屏障等）都是基于 AQS 类构建的。AQS 为同步状态的原子性治理、线程的阻塞和解除阻塞以及排队提供了一种通用的机制。
同步器个别蕴含两种根本办法，一种是 acquire，另一种是 release。acquire 操作用于阻塞调用的线程，直到或除非同步状态容许其继续执行。而 release 操作则是通过某种形式扭转同步状态，使得一或多个被 acquire 阻塞的线程继续执行。

• acquire 操作包含：Lock.lock，Semaphore.acquire，CountDownLatch.await 等。
• release 操作包含：Lock.unlock，Semaphore.release，CountDownLatch.countDown 等。
  AQS 封装了实现同步器时波及的大量细节问题，极大地缩小了同步器的实现工作，只用依据须要重写几个 AQS 的 protected 办法（tryAcquire/TryAcquireShard,tryRelease/tryReleaseShared,getState,setState 等）即可。

整个 AQS 框架的要害是如何治理被阻塞线程的链表队列，该队列是严格的 FIFO 队列（但不肯定是偏心的）。AQS 抉择了 CLH 锁作为实现此队列的根底，因为 CLH 锁能够更容易地去实现“勾销（cancellation）”和“超时”性能。

AQS 框架提供了一个 ConditionObject 类，给保护独占同步的类以及实现 Lock 接口的类应用。此条件对象提供了 await、signal 和 signalAll 操作，AQS 在一个独自的条件队列中保护这些条件对象节点，其中 signal 操作是通过将节点从条件队列转移到锁队列（即上述的 CHL 链表队列）中来实现的。

应用 AQS 框架构建同步器时，将 AQS 的子类作为同步器抽象类并不适宜，因为 AQS 子类必须提供办法在外部管制 acquire 和 release 的规定，但这些办法都应该对用户暗藏。倡议的做法是在定义的同步器类外部申明一个 AQS 子类作为公有外部类，把所有同步办法都委托给这个公有外部类，j.u.c 包里的同步器类都是这种用法（应用公有外部类 Sync）。
AQS 框架的应用例子：ReentrantLock 类代码截图

3. 死锁

3.1 什么是死锁

经典的“哲学家进餐”问题很好的形容了死锁的情况，当上面这种状况呈现时将产生死锁：每个哲学家都领有其他人须要的资源（一根筷子），同时又期待其他人曾经领有的资源（一根筷子），并且每个人在取得所需资源（两根筷子）前都不会放弃曾经领有的资源。此时每个哲学家都在期待另一根筷子，在没有外力干预的状况下，他们会始终期待上来，这就是死锁，所有哲学家都将“饿死”。

当死锁呈现时，往往是在最蹩脚的时候 – 零碎高负载时，因为这时并发最高竞争也最强烈。推波助澜莫过如此。

上面介绍死锁的几种类型，包含：锁程序死锁，动静的锁程序死锁，合作对象之间的死锁，资源死锁。

锁程序死锁
两个线程试图以不同的程序来取得雷同的锁，会产生锁程序死锁。如果所有线程以固定的程序来取得锁，那么在程序中就不会呈现锁程序死锁问题。代码示例如下，一个线程调用了 leftRightOrder()，另一个线程同时调用了 rightLeftOrder()办法，它们会产生死锁：

public static
class LockOrderingDeadlocks {private final Object left = new Object();
    private final Object right = new Object();

    public void leftRightOrder() {synchronized (left) {synchronized (right) {// doSomething()
            }
        }
    }

    public void rightLeftOrder() {synchronized (right) {synchronized (left) {// doSomethingElse()
            }
        }
    }
}

动静的锁程序死锁
这种状况比拟荫蔽，因为在办法内的锁程序是固定的，看似有害，但锁的程序取决于传递给办法的参数的程序，此时调用办法的单方可能传的参数是颠倒的，这时就会造成锁程序死锁，即在动静调用办法时产生了锁程序死锁。代码示例如下：

public void
transferMoney(Account fromAccount, Account toAccount, double amount) {synchronized (fromAccount) {synchronized (toAccount) {
            // fromAccount 缩小 amount 金额
            // toAccount 减少 amount 金额
        }
    }
}

上述定义了银行转账的办法 transferMoney，零碎如果同时调用了 transferMoney(A, B, 1) 和 transferMoney(B,
A, 2) 则会产生死锁。
要解决这个问题，必须定义锁的程序，并在整个应用程序中都依照这个程序来加锁。

合作对象之间的死锁
这种状况比后面两种状况更加荫蔽，如果在持有锁时调用某个内部办法，那么将可能呈现活跃性问题，因为这个合作对象提供的内部办法中可能会获取其余锁。

资源死锁
与期待锁一样，线程在雷同的资源汇合上期待资源时，也会产生死锁。资源池越大，呈现这种状况的概率越小。

死锁的产生必须是以下 4 个状况同时产生：

• 互斥条件：每个资源都被调配给了一个过程，且资源不能被共享；
• 放弃和期待条件：曾经获取资源的过程被认为可能再次获取新的资源，所以会始终持有取得的资源并期待；
• 不可抢占条件：调配给过程的资源不能被争夺；
• 循环期待：每个过程都在期待另一个过程开释资源，造成一个环路的期待。

如果其中任意一个条件不成立，死锁就不会产生。能够通过毁坏其中任意一个条件来毁坏资源死锁。

3.2 死锁的防止和诊断

在须要获取多个锁时，在设计时必须思考锁的程序：尽量减少潜在的加锁交互数量，把获取锁时须要遵循的协定写入正式文档，并始终遵循这些协定。

应用定时的锁 ，对超过期待时限的锁申请返回一个失败信息，而不是始终期待上来。Lock 接口的 tryLock(long, TimeUnit) 办法，提供了这个性能。定时的锁能够防止死锁的产生，或者说使线程能够从死锁中复原。

死锁的诊断剖析，能够通过 jstack dump 线程信息，查看每个线程持有了哪些锁，以及被阻塞的线程在期待哪个锁。命令为：jstack ${pid} > file_jstack.txt。把线程信息文件 file_jstack.txt 上传到
https://fastthread.io/ 能够帮忙你更疾速剖析。

3.3 其余活跃性危险

死锁是最常见的活跃性危险，除此之外，还有饥饿、失落信号和活锁等。

饥饿
定义：当线程因为无法访问他须要的资源而不能继续执行时，就产生了“饥饿”。

引发线程饥饿的最常见资源就是 CPU，比方一些线程的优先级高或者大量循环计算始终占用着 CPU，导致其余线程无奈竞争到 CPU。因而，要防止应用线程优先级，否则可能会减少产生饥饿的危险。

失落的信号
定义：线程在 wait 一个条件为真后继续执行，但在线程开始 wait 之前这个条件曾经为真，但线程 wait 前并没有查看这个条件，导致这个曾经为真的条件成为了一个失落的信号，从而使线程始终期待上来。

解决办法是在 wait 操作前都查看一次条件谓词，就不会产生信号失落的问题，如下所示：

synchronized(lock)
{while(!conditionPredicate()) { // 查看条件谓词
        lock.wait(); // 在 while 循环中调用 wait}
}

活锁
定义：当多个相互协作的线程都对彼此进行响应从而批改各自的状态，并使得任何一个线程都无奈继续执行时，就产生了活锁（Livelock）。

发生存锁时，只管未产生线程阻塞，但线程在一直反复执行雷同的操作，而且总会失败，所以没法继续执行上来。这种活锁通常是因为适度的谬误复原代码造成的，须要在重试机制中引入随机性来解决，比方随机化重试的期待时长，防止各线程又在同一时刻重试。

4. 晋升并发性能

上面介绍的几种晋升并发性能的形式是从缩小同步开销的方面登程的，除此之外晋升性能还蕴含其余伎俩，比方应用缓存，查问优化等。
除了锁优化是 JVM 主动实现的，上面的其余 3 种形式都是在编码设计时须要留神的。

4.1 缩小锁的竞争

有 3 种形式能够升高锁的竞争水平：1. 缩小锁的持有工夫；2. 升高锁的申请频率；3. 应用带有协调机制的独占锁，这些机制容许更高的并发性。
上面的几种具体措施即是基于下面的 3 种指导思想。

放大锁的范畴
放大锁的作用范畴，比方把一些无关代码移出被锁住的同步代码块，尤其是那些开销较大的操作，能无效缩小锁持有的工夫。或者说，只把真正须要同步的操作才加锁。

在合成同步代码块时，合成后的同步代码块也不能过小，比方一次原子操作须要同时更新多个变量的状况就必须蕴含在一个同步代码块中。如果合成为了多个同步代码块，因为过多的同步操作会产生更多的开销，在 JVM 执行锁粗化操作时，可能会将合成的同步块又从新合并起来。

减小锁的粒度
当一个锁须要爱护多个互相独立的状态变量时，能够将这个锁合成为多个更小粒度的锁，每个锁只爱护一个变量，从而进步可伸缩性，最终升高每个锁被申请的频率。

对锁粒度的合成，实际上是缩小原锁的竞争，使多个独立的变量之间没有锁竞争。代码示例如下，ServerStatus 类保护两个变量：以后的登录用户 users 和正在执行的查问 queries。两个同步办法 addUser 和 addQuery 都须要取得 ServerStatus 对象的锁能力执行。减小锁的粒度后，在 ServerStatusDecompose 类中这两个办法各自用了 users 和 queries 对象的锁，所以两个办法不存在锁的竞争。

public static
class ServerStatus {
    public final Set<String> users = new
HashSet<>();
    public final Set<String> queries =
new HashSet<>();

    public synchronized void addUser(String u)
{users.add(u); }
    public synchronized void addQuery(String q)
{queries.add(q); }
}
// 减小锁的粒度，两个独立变量 users 和 queries 别离用两个锁来爱护
public static
class ServerStatusDecompose {
    public final Set<String> users = new
HashSet<>();
    public final Set<String> queries =
new HashSet<>();

    public void addUser(String u) {synchronized (users) {users.add(u);
        }
    }
    public void addQuery(String q) {synchronized (queries) {queries.add(q);
        }
    }
}

锁分段
锁分段技术很出名的例子就是 ConcurrentHashMap 的实现，它应用了一个锁数组，这个数组存储了 16 个锁，每个锁爱护所有 hash buckets 的 1 /16，其中第 N 个 bucket 由第 N mod 16 个锁来爱护。这样分段爱护后，把对锁的申请缩小到原来的 1 /16，同时可能反对多达 16 个的并发写入。

某些状况下，能够将锁合成技术扩大至对一个变长的独立对象汇合进行分区锁定，这称为锁分段。

锁分段有其劣势，当要独占拜访整个汇合时须要获取多个锁，相比单个锁，这比拟艰难，开销也更大。比方当 ConcurrentHashMap 须要扩容并从新哈希键值时，就须要获取所有的分段锁。

代替独占锁
升高锁竞争的另一个办法是放弃应用独占锁。比方应用并发容器，读写锁，不可变对象和原子变量。

4.2 JVM 的锁优化

自旋锁
期待锁的线程执行一个忙循环（自旋）来期待锁，而不是挂起线程期待，这称为自旋锁。

因为很多锁状态只会继续很短一段时间，为了这段时间去挂起和复原线程并不值得。JDK1.6 曾经默认开启自旋锁（-XX:+UseSpinning），当锁占用工夫很短时，自旋锁的成果十分好；但如果锁占用工夫很长，那自旋的线程只会白白浪费 CPU 资源。因而自旋期待的工夫有一个限度，超过限度就挂起线程。这个固定的限度在 JDK1.6 进行了优化，引入了自适应自旋，使自旋的工夫不再固定，而是由前一次在同一个锁上的自旋工夫及锁的拥有者状态来决定。如果对于某个锁自旋很少胜利取得过锁，那么当前获取这个锁时可能间接省略掉自旋。

锁打消
锁打消是指 JVM 在即时编译阶段对一些同步代码块的锁进行革除，它的判断根据来自于逃逸剖析，如果同步代码块里的数据都不会逃逸进来被其余线程所拜访，那么就能够认为它们是线程公有的，对它们加的锁就能够打消掉。

锁粗化
如果一系列间断的操作都对同一个对象重复加锁和解锁，甚至在循环中进行重复加锁和解锁，那么即便没有线程竞争，这种频繁的互斥同步操作也会导致性能损耗。虚拟机探测到这种状况时，会把锁的范畴扩充（粗化）到所有间断操作的里面（或循环体的内部），这样只需加一次锁即可。

偏差锁 和 轻量级锁
偏差锁和轻量级锁是 JDK1.6 中引入的对内置锁 synchronized 的优化措施。偏差锁的目标是在无竞争的状况下把整个同步都打消掉，CAS 操作也省去。轻量级锁的加锁和解锁都是通过 CAS 操作来进行的，在没有竞争的状况下，防止了同步的开销。这两种锁的降级过程见“加锁机制 – 内置锁的原理”。

4.3 原子变量类

原子变量比锁的粒度更细，量级更轻，它既有原子性，也有内存可见性，是一种更好的 volatile 变量。最罕用的原子变量是标量类：AtomicInteger，AtomicLong，AtomicBoolean，AtomicReference。所有这些类都反对 CAS 操作（比拟并替换）。

锁与原子变量的性能比照：

1. 在中低水平的竞争下，原子变量的性能远超锁的性能，原子变量能提供更高的可伸缩性；
2. 在高度竞争的状况下，锁的性能将超过原子变量的性能。这是因为锁在产生竞争时会挂起线程，从而升高了 CPU 的使用率和共享内存总线上的同步通信量。

4.4 非阻塞算法

非阻塞算法是指，一个线程的失败或挂起不会导致其余线程也失败或挂起的算法。
无锁算法是指，算法中的每个步骤中都有某些线程可能执行上来。
如果在算法中仅应用 CAS 操作协调各线程，并且能正确地实现性能，那么这种算法既是非阻塞的，又是无锁的。

非阻塞算法之所以能晋升性能，是因为线程阻塞的代价较大。线程阻塞的代价，即线程上下文切换的代价。要阻塞或唤醒一个线程须要操作系统染指，要在户态与外围态之间切换。这种切换会耗费大量的系统资源，因为用户态与内核态都有各自专用的内存空间和寄存器等，用户态切换至内核态须要传递许多变量、参数给内核，内核也须要爱护好用户态在切换时的一些寄存器值、变量等，以便内核态调用完结后切换回用户态持续工作。这会耗费 cpu 工夫。

非阻塞的栈代码示例：

public static
class NonblockingStack<E> {
    AtomicReference<Node<E>> top =
new AtomicReference<>(); // 栈顶元素

    public void push(E item) {
        Node<E> newHead = new
Node<>(item);
        Node<E> oldHead;
        do {oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead,
newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {oldHead = top.get();
            if (oldHead == null) {return null;}
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead,
newHead));
        return oldHead.item;
    }
}

ABA 问题
在 CAS 操作中可能会遇到 ABA 问题，当值由 A -> B，再由 B -> A，是否认为值没有发生变化？在某些算法中，这被认为是产生了变动，会影响算法的执行步骤。解决 ABA 问题能够通过引入版本号，在比拟两个值的同时也一起比拟版本号。

非阻塞算法在设计和实现时十分艰难，但能提供更高的性能和可伸缩性。在 JVM 的版本升级过程中，并发性能的晋升都来自于类库中对非阻塞算法的应用。

参考文献

[1] Brian Goetz，Tim
Peierls，Joseph Bowbeer 等.《Java 并发编程实战》机械工业出版社，2012
[2] Brian Goetz,Tim
Peierls,Joseph Bowbeer,et al.《Java
Concurrency in Practice》Addison-Wesley，2006
[3] 周志明.《深刻了解 Java 虚拟机 - 第 3 版》机械工业出版社，2019
[4] Doug Lea. 欧振聪 译. AQS 论文翻译：https://www.cnblogs.com/dennyzhangdd/p/7218510.html，2017
    Doug Lea. AQS 论文原文：https://gee.cs.oswego.edu/dl/papers/aqs.pdf，2004