背景

开发中会存在多个任务之间互相依赖，运行非常慢的情况，譬如Android在主线程中初始化多个SDK导致App启动慢的情况，搜索一下发现业界的通用做法是构造任务的有向无环图，拓扑排序生成有序的任务列表，然后用线程池执行任务列表(通俗的说就是先找到没有依赖的任务执行，执行完了以后再找到剩下的没有依赖的任务执行，如此反复直到执行完所有任务)，但是这个做法无法解决有的任务需要点击对话框授权的情况,基于这个情况打算再造一个轮子出来。

问题

造轮子之前先梳理了一下对这个轮子的要求，发现除了有向无环图外还是有很多细节要解决的。

-依赖任务多线程启动
-支持交互性任务，先拦截任务，交互完成以后再继续执行
-可视化有向无环图
-可视化任务执行情况
-支持多线程、主线程、主进程、第一个任务、最后一个任务等配置属性

方案

开源

TaskGraph: github.com/JonaNorman/…

线程池只能执行没有依赖关系的任务，TaskGraph开源库用有向无环图实现多线程依赖线程池，用拦截器实现交互式任务

图中添加了A任务，B任务依赖A任务执行完再执行，其中A任务需要点击对话框才能执行。

TaskGraph taskGraph = new TaskGraph();
taskGraph.addTask(new Task("A",new Runnable() {//添加A任务
   @Override
   public void run() {
   }
}).addTaskInterceptor(new Task.TaskInterceptor() {
   @Override
   public void onIntercept(Task.TaskInterceptorChain interceptorChain) {//拦截A任务，在A任务之前可以插入对话框
       AlertDialog.Builder builder = new AlertDialog.Builder(TaskGraphModule.getTopActivity());
       builder.setPositiveButton("ok", new DialogInterface.OnClickListener() {
           @Override
           public void onClick(DialogInterface dialog, int which) {
               interceptorChain.proceed();//继续
           }
       });
       builder.setNegativeButton("cancel", new DialogInterface.OnClickListener() {
           @Override
           public void onClick(DialogInterface dialog, int which) {
               interceptorChain.cancel();//取消
           }
       });
       builder.show();
   }
}));
taskGraph.addTask(new Task("B",new Runnable() {
   @Override
   public void run() {//添加B任务,B任务依赖A任务先完成
   }
}).dependsOn("A").setMainThread(true));
taskGraph.execute();

可视化有向图

搜索TASK_GRAPH_LOG: graphviz:会输出有向图日志，复制到 graphviz-visual-editor 可视化查看

可视化任务执行情况

python systrace.py -o trace.html  -a packagename sched

packagename要替换成运行的app的包名 chrome浏览器打开chrome://tracing/,load 按钮加载trace.html

原理

依赖任务多线程启动

正常的线程池只能执行没有依赖关系的任务，怎么才能让线程池支持运行相互依赖的任务呢？ 先找到所有没有进来箭头的节点执行，在该图中也就是A，执行完后删除这个节点和边， 变成了下图

继续以上步骤，找到B运行后删除B,变成下图这样

继续以上步骤，找到C D E同时运行，最终所有任务执行完毕。

把上面的步骤翻译成术语

• 有箭头的图叫有向图
• 节点有多少个进来的箭头叫入度
• 没有进来箭头的节点叫入度为0的节点
• 箭头没有形成环的图叫有向无环图
• 依次找到所有入度为0的节点叫拓扑排序

这里有个问题，多线程怎么执行拓扑排序的节点，有两种做法

1. 拓扑排序的节点列表作为runnable提交到线程池，依赖的任务线程等待其他任务完成在执行
2. 先把入度为0的所有节点提交到线程池，有一个执行完，就触发寻找剩下入度为0的节点继续执行 两种方案我选了方案2，个人感觉方案2找到的节点执行顺序是最优的，并且不需要线程等待，代码简单而且不需要空占有线程池的线程数量

主要思想：

Grpah图有多个node节点，每个Node节点有一个Vertex顶点，多个入边edge，多个出边edge， 拓扑排序就是找所有node节点入度为0的边移除然后继续找直到找完所有节点，核心代码地址

支持交互性任务

有些任务需要交互输入，完成以后再继续执行，为了实现该功能，可以用拦截器的方式来实现。

拦截器的原理就是调用到拦截器时候会用锁等待，如果执行了proceed方法会唤醒锁然后执行下个拦截器，如果执行了cancel会唤醒锁终止所有任务标记cancel状态，每个拦截器必须调用其中一个方法，要不然会一直等待 核心代码如下：代码地址

private void nextIntercept() {
    synchronized (sync) {
        currentInterceptor = taskInterceptorQueue.poll();//获取下一个拦截器
        if (currentInterceptor == null) {
            return;
        }
        currentInterceptor.onIntercept(this);//处罚拦截器
    }
    while (!graphController.isFinished()) {
        synchronized (sync) {
            if (cancel) {//调用cancel方法会把cancel赋值为true
                throw new TaskCancelException();
            } else if (currentInterceptor == proceedInterceptor) {//如果调用了proceed会proceedInterceptor赋值为currentInterceptor
                nextIntercept();//执行下一个拦截器
                break;
            } else {
                try {
                    sync.wait();//等待执行proceed或者cancel方法
                } catch (InterruptedException e) {
                }
            }
        }
    }
}

可视化有向无环图

多个依赖任务添加进去以后如果不能可视化成图就会对影响对任务的把控程度，graphviz是一个图的可视化项目，只要把图的情况写成文本输入就会生成对应图。

  digraph pic {
    A->B;
    B->C;
    }

可视化任务执行情况

多个任务执行实时运行情况，有助于我们优化任务依赖，主要就是在每个任务执行开始调用Trace.beginSection(name),执行完调用Trace.endSection(),然后用命令

python systrace.py -o trace.html  -a packagename sched

生成trace.html,然后用chrome浏览器打开chrome://tracing/点击load按钮加载trace.html就可以查看每个任务的执行情况

支持多线程、主线程、主进程、第一个任务、最后一个任务等配置属性

任务具有多个属性，多线程、主线程、主进程等属性，该实现只要加对应判断就行，第一个任务和最后一个任务则需要遍历所有任务，添加对应依赖关系。

收获

依赖任务多线程调度本身不是很难，在该开源项目中我收获了很多，包括如何实现有向无环图，如何在多线程中实现任务拦截继发，如何使用graphviz实现可视化图，如何用systemtrace可视化任务执行，希望看完文章的同学也可以从中学到什么，谢谢大家的浏览，如果觉得可以，欢迎大家多多star这个开源项目。