Linux联合调度相关

发表于 更新于 分类于

摘录一下Jing Li的论文要点，方便查阅

性能界限的定义

通常，可以为实时调度器推导出两种类型的性能界限：

  1. 资源增益界限（Resource Augmentation Bound）：
    调度器 \(S\) 提供一个资源增益界限 \(b \geq 1\)，如果理想调度器能够在 \(m\) 个速度为 1 的核心上调度任何任务集 \(\tau\)，它能够在 \(m\) 个速度为 \(b\) 的核心上成功调度 \(\tau\)。
    • 资源增益界限很好地反映了调度器与最优调度的接近程度，但有一个缺点：理想调度器只是一个假设的调度器，它总能找到一个可行调度（如果存在）。
    • 由于无法验证理想调度器是否能够在单位速度核心上调度给定任务集，因此资源增益界限无法提供可调度性测试。
  2. 利用率界限（Utilization Bound）：
    调度器 \(S\) 提供一个利用率界限 \(b\)，如果它能够在 \(m\) 个核心上成功调度任何任务集，其总利用率不超过 \(m/b\)。
    • 利用率界限比资源增益界限提供了更多信息：任何保证利用率界限 \(b\) 的调度器都会自动保证资源增益界限 \(b\)。
    • 此外，利用率界限本身是一种简单的可调度性测试，因为任务集的总利用率可以在线性时间内计算，并与 \(m/b\) 进行比较。

注意这些界限讨论的是调度的相对效率，而不是程序执行的速度，所以b值越小，调度更有效率。

  1. 容量增益界限 Li 等人 [35] 定义了一个名为容量增益界限（capacity augmentation bound）的概念，这一概念与利用率界限类似，但增加了一个新条件：
    调度器 \(S\) 提供容量增益界限 \(b\)，如果它能够调度满足以下两个条件的任何任务集 \(\tau\)：
  • \(\tau\) 的总利用率最多为 \(m/b\)；
  • 每个任务的最差情况关键路径长度 \(L_i\)（即在无限核心上的执行时间）最多为其截止时间的 \(1/b\) 的比例。

容量增益界限与利用率界限非常相似，但它提供的信息比资源增益界限更多：
- 任何保证容量增益界限为 \(b\) 的调度器也自动保证资源增益界限为 \(b\)。
- 它同样可以作为一种简单的可调度性测试，并提供对系统可承受负载的估计。

策略分类

最近的研究主要集中在为并行任务的各种调度策略证明资源增益界限和容量增益界限。这些工作可以分为两类： 1. 基于分解的策略（Decomposition-based strategies）：
并行任务被分解为一组顺序任务，并使用现有的顺序任务调度策略在多处理器上进行调度。这些策略通常需要事先明确DAG的结构，以便进行分解。

  1. 非分解策略（Non-decomposition-based strategies）：
    程序可以动态展开，因此不需要离线知识。研究主要集中在两种调度策略上：

主要贡献

本文的主要贡献如下： 1. 提出了一种新的联合调度策略（federated scheduling strategy）：
- 在此策略中，每个高利用率任务（利用率 ≥ 1）被分配到一个专用的核心集（cluster）。
- 一个多处理器调度算法用于调度所有低利用率任务，这些任务依次运行在由剩余核心组成的共享核心集上。
- 联合调度可以看作是分区调度策略的推广，适用于并行任务。
- 这是目前已知的针对任意并行 DAG 调度器的最佳容量增益界限。

  1. 证明联合调度的容量增益界限为 2：
    此外，我们还证明了没有任何调度器能够为并行任务提供比 \(2 - 1/m\) 更好的容量增益界限。
    因此，当 \(m\) 足够大时，联合调度的界限为 2 是最优的。

  2. 改进了 G-EDF 的容量增益界限：
    对于 DAG 任务，G-EDF 的容量增益界限被改进为
    \[ \frac{3 + \sqrt{5}}{2} \approx 2.618 \] 当 \(m\) 足够大时，G-EDF 的容量增益界限达到这一匹配的下界。因此，这一结果填补了大 \(m\) 场景下的间隙，这是目前已知针对任意全局调度器的最佳容量增益界限。

  3. 证明 G-RM 的容量增益界限为 \(2 + \sqrt{3} \approx 3.732\) ：

    • 这是目前已知针对任何固定优先级调度器的 DAG 任务的最佳容量增益界限。
    • 即使仅限于同步任务，这仍是基于全局固定优先级调度（且无需分解）的最佳界限。

系统模型

我们现在详细描述并行任务的DAG模型以及一些附加定义。

我们考虑一个由 \(n\) 个独立的间歇性实时任务 \(\tau = \{\tau_1, \tau_2, \dots, \tau_n\}\) 组成的任务集。任务 \(\tau_i\) 表示任务实例（也称为作业）的无限到达和执行序列。我们考虑间歇性任务模型，其中对于任务 \(\tau_i\)： - 最小间隔时间（或周期）\(T_i\) 表示连续任务实例到达之间的时间； - 相对截止时间 \(D_i\) 表示完成作业的时间约束。

如果任务实例 \(\tau_i\) 在时间 \(t\) 到达，则其执行必须在绝对截止时间 \(t + D_i\) 之前完成，且下一个任务实例不能早于 \(t + T_i\) 到达。
在本文中，我们考虑隐式截止时间任务，即每个任务 \(\tau_i\) 的相对截止时间 \(D_i\) 等于其最小间隔时间 \(T_i\)，即 \(T_i = D_i\)。

我们研究在具有 \(m\) 个相同核心的多核系统上调度这些任务集的可调度性。

DAG任务的特性

每个任务 \(\tau_i \in \tau\) 是一个并行任务，并被描述为一个有向无环图（DAG）。
- DAG 中的每个节点（子任务）表示指令序列（一个线程），每条边表示节点之间的依赖关系。 - 当一个节点的所有前驱节点完成时，该节点准备好执行。

在本文中，由于不需要基于DAG的具体结构进行分析，仅定义了与任务 \(\tau_i\) 的执行模式相关的两个参数：

  1. 总执行时间（或工作量）\(C_i\)：
    这是任务 \(\tau_i\) 的所有子任务在最坏情况下的执行时间总和。

  2. 关键路径长度 \(L_i\)：
    在给定DAG中，这是关键路径的长度，其中每个节点由对应子任务的最坏情况下执行时间表示。
    关键路径长度是任务在无限核心下的最坏情况下执行时间。

给定一个DAG，计算 \(C_i\) 和 \(L_i\) 都可以在线性时间内完成。

任务的利用率

  • 任务 \(\tau_i\) 的利用率定义为 \(u_i = \frac{C_i}{T_i} = \frac{C_i}{D_i}\)。
  • 任务集的总利用率表示为： \[ U_\Sigma = \sum_{\tau_i \in \tau} u_i \]

基于利用率的可调度性测试

在本文中，我们从容量增益界限的角度分析调度器。形式化定义如下：

定义 1

给定总利用率为 \(U_\Sigma\) 的任务集 \(\tau\)，如果调度算法 \(S\) 在 \(m\) 个速度为 \(b\) 的核心上总能调度 \(\tau\)，且满足以下条件，则其容量增益界限为 \(b\)：

  1. 利用率限制条件：
    \[ \sum_{\tau_i \in \tau} u_i \leq \frac{m}{b} \]

  2. 关键路径限制条件：
    对于每个任务 \(\tau_i \in \tau\)： \[ L_i \leq \frac{D_i}{b} \]

说明

  • 条件 (1) 表示任务集的总利用率不超过 \(m/b\)。
  • 条件 (2) 表示每个任务的关键路径长度不超过其相对截止时间的 \(1/b\)。

因此，为了验证任务集是否可调度，我们只需知道任务集的总利用率和最大关键路径利用率即可。

当 \(b = 1\) 时，\(S\) 是一个理想调度器；调度器的 \(b\) 越小，其性能越优。

III. 联合调度（Federated Scheduling）

A. 联合调度算法（Federated Scheduling Algorithm）

给定任务集 \(\tau\)，联合调度算法的工作流程如下：

  1. 首先，将任务划分为两个不相交的集合：
    • \(\tau_{\text{high}}\) 包含所有高利用率任务，即利用率至少为 1 的任务（\(u_i \geq 1\)）。
    • \(\tau_{\text{low}}\) 包含所有剩余的低利用率任务。

考虑一个高利用率任务 \(\tau_i\)，其最坏情况下执行时间为 \(C_i\)，关键路径长度为 \(L_i\)，截止时间为 \(D_i\)（与其周期 \(T_i\) 相等）。我们为任务 \(\tau_i\) 分配 \(n_i\) 个专用核心，其中： \[ n_i = \left\lceil \frac{C_i - L_i}{D_i - L_i} \right\rceil \]

  1. 我们使用以下公式计算分配给高利用率任务的核心总数： \[ n_{\text{high}} = \sum_{\tau_i \in \tau_{\text{high}}} n_i \]

  2. 剩余的核心被分配给所有低利用率任务 \(\tau_{\text{low}}\)，其核心数为： \[ n_{\text{low}} = m - n_{\text{high}} \]

如果 \(n_{\text{low}}\) 非负且满足以下条件： \[ n_{\text{low}} \geq 2 \sum_{\tau_i \in \tau_{\text{low}}} u_i \] 则联合调度算法接受任务集 \(\tau\)。

运行时调度（Runtime Scheduling）

在有效的核心分配之后，运行时调度过程如下：

  1. 高利用率任务的调度：
    • 使用任何贪婪调度器（greedy scheduler）对高利用率任务 \(\tau_i\) 进行调度。
    • 贪婪调度器确保当某节点准备好执行时，不会让核心处于空闲状态。
  2. 低利用率任务的调度：
    • 将低利用率任务视为顺序任务，并使用任何多处理器调度算法（如分区EDF或速率单调调度器）进行调度。
    • 低利用率任务的总利用率最多为 \(1/2\)，因此可以在分配的 \(n_{\text{low}}\) 核心上进行调度。

关键点

联合调度算法的一个重要特性是：我们可以安全地将低利用率任务视为顺序任务，因为 \(C_i \leq D_i\)，这表明这些任务在其截止时间内完成时不需要并行执行。