线程模型

线程调度

线程状态

线程安全

并发控制策略

互斥同步（Mutual Exclusion & Synchronization）是一种最常见也是最主要的并发正确性保障手段。同步是指在多个线程并发访问共享数据时，保证共享数据在同一个时刻只被有限数量的线程使用，具体数量取决于并发控制策略。例如互斥锁就只允许一个线程独占资源，而信号量则可以允许多个。而互斥是实现同步的一种手段，临界区（Critical Section）、互斥量（Mutex）和信号量（Semaphore）都是常见的互斥实现方式。因此在“互斥同步”这四个字里面，互斥是因，同步是果；互斥是方法，同步是目的。

竞态的概念

线程数据安全需要锁来保证

CAS只是一种无锁的数据更新策略，但为了提高性能，防止无用的线程切换，CAS一般与循环配合使用，也就是自旋锁

乐观并发控制：典型的就是CAS与数据库中的MVCC。假定不会发生冲突，自由读取数据，当更新数据时需要根据数据的版本号判断是否发生了数据竞争

悲观并发控制：典型的就是synchronized与数据库中的LBCC。假定会发生冲突，直接将数据用同步块包裹，

锁是实现并发控制的重要手段，也是最基础的手段

monitor

管程、监视器

Linux内核提供的锁

Linux提供的锁API

理解互斥锁、条件锁、读写锁以及自旋锁

自旋锁

互斥锁

读写锁

读锁（共享锁）

写锁（排它锁）

可重入与不可重入锁

可重入

不可重入

公平与非公平锁

RCU锁

Java中的锁

synchronized

特性：可重入、独享、悲观锁

能够保证原子性、可见性、有序性

但由于实现依赖于mutex系统调用，因此性能消耗较大

实现原理 monitor对象

简单来说：每个对象的对象头中保存了该对象是否被锁定以及锁定的次数（针对可重入锁），每个对象也关联一个monitor对象，锁定对象的本质是锁定与对象相关联的monitor对象

作用于块状结构的synchronized关键字是Java中最基本的互斥同步手段，其包裹的代码块被称为同步块，而被修饰的方法则会变为同步方法。

synchronized的实现依赖于监视器模式

Javac在编译被synchronized包裹的块状结构时，会自动在其作用域前后插入monitorenter和monitorexit字节码指令。

因此synchronized提供了显式指定

这两个监视器字节码指令都需要reference类型的参数来指明要锁定和解锁的对象。

对处于静态方法（类方法）之内的同步块来说，其默认监视的对象为该类本身；而如果同步块在实例方法的方法体中，那么默认的监事对象就是发起调用实例。

与同步块不同的是，同步方法不能显式指定要锁定的实体，因此其锁定的目标取决于同步方法的种类。带有static修饰符的静态同步方法默认会将当前类的monitor当做锁，而普通的实例同步方法则会默认锁定发起调用的实例。

被Javac编译之后，会在同步块的前后分别形成monitorenter和monitorexit字节码指令，这两个监视器字节码指令都需要reference类型的参数来指明要锁定和解锁的对象。如果Java源码中的synchronized明确指定了对象参数，那就以这个对象的引用作为reference；如果没有明确指定，那将根据synchronized修饰的方法类型（如实例方法或类方法），来决定是取代码所在的对象实例还是取类型对应的Class对象来作为线程要持有的锁。

synchronized需要指定要锁定的实体，例如在同步代码块中显式指定某个对象；如果不指定，则javac会在字节码编译阶段自动选择锁定实例或者类型。

同步块：小括号中可以显式指定要锁定的实体；未指定则取决于当前上下文。在类中的同步块
同步方法：静态方法锁定的是类型，普通方法锁定的是实例

对应的字节码指令：监视器，monitorenter与monitorexit

对应的系统调用：互斥锁，mutex

《Java虚拟机规范》要求在执行monitorenter指令时首先要去尝试获取对象的锁。如果这个对象没被锁定，或者当前线程已经持有了那个对象的锁，就把锁的计数器的值增加一，而在执行monitorexit指令时会将锁计数器的值减一。一旦计数器的值为零，锁随即就被释放了。如果获取对象锁失败，那当前线程就应当被阻塞等待，直到请求锁定的对象被持有它的线程释放为止。即：

被synchronized修饰的同步块对同一条线程来说是可重入的。这意味着同一线程反复进入同步块也不会出现自己把自己锁死的情况。
被synchronized修饰的同步块在持有锁的线程执行完毕并释放锁之前，会无条件地阻塞后面其他线程的进入。这意味着无法像处理某些数据库中的锁那样，强制已获取锁的线程释放锁；也无法强制正在等待锁的线程中断等待或超时退出。

从执行成本的角度看，持有锁属于重量级（Heavy-Weight）操作。因为Java的线程是映射到操作系统的原生内核线程之上的，如果需要操作系统来阻塞或唤醒一条线程，这就不可避免地陷入用户态到核心态的转换中，进行这种状态转换需要耗费很多的处理器时间。尤其是对于代码特别简单的同步块，状态转换消耗的时间甚至会比用户代码本身执行的时间还要长。因此才说， synchronized是Java语言中一个重量级的操作，有经验的程序员都只会在确实必要的情况下才使用这种操作。而虚拟机本身也会进行一些优化，譬如在通知操作系统阻塞线程之前加入一段自旋等待过程，以避免频繁地切入核心态之中。

Lock接口

J.U.C包中的Lock接口是功能更强大的互斥同步实现机制；在JDK6之后，synchronized的性能与ReenteretLock相差无几，因此在必须使用重量级锁的情况下，应该优先使用在语法级别提供支持的synchronized关键字。

lock: 阻塞获取锁，一直等待直到获取成功 lockInterruptibly: 在锁的获取过程中，当前线程可以被中断 tryLock: 尝试非阻塞地获取锁，立即返回 unlock: 释放锁，注意必须与lock的次数对应

ReenteretLock的特点：

独享锁
支持公平锁和非公平锁
可重入锁

ReadWriteLock的特点:

维护一对关连锁，一个只用于读取，另一个只用于写入；读锁可以由多个读线程同时持有，而写锁同一时间只能被一个线程独占。读锁的作用是用于标记当前资源被其他线程读取，由于写锁在获取时是完全排它的，需要等待所有读锁都被释放后才能获取写锁。然而在获取写锁之后可以再次获取读锁，如果获取读锁后释放写锁，那就是锁降级过程；如果获取读锁后不释放，那就是锁升级过程；值得注意的是，在已经获取读锁的状态下是无法获取写锁的，因此读锁不存在升级与降级过程。
适用于读取比写入多的应用场景，可以提升互斥锁的性能，例如：缓存组件、集合的并发安全改造

例如：hashtable的读写都是synchronized方法，读和写都只能同时有一个线程执行，在读多写少的场景下，这种做法的性能损失严重，因此被替换为conncorrenthashmap

实现带缓存的查询：

读取缓存中的数据（加读锁）
如果缓存miss或过期失效就去数据库中查询，整个过程需要先释放读锁再加写锁。如果不加写锁，所有的请求都会打到数据库上，数据库压力过大可能崩溃；也就是说，在查数据库之前一定要加写锁，保证只有一个线程能够执行操作数据库的代码；此外，查数据库之前最好进行二次校验，防止被写锁阻塞的线程重复操作数据库
用查询到的新数据更新缓存快

与Lock配合的条件判断Condition：

用于替代 wait、notify、notifyAll
条件判断能进行更精确的唤醒、等待控制；例如在阻塞队列中

put(item){
    while (count == LENGTH)
        notFull.await();

    queue[count] = item;
    ++count;
    notEmpty.signal();
}

take(){
    while (count == 0)
        notEmpty.await();

    var item = queue[count];
    queue[count] = null;
    --count;
    notFull.signal();
    return item;
}

AQS抽象队列同步器

AQS不等于锁，AQS只是实现资源占用与释放的一种具体方式

AQS用链表实现阻塞队列，实现对阻塞线程的记录

详见代码OptAQS.java

获取资源：CAS + park

释放资源：CAS + unpark队列中所有的可用线程

同步锁的本质是排队

同步的方式：独享锁-单队列窗口；共享锁-多队列窗口
抢锁的方式：不公平锁-插队抢；公平锁-先来后到
没抢到锁的处理方式：自旋锁-快速尝试多次；普通锁-阻塞等待
唤醒阻塞线程的方式：全部通知-notifyAll，通知下一个-notify，通知指定-signal

实现锁的关键点（OptLock.java）：

判断锁的状态以及拥有者
保存正在等待的线程
用CAS实现trylock
while + trylock + park 实现阻塞 lock
unlock时要记得唤醒所有等待的线程
使用while防止伪唤醒

抽象类AQS提供了对资源占用、释放、线程等待、线程唤醒等接口的定义和实现。是ReentrantLock、CountDownLatch、Semphore的实现基础。

acquire、acquireShared：定义了资源争用的逻辑，没拿到就等待
tryAcquire、tryAcquireShared：抽象方法，子类必须自行实现资源获取的具体实现方式
release、releaseShared：定义了资源释放的逻辑，释放之后会通知所有等待该资源的线程
tryRelease、tryReleaseShared：抽象方法，子类必须自行实现资源释放的具体实现方式

ReentrantLock源码：

Sync类：继承AQS类
公平锁：继承Sync类的FairSync类中的lock方法，正常获取锁，阻塞的所有线程按照请求顺序排队
非公平锁：继承Sync类的NofairSync类中的lock方法，每次获取锁之前先做一次CAS，也就是插队

Semaphore信号量

最基础的并发控制方法，也可用于流量控制（Hystrix框架大量使用信号量）

// 创建 限制并发数量为N的信号量
Semaphore semaphore = new Semaphore(N);

semaphore.acquire();
// 需要并发控制的业务
semaphore.release();

同样依靠AQS实现其内部的Sync类，由于是非独占资源控制，需要使用tryAcquireShared、acquireShared等共享获取资源的API。

CountDownLatch倒计时器

创建倒计时器对象时，传入指定数值作为线程参与的数量，可以理解为是信号量的特殊用法

await：方法等待计数器值变为0，在这之前，线程进入等待状态；本质是申请资源

countdown：计数器数值减一，直到为0；本质是释放资源

经常用于等待其他线程执行到某一节点，再继续执行当前线程代码，也就是有条件的唤醒

典型应用：统计线程执行情况，多线程通信，等待全部执行完毕等

与join方法的区别：调用join方法需要等待thread执行完毕才能继续向下执行,而CountDownLatch只需要检查计数器的值为零就可以继续向下执行，相比之下，CountDownLatch更加灵活一些，可以实现一些更加复杂的业务场景

CountDownLatch的实现也是基于AQS，详见OptCDL.java

CyclicBarrier栅栏

栅栏的实现基于可重入锁，记录锁的数量，满足条件就释放所有锁，唤醒等待的线程，并重新计数。

创建对象时，指定栅栏线程数量以及barrierAction

await：等指定数量的线程都处于等待状态是，继续执行后续代码

barrierAction：线程数量到了指定量之后，自动触发执行指定任务

与CountDownLatch的区别在于，CyclicBarrier对象可以多次触发执行

典型应用场景：数据流分批处理；数据库请求缓冲；大数据分析，先拆分处理，再汇总

JVM对锁的优化

JDK6中实现了大量对锁的性能优化

白皮书

锁的消除与粗化

锁粗化（coarsening）

There are some patterns of locking where a lock is released and then reacquired within a piece of code where no observable operations occur in between. The lock coarsening optimization technique implemented in hotspot eliminates the unlock and relock operations in those situations (when a lock is released and then reacquired with no meaningful work done in between those operations). It basically reduces the amount of synchronization work by enlarging an existing synchronized region. Doing this around a loop could cause a lock to be held for long periods of times, so the technique is only used on non-looping control flow.

This feature is on by default. To disable it, please add the following option to the command line: -XX:-EliminateLocks

锁升级

从偏向锁到轻量级锁再到重量级锁

锁升级过程

原图地址

加偏向锁的过程：把对象头的线程ID改成当前请求访问的线程，只有第一次修改需要CAS，后续不需要

偏向锁本质就是无锁，如果没有发生过任何多线程争抢锁的情况，JVM就认为该对象暂时是线程安全的，不需要同步

用CAS加轻量级锁：直接改变对象头信息，读取对象头，修改对象头，CAS写回判断

轻量级锁到重量级锁：轻量级锁在获取锁时会先自旋，如果自旋N次之后仍没有获取到锁就升级为重量级锁

自适应自旋

JDK6之后对自旋锁的改进，增加历史记录中能够获取到锁的自旋操作的次数，减少历史记录中很少获取锁的自旋操作次数

fork/join并发处理框架

先拆分任务（fork）再合并任务（join），典型的就是归并排序（JDK8中的parallelSort方法），分布式系统，大业务拆分成微服务处理后合并；适用于计算密集型任务，而不适用于I/O密集型任务

ForkJoinPool是ExecutorService接口的实现，它专为可以递归分解成小块的工作而设计

submit

fork

join

get

工作窃取：ForkJoinPool中的线程会在闲置时去主动处理框架内其他线程拆分出的子任务，但工作窃取的实际性能提升要远小于理论性能提升，且API调用复杂性较高，也不可控

框架实现思路：

每个Worker线程都维护一个任务队列，即ForkJoinWorkerThread中的任务队列
任务队列是双向队列，同时支持FIFO和LIFO
拆分出的子任务会被加入到原先任务所在的Worker的任务队列
Worker线程以LIFO的方式取出任务，子任务后加入队列，但需要优先执行
任何Worker的任务队列为空时，都会主动进行任务窃取，如果没有任务可以窃取就会阻塞一段时间，被唤醒后会重复上述步骤
当Worker遇到Join操作时会将队列中的任务全部处理完后在返回

FutureTask

Future继承关系

Future表示异步计算的结果，提供了用于检查计算是否完成、等待计算完成以及获取结果的方法

FutureTask与Callable配合使用，Callable的call方法可以有返回值与异常；FutureTask可以传入Thread去执行，因为FutureTask所包装的Callable中的call方法最后还是要通过Runnable中的run方法去执行

FEATURED TAGS

历史 Java 数据结构数学史计算机科学史 Linux 分布式爬虫数据库 MySQL python

LICENSE

本作品遵照 CC BY-NC-ND 4.0 协议发布。使用者可以对本作品进行转载、节选、混编、二次创作，但不得用于商业目的。使用时必须给出适当的署名，提供指向本作品的链接，同时标明是否修改了本作品。如需发布基于本作品创作的内容，则必须采用与本作品相同的许可协议。

高性能程序设计（三）

锁的实现与优化