数据结构与算法 / 系统课时

综合项目:任务依赖调度器

综合项目:任务依赖调度器

本课把依赖图、拓扑排序与优先队列组合成一个可运行的任务调度器。最终程序能够校验任务关系、生成合法执行顺序,并在出现重复任务、未知依赖或循环依赖时给出明确诊断。

学习目标

  • 将任务依赖建模为有向图,并用入度判断任务是否就绪。
  • 在拓扑顺序合法的前提下,使用优先队列安排高优先级任务。
  • 为重复任务、未知依赖和循环依赖设计可验证的异常诊断。

项目目标与数据模型

调度器接收一组任务。每个任务包含唯一 id、整数 priority 和依赖任务列表 dependencies。任务只有在全部依赖完成后才能执行;同时存在多个就绪任务时,优先级数值更大的任务先执行,优先级相同则按 id 升序保证结果稳定。

约束 处理方式 失败结果
任务 id 唯一 建表时检测重复键 抛出重复任务异常
依赖必须存在 建图时查询任务表 抛出未知依赖异常
依赖关系无环 拓扑排序后核对完成数 报告仍被阻塞的任务
就绪任务按优先级执行 使用最大优先级语义的队列 输出稳定调度顺序

调度流程与核心原理

程序先建立邻接表与入度表。入度为 0 的任务进入就绪队列;每完成一个任务,就把它指向的后继任务入度减 1。后继入度降为 0 时,说明其全部依赖已经完成,可以进入队列等待调度。

任务依赖调度流程

设任务数为 VV,依赖边数为 EE。建图与释放后继共处理每个顶点和每条边一次,优先队列的插入与删除最多发生 VV 次,因此时间复杂度为 O(V+E+Vlog⁡V)O(V + E + V \log V),空间复杂度为 O(V+E)O(V + E)。Kahn 算法能确认存在环并找出仍被阻塞的任务;若必须输出精确环路径,可在诊断阶段追加带颜色标记的 DFS。

完整实现与运行

将以下代码保存为 TaskDependencyScheduler.java。示例使用 Java 17 的 record 与 Stream.toList(),同时演示正常调度和循环依赖诊断。

java
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 编译并运行:

bash
javac TaskDependencyScheduler.java
java TaskDependencyScheduler

预期输出:

text
调度顺序: fetch -> compile -> test -> package -> deploy -> notify
异常诊断: 检测到循环依赖,未完成任务: [A, B, C]

验收与边界

验收时不要只检查输出长度,还要验证每条依赖边都满足“前驱先于后继”。可以建立任务到输出位置的映射,对每条边 (u, v) 检查 position(u) < position(v)。优先级只在同时就绪的任务之间生效,不能让高优先级任务越过尚未完成的依赖。

还应覆盖空任务集、单任务、多个独立任务、重复 id、未知依赖、自环和多节点环。生产环境若需要并行执行,可把一次取出一个任务改为批量取出当前就绪任务,但共享入度更新必须保证线程安全。

本课总结

  • 入度表负责依赖合法性,优先队列负责就绪任务之间的选择策略,两者职责不能混淆。
  • 完成数少于任务总数时说明存在环;阻塞任务集合是最低成本且实用的诊断信息。
  • 稳定的次级排序、边界校验和基于依赖边的验收能显著提高调度器的可测试性。

下一课预告

下一课将进入“算法方案评审与优化”,把本项目的正确性依据、复杂度、测试证据、替代方案和优化方向整理为可审查的工程结论。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

综合项目:任务依赖调度器

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通