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

设计任务调度系统

设计任务调度系统

任务调度通常同时包含两类规则:依赖关系决定“能不能执行”,优先级决定“当前先执行谁”。本课把任务建模为有向图,用拓扑排序维护就绪状态,再用优先队列选择最高优先级任务,并在处理数量不足时识别依赖环。

学习目标

  • 将任务依赖建模为有向图和入度
  • 使用拓扑排序保证依赖先于任务完成
  • 仅在就绪任务之间应用优先级规则

依赖模型与调度过程

若任务 B 依赖任务 A,建立有向边 A -> B。indegree[B] 表示 B 仍有多少前置任务未完成,next[A] 保存 A 完成后可能被解锁的后继任务。

只有入度为 0 的任务才是就绪任务。全局直接按优先级排序是错误的,因为高优先级任务可能越过尚未完成的依赖;普通队列虽然能完成拓扑排序,却无法表达就绪任务之间的业务优先级。

依赖图与优先就绪队列调度流程

初始化时把所有入度为 0 的任务放入优先队列。每次取出当前最高优先级任务,记录执行顺序,再遍历它的后继并将对应入度减 1;某个后继的入度首次降为 0 时,才加入就绪队列。

构图和遍历所有边的成本为 O(V+E)O(V + E)。每个任务最多进入和离开优先队列一次,因此队列操作为 O(Vlog⁡V)O(V \log V)。如果最终处理的任务数少于任务总数,说明剩余任务被依赖环锁住。

主示例:单线程调度器

以下 Java 17 程序按“优先级降序、任务编号升序”调度就绪任务,并检查重复编号、未知依赖和依赖环。

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 TaskSchedulerDemo {
    private record Task(
            String id, String name, int priority, List<String> dependencies) {
    }

    public static void main(String[] args) {
        List<Task> tasks = List.of(
                new Task("A", "collect", 2, List.of()),
                new Task("B", "clean", 3, List.of("A")),
                new Task("C", "report", 1, List.of("B")),
                new Task("D", "notify", 5, List.of("A"))
        );

        System.out.println("调度顺序: " + schedule(tasks));
    }

    private static List<String> schedule(List<Task> tasks) {
        Map<String, Task> byId = new HashMap<>();
        Map<String, Integer> indegree = new HashMap<>();
        Map<String, List<String>> next = new HashMap<>();

        for (Task task : tasks) {
            if (byId.putIfAbsent(task.id(), task) != null) {
                throw new IllegalArgumentException("重复任务编号: " + task.id());
            }
            indegree.put(task.id(), task.dependencies().size());
        }

        for (Task task : tasks) {
            for (String dependency : task.dependencies()) {
                if (!byId.containsKey(dependency)) {
                    throw new IllegalArgumentException(
                            "未知依赖: " + dependency);
                }
                next.computeIfAbsent(dependency, key -> new ArrayList<>())
                        .add(task.id());
            }
        }

        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.name());

            for (String successor : next.getOrDefault(
                    current.id(), List.of())) {
                int remaining = indegree.merge(
                        successor, -1, Integer::sum);
                if (remaining == 0) {
                    ready.offer(byId.get(successor));
                }
            }
        }

        if (order.size() != tasks.size()) {
            throw new IllegalStateException("任务依赖中存在环");
        }
        return List.copyOf(order);
    }
}

将代码保存为 TaskSchedulerDemo.java,然后编译运行:

bash
javac TaskSchedulerDemo.java
java TaskSchedulerDemo

预期输出:

text
调度顺序: [collect, notify, clean, report]

工程边界

同优先级任务需要稳定的次级排序,否则结果可能随容器遍历顺序变化。生产系统还要区分“进入就绪队列”和“执行成功”:任务失败、重试、超时或取消时,不能直接把后继视为已解锁。

动态新增依赖会改变入度和就绪状态,通常不能只修改一个队列元素。并发执行时,还需要保证某个任务只被一个工作线程领取,并且只有全部前置任务成功后才允许启动后继。

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

目录与阅读设置

阅读设置

17

记录一个想法

设计任务调度系统

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

登录哪都通