I take back the words of the title, from 0 hand rolled a frame is not easy, need to consider more, some details and realized is questionable, chicken for me this kind of food is also a big challenge, there is insufficient place, offering advice welcome leaders finally heading is a big common style, I see so I, that’s right.
Dependent task loading
We often use a variety of third-party frameworks, such as MMKV, Glide, Leakcanary and other excellent third-party libraries. Most third-party libraries need to be initialized before they can be used, so the following code will appear:
private void init(a) { mmkv.init(context); glide.init(context); leakcanary.init(context); . }Copy the codeIf you don’t want the initialization of a task to block the main thread for too long, you can consider loading the task asynchronously until the last necessary task is loaded and the corresponding operation is performed.
If part of the tasks are dependent, as shown in the following figure, task A depends on task B, and the simple asynchronous mode obviously cannot meet the requirements.
The solutions we usually come up with fall into three categories:
- Write task B at the end of task A
- Listen for the callback function successfully loaded by task A and execute task B
- The loading process is blocked by the volatile keyword
This does solve the problem of loading dependent tasks, but what if the number of tasks and dependencies are more complex?
So if that’s the case, how do you deal with it?
There’s obviously a more general way to do this, and that’s called directed acyclic graphs, which we’ll see below.
Topological ordering of directed acyclic graphs
The above dependency can be viewed as an Directed Acyclic Graph (DAG), which is understood to represent the dependency of the task, and Acyclic is necessary because if task A and task B depend on each other, they need to wait for each other’s end to start, classic deadlock doll-like.
We can present the final linear execution through topological sorting. What is topological sorting?
A simple analysis of the above complex dependency tasks shows that there is no dependency in front of task A, so we can mark the degree of task A as 0, and there is one dependency in front of task B, C and E, and mark the degree as 1. For the remaining task D, because there are two dependencies, we mark the degree as 2. A task queue is used to store tasks with a degree of 0. When the listed task is loaded, it corresponds to the degree -1 of the dependent task, and the new task with a degree of 0 is put into the queue.
- After task A is queued and task A is completed, task B and task C are -1
- In this case, the degree of task B and C are both 0, and both can be queued. There is no established order, so we select task C to be queued. After task C is completed, the degree of task D depends on task C’s degree -1
- Then task B goes in, and after task B is done, the degree of task D and E is -1
- And then finally, one of D, one of E goes in, and we pick whatever we want, we pick D
- The last task is E
Regardless of the time consumption of each task, the dependent task relationship is topologically sorted into A->C->B->D->E. Is it found that the dependency relationship is disentangled and arranged into A linear relationship? This way of topologically linear relationship of directed acyclic graph is called topological sorting, and the topological results vary according to the different algorithms used? This is the central idea behind the implementation of the dependency task loading framework.
Hand lifting relies on the task loading framework
Define IDAGTask class
As mentioned above, the loading of dependent tasks can be solved by topological sorting of directed acyclic graphs. We will start with code to achieve this. First define an IDAGTask class:
public class IDAGTask{}Copy the codeYou may wonder why you don’t use the idea of an interface or abstract class to do this basic class.
Special tasks have load thread constraints, such as loading the task only on the main thread, so we need to consider whether the task can be synchronized. Asynchronous tasks obviously need to use the thread pool, define the IDAGTask class to implement the Runnable interface, convenient to drop into the thread pool later.
In order to ensure thread visibility of the number of dependencies in a concurrent environment, we use the AtomicInteger variable to ensure the real-time correctness of the number of dependencies through the CAS lock. Therefore, the IDAGTask class looks like this:
public class IDAGTask implements Runnable {
private final boolean mIsSyn;
private final AtomicInteger mAtomicInteger;
boolean getIsAsync(a) {
return mIsSyn;
}
void addRely(a) {
mAtomicInteger.incrementAndGet();
}
void deleteRely(a) {
mAtomicInteger.decrementAndGet();
}
int getRely(a) {
return mAtomicInteger.get();
}
@Override
public void run(a) {}}Copy the codeIDAGTask implements the Runnable interface in order to throw tasks into the thread pool. On the other hand, the abstract class approach involves another problem:
- Abstract the run method, which encapsulates the listening of the IDAGTask task, such as startTask and completeDAGTask. If we inherit the IDATask, we simply write the initialization part into the run method, which is very elegant, but there is a case, If the Task is initialized using multiple threads, it would be wrong to listen for completeDAGTask as soon as we call task.init ()
- Based on the above case, I choose an inelegant implementation way, write the startTask listener at the beginning of the run method, and the listener of completeDAGTask needs to be added by the caller himself. The task initialization is realized by single thread at the end of the run method, and the task initialization is realized by multi-thread. The completeDAGTask listener needs to be written into the load success callback
- To sum up, the run method is written into the startTask callback, so the abstraction fails, so IDAGTask has no abstract method and does not need to be an abstract class
After some processing, the final IDATask implementation is as follows:
public class IDAGTask implements Runnable {
private final boolean mIsSyn;
private final AtomicInteger mAtomicInteger;
private IDAGCallBack mDAGCallBack;
private final Set<IDAGTask> mNextTaskSet;
public IDAGTask(a) {
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(a) {
return mIsSyn;
}
void addRely(a) {
mAtomicInteger.incrementAndGet();
}
void deleteRely(a) {
mAtomicInteger.decrementAndGet();
}
int getRely(a) {
return mAtomicInteger.get();
}
void addNextDAGTask(IDAGTask DAGTask) {
mNextTaskSet.add(DAGTask);
}
public void setDAGCallBack(IDAGCallBack DAGCallBack) {
this.mDAGCallBack = DAGCallBack;
}
public void completeDAGTask(a) {
for (IDAGTask DAGTask : mNextTaskSet) {
DAGTask.deleteRely();
}
mDAGCallBack.onCompleteDAGTask();
}
@Override
public void run(a) { mDAGCallBack.onStartDAGTask(); }}Copy the codeDefine DAGProject class
Now that the IDAGTask template is finalized, we need to establish relationships between tasks
- Set stores all tasks. Add tasks through addDAGTask
- Map
stores all tasks and their pre-dependencies. AddDAGEdge adds task dependencies
- The DAGProject class is constructed with the builder pattern
The DAGProject implementation is as follows:
public class DAGProject {
private final Set<IDAGTask> mTaskSet;
private final Map<IDAGTask, Set<IDAGTask>> mTaskMap;
public DAGProject(Builder builder) {
mTaskSet = builder.mTaskSet;
mTaskMap = builder.mTaskMap;
}
Set<IDAGTask> getDAGTaskSet(a) {
return mTaskSet;
}
Map<IDAGTask, Set<IDAGTask>> getDAGTaskMap() {
return mTaskMap;
}
public static class Builder {
private final Set<IDAGTask> mTaskSet = new HashSet<>();
private final Map<IDAGTask, Set<IDAGTask>> 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<IDAGTask> 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(a) {
return new DAGProject(this); }}}Copy the codeTo use it, we need to create the corresponding IDAGTask, and use addDAGTask and addDAGEdge methods to build the acyclic graph of the orientation of the pair:
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();
Copy the codeDAGProject objects expressing task dependencies are constructed successfully through the Builder pattern.
Scheduling depends on task loading
When multiple tasks are built into DAGProject with directed acyclic graph, we do not rush to throw it into the thread pool, and check whether there is a loop before executing the corresponding logic. In this way, we can throw interdependent errors before the task is loaded, rather than wait until the step with a loop is executed. Although there are loops that can be guaranteed by the input, in some small details, we require the input to guarantee too harsh and too poor experience.
- Store tasks with degree 0 in tempTaskQueue
- The while loop takes out the task. If there is a dependency relationship, the corresponding task degree is -1. If the degree is 0, it is added to the resultTaskQueue
- Check whether the last resultTaskQueue is the same as the number of previous stored task sets. If false, a ring will throw an exception
public class DAGScheduler {
private void checkCircle(Set<IDAGTask> TaskSet, Map<IDAGTask, Set<IDAGTask>> TaskMap) {
LinkedList<IDAGTask> resultTaskQueue = new LinkedList<>();
LinkedList<IDAGTask> 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<IDAGTask> 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("Interdependence? Fuck you! I'm not running!"); }}}Copy the codeAfter the loop detection is completed, the dependent tasks are scheduled, and the tasks with degree 0 are added to the blocking queue. Through newSingleThreadExecutor, a thread is started to continuously block the queue to get the tasks.
- The main thread is sent through handler.post, and the asynchronous thread is executed through the thread pool execute
- When all tasks are complete, close the thread pool and end traversal
- Keep adding tasks with degree 0 to the blocking queue
public class DAGScheduler {
private void loop(a) {
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<IDAGTask> iterator = mTaskSet.iterator();
while (iterator.hasNext()) {
IDAGTask DAGTask = iterator.next();
if (DAGTask.getRely() == 0) { mTaskBlockingDeque.put(DAGTask); iterator.remove(); }}}catch(InterruptedException e) { e.printStackTrace(); }}}); }}Copy the codeAt this point, the task-dependent scheduler has been built, and the usage method is as follows in conjunction with the previously constructed DAGProject:
DAGScheduler dagScheduler = newDAGScheduler(); dagScheduler.start(dagProject);Copy the codeuse
The first step is to configure remote dependencies for build.gradle, which has been published to Maven Central. Do not worry about jCenter deprecation
implementation 'work. Lingling. Dagtask: dagtsk: 1.0.0'
Copy the codeSecond, inherit the IDAGTask class and implement the corresponding initialization logic in the RUN method
public class ATask extends IDAGTask {
public ATask(String alias) {
super(alias);
}
@Override
public void run(a) {
super.run();
try {
// Simulate random time
Random random = new Random();
Thread.sleep(random.nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
// Third-party frameworks use synchronous loading internally
// Write the completeDAGTask method at the end of the run method
completeDAGTask();
}
// Third-party frameworks use asynchronous loading internally
The completeDAGTask method needs to be written into the success callback
/*onLibrarySuccess(){ completeDAGTask(); } * /
}
Copy the codeThe completeDAGTask method is written at the end of the run method, sensing the completion of initialization. The load task uses multithreading internally, and you need to write the completeDAGTask method into the load success callback.
The third step is to build and execute the DAGProject based on the dependencies of the tasks
Looking back at the complex dependencies that emerged from the beginning:
We simulate the corresponding tasks, tasks A, B, C, D and E, to construct DAGProject as follows:
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);
Copy the codeThe results of dependent tasks are as follows:
You can see that the dependency tasks are broken down into A, C, B, E, and D for execution.
conclusion
It’s 1202, and there are still people writing clients in Java.
The overall framework implementation is simple, but there are a lot of holes in how the framework should be implemented, how design patterns should be used, what methods should be exposed, and how Maven Central should be uploaded. Midway referred to a lot of big man’s article ideas and good opinions, but still very inadequate, welcome big men next one one guidance.
Finally post the github link: github.com/LING-0001/D… Thanks for watching.