Android 启动优化（四）- AnchorTask 是怎么实现的

╰半夏微凉° 2022-11-05 15:47 123阅读 0赞

上一篇博客介绍了 AnchorTask 的基本使用，今天，让我们一起看一下怎么实现它。

[Android 启动优化（一） - 有向无环图][Android _ -]

[Android 启动优化（二） - 拓扑排序的原理以及解题思路][Android _ - 1]

[Android 启动优化（三）- AnchorTask 开源了][Android _- AnchorTask]

## 原理简介 ##

AnchorTask，锚点任务，它的实现原理是构建一个有向无环图，拓扑排序之后，如果任务 B 依赖任务 A，那么 A 一定排在任务 B 之前。

***了解原理之前，请必须先了解有向无环图和多线程的一些基本知识，不然，下文，你基本是看不懂的***。

### 一个共识 ###

![e133e07a0a72f89fcfac3325e77027e5.png][]

*  **前置任务**：任务 3 依赖于任务 0，1，那么任务 3 的前置任务是任务 0， 1
 *  **子任务**：任务 0 执行完之后，任务 3 才能执行，那么称呼任务 3 为 任务 0 的子任务

### 如何构建一个有向无环图 ###

这里我们采用 BFS 方法实现，算法思想大概是这样的

*  建立入度表，入度为 0 的节点先入队
 *  当队列不为空，进行循环判断
 *   *  节点出队，添加到结果 list 当中
     *  将该节点的邻居入度减 1
     *  若邻居课程入度为 0，加入队列
 *  若结果 list 与所有节点数量相等，则证明不存在环。否则，存在环

### 多线程中，任务执行是随机的，那如何保证任务被依赖的任务先于任务执行呢？ ###

这里要解决的主要有三个问题

1.  首先我们要解决一个问题，它有哪些前置任务，这个可以用 list 存储，代表它依赖的任务 list。当它所依赖的任务 list 没有执行完毕，当前任务需要等待。
2.  当前任务执行完毕之后，所有依赖它的子任务需要感知到。我们可以用一个 map 来存储这种关系，key 是当前任务，value 是依赖于当前任务的集合（list）
3.  多线程当中，等待和唤醒功能，有多种方式可以实现。wait、notify 机制，ReentrantLock Condition 机制，CountDownLatch 机制。这里我们选择 CountDownLatch 机制，因为 CountDownLatch 有点类似于计数器，特别适合这种场景。

## 具体实现 ##

### IAnchorTask ###

首先，我们定义一个 IAnchorTask 接口，主要有一个方法

*  `isRunOnMainThread(): Boolean` 表示是否在主线程运行，默认值是 false
 *  `priority(): Int` 方法 表示线程的优先级别，默认值是 Process.THREAD\_PRIORITY\_FOREGROUND
 *  `needWait()` 表示当我们调用 `AnchorTaskDispatcher await` 时，是否需要等待，return true，表示需要等待改任务执行结束，`AnchorTaskDispatcher await` 方法才能继续往下执行。
 *  `fun getDependsTaskList(): List<class>?</class` 方法返回前置任务依赖，默认值是返回 null.
 *  `fun run()` 方法，表示任务执行的时候

1interface IAnchorTask : IAnchorCallBack {
     2
     3    /**
     4     * 是否在主线程执行
     5     */
     6    fun isRunOnMainThread(): Boolean
     7
     8    /**
     9     * 任务优先级别
    10     */
    11    @IntRange(
    12        from = Process.THREAD_PRIORITY_FOREGROUND.toLong(),
    13        to = Process.THREAD_PRIORITY_LOWEST.toLong()
    14    )
    15    fun priority(): Int
    16
    17    /**
    18     * 调用 await 方法，是否需要等待改任务执行完成
    19     * true 不需要
    20     * false 需要
    21     */
    22    fun needWait(): Boolean
    23
    24    /**
    25     * 当前任务的前置任务，可以用来确定顶点的入度
    26     */
    27    fun getDependsTaskList(): List<Class<out AnchorTask>>?
    28
    29    /**
    30     * 任务被执行的时候回调
    31     */
    32    fun run()
    33
    34}

它有一个实现类 AnchorTask，增加了 await 和 countdown 方法

*  await 方法，调用它，当前任务会等待
 *  countdown() 方法，如果当前计数器值 > 0,会减一，否则，什么也不操作

1abstract class AnchorTask : IAnchorTask {
     2
     3    private val countDownLatch: CountDownLatch = CountDownLatch(getListSize())
     4    private fun getListSize() = getDependsTaskList()?.size ?: 0
     5
     6    companion object {
     7        const val TAG = "AnchorTask"
     8    }
     9
    10    /**
    11     * self call,await
    12     */
    13    fun await() {
    14        countDownLatch.await()
    15    }
    16
    17    /**
    18     * parent call, countDown
    19     */
    20    fun countdown() {
    21        countDownLatch.countDown()
    22    }
    23}

### 排序实现 ###

无环图的拓扑排序，这里采用的是 BFS 算法。具体的可以见 `AnchorTaskUtils#getSortResult` 方法，它有三个参数

*  list 存储所有的任务
 *  `taskMap: MutableMap<class, AnchorTask> = HashMap()</class`存储所有的任务,key 是 Class
    
    ，value 是 AnchorTask
 *  `taskChildMap: MutableMap<class, ArrayList<class>?> =<br /> HashMap()</class</class`,储存当前任务的子任务， key 是当前任务的 class，value 是 AnchorTask 的 list

算法思想

1.  首先找出所有入度为 0 的队列，用 queue 变量存储
2.  当队列不为空，进行循环判断。

*  从队列 pop 出，添加到结果队列
 *  遍历当前任务的子任务，通知他们的入度减一（其实是遍历 taskChildMap），如果入度为 0，添加到队列 queue 里面

*  当结果队列和 list size 不相等试，证明有环
 *      1    @JvmStatic
         2    fun getSortResult(
         3        list: MutableList<AnchorTask>, taskMap: MutableMap<Class<out AnchorTask>, AnchorTask>,
         4        taskChildMap: MutableMap<Class<out AnchorTask>, ArrayList<Class<out AnchorTask>>?>
         5    ): MutableList<AnchorTask> {
         6        val result = ArrayList<AnchorTask>()
         7        // 入度为 0 的队列
         8        val queue = ArrayDeque<AnchorTask>()
         9        val taskIntegerHashMap = HashMap<Class<out AnchorTask>, Int>()
        10
        11        // 建立每个 task 的入度关系
        12        list.forEach { anchorTask: AnchorTask ->
        13            val clz = anchorTask.javaClass
        14            if (taskIntegerHashMap.containsKey(clz)) {
        15                throw AnchorTaskException("anchorTask is repeat, anchorTask is $anchorTask, list is $list")
        16            }
        17
        18            val size = anchorTask.getDependsTaskList()?.size ?: 0
        19            taskIntegerHashMap[clz] = size
        20            taskMap[clz] = anchorTask
        21            if (size == 0) {
        22                queue.offer(anchorTask)
        23            }
        24        }
        25
        26        // 建立每个 task 的 children 关系
        27        list.forEach { anchorTask: AnchorTask ->
        28            anchorTask.getDependsTaskList()?.forEach { clz: Class<out AnchorTask> ->
        29                var list = taskChildMap[clz]
        30                if (list == null) {
        31                    list = ArrayList<Class<out AnchorTask>>()
        32                }
        33                list.add(anchorTask.javaClass)
        34                taskChildMap[clz] = list
        35            }
        36        }
        37
        38        // 使用 BFS 方法获得有向无环图的拓扑排序
        39        while (!queue.isEmpty()) {
        40            val anchorTask = queue.pop()
        41            result.add(anchorTask)
        42            val clz = anchorTask.javaClass
        43            taskChildMap[clz]?.forEach { // 遍历所有依赖这个顶点的顶点，移除该顶点之后，如果入度为 0，加入到改队列当中
        44                var result = taskIntegerHashMap[it] ?: 0
        45                result--
        46                if (result == 0) {
        47                    queue.offer(taskMap[it])
        48                }
        49                taskIntegerHashMap[it] = result
        50            }
        51        }
        52
        53        // size 不相等，证明有环
        54        if (list.size != result.size) {
        55            throw AnchorTaskException("Ring appeared，Please check.list is $list, result is $result")
        56        }
        57
        58        return result
        59
        60    }
    
    ### AnchorTaskDispatcher ###
    
    AnchorTaskDispatcher 这个类很重要，有向无环图的拓扑排序和多线程的依赖唤醒，都是借助这个核心类完成的。
    
    它主要有几个成员变量
    
        1// 存储所有的任务
         2    private val list: MutableList<AnchorTask> = ArrayList()
         3
         4    // 存储所有的任务,key 是 Class<out AnchorTask>，value 是 AnchorTask
         5    private val taskMap: MutableMap<Class<out AnchorTask>, AnchorTask> = HashMap()
         6
         7    // 储存当前任务的子任务， key 是当前任务的 class，value 是 AnchorTask 的 list
         8    private val taskChildMap: MutableMap<Class<out AnchorTask>, ArrayList<Class<out AnchorTask>>?> =
         9        HashMap()
        10
        11    // 拓扑排序之后的主线程任务
        12    private val mainList: MutableList<AnchorTask> = ArrayList()
        13
        14    // 拓扑排序之后的子线程任务
        15    private val threadList: MutableList<AnchorTask> = ArrayList()
        16
        17    //需要等待的任务总数，用于阻塞
        18    private lateinit var countDownLatch: CountDownLatch
        19
        20    //需要等待的任务总数，用于CountDownLatch
        21    private val needWaitCount: AtomicInteger = AtomicInteger()
    
    它有一个比较重要的方法 `setNotifyChildren(anchorTask: AnchorTask)` ，有一个方法参数 AnchorTask，它的作用是通知该任务的子任务，当前任务执行完毕，入度数减一。
    
        1    /**
         2     *  通知 child countdown,当前的阻塞任务书也需要 countdown
         3     */
         4    fun setNotifyChildren(anchorTask: AnchorTask) {
         5        taskChildMap[anchorTask::class.java]?.forEach {
         6            taskMap[it]?.countdown()
         7        }
         8        if (anchorTask.needWait()) {
         9            countDownLatch.countDown()
        10        }
        11    }
    
    接下来看一下 start 方法
    
        1fun start(): AnchorTaskDispatcher {
         2        if (Looper.myLooper() != Looper.getMainLooper()) {
         3            throw AnchorTaskException("start method should be call on main thread")
         4        }
         5        startTime = System.currentTimeMillis()
         6
         7        val sortResult = AnchorTaskUtils.getSortResult(list, taskMap, taskChildMap)
         8        LogUtils.i(TAG, "start: sortResult is $sortResult")
         9        sortResult.forEach {
        10            if (it.isRunOnMainThread()) {
        11                mainList.add(it)
        12            } else {
        13                threadList.add(it)
        14            }
        15        }
        16
        17        countDownLatch = CountDownLatch(needWaitCount.get())
        18
        19        val threadPoolExecutor =
        20            this.threadPoolExecutor ?: TaskExecutorManager.instance.cpuThreadPoolExecutor
        21
        22        threadList.forEach {
        23            threadPoolExecutor.execute(AnchorTaskRunnable(this, anchorTask = it))
        24        }
        25
        26        mainList.forEach {
        27            AnchorTaskRunnable(this, anchorTask = it).run()
        28        }
        29
        30        return this
        31    }
    
    它主要干几件事
    
     *  检测是否在主线程，不是抛出异常，这里为什么要检测在主线程呢？主要是构建有向无环图的过程，我们必须保证是线程安全的
     *  获取有向无环图的拓扑排序
     *  根据拓扑排序的排序结果，执行相应的任务。可以看到在执行任务的时候，我们使用 `AnchorTaskRunnable` 包裹起来
    
        1class AnchorTaskRunnable(
         2    private val anchorTaskDispatcher: AnchorTaskDispatcher,
         3    private val anchorTask: AnchorTask
         4) : Runnable {
         5
         6    override fun run() {
         7        Process.setThreadPriority(anchorTask.priority())
         8        //  前置任务没有执行完毕的话，等待，执行完毕的话，往下走
         9        anchorTask.await()
        10        anchorTask.onStart()
        11        // 执行任务
        12        anchorTask.run()
        13        anchorTask.onFinish()
        14        // 通知子任务，当前任务执行完毕了，相应的计数器要减一。
        15        anchorTaskDispatcher.setNotifyChildren(anchorTask)
        16    }
        17}
    
    AnchorTaskRunnable 有点类似于装饰者模式，多线程依赖的执行关系在这里都得到体现，只有几行代码
    
    1.  前置任务没有执行完毕的话，等待，执行完毕的话，往下走
    2.  执行任务
    3.  通知子任务，当前任务执行完毕了，相应的计数器（入度数）要减一。
    
    ## 总结 ##
    
    AnchorTask 的原理不复杂，本质是有向无环图与多线程知识的结合。
    
    1.  根据 BFS 构建出有向无环图，并得到它的拓扑排序
    2.  在多线程执行过程中，我们是通过任务的子任务关系和 CounDownLatch 确保先后执行关系的
    3.  1.  前置任务没有执行完毕的话，等待，执行完毕的话，往下走
        2.  执行任务
        3.  通知子任务，当前任务执行完毕了，相应的计数器（入度数）要减一。
    
    AnchorTask 源码已经更新到 github，https://github.com/gdutxiaoxu/AnchorTask  
      
    
    
    ## 特别鸣谢 ##
    
    在实现这个开源框架的时候，借鉴了以下开源框架的思想。AppStartFaster 主要是通过 ClassName 找到相应的 Task，而阿里 alpha 是通过 taskName 找到相应的 Task，并且需要指定 ITaskCreator。两种方式各有优缺点，没有优劣之说，具体看使用场景。
    
    android-startup
    
    alpha
    
    AppStartFaster
    
    [Android 启动优化（一） - 有向无环图][Android _ -]
    
    [Android 启动优化（二） - 拓扑排序的原理以及解题思路][Android _ - 1]
    
    [Android 启动优化（三）- AnchorTask 开源了][Android _- AnchorTask]
    
    ![dfefd56586c7e97dec946d5d57a3fa84.png][]

[Android _ -]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95968cdaed07e1ce56e11cffdb84638092e37aaa300b68f2de7a267aceaf19df152b21825&idx=1&mid=2247484968&scene=21&sn=a7938f7504167110baae12f777b248e7#wechat_redirect
[Android _ - 1]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad9597ccdaed06a4064b026d9142235d743e6873e042ce83066edb4e5e6a191f0deeb688bc5&idx=1&mid=2247484988&scene=21&sn=42c83e9ca5eb3d60a1b993e340086e7c#wechat_redirect
[Android _- AnchorTask]: http://mp.weixin.qq.com/s?__biz=MzUzODQxMzYxNQ%3D%3D&chksm=fad95908cdaed01e0ae8c051c8bd8d78bf336d7dfdce02d57a954bc49bd4c8b16e78ab92232f&idx=1&mid=2247485000&scene=21&sn=36f6b98ac4fb90374149e60e6455fca3#wechat_redirect
[e133e07a0a72f89fcfac3325e77027e5.png]: /images/20221023/c71c5fd3d6a1435194b3704150a4c784.png
[dfefd56586c7e97dec946d5d57a3fa84.png]: /images/20221023/f5a7935943c8424fb87e54b8c3701434.png