2、核心概念：DAG（有向无环图）的定义、拓扑排序与调度边界

在分布式任务调度领域，DAG（Directed Acyclic Graph，有向无环图）是描述任务依赖关系与执行顺序的核心数学模型。理解 DAG 的定义、拓扑排序机制以及调度边界，是设计高效、可靠的 Job Scheduler 的基础。

2.1 DAG 的定义与数学表示

一个 DAG 由一组顶点（Vertex）和一组有向边（Directed Edge）组成，且图中不存在任何环路。在调度场景中：

• 顶点（Vertex）：代表一个具体的任务（Job/Task），包含执行逻辑、资源需求、超时策略等属性。
• 有向边（Directed Edge）：代表任务间的依赖关系，方向从前置任务指向后置任务，表示后置任务必须等待前置任务完成后才能开始执行。
• 无环（Acyclic）：图中不存在从某个顶点出发、经过若干条边后又回到该顶点的路径。这是保证调度可终止、无死锁的前提。

2.2 拓扑排序：从依赖图到执行序列

拓扑排序（Topological Sorting）是将 DAG 中的所有顶点排成一个线性序列，使得对于每一条有向边 (u → v)，顶点 u 在序列中都出现在顶点 v 之前。调度器利用拓扑排序结果来决定任务的启动顺序。

以下是一个包含 6 个任务的 DAG 及其拓扑排序示例：

2.3 调度边界：DAG 在调度系统中的关键约束

调度边界（Scheduling Boundary）是指 DAG 在分布式调度环境中必须遵守的物理与逻辑限制。这些边界决定了调度器的设计复杂度与容错策略。

2.4 拓扑排序在调度边界中的工程实现

在实际的 Job Scheduler 中，拓扑排序并非一次性完成，而是增量式、事件驱动的。调度器维护一个可执行任务队列（Ready Queue），每当一个任务完成，就更新其下游任务的入度计数，并将入度变为 0 的任务加入队列。

// 伪代码：基于 Kahn 算法的增量调度循环
class DAGScheduler:
    def __init__(self, dag):
        self.in_degree = {v: 0 for v in dag.vertices}
        self.adj = dag.edges
        for u, v in dag.edges:
            self.in_degree[v] += 1
        self.ready_queue = [v for v in dag.vertices if self.in_degree[v] == 0]

    def on_task_completed(self, task):
        for successor in self.adj[task]:
            self.in_degree[successor] -= 1
            if self.in_degree[successor] == 0:
                self.ready_queue.append(successor)
        # 调度器从 ready_queue 中取出任务并分配资源执行
        self.dispatch_ready_tasks()