/ 前言 /

我收回標題上的話，從0手擼一個框架一點也不輕松，需要考慮的地方比較多，一些實現和細節值得商榷，是一個比較大的挑戰，有不足的地方歡迎大佬們提供意見

/ 依賴任務加載 /

平時我們常常會使用各種第三方框架，如mmkv、glide、leakcanary等優秀的第三方庫，大多數第三方庫需要初始化后才能使用，因此會出現下面的代碼：

private void init() {
mmkv.init(context);
glide.init(context);
leakcanary.init(context);
......
}

如果不想讓任務的初始化阻塞主線程太久，我們可以考慮通過異步的方式加載任務，直到最后一個必要任務加載完畢，開始進行對應的操作。

如果部分任務是依賴關系，如下圖任務A依賴任務B，單純異步的方式的方式顯然不能滿足述求。

我們通常會想到的解決辦法有三類：

• 將任務B寫進任務A的末尾

• 監聽任務A加載成功的回調函數執行任務B

• 通過volatile關鍵字卡住加載流程

這樣確實能夠解決依賴任務的加載問題，但如果任務的數量和依賴關系更復雜呢？

那如果是這樣，你要怎么去處理？

顯然是有一種更通用的方法來解決這種場景，也就是下面會講到的有向無環圖。

/ 有向無環圖的拓撲排序 /

上面的依賴關系可以看成一種有向無環圖（Directed Acyclic Graph, DAG)，有向可以理解，表現的是任務的依賴關系，而無環是必要的，因為如果任務A和任務B相互依賴，都需要等待對方的結束來開始，經典死鎖套娃。

我們可以通過拓撲排序將最后的線性執行關系呈現出來，什么是拓撲排序？

將上面復雜依賴任務簡單的分析一下，任務A前方沒有依賴，因此我們可以將任務A的度記為0，任務B、C、E前方各有一個依賴關系，我們把度記為1，剩下的任務D前方由于有兩個依賴關系，我們將度計為2；用一個任務隊列儲存度為0的任務，每當入列任務加載完畢，它對應依賴任務的度-1，新的度為0的任務進隊列。

• A入隊列，A任務完成后，依賴A任務的任務B、C度-1。

• 這時任務B、C度都為0，都可以入隊列，沒有既定的順序，我們選擇入任務C，待C任務完成后，依賴C任務的D任務的度-1。

• 接著是任務B進去，B任務完成后，任務D、E的度-1。

• 最后是任務D、E其中的一個進去，隨意選擇，我們選擇任務D。

• 最后一個任務E。

不考慮各個任務之間的耗時情況，依賴任務關系被拓撲排序成A->C->B->D->E，是不是發現依賴關系被解開了，排成了線性關系，這種將有向無環圖拓撲成線性關系的方式被稱為拓撲排序，拓撲結果根據所使用算法的不同而有所差異，這也是后面實現依賴任務加載框架的中心思想。

/ 手擼依賴任務加載框架 /

定義IDAGTask類

上面提到依賴任務的加載可以通過有向無環圖的拓撲排序解決，我們開始用代碼實現，先定義一個IDAGTask類：

public class IDAGTask{
}

可能大家會疑問，為什么不用接口或者抽象類的思想去做這個基礎類，后面解答這個疑惑。

特殊的任務會存在加載線程限制，比如只能在主線程對這個任務進行加載，因此我們需要考慮這個任務是否可以同步。異步任務顯然需要使用到線程池，定義IDAGTask類實現Runnable接口，方便后續丟進線程池。

除此之外，之前講到拓撲排序中任務有個度的概念，其實就是依賴關系的數量，在并發環境下為了保證依賴關系數量的線程可見性，這里我們使用AtomicInteger變量，通過CAS鎖來保證依賴數量的實時正確性，因此IDAGTask類變成了這樣：

public class IDAGTask implements Runnable {

private final boolean mIsSyn;
private final AtomicInteger mAtomicInteger;

boolean getIsAsync() {
return mIsSyn;
}

void addRely() {
mAtomicInteger.incrementAndGet();
}

void deleteRely() {
mAtomicInteger.decrementAndGet();
}

int getRely() {
return mAtomicInteger.get();
}

@Override
public void run() {
}

回到之前為什么不用接口或者抽象類的方式來實現這個基礎類，一方面為了后續將任務丟進線程池，IDAGTask實現了Runnable接口，接口的方式顯然pass，另一方面抽象類的方式涉及到了另一個問題：

• 抽象run方法，可以將IDAGTask任務的監聽封裝進去，比如startTask、completeDAGTask，如果我們繼承IDATask，只需要將初始化部分單純寫進run方法就好了，非常優雅，但是有一種case，如果這個任務的初始化是用多線程實現的，我們調用完Task.init()，馬上執行completeDAGTask的監聽其實是不對的

• 基于上面的case，我選擇了一種不優雅的實現方式，將startTask的監聽寫在run方法的開頭，completeDAGTask的監聽需要調用者自己添加，任務初始化是單線程實現寫在run方法的末尾即可，任務初始化采用多線程實現，需要將completeDAGTask監聽寫進加載成功回調

• 綜上，run方法寫進了startTask的回調，因此抽象失敗，那么IDAGTask沒有抽象方法，自然也不需要作為一個抽象類

經過一些加工，最后IDATask實現如下：

public class IDAGTask implements Runnable {

private final boolean mIsSyn;
private final AtomicInteger mAtomicInteger;
private IDAGCallBack mDAGCallBack;
private final Set mNextTaskSet;

public IDAGTask() {
this("");
}

public IDAGTask(boolean isSyn) {
this("", isSyn);
}

public IDAGTask(String alias) {
this(alias, false);
}

public IDAGTask(String alias, boolean IsSyn) {
mIsSyn = IsSyn;
mAtomicInteger = new AtomicInteger();
mDAGCallBack = new DAGCallBack(alias);
mNextTaskSet = new HashSet<>();
}

boolean getIsAsync() {
return mIsSyn;
}

void addRely() {
mAtomicInteger.incrementAndGet();
}

void deleteRely() {
mAtomicInteger.decrementAndGet();
}

int getRely() {
return mAtomicInteger.get();
}

void addNextDAGTask(IDAGTask DAGTask) {
mNextTaskSet.add(DAGTask);
}

public void setDAGCallBack(IDAGCallBack DAGCallBack) {
this.mDAGCallBack = DAGCallBack;
}

public void completeDAGTask() {
for (IDAGTask DAGTask : mNextTaskSet) {
DAGTask.deleteRely();
}
mDAGCallBack.onCompleteDAGTask();
}

@Override
public void run() {
mDAGCallBack.onStartDAGTask();
}

定義DAGProject類

IDAGTask的模板就被敲定了，接下來我們需要建立任務之間的關系：

• Set儲存所有的任務，通過addDAGTask添加任務

• Map儲存所有的任務與其前置依賴關系，通過addDAGEdge添加任務依賴關系

• 整體采用建造者模式構建DAGProject類

于是DAGProject實現如下：

public class DAGProject {

private final Set mTaskSet;
private final Map> mTaskMap;

public DAGProject(Builder builder) {
mTaskSet = builder.mTaskSet;
mTaskMap = builder.mTaskMap;
}

Set getDAGTaskSet() {
return mTaskSet;
}

Map> getDAGTaskMap() {
return mTaskMap;
}

public static class Builder {

private final Set mTaskSet = new HashSet<>();
private final Map> mTaskMap = new HashMap<>();

public Builder addDAGTask(IDAGTask DAGTask) {
if (this.mTaskSet.contains(DAGTask)) {
throw new IllegalArgumentException();
}
this.mTaskSet.add(DAGTask);
return this;
}

public Builder addDAGEdge(IDAGTask DAGTask, IDAGTask preDAGTask) {
if (!this.mTaskSet.contains(DAGTask) || !this.mTaskSet.contains(preDAGTask)) {
throw new IllegalArgumentException();
}
Set preDAGTaskSet = this.mTaskMap.get(DAGTask);
if (preDAGTaskSet == null) {
preDAGTaskSet = new HashSet<>();
this.mTaskMap.put(DAGTask, preDAGTaskSet);
}
if (preDAGTaskSet.contains(preDAGTask)) {
throw new IllegalArgumentException();
}
DAGTask.addRely();
preDAGTaskSet.add(preDAGTask);
preDAGTask.addNextDAGTask(DAGTask);
return this;
}

public DAGProject builder() {
return new DAGProject(this);
}

使用時，我們需要創建對應的IDAGTask，通過addDAGTask、addDAGEdge方法構建出對應有向無環圖：

ATask a = new ATask();
BTask b = new BTask();
CTask c = new CTask();
DTask d = new DTask();
ETask e = new ETask();
DAGProject dagProject = new DAGProject.Builder()
.addDAGTask(a)
.addDAGTask(b)
.addDAGTask(c)
.addDAGTask(e)
.addDAGTask(d)
.addDAGEdge(b, a)
.addDAGEdge(c, a)
.addDAGEdge(d, b)
.addDAGEdge(d, c)
.addDAGEdge(e, b)
.builder();

表達任務依賴關系的DAGProject對象就通過建造者模式構建成功了。

依賴任務加載的調度

當多個任務構建成有向無環圖的DAGProject后，我們先不著急丟進線程池，執行對應邏輯前先檢測是否有環，這樣我們可以在任務加載前拋出相互依賴的錯誤，大可不必等到執行至有環那一步才拋出。雖然有環可以靠輸入者去保障，但是在一些小細節方面，我們要求輸入者保證過于苛刻也過于差體驗。

• 將度為0的任務儲存在tempTaskQueue

• while循環將任務取出，存在依賴關系則對應的任務度-1，如果度為0，添加到resultTaskQueue

• 判斷最后的resultTaskQueue與之前儲存任務的set個數是否相等，false則有環拋出異常

public class DAGScheduler {
private void checkCircle(Set TaskSet, Map> TaskMap) {
LinkedList resultTaskQueue = new LinkedList<>();
LinkedList tempTaskQueue = new LinkedList<>();
for (IDAGTask DAGTask : tempTaskSet) {
if (tempTaskMap.get(DAGTask) == null) {
tempTaskQueue.add(DAGTask);
}
}
while (!tempTaskQueue.isEmpty()) {
IDAGTask tempDAGTask = tempTaskQueue.pop();
resultTaskQueue.add(tempDAGTask);
for (IDAGTask DAGTask : tempTaskMap.keySet()) {
Set tempDAGSet = tempTaskMap.get(DAGTask);
if (tempDAGSet != null && tempDAGSet.contains(tempDAGTask)) {
tempDAGSet.remove(tempDAGTask);
if (tempDAGSet.size() == 0) {
tempTaskQueue.add(DAGTask);
}
}
}
}
if (resultTaskQueue.size() != tempTaskSet.size()) {
throw new IllegalArgumentException("相互依賴，玩屁啊，我不跑了！");
}
}
}

檢測完環后，開始調度這些依賴任務，將度為0的任務加入阻塞隊列，通過newSingleThreadExecutor開啟一個線程不斷去阻塞隊列拿任務。

• 判斷拿出的任務屬于主線程執行還是異步執行，主線程執行通過handler.post發送出去，異步執行通過線程池execute

• 所有任務執行完畢，關閉線程池，結束遍歷

• 不斷將度為0的任務加入阻塞隊列

public class DAGScheduler {
private void loop() {
for (IDAGTask DAGTask : mTaskSet) {
if (DAGTask.getRely() == 0) {
mTaskBlockingDeque.add(DAGTask);
}
}
ExecutorService singleThreadExecutor = Executors.newSingleThreadExecutor();
singleThreadExecutor.execute(() -> {
for (; ; ) {
try {
while (!mTaskBlockingDeque.isEmpty()) {
IDAGTask executedDAGTsk = (IDAGTask) mTaskBlockingDeque.take();
if (executedDAGTsk.getIsAsync()) {
Handler handler = new Handler(getMainLooper());
handler.post(executedDAGTsk);
} else {
mTaskThreadPool.execute(executedDAGTsk);
}
mTaskSet.remove(executedDAGTsk);
}
if (mTaskSet.isEmpty()) {
singleThreadExecutor.shutdown();
mTaskThreadPool.shutdown();
return;
}
Iterator iterator = mTaskSet.iterator();
while (iterator.hasNext()) {
IDAGTask DAGTask = iterator.next();
if (DAGTask.getRely() == 0) {
mTaskBlockingDeque.put(DAGTask);
iterator.remove();
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
}
}

至此依賴任務的調度器搭建完畢，配合之前構建好的DAGProject，使用方法如下：

DAGScheduler dagScheduler = new DAGScheduler();dagScheduler.start(dagProject);

/ 使用方式 /

第一步，對應build.gradle配置遠程依賴，已經發布到maven central，不用擔心jcenter棄用。

implementation 'work.lingling.dagtask:dagtsk:1.0.0'

第二步，繼承IDAGTask類，在run方法中實現對應的初始化邏輯。

public class ATask extends IDAGTask {

public ATask(String alias) {
super(alias);
}

@Override
public void run() {
super.run();
try {
// 模擬隨機時間
Random random = new Random();
Thread.sleep(random.nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
// 第三方框架內部使用同步加載
// completeDAGTask方法寫在run方法末尾即可
completeDAGTask();
}

// 第三方框架內部使用異步加載
// completeDAGTask方法需要寫進成功回調
/*onLibrarySuccess(){
completeDAGTask();
}*/

tips：加載任務內部未開線程，completeDAGTask方法寫在run方法的末尾，感知初始化結束；加載任務內部使用多線程，需要將completeDAGTask方法寫進加載成功回調。

第三步，根據任務的依賴關系構建DAGProject并執行。

回首一開始出現的復雜依賴關系：

我們模擬對應的任務，任務A、B、C、D、E，構建DAGProject如下：

ATask a = new ATask("ATask");
BTask b = new BTask("BTask");
CTask c = new CTask("CTask");
DTask d = new DTask("DTask");
ETask e = new ETask("ETask");
DAGProject dagProject = new DAGProject.Builder()
.addDAGTask(b)
.addDAGTask(c)
.addDAGTask(a)
.addDAGTask(d)
.addDAGTask(e)
.addDAGEdge(b, a)
.addDAGEdge(c, a)
.addDAGEdge(d, b)
.addDAGEdge(d, c)
.addDAGEdge(e, b)
.builder();
DAGScheduler dagScheduler = new DAGScheduler();
dagScheduler.start(dagProject);

依賴任務執行結果如下：

可以看到依賴任務被拆開成A、C、B、E、D的順序進行執行。

/ 結語 /

行文至此，總算湊到了結尾，1202年了，居然還有人在用java寫客戶端。

框架實現整體很簡單，但還是踩了很多坑，大到框架整體應該如何實現，小到設計模式應該如何使用、對外應該暴露什么方法、maven central如何上傳等等各種細節問題，綜上，這是一篇很青澀的文章。中途參考了很多大佬的文章思路和美好意見，但還是很不足，歡迎大佬們下場one one指導。

最后貼一下github鏈接：

https://github.com/LING-0001/DAGTask