上一篇博客介绍了 AnchorTask 的基本使用,今天,让我们一起看一下怎么实现它。
Android 启动优化(二) - 拓扑排序的原理以及解题思路
Android 启动优化(三)- AnchorTask 开源了
AnchorTask,锚点任务,它的实现原理是构建一个有向无环图,拓扑排序之后,如果任务 B 依赖任务 A,那么 A 一定排在任务 B 之前。
了解原理之前,请必须先了解有向无环图和多线程的一些基本知识,不然,下文,你基本是看不懂的。
这里我们采用 BFS 方法实现,算法思想大概是这样的
这里要解决的主要有三个问题
首先,我们定义一个 IAnchorTask 接口,主要有一个方法
isRunOnMainThread(): Boolean
表示是否在主线程运行,默认值是 falsepriority(): Int
方法 表示线程的优先级别,默认值是 Process.THREAD_PRIORITY_FOREGROUNDneedWait()
表示当我们调用 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 方法
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
方法,它有三个参数
taskMap: MutableMap<class, AnchorTask> = HashMap()</class
存储所有的任务,key 是 Class
,value 是 AnchorTasktaskChildMap: MutableMap<class, ArrayList<class>?> =<br /> HashMap()</class</class
,储存当前任务的子任务, key 是当前任务的 class,value 是 AnchorTask 的 list算法思想
当结果队列和 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 这个类很重要,有向无环图的拓扑排序和多线程的依赖唤醒,都是借助这个核心类完成的。
它主要有几个成员变量
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 有点类似于装饰者模式,多线程依赖的执行关系在这里都得到体现,只有几行代码
AnchorTask 的原理不复杂,本质是有向无环图与多线程知识的结合。
AnchorTask 源码已经更新到 github,https://github.com/gdutxiaoxu/AnchorTask
在实现这个开源框架的时候,借鉴了以下开源框架的思想。AppStartFaster 主要是通过 ClassName 找到相应的 Task,而阿里 alpha 是通过 taskName 找到相应的 Task,并且需要指定 ITaskCreator。两种方式各有优缺点,没有优劣之说,具体看使用场景。
android-startup
alpha
AppStartFaster