0 引　言

由于各个国家国土覆盖面积有限，建立在国家内部的地面测量和通信站难以满足全球性科学监测和通信的需求。为此，越来越多的国家采用远洋测量舰船来实现在大洋等难以触及的海域设立测量通信点的目的。远洋测量舰船覆盖范围广、灵活性强，是国家内陆测量和通信站的有效补充，被广泛应用在测量勘探、飞行器间信息通信和数据传输、中继等方面，例如我国投入使用的“远望”系列测量船等。然而，随着测量任务的增多，数据通信量的加大，传输码率的与日俱增，在远洋测量舰船上有限的电子设备处理和通信硬件资源受限的条件下，很多传统的、逻辑简单数据通信和处理任务调度算法已经不能适应未来的应用需求。为了解决这一问题，研究人员开发出很多种任务调度的算法。这些算法大体可以分为离线和在线调度两类。

离线调度的算法通常使用历史资源数据，同时假设这些任务有着不变的属性（例如，到来时间，截止时间，执行时间和资源占用情况等）。Kansal等^[1]提出一种在不同资源模式下进行周期性切换的离线调度方法。Audet等^[2]给出一种基于资源占用的、针对周期性任务的静态调度器。以上 2 种典型的静态调度算法都没有考虑资源供应和任务执行的变化。这一点限制了这两类调度算法的使用范围。

对于在线调度算法，Liu等^[3]提出了一种基于任务紧急程度的最早截止时间先执行（EDF）的调度算法。基于EDF算法，Moser等^{[4 – 5]}设计出了懒惰调度算法（LSA）并证明了对给定的时间和资源约束，如果供能变化规律完全已知，则LSA能够实现最小的任务延误率（DMR），即理论最优值。然而，这些调度方法都是粗粒度的调度方法，即不管发生什么情况，一旦一个任务开始执行，就必须执行到最后结束为止。这给系统带来了很大的资源浪费，导致了较高的任务延误率。

最近一段时间，Zhang等^[6]设计了一种任务内部调度方法，即任务在执行的过程中可以被中断并在之后继续执行。该方法调度的粒度更细，因此也更加灵活。这样，任务延误率（DMR）也能够有效得到改善。但是，并不是所有的任务都可以在执行过程中被切分。原子任务是不可拆分的，需要一次性地连续执行完。此外，突发性任务也没有在该算法中被考虑。

为了进一步减低任务延误率，本文针对远洋测量舰船电子设备进行数据通信和处理时存在的突发性，周期性和非周期性 3 种任务，提出了基于资源感知的任务内部调度算法，其中原子和非原子任务都被考虑到算法之中。

本文面向远洋测量舰船应用提出了基于资源感知的任务内部调度算法，在算法设计之前，首先对远洋测量舰船数据处理和通信任务的特性进行建模，然后分析了任务的可调度性问题；在设计的调度算法中，首先针对突发性、周期性和非周期性几类任务分别进行调度点选取。接着供能变化规律和遥测任务特性设计供能预测模型和负载匹配算法，计算任务的实时优先级。最后基于优先级选择任务执行顺序。

1 研究动机和设计挑战 1.1 研究动机

图 1给出了本文提出算法的设计动机实例。资源供应曲线在该例子中给出。选择4个任务调度进行调度。其中，任务1和任务2是周期性的任务，即它们的开始时间和截止时间都是固定的。任务3是一个非周期性的任务，即需要在一段时间内被执行，但是没有固定的开始时间。任务4是一各突发性紧急任务，即该任务的开始时间和截止时间是预先未知的。一旦紧急突发性任务出现，它就具有最高优先级需要立刻被执行。这对系统的任务延误率影响很大。因此，调度算法在设计时必须谨慎对待这一类任务。此外，白色的任务为原子任务，这说明在它们在执行的过程中不可拆分。灰色的为非原子任务，即它们在执行过程中可以被拆分。

从图1可以看出，如果没有针对资源供应和紧急任务预测的步骤，则资源从t₀–t₁时间段会被浪费。但是资源在t₁–t₂时间段非常有限，传统的任务间调度方法不能满足突发性任务和其他正在执行的原子任务的执行能耗需求。因此，包括紧急任务在内的几个任务最终都错过了截止时间，导致系统的任务延误率很高。相反地，本文提出的调度算法能够同时考虑资源供应和任务的不同类型。这样，更多的任务在t₀–t₁这个资源供应充足的时间被执行。由于在t₁时刻资源供应突然减少，本文提出的调度算法及时停止了周期性任务（任务1和任务2）。这样，积极任务（任务4）就可以在其截止时间到来前按时完成。之后，被中断的 2 个任务继续完成。最终，与传统的任务间调度相比，采用本算法的系统任务延误率就得到了有效地降低。这个例子说明，本文提出的面向远洋测量船应用的基于资源感知的任务内部调度算法能够有效地实现复杂任务的调度。

1.2 设计挑战

设计这样的调度算法，面临如下挑战：

1）对于非原子任务，什么时候停止执行一个任务而开始执行另一个？算法的设计复杂度很高。

2）对于资源感知的调度算法，如何同时考虑资源应变化和紧急任务？

3）怎样提高紧急任务预测的准确性？

2 系统建模 2.1 调度模型参数

对于任务调度问题，主要针对一个时间段内的调度。每个时间段持续时间为T，该时间段包含M个时间片段，时间片段是最小不可分的任务调度单元，每个时间片段持续时间为t。因此，有

$T = M \cdot t {\text{。}}$

(1)

每个任务有8个参数，一共有N个任务。D_i任务i的截止时间。T_i和N_i分别是任务i在一段时间内一次执行所需的时间和执行次数。这说明一些任务在这段时间内可能会执行不止一次（N_i≥1）。P_i任务i的执行功耗。S_i任务i执行所需的硬件资源百分比。如果任务i为原子任务，则A_i=1; 如果任务i为非原子任务，则A_i=0; B_i是任务i的类型。当任务i为周期性任务时，B_i=1；当任务i为非周期任务时，B_i=2；当任务为紧急任务时，B_i=3。W_i是任务i的权重。它代表了该任务的重要性。

系统一共包含4个参数。T和t分别是任务执行的周期和时间片段。Ps（t）在第m个时间片段的供能功率。TS是总的硬件资源，归一化后该参数的值为1。

任务调度的变量定义如下。x_i（m）是一个独立变量，它表示任务i在第m个时间片段的执行状态。如果该任务在执行，则x_i（m）=1。如果该任务没有被执行，则x_i（m）=0。

由于所有正在执行的硬件资源的需求百分比之和应满足系统总的硬件资源限制，则有

${x_i}\left( m \right) \cdot {S_i}Ts = 1 \text{。}$

(2)

r_i（m）是一个独立变量，它表示任务i在第m个时间片段的剩余执行时间，有

${r_i}(m) = {N_i} \cdot {T_i} - \displaystyle\sum\nolimits_{j = 1}^m {{x_i}\left( j \right)} \text{。} $

(3)

$\min \sum\nolimits_{i = 1}^N {\left( {\left\lceil {{r_i}\left( {{D_i}} \right)/{T_i}} \right\rceil \cdot {W_i}} \right)} \text{。} $

(4)

给定上述的参数和相应的变量，该调度问题可以用如下的关系式来表示：设计目标是找到一种最优的调度方案{x_i（m）}（m∈[1,M]），使其能够最小化天气测量系统中某一个具体的中继卫星上的任务延误率（DMR）。

2.2 可调度性分析

一般而言，如果所有任务在有限的约束条件（比如，硬件资源，资源供应等）下，都能够在它们的截止时间到来之前被执行完，则该调度问题是可调度的；否则，该调度问题不可调度，在这种情况下，就存在一个理论最优的任务延误率。对于本文的调度问题，可调度性可以用如下的公式去描述：

在一段时间内的第m个时间片段上的资源和硬件供应约束（Es（m）和Hs（m））可以表示为

$Es\left( m \right) = \displaystyle\sum\nolimits_{j = 1}^m (\left\lceil {P{s_i}\left( m \right) \cdot t} \right\rceil {\text{，}}$

(5)

$Hs\left( m \right) = \sum\nolimits_{j = 1}^m 1 \text{；}$

(6)

在一段时间内的第m个时间片段上的资源和硬件需求（Er（m） and Hr（m））可以表示为

$Er\left( m \right) = \sum\nolimits_{j = 1}^m {(\left\lceil {{P_i}\left( m \right) \cdot t \cdot {z_i}\left( m \right)} \right\rceil } \text{，}$

(7)

$Hr\left( m \right) = \sum\nolimits_{j = 1}^m {{s_i} \cdot {z_i}\left( m \right)} \text{。}$

(8)

其中：z_i（m）为任务i的最晚开始时间（基于该任务的截止时间）。这样，如果任务是可调度的，需要满足下面的条件：

$Hr\left( m \right)Hc\left( m \right)\& Er\left( m \right)Ec\left( m \right),m\left[ {1,M} \right] \text{。}$

(9)

否则，该调度问题为不可调度问题，能够根据式（5）–式（9）来估计最优的任务延误率。

3 调度算法设计 3.1 调度算法设计框图

调度算法设计框图如图2所示。首先针对突发性、周期性和非周期性几类任务分别进行调度点选取。接着供能变化规律和遥测任务特性设计供能预测模型和负载匹配算法，计算任务的实时优先级。最后基于优先级选择任务执行顺序，得到具体的任务调度方案。

3.2 触发机制设计

基于任务特征，时间状态和实际的资源供应情况，资源感知的任务内部调度算法在以下两类情况下执行：

1）任务变化

①一个新的任务（例如紧急任务）进入调度队列；

②一个调度队列中的任务到了它最晚执行时间；

③一个任务执行完毕；

2）资源供应变化

①资源供应增加，可以让调度队列中的一个或多个任务开始执行；

②资源供应减少，正在执行的一个或多个任务需要停止。

3.3 预测和负载匹配算法设计

对于资源供应的预测，采用一个资源供应情况移动平均法来估计资源供应的曲线变化趋势，这是因为该趋势在远洋测量舰船运行环境中有着较为稳定的规律。首先，收集多年的运行环境资源供应情况曲线。为了有效保存这些曲线，采用一个K均值的方法来对这些曲线进行压缩。然后，实际的资源变化会与存储在存储单元中的最接近的历史资源供应曲线去比较，基于保存的曲线，可以获取估计的下一个时间片段的资源值以及接下来一段时间内的资源变化趋势。

匹配算法来进行任务选择的工作流程如图3所示。首先，所有选中任务优先级基于它们的特征，状态和当前估计的资源供应情况计算得到。如果还有任务没有进行判定，则当前没有判定的任务种优先级最高的任务被选中，如果远洋测量舰船硬件电子设备系统中还有足够的资源来执行该任务，则该任务在下一个时间片段到来时开始执行。否则，该任务在本次调度判定中被放弃，不执行。然后接着判定其他的任务。如果当前所有的任务都已经被判定，则算法流程结束。这样，就得到了最终选择出来的、要在下一个时间片段到来时开始执行的任务。

4 实验分析 4.1 试验设置

选择10~15种任务（例如，关键数据通信，数据加密和解密，遥测数据传输，图像数据处理等）来进行调度实验。这些任务分属于3种类型（周期性，非周期性和突发性）。这些任务和卫星系统的相关参数通过仿真和实际测试获取。实际测试指的是基于遥测数据软硬件分析以及实验用天基系统部分硬件等效器分析得到的结果。本实验中所采用的资源供应数据采用的是某远洋测量船工作运行数据库中2014年的部分数据。

4.2 实验评估

基于系统建模和硬件测试，比较传统基于最早截止时间原则的任务间调度（EDF），传统任务内部调度（Intra）以及本文提出的调度方法（Proposed）。

表2给出了 3 种调度方法的任务延误率的比较结果。从表中我们可以看出，如果突发性任务比例不变，随着非周期性任务比例的增加，任务内部调度与任务间调度效果更好。这是因为同粗粒度的任务间调度相比，任务内部调度是细粒度的调度，可以更加灵活地进行资源管理和非周期性任务执行。如果非周期性任务比例不变，随着突发性任务比例的增加，本文提出的调度算法更好。这是因为本文提出的算法基于资源预测情况考虑了紧急任务的优先级和出现的概率。因此，延误率最多可以降低31%。这说明本文提出的调度算法对于天基系统中中继卫星上的任务调度非常有效。

表3给出了 3 种调度方法总资源消耗的比较。从表中可以看出，能够得出和表2类似的结论。这说明相比其他 2 种调度方法，本文提出的算法浪费的资源更少，资源利用率提高比率更高（最高可达22%）。

5 结　语

本文提出了一种基于资源感知（Resource-aware）的任务内部（Intra-task）调度设计方法来提高任务调度的有效性。与传统的粗粒度的任务间调度算法不同，采用任务内部调度方法，任务可以在执行中进行被中断。远洋测量舰船通信和处理的数据仿真分析及模拟硬件的实验结果表明，与EDF方式相比，采用本算法可以有效降低任务延误率30%，提升资源利用效率20%。

针对未来的研究，会进一步尝试探索长期任务调度的方法。另外，基于能量资源管理的约束也会纳入我们的研究之中，以此来设计针对长期调度的、更为高效的调度算法。