死锁

1. 定义

指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。

2. 临界区

指的是一个访问共用资源的程序片段，而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时，其他线程或是进程必须等待。

3. 死锁检测

• 每种资源类型只有一个实例：构建资源分配图，采用深度优先遍历算法确定是否存在环路：依次将每一个节点作为一棵树的根节点，并进行深度优先搜索，如果再次碰到已经遇到过的节点，那么就算找到了一个环。如果从任何给定的节点出发的弧都被穷举了，那么就回溯到前面的节点。如果回溯到根并且不能再深入下去，那么从当前节点出发的子图中就不包含任何环。如果所有的节点都是如此，那么整个图就不存在环也就是说系统不存在死锁。

• 每种资源类型还有多个实例：构建向量矩阵，利用向量矩阵算法模拟资源分配。这种算法的第一步是寻找可以运行完毕的进程Pi，该进程的特点是它有资源请求并且该请求可被当前的可用资源满足(R矩阵第i行向量小于A)。这一选中的进程随后就被运行完毕，在这段时间内它释放自己持有的所有资源并将它们返回到可用资源库中（将C矩阵的第i行向量加到A）。然后这一进程被标记为完成。如果所有的进程最终都能运行完毕的话，就不存在死锁的情况。

4. 死锁避免：

银行家算法

5. 必要条件：

• 互斥条件：进程对所分配到的资源不允许其他进程进行访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源。

• 请求且保持：进程获得资源后，又对其他资源发出请求，但该资源可能被其他进程占有，此时请求阻塞，但又对自己获得的资源保持不放。

• 不可剥夺：进程已获得资源，在未释放前不可被其他进程剥夺。

• 循环等待：进程之间形成一种头尾相接的循环等待资源关系。

并发特性

1. 原子性：一个操作或者多个操作 要么全部执行并且执行的过程不会被任何因素打断，要么就都不执行。

2. 可见性：指当多个线程访问同一个变量时，一个线程修改了这个变量的值，其他线程能够立即看得到修改的值。

3. 有序性：即程序执行的顺序按照代码的先后顺序执行。

线程状态转换

1. NEW：线程定义后（new Thread()）进入的状态。

2. RUNNABLE：Thread.start()后进入RUNNABLE的READY状态，等待获取CPU，获取到CPU后进入RUNNING状态。

3. BOLCK：获得锁失败后进入的状态，获取锁后再进入就绪态（READY）。

4. TERMINATED：线程退出后状态。

5. TIME_WAITING：通过Object.wait(long)等进入到状态，通过Object.notify等重新进入就绪态。

6. WAITING：通过Object.wait等进入到状态，通过Object.notify等重新进入就绪态。

基本机制

• ThreadLocal：用来提供线程内部的共享变量，在多线程环境下，可以保证各个线程之间的变量互相隔离、相互独立。原理是ThreadLocal内部实现是一个线程安全的ThreadLocalMap，key为threadId，value通过set(T value)或者initialValue()设置，达到线程隔离效果。

• Fork/Join：大任务分割成若干小任务，最终汇总每个小任务的结果。内部使用的是工作窃取的方式。假设A和B两个双向队列，每个双向队列拥有一个线程，当A工作结束后就会到B中完成B的任务，被窃取任务线程永远从双端队列的头部拿任务执行，而窃取任务的线程永远从双端队列的尾部拿任务执行。

• Volatile：

• 保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。

• 禁止进行指令重排序。

• Interrupt：线程中断。

同步与互斥

1. Synchronized简介

synchronized关键字最主要有以下3种应用方式：

• 修饰实例方法，作用于当前实例加锁，进入同步代码前要获得当前实例的锁

• 修饰静态方法，作用于当前类对象加锁，进入同步代码前要获得当前类对象的锁

• 修饰代码块，指定加锁对象，对给定对象加锁，进入同步代码库前要获得给定对 象的锁。

底层实现

Java的同步基于进入和退出管程（Monitor）对象实现的。方法同步是通过ACC_SYNCHRONIZED标志来隐式实现的。代码块同步是通过monitorenter和 monitorexit指令来实现的。

JVM中对象分为三块区域：对象头、实例数据、对齐填充。

我们主要来了解对象头，对象头包括Mark Word 和 Class Metadata Address，Mark Word中记录着对象的锁状态信息。默认结构状态如下：

锁状态

25bit

4bit

1bit是否为偏向锁

2bit锁标志位

由于Mark Word被设计成一个非固定的数据结构，以便于存储更多有效的数据，还有可能变换为以下结构：

在Java虚拟机(HotSpot)中，monitor是由ObjectMonitor实现的，其主要数据结构如下（位于HotSpot虚拟机源码ObjectMonitor.hpp文件，C++实现的）

ObjectMonitor() {
    _header       = NULL;
    _count        = 0; //记录个数
    _waiters      = 0,
    _recursions   = 0;
    _object       = NULL;
    _owner        = NULL; //指向拥有锁的线程地址
    _WaitSet      = NULL; //处于wait状态的线程，会被加入到_WaitSet
    _WaitSetLock  = 0 ;
    _Responsible  = NULL ;
    _succ         = NULL ;
    _cxq          = NULL ;
    FreeNext      = NULL ;
    _EntryList    = NULL ; //处于等待锁block状态的线程，会被加入到该列表
    _SpinFreq     = 0 ;
    _SpinClock    = 0 ;
    OwnerIsThread = 0 ;
  }

ObjectMonitor中有两个队列分别是_WaitSet和_EntryList，运行流程：

• enter：线程进入_EntryList队列等待争夺机会进入_Owner。

• acquire：争夺进入_Owner的机会，进入_Owner后，ObjectMonitor的_owner对象指针指向运行线程，count+1。

• release：线程使用wait()方法后，_owner为null，count-1，线程从_Owner移动到_WaitSet队列。

• release and exit：将释放monitor(锁)并复位变量的值，以便其他线程进入获取monitor(锁)。

注：
绿色：正在执行的线程
灰色：等待的线程

2. Lock简介

基于Lock实现类中ReentrantLock的使用场景更广泛，本节简单介绍ReentrantLock的常识。实际上，Lock的实现类还有WriteLock和ReadLock。

ReentrantLock内部Sync继承AQS，包括公平锁FairSync和非公平锁NonFairSync。

• 公平锁：加锁前先查看是否有排队等待的线程，有的话优先处理排在前面的线程，先来先得。

• 非公平锁：线程加锁时直接尝试获取锁，获取不到就自动到队尾等待，默认使用，因为效率比公平锁高。

AQS（AbstractQueuedSynchronizer）

AQS是由一个volatile标记的state、一个同步队列和多个Condition等待队列组成。当state不等于0时，代表锁被占用，进入等待队列，当state为0时则可以参与锁的竞争。

AQS有两种资源共享方式：Exclusive（独占，只有一个线程能执行，如ReentrantLock）和Share（共享，多个线程可同时执行，如Semaphore/CountDownLatch）

以ReentrantLock为例，state初始化为0，表示未锁定状态。A线程lock()时，会调用tryAcquire()独占该锁并将state+1。此后，其他线程再tryAcquire()时就会失败，直到A线程unlock()到state=0（即释放锁）为止，其它线程才有机会获取该锁。当然，释放锁之前，A线程自己是可以重复获取此锁的（state会累加），这就是可重入的概念。但要注意，获取多少次就要释放多么次，这样才能保证state是能回到零态的。

以CountDownLatch以例，任务分为N个子线程去执行，state也初始化为N（注意N要与线程个数一致）。这N个子线程是并行执行的，每个子线程执行完后countDown()一次，state会CAS减1。等到所有子线程都执行完后(即state=0)，会unpark()主调用线程，然后主调用线程就会从await()函数返回，继续后余动作。

3. 多线程锁

JVM中的锁状态

• 无状态锁：顾名思义就是无锁。

• 偏向锁：如果一个线程获得锁，那么锁就进入偏向模式，此时Mark Work结构变为偏向锁结构。当该线程再次获取时节省了请求时间，直接获取锁。而在锁竞争激烈的场景下不能使用偏向锁。

• 轻量级锁：在偏向锁失败的后，Mark Work结构变为轻量级锁结构，如果同一时间访问同一锁的场合，会导致轻量级锁膨胀为重量级锁。

• 重量级锁：会使用到操作系统的互斥量（Mutex）作为同步标志，那么会把想等待获取锁的线程阻塞，这时候不消耗CPU，但这种方式会引起线程在内核态与用户态之间切换、线程之间的切换等开销。

锁类型

优点

缺点

适用场景

锁优化

• 自旋锁：为了避免操作系统的挂起（系统额外庞大开销），使用自旋的方式进行优化，自旋时通过让线程做空循环，在短时间内重新获取锁，进入临界区。

• 锁消除：JVM在JIT时去锁不存在资源竞争的锁，例如单线程的StringBuffer，在JIT阶段会自动清除锁。

4. CAS（Conmpare And Swap）

• 概念：假设V值等于E值则说明线程变量未改变，则可以把V值设置为N值，否则说明该线程的值已被其他线程修改，不可将V值设置为N值。

• CPU对CAS支持：由于CAS是系统原语是由个CPU的指令组成的，保证了原子性、有序性的问题，不会造成数据不一致的问题。

• Unsafe类：Unsafe类中的方法都直接调用操作系统底层资源执行相应任务，CAS也是通过Unsafe实现的，方法都是native方法。

• ABA问题：

• 添加时间戳：AtomicStampedReference彻底解决

• 增加标志位：AtomicMarkableReference减少发生概率。

线程池

构建方法

public ThreadPoolExecutor(int corePoolSize,
                          int maximumPoolSize,
                          long keepAliveTime,
                          TimeUnit unit,
                          BlockingQueue<Runnable> workQueue,
                          ThreadFactory threadFactory,
                          RejectedExecutionHandler handler)

• corePoolSize：核心线程会一直存活，及时没有任务需要执行，且当线程数小于核心线程数时会优先创建线程以达到核心线程数。

• maximumPoolSize：最大线程数，超过最大线程数时会执行拒绝策略。

• keepAliveTime：当线程空闲时间达到keepAliveTime时，线程会退出，直到线程数量=corePoolSize，如果allowCoreThreadTimeout=true，则会直到线程数量=0。

• unit：针对于keepAliveTime的时间单位。

• workQueue：缓冲队列。

• ArrayBlockingQueue(capacity)：设置一个定量的缓冲队列。

• LinkedBlockingQueue：单向链表实现的缓冲队列，无界。

• SynchronousQueue：一个不存储元素的阻塞队列。每个插入操作必须等到另一个线程调用移除操作，否则插入操作一直处于阻塞状态，吞吐量通常要高于LinkedBlockingQueue。

• PriorityBlockingQueue：一个具有优先级的无界阻塞队列。

• threadFactory：定制线程工厂，默认使用DefaultThreadFactory。

• handler：

• Abort：丢弃任务，抛运行时异常，默认策略。

• Discord：忽视，什么都不会发生。

• CallerRuns：执行任务。

• DiscardOldset：从队列中踢出最先进入队列（最后一个执行）的任务。

• 当线程数已经达到maxPoolSize，切队列已满，会拒绝新任务。

• 当线程池被调用shutdown()后，会等待线程池里的任务执行完毕，再shutdown。如果在调用shutdown()和线程池真正shutdown之间提交任务，会拒绝新任务。

• 触发条件：

• 拒绝策略：

应用方法

• newFixedThreadPool

• 源码剖析：

public static ExecutorService newFixedThreadPool(int nThreads) {
    return new ThreadPoolExecutor(nThreads, nThreads,
                                  0L, TimeUnit.MILLISECONDS,
                                  new LinkedBlockingQueue<Runnable>());}

• 核心线程数和最大线程数都设置为nThreads，超时时间为0，且通过LinkedBlockingQueue无界队列创建和未设置参数，那么maximumPoolSize不起作用，当线程池没有可执行任务时，也不会释放线程。
  
  因为队列LinkedBlockingQueue大小为默认的Integer.MAX_VALUE，可以无限的往里面添加任务，直到OOM。

• 使用场景：固定线程数、无界队列、需要保证所有提交的任务都要被执行的情况。

• newCachedThreadPool

• 源码剖析：

• public static ExecutorService newCachedThreadPool() {
      return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                    60L, TimeUnit.SECONDS,
                                    new SynchronousQueue<Runnable>());}
  

  核心线程数为0，但是最大线程数为Integer.MAX_VALUE，默认超时时间60s，内部使用SynchronousQueue作为阻塞队列。
  
  因为线程池的最大值了Integer.MAX_VALUE，会导致无限创建线程；所以，使用该线程池时，一定要注意控制并发的任务数，如果短时有大量任务要执行，就会创建大量的线程，导致严重的性能问题（线程上下文切换带来的开销），线程创建占用堆外内存，如果任务对象也不小，它就会使堆外内存和堆内内存其中的一个先耗尽，导致OOM;

• 使用场景：无限线程数，适用于要求低延迟的短期任务场景。

• newSingleThreadExecutor

• 源码剖析：

• public static ExecutorService newSingleThreadExecutor() {
      return new FinalizableDelegatedExecutorService        (new ThreadPoolExecutor(1, 1,
                                  0L, TimeUnit.MILLISECONDS,
                                  new LinkedBlockingQueue<Runnable>()));}
  

  核心线程数和最大线程数为1，延迟时间为0，使用的是无界的LinkedBlockingQueue，最大线程数保证了执行顺序，LinkedBlockingQueue存在这OOM风险。

• 使用场景：单个线程的固定线程池，适用于保证异步执行顺序的场景。

• newSheduledThreadPool

• 源码剖析：

• public static ExecutorService newFixedThreadPool(int nThreads) {
      return new ThreadPoolExecutor(nThreads, nThreads,
                                    0L, TimeUnit.MILLISECONDS,
                                    new LinkedBlockingQueue<Runnable>());}
  

• 使用场景：：适用于定期执行任务的场景，支持固定频率和固定延迟。

• newWorkStealingPool

  public static ExecutorService newWorkStealingPool(int parallelism) {
      return new ForkJoinPool
          (parallelism,
           ForkJoinPool.defaultForkJoinWorkerThreadFactory,
           null, true);}
  

  ForkJoin使用的是分治策略 + 工作窃取。具体参照上文所述。

• 使用场景：使用的是ForkJoinPool，多任务队列的固定并行度，适合任务执行时长不均匀的场景。

• 源码剖析：

常用工具类（JUC）

类名

特点