实时系统调度 课程笔记

写在前面：

本文章是根据法国国立高等电力技术、电子学、计算机、水力学与电信学校 (E.N.S.E.E.I.H.T.) 第九学期课程 “Real Time System Scheduling” 及以下参考资料总结而来的课程笔记。碍于本人学识有限，部分叙述难免存在纰漏，请读者注意甄别。

一、什么是实时系统

1 实时系统的相关概念

与我们日常使用的操作系统不同，实时系统不仅要求计算结果正确，而且要求结果必须在一个特定的截止期限内产生（时间约束），否则即使正确也没有意义。

例如我们在实验中遇到的自平衡车：我们设计的系统需要根据传感器反馈的数据（加速度等）实时地调整车的姿态，从而使得车在一段时间内不会倾倒（时间约束），一旦超过这个时间，车就会倾倒，此时就算做出正确的调整也无济于事，因为车已经倒了。

“A real-time system is able, first to read all incoming data before they become useless, second to give an appropriate timely reaction.”

“一个实时系统首先能够在所有传入的数据变得无用之前读取它们，其次能够及时做出适当的反应”

由此可见，实时系统的一个最大的特点就是时间正确性（timporal correctness）：在数据变得无用（ddl）之前产生结果，否则产生的结果便是错误的。

然而在时间的约束上也有严格与不严格之分：

• 硬实时系统：必须在截止日期之前（deadline）完成，比如汽车的制动系统

  Hard real-time : a missed deadline can have catastrophic consequences

• 软实时系统：可以偶尔超过截止时间（deadline）完成，比如视频播放的跳帧

  • Soft real-time : some (not frequent) missed deadlines can be tolerated

2 实时系统中的任务

按周期划分的任务

在实时系统中，一个应用通常由一组任务构成，每个任务完成应用中的一部分功能，组合后为用户提供特定的服务。根据任务的周期划分实时任务，可以分为 3 类：

我们通常规定，在处理器的时序图中，

• 使用向上的箭头 $\uparrow$ 表示该任务的一个周期的开始时间（或就绪时间，即任务可以在此时刻后开始）；
• 使用向下的箭头 $\downarrow$ 表示该任务的截止时间（deadline）。

• 周期任务（Periodic tasks）：周期任务是指按一定周期达到并请求运行。对于每个周期任务，假设周期为 $P$，运行时间为 $C$，截止时长为 $D$，一般有 $0 \le C \le D \le P$。

  

• 偶发任务（Sporadic tasks）：在偶发任务中，虽然其任务实例的到达时刻不是严格周期的，但相邻任务实例到达时刻的时间间隔一定 $\ge$ 某个最小值，即偶发任务的各任务按照不高于某个值的速率到达。因此在实际应用中，偶发任务经常被当作周期任务进行处理，其周期为相邻任务实例到达时刻的最小时间时隔。

  

• 非周期性任务（Aperiodic tasks）：非周期任务是指随机到达系统的任务。通常每个任务有一个最迟开始时间，或者最迟结束时间的限制。

  

任务的优先级

我们也可以对任务赋予有优先级（Priority）属性，

• 在抢占式（Preemptive）的调度中，一个优先级更高的任务可以抢占当前正在处理的任务，从而获得处理器资源；
• 在非抢占式（Non- Preemptive）的调度中，旦把处理器资源分配给某个任务后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在处理的任务，直至该任务处理完成，或发生某事件而被阻塞时，该任务才释放处理器资源。

任务具有的必要属性

一个任务 $T_i$ 是由多个工作（job）组成。我们思考一下一个任务 $T_i$ 应该具有哪些属性？

• 最坏情况下的执行时间（WCET，Worst-Case Execution Time）：

  执行一项工作所花费时间的安全上限，即实际执行时间（下图中用阴影表示）应该小于等于这个上限。使用 $C_i$ 表示。

  “Safe upper bound on the execution time of one job of the task”

• （对于一个周期性任务）周期（Release period）：

  在该任务中，连续的两个工作间的持续时间。使用 $P_i$ 表示。

  提示 ⚠️：

  周期 $P_i$，也即连续两个工作的就绪时间之间的时间段，表现在图上就是两个向上的箭头 $\uparrow$ 间的时间段。

  “(Minimum) duration between consecutive job releases of the task”

• 相对的截止时间（Relative deadline）：

  任务中每项工作的最大允许响应时间。使用 $D_i$ 表示。

  表现在图上就是向上的箭头 $\uparrow$ 与向下的箭头 $\downarrow$ 之间的时间段。

  “Maximum allowed response time for each job of the task”

当我们在一个多任务（multitask）的系统内编排这些任务时，就需要引入调度器（Scheduler）与不同的调度策略（Scheduling strategy）。

二、实时调度

1 实时调度简介

在多任务的实时系统中，任务必须满足实时约束地被调度。那么，什么样的调度可以称为可行的调度（Feasible scheduling）呢？

“The worst-case response time of every job of every task is not greater than the task’s relative deadline”

"任务中每项工作 $T_i$ 的最坏情况响应时间 $C_i$（WCET）不超过任务的相对截止日期 $D_i$ "

如下图，我们给出任务 $T_1$、$T_2$ 的各项属性：

• $T_1 (r_1:0, \; C_1:1, \; D_1:2, \; P_1:3)$ ，即（初始就绪时刻=0，WCET=1，ddl=2，周期=3）
• $T_2 (r_2:0, \; C_2:4, \; D_2:6, \; P_2:6)$ ，即（初始就绪时刻=0，WCET=4，ddl=6，周期=6）

• 我们可以看到，第一种调度显然是一种非抢占式的调度。因为在时刻 1 时， $T_2$ 任务获取处理器资源并使用，时刻 3 时 $T_1$ 任务想要获取处理器但是 $T_2$ 任务仍然在占用。直至 $T_1$ 任务的 $D_2$ 时刻才释放，然而 $T_1$ 任务已经错过了本次的 Deadline（$T_1$ misses its deadline）。所以该调度不可行。
• 第二种调度显然是一种抢占式的调度，且给出了一种满足可行性要求的调度。所以该调度可行。

2 竞争时刻与繁忙阶段

我们假设若干个任务 $T_n$ 按照优先级排序：

$\text{Priority}(T_1) > \text{Priority}(T_2) > \text{Priority}(T_3) > ... >\text{Priority}(T_n)$

我们做出如下定义：

• 竞争时刻（Critical instant）：任务 $T_i$ 与所有更高优先级的任务同时处于就绪时刻（即可以开始任务执行的时刻）。

  "$T_i$ is released simultaneously with all the higher priority tasks"

  在图中使用向上的箭头 $\uparrow$ 表示就绪时刻。

• Level-i 繁忙阶段（Level-i busy period）：CPU 被优先级高于或等于 $T_i$ 的任务的阶段。

  "Time period where the CPU is kept busy by tasks whose priority is higher or equal to priority of $T_i$"

下面，我们将给出一个关于任务 $T_1$、$T_2$ 的例子，并逐步分析：

• $T_1 (r_1:0, \; C_1:1, \; D_1:2, \; P_1:2)$ ，即（初始就绪时刻=0，WCET=1，ddl=2，周期=2）
• $T_2 (r_2:0, \; C_2:2, \; D_2:5, \; P_2:5)$ ，即（初始就绪时刻=0，WCET=2，ddl=5，周期=5）
• $\text{Priority}(T_1) > \text{Priority}(T_2)$
• CPU 空闲点（idle point）

---

【逐步分析】：

在分析之前，我们观察到各个任务周期的最小公倍数 $LCM_{1\le i \le n}$ 可以构成一个“最小公倍周期（hyperperiod）”。即每个“最小公倍周期（hyperperiod）”的调度都相同。

$LCM_{1\le i \le n}(P_1,P_2,...P_n), 关于所有周期P_i的最大公约数$

0. 第 0 时刻，任务 $T_1$、$T_2$ 均处于就绪时刻，此时是竞争时刻。但由于 $T_1$ 的优先级更高，所以先执行。对于 Level-2 繁忙阶段 来说，此时有 3 个单位（$C_1:0/1$、$C_2:0/2$）的工作可以执行（Workload）。
1. 第 1 时刻，任务 $T_1$ 执行完毕，任务 $T_2$ 依然处于就绪时刻。 $T_2$ 开始执行。对于 Level-2 繁忙阶段 来说，此时有 2 个单位（$C_1:1/1$、$C_2:0/2$）的工作可以执行（Workload）。
2. 第 2 时刻，任务 $T_1$ 处于新周期的就绪时刻，任务 $T_2$ 处理了一个单位时间。但由于 $T_1$ 的优先级更高，所以暂停 $T_2$，开始执行 $T_1$。对于 Level-2 繁忙阶段 来说，此时有 2 个单位（$C_1:0/1$、$C_2:1/2$）的工作可以执行（Workload）。
3. 第 3 时刻，任务 $T_1$ 执行完毕，任务 $T_2$ 可以继续执行。 $T_2$ 开始执行。对于 Level-2 繁忙阶段 来说，此时有 1 个单位（$C_1:1/1$、$C_2:1/2$）的工作可以执行（Workload）。
4. 第 4 时刻，任务 $T_1$ 处于新周期的就绪时刻，任务 $T_2$ 执行完毕。所以开始执行 $T_1$。对于 Level-2 繁忙阶段 来说，此时有 1 个单位（$C_1:0/1$、$C_2:2/2$）的工作可以执行（Workload）。
5. 第 5 时刻，任务 $T_1$ 执行完毕，任务 $T_2$ 处于新周期的就绪时刻。 $T_2$ 开始执行。对于 Level-2 繁忙阶段 来说，此时有 2 个单位（$C_1:1/1$、$C_2:0/2$）的工作可以执行（Workload）。
6. 第 6 时刻，任务 $T_1$ 处于新周期的就绪时刻，任务 $T_2$ 处理了一个单位时间。但由于 $T_1$ 的优先级更高，所以暂停 $T_2$，开始执行 $T_1$。对于 Level-2 繁忙阶段 来说，此时有 2 个单位（$C_1:0/1$、$C_2:1/2$）的工作可以执行（Workload）。
7. 第 7 时刻，任务 $T_1$ 执行完毕，任务 $T_2$ 可以继续执行。 $T_2$ 开始执行。对于 Level-2 繁忙阶段 来说，此时有 1 个单位（$C_1:1/1$、$C_2:1/2$）的工作可以执行（Workload）。
8. 第 8 时刻，任务 $T_1$ 处于新周期的就绪时刻，任务 $T_2$ 执行完毕。所以开始执行 $T_1$。对于 Level-2 繁忙阶段 来说，此时有 1 个单位（$C_1:0/1$、$C_2:2/2$）的工作可以执行（Workload）。
9. 第 9 时刻，任务 $T_1$ 执行完毕，任务 $T_2$ 执行完毕，且两个任务都没有到各自周期的 deadline。所以没有任务执行。对于 Level-2 繁忙阶段 来说，此时有 0 个单位（$C_1:1/1$、$C_2:2/2$）的工作可以执行（Workload）。
10. 第 10 时刻与第 0 时刻完全相同，因为两个任务周期（$P_1:2$、$P_2:5$）的最大公约数 LCM=10。

---

在上面的例子中，我们发现在第 9 时刻到第 10 时刻内，处理器是空闲的。

处理器的使用率

我们使用 $U$ 来表示处理器的使用率：

$U = \sum ^{n} _{i=1} \frac {C_i} {P_i} \le 1$

当 $U \le 1$ 时，说明这个处理器没有过载（Overloaded）。

响应时间与最小不动点

注意 ⚠️：笔者并未完全理解这里的公式意图。给出参考文献地址，建议读者自行研究：

• 学习课件：GitHub : S9_S9_3A_SN_ENSEEIHT
• 网上资料：EN : Tutorial on real-time scheduling

【情况 1】：$D_i \le P_i$ 且抢占式调度

我们使用以下公式寻找任务 $T_i$ 的响应时间 $R^{(n+1)}_i$ 中的最小不动点 $R^{(*)}_i$（当响应时间不变时，即为不定点）：

$\begin{aligned} & R^{(0)}_i \quad = C_i \\ & R^{(n+1)}_i = C_i + \sum _{j\in hp(i)} \left \lceil \frac{R^{(n)}_i}{P_j} \right \rceil \times C_j \end{aligned}$

提示 ⚠️：

• $j \in hp(i)$，$hp(i)$ 是优先级高于 $i$ 的集合

• $\left \lceil \frac{R^{(n)}_i}{P_j} \right \rceil$ 符号为向上取整，$\left \lceil 4.1 \right \rceil = 5$

使用之前研究过的任务 $T_1$、$T_2$：

• $T_1 (r_1:0, \; C_1:1, \; D_1:2, \; P_1:2)$ ，即（初始就绪时刻=0，WCET=1，ddl=2，周期=2）
• $T_2 (r_2:0, \; C_2:2, \; D_2:5, \; P_2:5)$ ，即（初始就绪时刻=0，WCET=2，ddl=5，周期=5）

$\begin{aligned} & R^{(0)}_2 \quad = C_2 = 2\\ & R^{(1)}_2 \quad = C_2 + \left \lceil \frac{R^{(0)}_2}{P_1} \right \rceil \times C_1 = 2 + \left \lceil \frac{2}{2} \right \rceil \times 1 = 3 \\ & R^{(2)}_2 \quad = C_2 + \left \lceil \frac{R^{(1)}_2}{P_1} \right \rceil \times C_1 = 2 + \left \lceil \frac{3}{2} \right \rceil \times 1 = 4 \\ & R^{(3)}_2 \quad = C_2 + \left \lceil \frac{R^{(2)}_2}{P_1} \right \rceil \times C_1 = 2 + \left \lceil \frac{4}{2} \right \rceil \times 1 = 4 = R^{(2)}_2 = R^{(*)}_2 \end{aligned}$

【情况 2】：$D_i > P_i$（说明任务 $T_i$ 下一个周期的工作在前一个周期未结束的时候就绪）

• 在这种情况下，必须计算这个工作 $\text{job}_k$ 的响应时间 $R^{(n+1)}_i(k)$，有时也写作 $t_k$

• 因为我们需要：测试 $k$ 个工作（jobs），直到满足一个工作完成后才发布下一个工作，即

  $R^{(*)}_i(k) \le k \times P_i$

  "$k$ jobs have to be tested, until a job finishes execution before the release of the following job"

• 计算公式类比于【情况 1】，如下所示：

$\begin{aligned} & R^{(0)}_i(k) \quad = k \times C_i \\ & R^{(n+1)}_i(k) = k \times C_i + \sum _{j\in hp(i)} \left \lceil \frac{R^{(n)}_i(k)}{P_j} \right \rceil \times C_j \end{aligned}$

下面，我们将给出另一个关于任务 $T_1$、$T_2$ 的例子，并分析：

---

• $T_1 (r_1:0, \; C_1:26, \; D_1:70, \; P_1:70)$ ，即（初始就绪时刻=0，WCET=26，ddl=70，周期=70）

• $T_2 (r_2:0, \; C_2:62, \; D_2:118, \; P_2:100)$ ，即（初始就绪时刻=0，WCET=62，ddl=118，周期=100）

计算过程：

• 对于任务 $T_1$，没有优先级高于该任务的：

  $\begin{aligned} & R^{(0)}_1 \quad = C_1 = 26\\ & R^{(1)}_1 \quad = C_1 = 26 = R^{(0)}_1 = R^{(*)}_1 \end{aligned}$

• 对于任务 $T_2$，$T_1$ 优先级高于该任务：

  $\begin{aligned} & R^{(0)}_2(1) \quad = C_2 = 62\\ & R^{(1)}_2(1) \quad = C_2 + \left \lceil \frac{R^{(0)}_2(1)}{P_1} \right \rceil \times C_1 = 62 + \left \lceil \frac{62}{70} \right \rceil \times 26 = 88 \\ & R^{(2)}_2(1) \quad = C_2 + \left \lceil \frac{R^{(1)}_2(1)}{P_1} \right \rceil \times C_1 = 62 + \left \lceil \frac{88}{70} \right \rceil \times 26 = 114 \\ & R^{(3)}_2(1) \quad = C_2 + \left \lceil \frac{R^{(2)}_2(1)}{P_1} \right \rceil \times C_1 = 62 + \left \lceil \frac{114}{70} \right \rceil \times 26 = 114 = R^{(2)}_2(1) = R^{(*)}_2(1)\\ & \because R^{(*)}_2(1) > k \times P_2 \text{，不满足要求}\quad \therefore\text{令 k=2，继续计算}\\ \\ & R^{(*)}_2(2) = 202 > 2 \times P_2(=200) \\ & R^{(*)}_2(3) = 316 > 3 \times P_2(=300) \\ & R^{(*)}_2(4) = 404 > 4 \times P_2(=400) \\ & R^{(*)}_2(5) = 518 > 5 \times P_2(=500) \\ & R^{(*)}_2(6) = 606 > 6 \times P_2(=600) \\ & R^{(*)}_2(7) = 694 < 7 \times P_2(=700) \quad \text{满足条件，且最后一个工作的响应时间为 94} \end{aligned}$

---

三、静态优先级抢占调度算法

1 速率单调

描述

速率单调（Rate Monotonic，RM）：对于周期任务来说，速率指任务就绪的速率，即任务周期 $P$ 的倒数 $\frac{1}{P}$。

• 该策略需要知道欲执行任务的周期 $P$；
• 而且要为每个任务 $T_i$ 根据它的周期 $P_i$ 分配一个优先级。任务的周期越小，优先级就越高。

可调度性分析

必要条件

前面我们已经介绍过有关处理器利用率 $U$ 的要求，给出周期任务在速率单调算法下是可调度的【必要】条件（Necessary）是：

$U \le 1$

充分条件

我们通过对周期任务的分析，我们得出周期任务在速率单调算法下是可调度的【充分】条件（Sufficient）是：

$U = \sum _{i=1} ^n \frac{C_i}{P_i} \le n \times (2^{\frac{1}{n}} -1)$

下面，我们给出几个常见的周期任务 $T_i,i\in[0...n]$ 在单调速率下可调度的处理器使用率上界值（$bound$）

$n$	1	2	3	4	5	6	10	$\infin$
$bound$	$1$	$0.828$	$0.779$	$0.756$	$0.743$	$0.734$	$0.717$	$0.693$

例子

我们给出一个使用速率单调法来确定静态优先级的可调度的例子：

（1）首先，我们可以先计算一下任务 $T_1$、$T_2$ 和 $T_3$ 的处理器利用率 $U$：

$U = \sum _{i=1} ^n \frac{C_i}{P_i} = \frac{1}{5} + \frac{3}{10} + \frac{3}{15} = \frac{7}{10} < 0.779$

所以，该任务可以被成功调度。

（2）其次，通过速率单调法，我们可以确定任务 $T_1$、$T_2$ 和 $T_3$ 的静态优先级 是：

$\text{Priority}(T_1) > \text{Priority}(T_2) > \text{Priority}(T_3)$

我们可以画出调度时序图（Scheduling sequence）：

（3）最后，我们可以计算出各个任务的响应时间分析（response time analyse）：

$\begin{aligned} & t_0 = \sum _{i=1..j,j\in hp(i)} C_i\\ & t_{n+1} = \sum _{i=1..j,j\in hp(i)} \left \lceil \frac{t_{n}}{P_i} \right \rceil \times C_i\\ & \text{iff } R^{(*)}_i \le D_i, \quad \text{then OK}, \quad \text{else KO} \end{aligned}$

注意 ⚠️：与之前的公式不同，笔者并未完全理解这里的公式意图，结合课件与网上资料尝试改写。给出参考文献地址，请读者指正：

• 学习课件：GitHub : S9_S9_3A_SN_ENSEEIHT
• 网上资料：EN : Tutorial on real-time scheduling

$t_n$	$T_1$	$T_2$	$T_3$
$t_0$	$C_1 = 1$	$C_1 + C_2 = 4$	$C_1 + C_2 + C_3 = 7$
$t_1$	$\left \lceil \frac{t_{0}}{P_1} \right \rceil C_1 = 1$	$\left \lceil \frac{t_{0}}{P_1} \right \rceil C_1 + \left \lceil \frac{t_{0}}{P_2} \right \rceil C_2 = 4$	$\left \lceil \frac{t_{0}}{P_1} \right \rceil C_1 + \left \lceil \frac{t_{0}}{P_2} \right \rceil C_2 + \left \lceil \frac{t_{0}}{P_3} \right \rceil C_3 = 8$
$t_2$	-	-	$\left \lceil \frac{t_{1}}{P_1} \right \rceil C_1 + \left \lceil \frac{t_{1}}{P_2} \right \rceil C_2 + \left \lceil \frac{t_{1}}{P_3} \right \rceil C_3 = 8$
$t_3$	-	-	-
	OK	OK	OK

四、动态优先级抢占调度算法

0 前言

在静态优先级算法中，尤其是速率单调法中，我们得出了一个可调度的充分条件：

• 当处理器使用率 $U \le n \times (2^ {\frac{1}{n}} -1)$ 时，任务可以被调度

显然，这个上界值并不是很好。我们为了使这个上界值接近 $\le 1$，我们类比单调速率法引入了单调截止时间法（截止时间 $D$ 越小，优先级越高）来确定静态优先级。

但是，这种单调截止时间法并不是最佳的静态优先级分配。所以我们提出了动态的优先级分配策略，最早截止时间优先（Earliest Deadline First，EDF）

1 最早截止时间优先

与固定优先级相比较

提示：课件 $P_{38}$

• 一个固定优先级（静态优先级）的抢占式调度器比一个动态优先级调度器，如 EDF，要容易实现。
• 但是，动态优先级调度器，如 EDF 的处理器使用率 $U$ 可以达到 $100％$；而静态优先级调度器，如单调速率 RM 的处理器使用率 $U$ 的理论最大值约为 $69％$ 。
• 最早截止时间优先 EDF 可用于安排周期性和非周期性任务。

描述

在每一个新的就绪状态，调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务，并将执行该任务所需的资源分配给它。在有新任务到来时，调度器必须立即计算 EDF，排出新的定序，即正在运行的任务被剥夺，并且按照新任务的截止时间决定是否调度该新任务（动态的体现）。如果新任务的最后期限早于被中断的当前任务，就立即处理新任务。按照 EDF 算法，被中断任务的处理将在稍后继续进行。

EDF 在抢占式、单处理器的场景下是一个最优的调度算法：如果有一组互相无关的任务，每个任务都有一个到达时间、一个执行需求和一个截止时间，如果存在一个调度算法能够确保在截止时间前完成这些任务，使用 EDF 算法来调度这些任务将会达到这个效果。

周期任务的可调度性分析

情况1

【对于周期任务 $T$：$D \le P$ 】

可调度的充分必要条件（Necessary and Sufficient Condition）是：

$U = \sum _{i=1}^n \frac{C_i}{P_i} \le 1$

情况2

【对于周期任务 $T$：$D > P$ 】

可调度性分析会更加复杂：我们需要引入需求函数（Demand function，$df()$ ）。

关于需求函数 $df()$ 的原文定义十分晦涩难懂，我将在下方给出原文与我的粗浅认识：

“Definition:

The demand function for a task $T_i$ is a function of an interval $[t_1, t_2]$ that gives the amount of computation time that must be completed in $[t_1, t_2]$ for $T_i$ to be schedulable."

$df_i(t_1, t_2) = \sum _{a_{ij} \ge t_1 , d_{ij} \le t_2} C_{ij}$

For the entire task set:

$df(t_1, t_2) = \sum _{i=1} ^n df_i(t_1, t_2)$

此时我们先给出，在一般情况下，对于该问题，任务可以被 EDF 成功调度的充分必要条件是：

$\forall t_1, t_2 \qquad df(t_1, t_2) \le t_2 − t_1$

但是我们无法计算所有的 $[t_1,t_2]$ 区间，所以我们在后面会继续探讨该问题，此时给出该条件只是为了明确我们的目标。

个人理解：

• 对于任务 $T_i$ 的需求函数 $df_i()$，其目的是为了找出在同一个周期内，就绪时刻（下图中使用向上的箭头 $\uparrow$ 表示） 和截止时刻（下图中使用向下的箭头 $\downarrow$ 表示）都在 $[t_1,t_2]$ 时间段内的 $C_i$ 的和。

• 对于所有任务的需求函数 $df()$，其目的是为了找出所有任务在这个时间段内 $C$ 的总合。

  ---

  示例：给出如下任务

  $T_1 = (1, 4, 6),\quad T_2 = (2, 6, 8), \quad T_3 = (3, 5, 10)$

  我们即可画出调度时序图：

  

  当计算 $df(7,22)$ 时，如上图的红色部分：

  $df(7,22) = 2 \times C_1 + 2 \times C_2 + 1 \times C_3 = 9;$

  计算 $df(3,13)$ 时，同理可得出：

  $df(3,13) = 1 \times C_1 + 0 \times C_2 + 0 \times C_3 = 1;$

  计算 $df(10,25)$ 时，同理可得出：

  $df(10,25) = 2 \times C_1 + 1 \times C_2 + 2 \times C_3 = 10;$

  ---

对于一系列同步的周期任务 $T$，我们需要找出他们在最坏情况下的需求函数情况，也即从0开始，到任意一个截止时刻 $L$ ，$df(0,L)$。我们称此时的需求函数为临界需求函数（Demand bound function，dbf）：

$dbf(L) = \max _t(df(t,t+L)) = df(0,L)$

之前我们说过，对于一系列周期性任务，我们可以找到他们周期的最小公倍数 $LCM_{1\le i \le n}(P_i)$ 可以构成一个“最小公倍周期（hyperperiod）”。每个“最小公倍周期（hyperperiod）”的调度都相同。

$H = LCM_{1\le i \le n}(P_i)$

然后在这个最小公倍周期 $H$中找到一个由所有截止时间构成的集合 $DeadlineSet$

$\forall L \in DeadlineTest, \quad DeadlineSet \subset 集合[0,H]$

在此情况下，任务可以被 EDF 成功调度的充分必要 条件是：

$\forall L \in DeadlineSet, \quad dbf(L) \le L$

而对于异步情况来讲，同步是其中最特殊的情况，也是最坏的情况。所以异步的周期任务也满足该条件。

例子

给出如下任务：

1. 计算处理器使用率 $U$

   $U = \sum _{i=1}^n \frac{C_i}{P_i} = \frac{1}{4} + \frac{2}{6} + \frac{3}{8} = \frac{23}{24}$

2. 计算最小公倍周期 $H$（hyperperiod）

   $H = LCM_{1\le i \le n}(P_i)=24$

3. 列出 $DeadlineSet$：

   $DeadlineSet= \{4,6,8,12,16,18,20,24\}$

4. 计算所有的临界需求函数 $dbf(L)$：

   • $dbf(4) = df(0,4) = 1 \times C_1 = 1$
   • $dbf(6) = df(0,6) = 1 \times C_1 + 1 \times C_2 = 3$
   • $dbf(8) = df(0,8) = 2 \times C_1 + 1 \times C_2 + 1 \times C_3= 7$
   • $dbf(12) = df(0,12) = 3 \times C_1 + 2 \times C_2 + 1 \times C_3= 10$
   • $dbf(16) = df(0,16) = 4 \times C_1 + 2 \times C_2 + 2 \times C_3= 14$
   • $dbf(18) = df(0,18) = 4 \times C_1 + 3 \times C_2 + 2 \times C_3= 16$
   • $dbf(20) = df(0,20) = 5 \times C_1 + 3 \times C_2 + 2 \times C_3= 17$
   • $dbf(24) = df(0,24) = 6 \times C_1 + 4 \times C_2 + 3 \times C_3= 23$

5. 满足被 EDF 成功调度的充分必要 条件：

   $\forall L \in DeadlineSet, \quad dbf(L) \le L$

2 非周期任务的调度

对于非周期性（Aperiodic）任务来说，我们应该从两个方面来分析它们：

• 无截止时间的非周期任务：在确保周期任务可调度的同时尽量缩短非周期任务的响应时间。
• 有截止时间的非周期任务：先进行验收测试（待执行的任务能否在截止时间前完成执行，同时不会危及周期性工作和已经接受的非周期性任务）
  • 若不行，可以直接拒绝该任务或者停止一个最不“重要”的任务

无截止时间的非周期任务：后台(arrière-plan)执行

后台执行（arrière-plan）是最简单的解决方案，具体策略如下：

1. 使用先前提出的算法之一，为周期性任务分配优先级，调度周期性任务（RM、EDF 等）
2. 在***没有周期性任务的间隙（idle）***安排就绪的非周期任务，所有非周期性任务都分配相同的最低优先级
3. 非周期任务按照“先到先服务（First Come First Served）”的策略调度

注意 ⚠️：该解决方案无法尽量缩短非周期性作业的响应时间

【示例】

我们使用后台执行（arrière-plan）法调度如下任务：

可以看到，任务 $T_1$、$T_2$ 是周期任务，我们使用速率单调来调度； $T_3$、$T_4$ 和 $T_5$ 是非周期任务。

画出调度时序图：

无截止时间的非周期任务：轮询服务器(serveur de scrutation)

我们为了尽量缩短非周期性任务的响应时间，在此，我们引入服务器（Server）和预算（Budget）的概念：

• 服务器：可以将服务器看作一个周期任务，我们将非周期任务的工作封装进服务器中，使得这些非周期任务也可以参与周期性任务的调度算法。
  • 服务器一般具有较短的周期 $P_s$，在一些调度算法中可以获得高优先级。
• 预算：简单来讲，可以将预算看作是服务器的 $C_{s}$

轮询服务器（serveur de scrutation）法的策略如下：

每次服务器获取处理器资源:
	Budget <- C_s;
	下一次获取处理器资源的时间 <- 当前时间 + P_s;
	While( 有挂起或就绪的非周期任务 && Budget>0 ) :
		执行一个单位时间的最早挂起或就绪的非周期任务;
		Budget <- Budget - 1;
	EndWhile
	Budget <- 0;		// 若不满足while的执行条, 则直接置0, 从而结束本周期服务器的执行
释放处理器资源

【示例】

我们使用轮询服务器（serveur de scrutation）法结合速率单调法调度如下任务：

任务 $T_1$、$T_2$ 和服务器 $S$ 的优先级如下：

$\text{Priority}(S) > \text{Priority}(T_1) > \text{Priority}(T_2)$

画出调度时序图：

关于结果的一点解释：

• 0 时刻时，$S$ 优先获得处理器资源，但是因为没有挂起或就绪的非周期任务，所以立即将Budget 置 0 并释放处理器，等待下一个周期。

无截止时间的非周期任务：可延期服务器(serveur ajournable)

与轮询服务器不同，可延期服务器在其调用时如果没有挂起或就绪的非周期任务，则保留其 Budget，不会将 Budget 置为 0。

可延期服务器（serveur ajournable）法的策略如下：

• 服务器在每个周期初始获取处理器资源时：

Budget <- C_s;
下一次获取处理器资源的时间 <- 当前时间 + P_s;

While( 有挂起或就绪的非周期任务 && Budget>0 ) :
	执行一个单位时间的最早挂起或就绪的非周期任务;
	Budget <- Budget - 1;
EndWhile

• 当服务器没有获取处理器资源，但是有非周期任务就绪且本周期还有剩余的 Budget 时：

While( 有挂起或就绪的非周期任务 && Budget>0 ) :
	执行一个单位时间的最早挂起或就绪的非周期任务;
	Budget <- Budget - 1;
EndWhile

注意 ⚠️：

需要注意的是，这种策略可能导致周期任务错过 Deadline。

【示例】

我们使用可延期服务器（serveur ajournable）法继续研究上一个问题的调度：

任务 $T_1$、$T_2$ 和服务器 $S$ 的优先级如下：

$\text{Priority}(S) > \text{Priority}(T_1) > \text{Priority}(T_2)$

画出调度时序图：

关于结果的一点解释：

• 0 时刻时，$S$ 优先获得处理器资源，但是因为没有挂起或就绪的非周期任务，所以立即释放处理器，在本周期内继续“监听”之后是否有就绪的非周期任务。
• 4 时刻时，非周期任务 $T_3$ 就绪，按照“能力”（本周期剩余的 Budget）执行 $T_3$。

【示例：导致周期任务错过 ddl】

画出调度时序图：

无截止时间的非周期任务：偶发服务器(serveur sporadique)

这种调度方式与前两种最显著的区别，在于周期的更新（即，下一次获取处理器资源的时间）。

在之前的版本中，周期的更新是固定的；在这种调度方法下，只有在有非周期任务就绪时，才会确定下个周期的开始时间。

调度策略如下：

• 服务器在每个周期初始获取处理器资源时：

Budget <- C_s;

If (有挂起或就绪的非周期任务) then
	下一次获取处理器资源的时间 <- 当前时间 + P_s;
	
	While( 有挂起或就绪的非周期任务 && Budget>0 ) :
		执行一个单位时间的最早挂起或就绪的非周期任务;
		Budget <- Budget - 1;
	EndWhile
	
EndIf

• 当服务器没有获取处理器资源，但是有非周期任务就绪且本周期还有剩余的 Budget 时：

If ( Budget == C_s ) then
	下一次获取处理器资源的时间 <- 当前时间 + P_s;
EndIf
	
While( 有挂起或就绪的非周期任务 && Budget>0 ) :
	执行一个单位时间的最早挂起或就绪的非周期任务;
	Budget <- Budget - 1;
EndWhile

【示例】

我们使用可延期服务器（serveur ajournable）法继续研究相同问题的调度：

任务 $T_1$、$T_2$ 和服务器 $S$ 的优先级如下：

$\text{Priority}(S) > \text{Priority}(T_1) > \text{Priority}(T_2)$

画出调度时序图：

【示例 2】

我们继续研究上一节中导致周期任务错过 ddl 的例子：

画出调度时序图：

周期任务错过 ddl 的问题解决。

总结例题

下面我们用一道例题将这四种不同的无截止时间的非周期任务调度放在一起比较：

下面的所有周期任务均使用速率单调法调度：

关于服务器的信息：周期 $P_s = 4$，预算 $\text{Budget} = 1$

任务 $T_1$、$T_2$ 和 $T_3$ 的优先级如下：

$\text{Priority}(S) > \text{Priority}(T_1) > \text{Priority}(T_2) > \text{Priority}(T_3)$

画出调度时序图：

后台执行（arrière-plan）

轮询服务器（serveur de scrutation）

可延期服务器（serveur ajournable）

偶发服务器（serveur sporadique）

3 带有共享资源的任务调度

除了处理器资源外，任务在执行的过程中还需要访问共享的临界区资源。任务通常必须以互斥方式访问共享资源。一个任务在执行时，只有在完成所有临界区资源访问后，后才会释放这些资源。

在这种约定下，任务调度会出现两种问题：

1. 死锁（Deadlock）：在截止时间（ddl）前发现资源依赖中存在环；

   • 可以通过一种资源分配机制（resource allocation mechanism）防止死锁的产生
   • 【死锁例子】
   

2. 优先级倒置（Priority Inversion）：一个优先级更高的任务在等待另一个低优先级任务占有的临界区资源。

   • 优先级反转无法避免，但应该被限制资源等待时间（依托于资源分配机制）
   • 【优先级倒置例子】
   

那么我们如何“避免”这些问题呢？

“超级优先级”方法

“超级优先级”（Super priority）方法是最简单的防止死锁和上界优先级反转的方案。

方法描述：

当一个任务请求一个临界区资源时，会立即获得该资源。此时，该临界区拥有最高的优先级，即任务在访问临界区资源时不会被抢占（在任何时候临界区中最多有一个任务）。

在这种方法下：

• 不会发生死锁
• 优先级反转的持续时间上限为最长临界区（无法避免优先级反转，但可能产生额外的优先级反转）

【例 1（课件 $P_{66}$）】

【例 2（课件 $P_{67}$）】

“优先级继承”方法

优先级继承（Priority inheritance）方法：不防止死锁，但优先级反转的等待时间的上限被缩短

方法描述：

• 当高优先级任务 $T_{hp}$ 请求的资源被一个低优先级任务 $T_{lp}$ 占有时，可以将任务 $T_{lp}$ 的优先级暂时提高到与任务 $T_{hp}$ 相同的优先级。这样可以确保 $T_{lp}$ 可以尽快结束，退出临界区。
• 之后恢复至原有的优先级

【例子（课件 $P_{70}$）】

“基于堆栈”的方法

在这种方法中，每个临界区资源维护一个堆栈，用来记录访问该资源的任务优先级：优先级低的先入栈，优先级高的后入栈。

方法描述：

• 在开始之前，确定每个临界区资源的任务堆栈。
• 开始后，对于每个申请访问临界区资源的任务，我们将该任务的优先级提升到栈顶任务的优先级（即，提升到可能访问该资源的所有任务中的最高优先级）
• 直到该任务退出临界区

【例子（课件 $P_{72} - P_{74}$）】

五、多处理器调度

1 问题定义

• 在 $m$ 个处理器 $P$ 上调度 n 个周期性任务 $T$
• 每个处理器 $P_i$ 在任何时刻最多执行一个任务 $T_j$
• 每个任务 $T_j$ 在任何时刻最多由一个处理器 $P_i$ 执行

对于多处理器的调度，我们主要将其分为两个部分：分区调度和全局调度

• 无迁移的分区调度：任务静态分布在一个处理器上，无法迁移到其他处理器
• 任务级别迁移的全局调度（工作执行期间无法迁移）和工作 Job 级别迁移的全局调度：可以从一个处理器迁移到另一个服务器

2 分区调度

对于分区调度，我们将任务静态地分布在可用的处理器上（类似于装箱问题）。

对于每个处理器来讲，它使用之前介绍的单处理器调度方法来独立执行其分配的任务集