[科普中国]-自适应调度

简介

自适应调度是指在满足不同工作方式相对优先级的条件下，在设计范围内，同时实时地平衡各种波束请求所要求的时间、能量和计算机资源，为一个调度间隔选择一个最佳任务序列的一种调度方法。这种调度策略能够与动态的环境相适应，与规定的不同工作方式优先级相适应，与可用的时间、能量和计算机资源量相适应。针对多任务或者多功能雷达，自适应调度策略被认为是最灵活最有效的调度策略。1

调度原则在具体设计一种任务调度算法时应遵循以下三个原则：

( 1 )优先级原则：当申请调度的驻留任务中出现多个任务竞争同一个时间段时，优先调度相对优先级较高的驻留任务。优先级原则保证在雷达资源无法满足所有请求时，将可用资源分配给相对优先级较高的任务，如果优先级较低的任务不能在某个合理的周期内被调度时，则要延时或是放弃这些任务。

(2) 时间利用原则：

其中N 为当前调度间隔内调度成功的驻留任务个数，此为驻留任务驻留时间长度。时间利用原则要求相控阵雷达在一个调度间隔内尽可能地安排更多雷达任务，使得其空闲时间尽可能少，提高雷达时间资源利用率。

( 3 )期望时间原则：

式中dti为任务期望执行时刻，sti为任务实际执行时刻。期望时间原则要求雷达波束请求的实际执行时刻尽可能靠近其期望执行时刻。一般情况下，调度算法应首先满足优先级原则，其次是时间利用原则和期望时间原则，也可根据侧重点不同而有所调整。

影响调度的因素在设计自适应调度算法时，调度间隔的选择、工作方式优先级的划分、调度策略的选择和雷达资源约束条件的实现是需要考虑的四个关键问题，这四个因素将直接影响调度算法的性能。

调度间隔的选择调度间隔(Schedule Interval ，SI)的含义为雷达系统调用调度程序的时间间隔，它是整个雷达计算机程序体系结构的基础，决定了雷达控制回路中的主要子程序的执行频率。雷达控制器与雷达天线每隔一个调度间隔交换一次数据。若是调度间隔选择过长，则无法满足雷达系统对某些工作方式时间紧迫性要求；若是调度间隔选择过短，则会额外增加雷达系统计算机的支援程序和内部处理程序的开销和负载。因此，调度间隔必须合理设置。

为保证所有任务能够得到正常执行，调度间隔长度必须小于最小任务执行周期的四分之一。同时，考虑到在一个调度间隔内雷达控制器需要进行雷达回波处理和驻留任务调度处理，因此，调度间隔长度必须大于最恶劣情况下支持调度和数据处理所需要的总时间。实际选取的调度间隔只要在上述范围内，就认为是合理的。2

相对优先级确定在任务调度过程中，有可能出现多种任务请求竞争同一个执行时间段的情况，此时，调度算法必须决定哪些任务被调度，哪些任务被延迟或是删除。任务的相对优先级为调度算法提供了决策的依据。

任务的相对优先级由任务重要性和时间紧迫性两个要素决定。任务重要性通常用任务工作方式优先级表示，而任务的时间紧迫性则是从任务期望发射时间角度对任务进行衡量。Huizing等人提出了时间窗的概念，其具体含义是指雷达任务请求的实际执行时间可以在其期望执行时间前后能够移动的有效范围。这使得驻留任务的实际执行时刻不一定与其期望执行时刻相等。一旦雷达任务的时间窗给定后，便可以得到各驻留任务的最早和最晚可执行时刻(截止期)。在所有申请调度执行的任务中，最晚可执行时间与当前调度间隔起始时刻越近，则说明该任务的时间紧迫性越高。此时，时间紧迫性高的任务相对优先级应提高，以便尽快得到调度。1

调度策略的选择调度策略可进分固定模板、多模板和部分模板法。

固定模板法是最为简单的一种调度方法。在这种调度方法中，只需要为雷达申请任务预先分配一个固定的调度间隔，用于一组固定组合的雷达任务的调度。固定模板法设计和分析简单，不需要实时地对雷达任务排序，占用系统资源较少。但是由于模板的固定性，这种调度策略只适用于特定的目标环境，它缺乏灵活性和自适应能力，不利于波形和能量的调整，因此，不可能适用于多样化的动态环境。这种设计方法只能供单一用途或单一功能的雷达使用。

多模板设计法是固定模板设计方法的一种简单推广，相较于前者，它的灵活性和自适应能力有所提高。这种方法中首先需要根据相应的操作环境设计好多个固定的模板，模版的数目是由操作环境的多样性、期望的操作效率和选择逻辑的复杂程度决定的。在实时调度时，将根据一定的准则及相应的环境来选择最适合的模板。多模板方法设计和分析相对简单，所用系统资源较少，但它也存在着效率低、不利于波形和能量调整等缺点，因此，该方法仅适合于对目标环境和操作环境具有先验知识的雷达使用。

部分模板法在每个调度间隔内事先安排好一个或多个任务，以维持某个最小程度的操作，该调度间隔内剩余的时间可用来安排执行紧急任务或是满足设备约束条件的其它类型的任务。部分模板设计方法较前两种方法使得雷达的利用效率有所提高，同时，它对环境有着一定程度的灵活性和适应性，可用于多功能和多用途雷达，但是由于其设计和分析的困难，它还是常用于有限功能的雷达。1

资源约束条件雷达每一种工作方式的实现都是通过发射波束驻留实现的，均会消耗一定的雷达资源，而雷达系统所拥有的资源是有限的，因此，设计调度算法时必须综合考虑各种资源的约束。调度中主要考虑三大资源约束：

( 1 )时间资源约束：一旦调度时间间隔确定之后，在其中可能安排的雷达任务是有限的。任何一个雷达任务的发生，都要求雷达有相应的动作时间，所有安排执行的雷达任务必须在它们的截止期之前完成，同时它们不会出现竞争同一个执行时间段的现象。

( 2 )能量资源约束：如同时间约束一样，任何一个雷达任务的发生，都要求雷达发射机发射一种或多种信号波形，都要消耗一定数量的能量。特别是对那些距离远或跟踪精度较高的目标，为保证足够的数据质量，可能要消耗更多的发射机能量。

( 3 )计算机资源约束：在每一个雷达任务结束后，雷达回波要经过信号处理机送到雷达系统计算机进行数据处理，因而要占用相应的计算机处理与存储资源。

三大资源约束中，时间资源约束是最主要的的资源约束，也是调度中主要考虑的因素。1

自适应调度算法计算模块的自适应调度算法，即负载平衡策略，是在包含大量不同计算机中的网络中，选择最合适给定问题的计算机进行计算。下面给出了选择最优计算模块的策略。并讨论了调度算法涉及到的各个参数，给出了计算(或者估计)这些参数的模型及方法。

选择最优计算模块策略假定最合适的计算模块是对给定问题P需要最少执行时间T的计算模块。这样，就需要估计系统中每个计算模块M需要的执行时间。基本上，可以把执行T分成两部分Ta和Tc，这里的Ta是通过网络把数据发送给M和从M取得结果的时间；Tc是执行计算所需要的时间。

时间Ta可以通过计算下列参数得到:

1．本机与M之间的网络延迟与网络带宽；

2．发送数据的规模；

3．返回结果的规模。

计算Tc需要计算下列参数:

1.问题的规模；

2.使用算法的复杂度；

3.M的性能，它取决于M的负载和M的原始性能3

性能模型

其中，P为估计的性能指数；P为原始性能指数；ω为M的工作负载。当然，由于未考虑到操作系统的因素，这个模型并不精确。3

执行时间T的计算每当有任何请示时．代理对每个计算服务模块执行一次T的估算。这个计算使用前面所述的所有参数进行计算。可以把这些参数分成三类：

●客户相关参数

1．发送数据的规模；

2．接收结果的规模；

3．问题的规模。

●静态的服务模块相关参数

1．本机与M之间的网络特性，如带宽、延迟等；

2．M使用的算法的复杂度；

3．M的原始性能指数。

●动态的服务模块相关参数

1．M的工作负载：

客户端相关参数包含在客户对调度代理的问题请求中，因此它们的计算是直接的。静态的服务模块相关参数通过只需要一次存储。

网络特即性通过多次计算网络特性(带宽、网络延迟)等，可以得到一个合理的网络延迟和带宽的平均值。由于在取得它们的平均值后，这些值通常不会有很大改变，因此可以把它们称为静态参数。

算法复杂度是当一个新的计算服务模块加入系统中时，它通告了其能解决问题的复杂度。由于算法复杂度只取决于计算服务模块的软件设计，因此这个复杂度以后不会改变。

原始性能指数原始性能指数，指的是计算机空载时候的性能指数。在计算服务模块启动时，这个指数就由其本身硬件、操作系统决定。计算时，我们可以使用benchmark程序获取其值。3

工作负载模型在计算预测执行时间T时，工作负载参数是唯一的动态的服务模块相关参数。每个代理为每个计算模块保存工作负载的缓冲值。通过缓冲，在计算预测执行时间r时就可以直接计算，而此缓冲值只需要周期性更新。这个缓冲值可能过期，从而导致对预测执行时间T的错误估计。但是，考虑到不断获取精确的工作负载的代价，可以折衷采取这种取平均值的方法。3

请求序列用户请求的任务组合图，可用有向无环图(DAG)来表示。由于用户的输入数据可能需要送给多个计算模块，用户请求的数据可能存在数据冗余，因此对用户请求的序列进行优化，从而避免数据在网络上重复传输，改善数据通信性能。请求序列的目的在于降低网络传输量，减少总体请求响应时间。为此，请求序列的调度要做到：

1)不传输所有不必要的数据；

2)传输所有必要的数据。

同时，通过尽可能地同时执行计算模块，还可以缩短执行时间。为此，需要对请求序列的输入和输出参数进行细节分析，产生代表任务及其执行相关性的有向无环图。此有向无环图再被送到被选中进行请求序列计算的模块。3

调度性能评估指标在上述调度原则基础上，定义性能评估指标，用于评估调度算法的性能和有效性。主要包括调度成功率(Schedule Sccess Ratio，SSR)、时间利用率(TimeUtilization Ratio， TUR)、平均时间偏移率(Average Time Shift Ratio，ATSR)。

( 1 )调度成功率(SSR)：

式中N 调度任务个数，Ntotal为相应任务总个数。此指标用以描述各种任务调度情况，并用于评估调度算法对优先级原则的遵循程度。

( 2 )时间利用率( TUR)：

式中T 为总时间，lti为调度成功任务的驻留时间长度。此指标用以描述调度算法对雷达时间的利用情况，并用于评估其对时间利用原则的遵循情况。

( 3 )平均时间偏移率(ATSR)：

其中N 为调度成功任务个数，sti为任务实际执行时刻，dti为任务期望发射时刻，wi为任务时间窗长度。

此指标用以描述任务实际执行时刻与期望执行时刻的偏移程度，并用以评估调度算法对期望时间原则的遵循程度。1