ExecutorService 接口实现源码分析 - 《Java 多线程》

ExecutorService 接口简介
FutureTask
Runnable#run 方法
get 方法
总结

ExecutorService 接口简介

ExecutorService 接口是线程池扩展功能服务接口，它的定义如下：

public interface ExecutorService extends Executor {
    // 停止线程池
    void shutdown();
    // 立即停止线程池，返回尚未执行的任务列表
    List<Runnable> shutdownNow();
    // 线程池是否停止
    boolean isShutdown();
    // 线程池是否终结
    boolean isTerminated();
    // 等待线程池终结
    boolean awaitTermination(long timeout, TimeUnit unit)
        throws InterruptedException;
    // 提交Callable类型任务
    <T> Future<T> submit(Callable<T> task);
    // 提交Runnable类型任务，预先知道返回值
    <T> Future<T> submit(Runnable task, T result);
    // 提交Runnable类型任务，对返回值无感知
    Future<?> submit(Runnable task);
    // 永久阻塞 - 提交和执行一个任务列表的所有任务
    <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks)
        throws InterruptedException;
    // 带超时阻塞 - 提交和执行一个任务列表的所有任务
    <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks,
                                  long timeout, TimeUnit unit)
        throws InterruptedException;
    // 永久阻塞 - 提交和执行一个任务列表的某一个任务
    <T> T invokeAny(Collection<? extends Callable<T>> tasks)
        throws InterruptedException, ExecutionException;
    // 带超时阻塞 - 提交和执行一个任务列表的某一个任务
     <T> T invokeAny(Collection<? extends Callable<T>> tasks,
                    long timeout, TimeUnit unit)
        throws InterruptedException, ExecutionException, TimeoutException;
}

ExecutorService 继承自 Executor，主要提供了线程池的关闭、状态查询、可获取返回值的任务提交、整个任务列表或执行任务列表任意一个任务（返回执行最快的任务的结果）等功能。
让线程运行需要实现 Runnable 接口，才能让线程执行，为了获得返回值，所以要实现 Future 接口。提交到线程池的任务必须要实现 Runnable 接口，但是前面已经实现过一次了，所以要任务封装到其它类，这种做法就是适配器模式。

JUC 的组件	适配描述
Callable	被适配角色
Runnable, Future	Target 对象，该角色定义的方法需要具体处理
FutureTask	适配器，满足提交到线程池的功能
ExecutorService（ThreadPoolExecutor）	线程池，最终任务执行的场合

其中大部分实现逻辑都由 FutureTask 和 ThreadPoolExecutor 的抽象父类 AbstractExecutorService 承担，下面会重点分析这两个类核心功能的源码实现。

FutureTask

提供回调的 Runnable 类型任务实际最终都会包装为 FutureTask 再提交到线程池中执行，而 FutureTask 是 Runnable, Future 和 Callabe 三者的桥梁。先看 FutureTask 的类继承关系：
ExecutorService 接口实现源码分析 - 图1
利用接口可以多继承的特性，RunnableFuture 接口继承自 Runnable 和 Future 接口：

public interface RunnableFuture<V> extends Runnable, Future<V> {
    void run();
}
@FunctionalInterface
public interface Runnable {
    public abstract void run();
}    
public interface Future<V> {
    // 取消，mayInterruptIfRunning用于控制是否中断，实际上这个方法并不能终止已经提交的任务，后面会详细说明
    boolean cancel(boolean mayInterruptIfRunning);
    // 是否取消
    boolean isCancelled();
    // 是否完成，包括正常和异常的情况
    boolean isDone();
    // 永久阻塞获取结果，响应中断
    V get() throws InterruptedException, ExecutionException;
    // 带超时的阻塞获取结果，响应中断
    V get(long timeout, TimeUnit unit)
        throws InterruptedException, ExecutionException, TimeoutException;
}

而 FutureTask 实现了 RunnableFuture 接口，本质就是实现 Runnable 和 Future 接口的方法。
先看看 FutureTask 的重要属性：

// 状态
private volatile int state;
// 初始化状态
private static final int NEW          = 0;
// 完成中状态
private static final int COMPLETING   = 1;
// 正常情况下的完成状态
private static final int NORMAL       = 2;
// 异常情况下的完成状态
private static final int EXCEPTIONAL  = 3;
// 取消状态
private static final int CANCELLED    = 4;
// 中断中状态
private static final int INTERRUPTING = 5;
// 已中断状态
private static final int INTERRUPTED  = 6;
// 底层的Callable实现，执行完毕后需要置为null
private Callable<V> callable;
// 输出结果，如果是正常执行完成，get()方法会返回此结果，如果是异常执行完成，get()方法会抛出outcome包装为ExecutionException的异常
private Object outcome; 
// 真正的执行Callable对象的线程实例，运行期间通过CAS操作此线程实例
private volatile Thread runner;
/**
* 调用 get 方法阻塞的线程会被构造为一个节点，加入到链表 waiters 中，waiters是链表的头节点
* 并不是所有执行 get 方法的线程都会加入到链表中
*/
private volatile WaitNode waiters;
// 下面是变量句柄，底层是基于Unsafe实现，通过相对顶层的操作原语，如CAS等
private static final VarHandle STATE;
private static final VarHandle RUNNER;
private static final VarHandle WAITERS;
static {
    try {
        MethodHandles.Lookup l = MethodHandles.lookup();
        STATE = l.findVarHandle(FutureTask.class, "state", int.class);
        RUNNER = l.findVarHandle(FutureTask.class, "runner", Thread.class);
        WAITERS = l.findVarHandle(FutureTask.class, "waiters", WaitNode.class);
    } catch (ReflectiveOperationException e) {
        throw new ExceptionInInitializerError(e);
    }
    // Reduce the risk of rare disastrous classloading in first call to
    // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
    Class<?> ensureLoaded = LockSupport.class;
}
// ... 省略其他代码

WaitNode 结构

/**
     * Treiber stack of waiting threads
     * 使用Treiber算法实现的无阻塞的Stack，
     * 用于存放等待的线程
     * 实际上是一个单链表，实现了一个非阻塞栈
     */
    private volatile WaitNode waiters;
    static final class WaitNode {
        volatile Thread thread;
        volatile WaitNode next;
        WaitNode() { thread = Thread.currentThread(); }
    }

这里的 waiters 相当于一个 stack，因为在调用 get 方法时任务可能还没有完成，这时需要将调用 get 方法的线程放入 waiters 中。
存储了线程和下一个节点信息，存储线程主要是为了直到唤醒哪一个线程。

FutureTask 的状态管理

FutureTask 的内部有七种状态：

状态	状态值	描述
NEW	0	初始化状态，FutureTask 实例创建时候在构造函数中标记为此状态
COMPLETING	1	完成中状态，这个是中间状态，执行完成后设置 outcome 之前标记为此状态
NORMAL	2	正常执行完成，通过调用 get() 方法能够获取正确的计算结果
EXCEPTIONAL	3	异常执行完成，通过调用 get() 方法会抛出包装后的 ExecutionException 异常
CANCELLED	4	取消状态
INTERRUPTING	5	中断中状态，执行线程实例 Thread#interrupt() 之前会标记为此状态
INTERRUPTED	6	中断完成状态

ExecutorService 接口实现源码分析 - 图2

FutureTask 的构造函数

// 适配使用Callable类型任务的场景
public FutureTask(Callable<V> callable) {
    if (callable == null)
        throw new NullPointerException();
    this.callable = callable;
    this.state = NEW;       
}
// 适配使用Runnable类型任务和已经提供了最终计算结果的场景
public FutureTask(Runnable runnable, V result) {
    this.callable = Executors.callable(runnable, result);
    this.state = NEW;      
}

Executors#callable 方法

// Executors中
public static <T> Callable<T> callable(Runnable task, T result) {
    if (task == null)
        throw new NullPointerException();
    return new RunnableAdapter<T>(task, result);
}
// Runnable和Callable的适配器，设计十分巧妙，实际上run()方法委托给传入的Runnable实例执行，实现了Callable的call()方法，使用的是外部传入的值作为返回结果
private static final class RunnableAdapter<T> implements Callable<T> {
    private final Runnable task;
    private final T result;
    RunnableAdapter(Runnable task, T result) {
        this.task = task;
        this.result = result;
    }
    public T call() {
        task.run();
        return result;
    }
    public String toString() {
        return super.toString() + "[Wrapped task = " + task + "]";
    }
}

submit 方法

既然知道了 FutureTask 的构造函数，我们就来看看是合适调用它的，以及什么时候提交到线程池。
回顾一下线程池的类结构图：
ExecutorService 接口实现源码分析 - 图3

ExecutorService executor = Executors.newCachedThreadPool();
Task task = new Task();
Future<Integer> result = executor.submit(task);

调用 Executors#newCachedThreadPool() 方法默认返回一个 ThreadPoolExecutor，它继承自 AbstractExecutorService 。
在ThreadPoolExecutor 类里没有 submit 方法，所以 executor#submit 方法肯定在它的父类里，所以我们先把目光聚焦于 AbstractExecutorService 里。果然，AbstractExecutorService 类中有 submit 方法。
代码如下：

// AbstractExecutorService
    public <T> Future<T> submit(Callable<T> task) {
        if (task == null) throw new NullPointerException();
        RunnableFuture<T> ftask = newTaskFor(task);
        execute(ftask);
        return ftask;
    }
    protected <T> RunnableFuture<T> newTaskFor(Callable<T> callable) {
        return new FutureTask<T>(callable);
    }

通过 newTaskFor 构造一个 FutureTask 实例，然后把任务投递到线程池中。
AbstractExecutorService 没有实现 execute 方法，所以它必定是由其本身ThreadPoolExecutor 去实现。这么做的好处就是复用了 ThreadPoolExecutor 的逻辑代码，代码简洁明了。

Runnable#run 方法

// FutureTask 实现的Runnable#run()方法
public void run() {
    // 如果状态不为NEW(0)或者CAS(null,当前线程实例)更新runner-真正的执行Callable对象的线程实例失败，那么直接返回，不执行任务
    if (state != NEW ||
        !RUNNER.compareAndSet(this, null, Thread.currentThread()))
        return;
    try {
        // 获取Callable任务实例赋值到临时变量c
        Callable<V> c = callable;
        // 判断任务不能为空，二次校验状态必须为NEW(0)
        if (c != null && state == NEW) {
            V result;
            boolean ran;
            try {
                // 调用任务实例 Callable#call() 回调方法，正常情况下的执行完毕，没有抛出异常，则记录执行结果
                result = c.call();
                // 记录正常执行完毕
                ran = true;
            } catch (Throwable ex) {
                // 异常情况下的执行完毕，执行结果记录为null
                result = null;
                // 记录异常执行完毕
                ran = false;
                // 设置异常实例
                setException(ex);
            }
            // 正常执行完毕设置结果
            if (ran)
                set(result);
        }
    } finally {
        // runner更新为null，防止并发执行run()方法
        runner = null;
        // 记录新的状态值，因为run()方法执行的时候，状态值有可能被其他方法更新了
        int s = state;
        if (s >= INTERRUPTING)
            // 处理run()方法执行期间调用了cancel(true)方法的情况
            handlePossibleCancellationInterrupt(s);
    }
}

set 方法

程序正常执行，使用 CAS 原语把状态修改为 COMPLETING，成功后将结果赋值给 outcome 变量。然后设置最终状态为 NORMAL。最后调用完成后的通知方法 finishCompletion。

protected void set(V v) {
    if (STATE.compareAndSet(this, NEW, COMPLETING)) {
        outcome = v;
        STATE.setRelease(this, NORMAL); // final state
        finishCompletion();
    }
}

setException 方法

程序执行时出现异常。

// 异常执行的情况下，设置异常实例
protected void setException(Throwable t) {
    // CAS更新状态state，由NEW(0)更新为COMPLETING(1)
    if (STATE.compareAndSet(this, NEW, COMPLETING)) {
        // 设置异常实例到outcome属性中
        outcome = t;
        // 设置最终状态state = EXCEPTIONAL(3)，意味着任务最终异常执行完毕
        STATE.setRelease(this, EXCEPTIONAL); // final state
        // 完成后的通知方法
        finishCompletion();
    }
}

finishCompletion 方法（重要）

这个方法尤为重要，因为它是唤醒 get 方法的关键。
我们将任务提交到线程池，然后调用 get 方法返回结果，但是 get 方法是一个阻塞线程的方法，程序执行完成或执行出现异常的时候需要通知对应的线程（唤醒线程），给调用 get 方法的主线程一个结果（或异常）。

// 完成任务后的通知方法，最要作用是移除和唤醒所有的等待结果线程，调用钩子方法done()和设置任务实例 callable 为 null
private void finishCompletion() {
    // 遍历栈，终止条件是下一个元素为null
    for (WaitNode q; (q = waiters) != null;) {
        // 出栈操作，CAS设置栈顶为null，使用 CAS 原语效率高
        if (WAITERS.weakCompareAndSet(this, q, null)) {
            // 遍历栈中的所有节点，唤醒节点中的线程，这是一个十分常规的遍历单链表的方法，注意几点：
            // 1. 使用LockSupport.unpark()唤醒线程，因为后面会分析，线程阻塞等待的时候使用的是LockSupport.park()方法
            // 2. 断开链表节点的时候后继节点需要置为null，这样游离节点才能更容易被JVM回收
            for (;;) {
                Thread t = q.thread;
                if (t != null) {
                    q.thread = null;
                    LockSupport.unpark(t);
                }
                WaitNode next = q.next;
                if (next == null)
                    break;
                q.next = null; 
                q = next;
            }
            break;
        }
    }
    // 回调钩子方法done()，这个可以通过子类进行扩展
    done();
    // 置任务实例callable为null，从而减少JVM memory footprint（这个东西有兴趣可以自行扩展阅读）
    callable = null;        // to reduce footprint
}

handlePossibleCancellationInterrupt 方法

// 处理run()方法执行期间调用了cancel(true)方法的情况
// 这里还没分析cancel()方法，但是可以提前告知：它会先把状态更新为INTERRUPTING，再进行线程中断，最后更新状态为INTERRUPTED
// 所以如果发现当前状态为INTERRUPTING，当前线程需要让出CPU控制权等待到状态更变为INTERRUPTED即可，这个时间应该十分短暂
private void handlePossibleCancellationInterrupt(int s) {
    if (s == INTERRUPTING)
        while (state == INTERRUPTING)
            Thread.yield(); 
}

run 方法流程图

ExecutorService 接口实现源码分析 - 图4

get 方法

带阻塞的 get 方法

// #FutureTask.get
// 获取执行结果 - 永久阻塞
public V get() throws InterruptedException, ExecutionException {
    int s = state;
    // 如果状态小于等于COMPLETING(1)，也就是COMPLETING(1)和NEW(0)，那么就需要等待任务完成
    if (s <= COMPLETING)
        // 注意这里调用awaitDone方法的参数为永久阻塞参数，也就是没有超时期限，返回最新的状态值
        s = awaitDone(false, 0L);
    // 根据状态值报告结果
    return report(s);
}

带超时的阻塞

// 获取执行结果 - 带超时的阻塞
public V get(long timeout, TimeUnit unit)
    throws InterruptedException, ExecutionException, TimeoutException {
    if (unit == null)
        throw new NullPointerException();
    int s = state;
    // 如果状态小于等于COMPLETING(1)，也就是COMPLETING(1)和NEW(0)，那么就需要等待任务完成
    // 注意这里调用awaitDone方法的参数为带超时上限的阻塞参数
    // 如果超过了指定的等待期限（注意会把时间转化为纳秒），返回的最新状态依然为COMPLETING(1)或者NEW(0)，那么抛出TimeoutException异常
    if (s <= COMPLETING &&
        (s = awaitDone(true, unit.toNanos(timeout))) <= COMPLETING)
        throw new TimeoutException();
    // 根据状态值报告结果    
    return report(s);
}

等待任务完成的 awaitDone 方法

// 等待任务完成，区分永久阻塞等待和带超时上限的阻塞等待两种场景
private int awaitDone(boolean timed, long nanos) throws InterruptedException {
    long startTime = 0L;   
    WaitNode q = null;
    boolean queued = false;
    for (;;) {
        int s = state;
        // 如果状态值已经大于COMPLETING(1)，说明任务已经执行完毕，可以直接返回，如果等待节点已经初始化，则置空其线程实例引用，便于GC回收
        if (s > COMPLETING) {
            if (q != null)
                q.thread = null;
            return s;
        }
        else if (s == COMPLETING)
            // 状态值等于COMPLETING(1)，说明任务执行到达尾声，在执行set()或者setException()，只需让出CPU控制权等待完成即可等待下一轮循环重试即可
            Thread.yield();
        else if (Thread.interrupted()) {
            // 如果线程被中断，则清除其中断状态，并且断开超时或中断的等待节点的链接
            removeWaiter(q);
            // 抛出InterruptedException异常
            throw new InterruptedException();
        }
        else if (q == null) {
            // 等待节点尚未初始化，如果设置了超时期限并且超时时间小于等于0，则直接返回状态并且终止等待，说明已经超时了
            // 这里的逻辑属于先行校验，如果命中了就不用进行超时阻塞
            if (timed && nanos <= 0L)
                return s;
            // 初始化等待节点
            q = new WaitNode();
        }
        else if (!queued)
            //如果等待节点尚未加入到栈中，则把当前线程所在的节点压入栈中，top引用指向当前等待节点
            // 这里就是Treiber Stack算法的入栈操作
            queued = WAITERS.weakCompareAndSet(this, q.next = waiters, q);
        else if (timed) {
            // 计算开始时间等待时间于当前时间的相差值作为阻塞的时间parkNanos，因为这里涉及到循环，startTime就是第一轮循环时候的当前系统纳秒
            final long parkNanos;
            if (startTime == 0L) {
                startTime = System.nanoTime();
                if (startTime == 0L)
                    startTime = 1L;
                parkNanos = nanos;
            } else {
                long elapsed = System.nanoTime() - startTime;
                if (elapsed >= nanos) {
                    removeWaiter(q);
                    return state;
                }
                parkNanos = nanos - elapsed;
            }
            // 如果状态为NEW(0)，则进行超时阻塞，阻塞的是当前的线程
            if (state < COMPLETING)
                LockSupport.parkNanos(this, parkNanos);
        }
        else
            // 这种就是最后一个if分支，就是不命中任何条件的永久阻塞，阻塞的是当前的线程
            LockSupport.park(this);
    }
}

移除等待节点的 removeWaiter 方法

// 移除等待节点，这个方法有两次使用的地方：
// 1. 获取结果的线程进行阻塞等待的时候被中断的场景（处理中断）
// 2. 获取结果的线程采用带超时的阻塞等待并且在进行阻塞之前已经判断到超时时间已经到期（处理不小心进栈的无效节点）
// 实际上，这个方法就是Treiber Stack算法的出栈操作
private void removeWaiter(WaitNode node) {
    // 只有目标等待节点不空时候才处理
    if (node != null) {
        // 目标等待节点的线程引用置为空
        node.thread = null;
        // 这里循环标记用于因为此方法执行的竞态条件需要重试的起点
        retry:
        for (;;) {          
            // 遍历的终止条件：q == null，由于变化条件是q = s，并且每轮循环s = q.next，因此终止条件是栈节点的后继节点next为null
            for (WaitNode pred = null, q = waiters, s; q != null; q = s) {
                // 第一轮循环，q其实就是栈顶节点，栈顶节点的后继节点为s，获取说q是当前需要处理的节点，s是其后继节点
                s = q.next;
                // 如果当前节点时有效（持有的线程引用非空）的节点，则前驱节点pred更新为当前节点，进行下一轮遍历
                if (q.thread != null)
                    pred = q;
                // 如果当前节点已经无效，并且它存在前驱节点，那么前驱节点pred的后继节点引用连接到当前节点的后继节点s，实现当前节点的删除
                // 这个是单链表删除中间某一个节点的常规操作
                else if (pred != null) {
                    pred.next = s;
                    // 如果在当前节点已经无效，并且它存在前驱节点，但是前驱节点二次判断为无效，说明出现了竞态，需要重新进行栈waiters的遍历
                    if (pred.thread == null) // check for race
                        continue retry;
                }
                // 当前节点已经无效，它不存在前驱节点，则直接把当前节点的后继节点s通过CAS更新栈顶节点
                // 类比前面分析过的ConcurrentStack的pop()方法，这里的q就是oldHead，s就是newHead。
                // CAS更新失败说明存在竞态，则需要重新进行栈waiters的遍历
                else if (!WAITERS.compareAndSet(this, q, s))
                    continue retry;
            }
            break;
        }
    }
}

报告结果的方法 report

// 报告结果的方法，入参是awaitDone()方法返回的状态值
private V report(int s) throws ExecutionException {
    Object x = outcome;
    // 如果状态值为NORMAL(2)正常执行完毕，则直接基于outcome强转为目标类型实例
    if (s == NORMAL)
        return (V)x;
    // 如果状态值大于等于CANCELLED(4)，则抛出CancellationException异常
    if (s >= CANCELLED)
        throw new CancellationException();
    // 其他情况，实际上只剩下状态值为EXCEPTIONAL(3)，则基于outcome强转为Throwable类型，则包装成ExecutionException抛出
    throw new ExecutionException((Throwable)x);
}

cancel 方法

public boolean cancel(boolean mayInterruptIfRunning) {
    // 状态必须为NEW(0)
    // 如果mayInterruptIfRunning为true，则把状态通过CAS更新为INTERRUPTING(5)
    // 如果mayInterruptIfRunning为false，则把状态通过CAS更新为CANCELLED(4)
    // 如果状态不为NEW(0)或者CAS更新失败，直接返回false，说明任务已经执行到set()或setException()，无法取消
    if (!(state == NEW && STATE.compareAndSet(this, NEW, mayInterruptIfRunning ? INTERRUPTING : CANCELLED)))
        return false;
    try {   
        // mayInterruptIfRunning为true，调用执行任务的线程实例的Thread#interrupt()进行中断，更新最终状态为INTERRUPTED(6)
        if (mayInterruptIfRunning) {
            try {
                Thread t = runner;
                if (t != null)
                    t.interrupt();
            } finally { // final state
                STATE.setRelease(this, INTERRUPTED);
            }
        }
    } finally {
        // 完成后的通知方法，唤醒下一个节点
        finishCompletion();
    }
    return true;
}

cancel 方法只能中断 NEW(0) 状态的线程，并且由于线程只在某些特殊情况下（例如阻塞在同步代码块或同步方法中阻塞在 Object#wait 方法、主动判断线程中断状态等等）才能响应中断，所以需要思考这个方法是否可以达到预想的目的。
最后看看状态判断方法：

// 判断是否取消状态，包括CANCELLED(4)、INTERRUPTING(5)、INTERRUPTED(6)三种状态
public boolean isCancelled() {
    return state >= CANCELLED;
}
// 判断是否已经完成，这里只是简单判断状态值不为NEW(0)，原因是所有的中间状态都是十分短暂的
public boolean isDone() {
    return state != NEW;
}

总结

出栈和入栈操作使用了 CAS，没有加锁。这块还得再理解理解。《Java 并发编程实战》有无锁并发栈的相关代码，维基百科有收录，ConcurrentStack。
依赖于线程池实现的 execute 方法进行异步任务提交。
使用适配器模式设计 FutureTask 适配 Future, Runnable 和 Callable，提供了状态的生命周期管理。