简介
在启动器（1）中，我们解决了前后依赖的问题。但是还存在一个问题，实际生产环境中，为了提升性能，一些任务需要放到多线程环境运行。本文主要解决的就是多线程环境下的被依赖的任务先于当前任务执行。
分析
实际上在启动器（1）中，我们已经有相应的一些设计了。比如每个Node都设置了一个List用于存储其依赖的节点（先于当前节点执行），一个List用于存储要依赖当前节点的节点列表（当前节点执行完再执行的节点）。整体上需要解决3个问题，还有一个问题是如何等待和唤醒任务。
问题1：
代码
已BFS为例，后续的启动器也会使用BDS算法：
以下图为例：
遍历的顺序应该为G, E, F, D, C, B, A（顺序不唯一）
import java.util.*;
public class Main {
public static void main(String[] args) {
// 存储所有的节点
List<Node> allNodes = new ArrayList<>();
allNodes.add(new Node("A", new ArrayList<>(Arrays.asList("C", "B")), new ArrayList<>()));
allNodes.add(new Node("B", new ArrayList<>(Collections.singletonList("C")), new ArrayList<>(Collections.singletonList("A"))));
allNodes.add(new Node("C", new ArrayList<>(Collections.singletonList("F")), new ArrayList<>(Arrays.asList("B", "A"))));
allNodes.add(new Node("D", new ArrayList<>(Collections.singletonList("E")), new ArrayList<>()));
allNodes.add(new Node("E", new ArrayList<>(Collections.singletonList("G")), new ArrayList<>(Collections.singletonList("D"))));
allNodes.add(new Node("F", new ArrayList<>(Collections.singletonList("G")), new ArrayList<>(Collections.singletonList("C"))));
allNodes.add(new Node("G", new ArrayList<>(), new ArrayList<>(Arrays.asList("E", "F"))));
createDagGraph(allNodes);
}
/**
* 计算所有节点的入度
*
* @param allNodes 所有节点
*/
private static Map<Node, Integer> calculateDegree(List<Node> allNodes,Node removedNode) {
// 存储每个节点的入度
Map<Node, Integer> degreeMap = new HashMap<>();
// 删除节点
allNodes.remove(removedNode);
// 删除边
for (Node node : allNodes) {
List<String> endNodes = node.getAfterNodes();
endNodes.removeIf(endNodeName -> endNodeName.equals(removedNode.getNodeName()));
List<String> beforeNodes = node.getBeforeNodes();
beforeNodes.removeIf(beforeNode -> beforeNode.equals(removedNode.getNodeName()));
}
// 计算入度
for (Node node : allNodes) {
degreeMap.put(node, node.getBeforeNodes().size());
}
return degreeMap;
}
/**
* 构造DAG图
* @param allNodes 所有节点
*/
private static void createDagGraph(List<Node> allNodes) {
// 存储入度为0的节点，先进先出
Queue<Node> zeroNodeQueue = new LinkedList<>();
// 存储最终的顺序
Queue<Node> resultNodeQueue = new LinkedList<>();
// 所有节点的个数
int nodeSize = allNodes.size();
// 将所有入度为0的节点放入队列
for (Node node : allNodes) {
if (node.getBeforeNodes() != null && node.getBeforeNodes().size() == 0){
zeroNodeQueue.add(node);
}
}
while (zeroNodeQueue.size() > 0){
// 如果存在入度为0的节点，就直接出队列
Node outNode = zeroNodeQueue.remove();
System.out.println("遍历节点 = " + outNode.getNodeName());
resultNodeQueue.add(outNode);
// 移除该节点，计算剩余节点的入度，入度为0的加入到队列
Map<Node, Integer> degreeList = calculateDegree(allNodes,outNode);
for (Map.Entry<Node,Integer> entry : degreeList.entrySet()){
if (entry.getValue() == 0 && !zeroNodeQueue.contains(entry.getKey())){
// 入度为 0 的节点
Node node = entry.getKey();
zeroNodeQueue.add(node);
}
}
}
if (resultNodeQueue.size() != nodeSize){
System.out.println("不是有向无环图，存在环");
}
System.out.println("结果 = " + resultNodeQueue);
}
}
/**
* 节点
*/
class Node {
public Node(String nodeName, List<String> beforeNodes, List<String> afterNodes) {
this.nodeName = nodeName;
this.beforeNodes = beforeNodes;
this.afterNodes = afterNodes;
}
private String nodeName;
private List<String> beforeNodes;
private List<String> afterNodes;
public String getNodeName() {
return nodeName;
}
public void setNodeName(String nodeName) {
this.nodeName = nodeName;
}
public List<String> getBeforeNodes() {
return beforeNodes;
}
public void setBeforeNodes(List<String> beforeNodes) {
this.beforeNodes = beforeNodes;
}
public List<String> getAfterNodes() {
return afterNodes;
}
public void setAfterNodes(List<String> afterNodes) {
this.afterNodes = afterNodes;
}
@Override
public String toString() {
return nodeName;
}
}
