数据结构与算法 / 系统课时
综合项目:任务依赖调度器
综合项目:任务依赖调度器
本课把依赖图、拓扑排序与优先队列组合成一个可运行的任务调度器。最终程序能够校验任务关系、生成合法执行顺序,并在出现重复任务、未知依赖或循环依赖时给出明确诊断。
学习目标
- 将任务依赖建模为有向图,并用入度判断任务是否就绪。
- 在拓扑顺序合法的前提下,使用优先队列安排高优先级任务。
- 为重复任务、未知依赖和循环依赖设计可验证的异常诊断。
项目目标与数据模型
调度器接收一组任务。每个任务包含唯一 id、整数 priority 和依赖任务列表 dependencies。任务只有在全部依赖完成后才能执行;同时存在多个就绪任务时,优先级数值更大的任务先执行,优先级相同则按 id 升序保证结果稳定。
| 约束 | 处理方式 | 失败结果 |
|---|---|---|
任务 id 唯一 |
建表时检测重复键 | 抛出重复任务异常 |
| 依赖必须存在 | 建图时查询任务表 | 抛出未知依赖异常 |
| 依赖关系无环 | 拓扑排序后核对完成数 | 报告仍被阻塞的任务 |
| 就绪任务按优先级执行 | 使用最大优先级语义的队列 | 输出稳定调度顺序 |
调度流程与核心原理
程序先建立邻接表与入度表。入度为 0 的任务进入就绪队列;每完成一个任务,就把它指向的后继任务入度减 1。后继入度降为 0 时,说明其全部依赖已经完成,可以进入队列等待调度。

设任务数为 ,依赖边数为 。建图与释放后继共处理每个顶点和每条边一次,优先队列的插入与删除最多发生 次,因此时间复杂度为 ,空间复杂度为 。Kahn 算法能确认存在环并找出仍被阻塞的任务;若必须输出精确环路径,可在诊断阶段追加带颜色标记的 DFS。
完整实现与运行
将以下代码保存为 TaskDependencyScheduler.java。示例使用 Java 17 的 record 与 Stream.toList(),同时演示正常调度和循环依赖诊断。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class TaskDependencyScheduler {
record Task(String id, int priority, List<String> dependencies) {
}
static List<String> schedule(List<Task> tasks) {
Map<String, Task> taskById = new HashMap<>();
Map<String, Integer> indegree = new HashMap<>();
Map<String, List<String>> outgoing = new HashMap<>();
for (Task task : tasks) {
if (taskById.putIfAbsent(task.id(), task) != null) {
throw new IllegalArgumentException("任务 ID 重复: " + task.id());
}
indegree.put(task.id(), 0);
outgoing.put(task.id(), new ArrayList<>());
}
for (Task task : tasks) {
for (String dependency : task.dependencies()) {
if (!taskById.containsKey(dependency)) {
throw new IllegalArgumentException("未知依赖: " + dependency);
}
outgoing.get(dependency).add(task.id());
indegree.put(task.id(), indegree.get(task.id()) + 1);
}
}
// 在所有可执行任务中,优先选择优先级更高的任务。
PriorityQueue<Task> ready = new PriorityQueue<>(
Comparator.comparingInt(Task::priority).reversed()
.thenComparing(Task::id));
for (Task task : tasks) {
if (indegree.get(task.id()) == 0) {
ready.offer(task);
}
}
List<String> order = new ArrayList<>();
while (!ready.isEmpty()) {
Task current = ready.poll();
order.add(current.id());
// 释放当前任务的后继;入度归零时才进入就绪队列。
for (String nextId : outgoing.get(current.id())) {
int nextIndegree = indegree.get(nextId) - 1;
indegree.put(nextId, nextIndegree);
if (nextIndegree == 0) {
ready.offer(taskById.get(nextId));
}
}
}
if (order.size() != tasks.size()) {
List<String> blocked = indegree.entrySet().stream()
.filter(entry -> entry.getValue() > 0)
.map(Map.Entry::getKey)
.sorted()
.toList();
throw new IllegalStateException("检测到循环依赖,未完成任务: " + blocked);
}
return order;
}
public static void main(String[] args) {
List<Task> validTasks = List.of(
new Task("fetch", 3, List.of()),
new Task("compile", 5, List.of("fetch")),
new Task("test", 4, List.of("compile")),
new Task("package", 2, List.of("compile")),
new Task("deploy", 5, List.of("test", "package")),
new Task("notify", 1, List.of("deploy")));
System.out.println("调度顺序: " + String.join(" -> ", schedule(validTasks)));
List<Task> cyclicTasks = List.of(
new Task("A", 1, List.of("C")),
new Task("B", 1, List.of("A")),
new Task("C", 1, List.of("B")));
try {
schedule(cyclicTasks);
} catch (IllegalStateException exception) {
System.out.println("异常诊断: " + exception.getMessage());
}
}
}使用 Java 17 编译并运行:
javac TaskDependencyScheduler.java
java TaskDependencyScheduler预期输出:
调度顺序: fetch -> compile -> test -> package -> deploy -> notify
异常诊断: 检测到循环依赖,未完成任务: [A, B, C]验收与边界
验收时不要只检查输出长度,还要验证每条依赖边都满足“前驱先于后继”。可以建立任务到输出位置的映射,对每条边 (u, v) 检查 position(u) < position(v)。优先级只在同时就绪的任务之间生效,不能让高优先级任务越过尚未完成的依赖。
还应覆盖空任务集、单任务、多个独立任务、重复 id、未知依赖、自环和多节点环。生产环境若需要并行执行,可把一次取出一个任务改为批量取出当前就绪任务,但共享入度更新必须保证线程安全。
本课总结
- 入度表负责依赖合法性,优先队列负责就绪任务之间的选择策略,两者职责不能混淆。
- 完成数少于任务总数时说明存在环;阻塞任务集合是最低成本且实用的诊断信息。
- 稳定的次级排序、边界校验和基于依赖边的验收能显著提高调度器的可测试性。
下一课预告
下一课将进入“算法方案评审与优化”,把本项目的正确性依据、复杂度、测试证据、替代方案和优化方向整理为可审查的工程结论。