反馈控制下嵌入式实时系统调度算法设计研究

皇甫大双

(江苏安全技术职业学院，江苏 徐州 221000)

0 引言

实时系统的提出，为多个领域的发展创造了有利条件[1]，例如多媒体信息处理、航空航天控制、机械设备控制等系统。这些系统作业与时间的约束密切相关，对任务开始执行、完成等时间要求较高[2]。为了达到任务实时管理目标，必须为其设置一套高效的调度机制。目前，应用比较多的两种调度机制分别为静态调度、动态调度，由于前者应用期间需要明确负载模型，确定可调度性，应用灵活性较低，所以应用较少[3-4]。后者虽然具备一定的灵活性，但是应用条件受限，一旦负载超过预期设置，调度耗费的处理器资源就会明显增加[5]。为了弥补动态调度的不足，本文尝试提出一种反馈控制下的嵌入式实时系统调度算法，并展开深入探究。

1 反馈控制下的嵌入式实时调度系统

1.1 动态调度存在的问题

目前，实时调度算法的开发主要采取动态调度方法。动态调度方法分为两种，其中一种为最小松弛时间优先调度算法(Least Slack Time First，LST)，另外一种为最早截止期优先算法(Earliest Deadline First，EDF)[6]。这两种方法的应用都是建立在已经创建的任务基础上，根据任务内容要求，按照一定顺序执行。存在的不足在于系统负载模型不确定条件下，调度任务过程会对系统运行造成较大影响，部分时段出现大幅度的动荡[7]。从理论层面而言，系统当前输入及以前输入在很大程度上决定了系统输出，不利于任务调度。

1.2 反馈控制调度系统的提出

一般情况下，工程师采用反馈控制环节改善系统运行稳定性，所以，本文尝试引入反馈控制方法，进行反馈控制调度系统研究[8]。该系统中，反馈控制器采用的是比例积分微分控制器(Proportional Integral Derivative，PID)，该装置不仅稳定性能较高，而且结构比较简单，支持不确定、数学模型精度偏低条件作业，并且控制效果较好[9-10]。根据实时调度需求，设计的反馈控制调度系统结构如图1所示。

图1 反馈控制调度系统结构

该结构主要由比例调节器、微分调节器、积分调节器、监视器、任务调度器组成，在执行等级控制器的作用下，下达执行任务，经过多番调节处理，完成相关任务的执行，同时利用监视器观察任务执行的整个过程。其中，被控变量为任务错过率，记为MR(t)，控制变量为处理器总利用率调整量，记为ΔCPU。关于控制器PID作业描述如下：

(1)

公式(1)中，KD代表微分系数；KI代表积分系数；Kp代表比例系数。

关于任务错过率的求解，采用以下公式计算：

MR(t)=n/(n+m)

(2)

公式(2)中，n和m均代表任务数，前者计量的是错误时限的数据，后者计量的是在时限范围内的数据。

一般情况下，运行监视器能够有效采集任务错过率相关数据，作业期间，通过调节部分参数数据，控制监视器作业状态[11]。为了便于控制，设置任务周期，记录任务执行时间，构建任务关系模型。其中，系统任务总占用率U的求解方法如下：

(3)

公式(3)中，Ti代表任务周期；EXTi代表任务执行时间。为了便于调度控制，本模型对非周期任务采取周期化处理。如果任务随机化严重，或者执行次数为1，那么为Ti赋予截止时间。

2 基于PID反馈控制的LST调度模型的构建

2.1 基于PID反馈控制的LST调度模型结构设计

本文以LST调度算法作为研究基础，引入PID反馈控制系统，提出一种新的调度模型，即PID-FC-LST(PID-Feedback Control-LST)调度模型[12]。该模型主要调度实时任务，作业效率较高。PID-FC-LST调度模型结构如图2所示。

图2 PID-FC-LST调度模型结构

该模型主要由PID控制器、监视器、任务准入控制器、任务执行等级控制器、LST调度器、处理器组成。开启监视器作业模式，按照一定周期规律，将系统任务错过率MR(t)反馈给调度体系，按照接收到的不同等级任务命令，开启处理器作业模式，采取针对性处理。当PID控制器接收到反馈信息MR(t)后，统计处理器利用率调整量，记为ΔCPU，涉及的计算公式如下：

(4)

公式(4)中，EMR(t)=MR(t)-MR0。其中，MR0代表错过率对应的校准值。

当ΔCPU<0时，处理器指标中利用率的需求明显下降；当ΔCPU>0时，处理器指标中利用率的需求明显上升。当ΔCPU发生变化时，容易对任务执行等级控制器、准入控制器的作业状态造成影响。假设系统作业期间，为了达到任务调度需求，任务执行等级控制器需要做出一定调整，涉及的调整参数为利用率，记为ΔCPU1。在此基础上，准入控制器也应做出相应调整。关于利用率的调整计算为ΔCPU0=ΔCPU-ΔCPU1。

考虑到错过率的修正，需要改变系统负载。所以，本研究尝试利用执行等级控制器和准入控制器分别对当前任务执行的等级、是否接收新的任务两项指标进行有效控制，实现系统运行队列的任务调度，同时处理器的占用率也将随之改变。在此环境下，系统负载发生改变，错过率因此得到修正。通常情况下，如果系统错过率数值偏高，ΔCPU<0，则下调处理器总体利用率；如果系统错过率数值偏低，ΔCPU>0，则上调处理器总体利用率。

2.2 调度任务执行模型设计

本研究系统作业任务用T，D，A，C，EXT，TYPE，INST来表示，从初级任务开始执行，按照从低到高的顺序执行。其中，执行时间由EXT决定，任务关键性由C决定。以下为换算公式：

EXL=C×a0-EXT×a1

(5)

公式(5)中，a1代表执行时间系数；a0代表关键性系数；EXL代表任务执行等级。从该公式中参数关系可以看出，执行时间与关键性之间呈现负相关关系，与任务执行等级之间呈现正相关关系。INST代表任务急迫性，通过调节该参数，能够对准入任务加以控制。TYPE代表任务类型，主要分为3类，分别是软实时、固定实时、硬实时。其中，任务关键性最强的类型为硬实时，最为薄弱的是软实时。

本研究中，为了保证较高的时间要求，系统能够有序调度，避免资源调度混乱问题的发生。系统对各个任务类型的最低优先级的调度顺序进行了设定：(1)最高优先级(固定实时任务)<最低高优先级(硬实时任务)；(2)最高优先级(软实时任务)<最低高优先级(固定实时任务)。

另外，D任务描述的是截止时间；A任务描述的是达到时间；T任务描述的是周期。当实时任务发生改变时，软实时任务、固定实时任务的执行等级也将发生改变，此情况下T任务和D任务数值也将发生改变。这种任务调度设计方式，可以为控制器作业提供更为足够空间的同时，根据操控需求及时为其提供资源。3种任务类型中，硬实时任务较为特殊，因其对时间要求较高，所以无法自动提供足够的数据资源，需要借助调控设备，调整T值和D值。

3 嵌入式可配置操作系统环境下LST调度算法设计

本研究将设计的PID-FC-LST调度模型投入实践应用，根据操控需求，为其配备嵌入式可配置操作系统，在此系统中开发LST调度算法，使其得以满足嵌入式操作系统作业环境，从而为多功能操作系统作业提供较为可靠的资源调度控制工具。

3.1 嵌入式任务接口结构设计

由于PID-FC-LST调度模型在嵌入式操作系统环境中应用，任务调度功能无法被开启，所以设计了程序编程接口，对操作系统结构进行了优化，使其得以与其他功能模块兼容。任务接口结构的设计是以操作系统内核作为基底，利用内核线程API，创建任务API，开发用户应用程序，从而实现任务接口的连接。

其中，API函数作为接口连接的主要工具，以entry_data为入口函数参数，该参数类型为cyg_addrword_t。运用API函数作为多种类型数据传递指针，主要用来传递任务中私有部分数据。通过数据传递，实现任务数据的扩展。嵌入式变量描述与程序任务数据结构如表1所示。

表1 嵌入式变量描述与程序任务数据结构

系统分别为各个实时任务分配定时器，绑定后操控时间相关数据。其中，扩展数据成员均利用API程序访问，或者对数据加以修改处理。

3.2 LST调度系统作业设计

为了使资源调度得以有序进行，本系统开发了LST调度作业管理功能模块。该模块主要用于实时任务接收的调度控制，利用优先级映射器，排列实时任务执行顺序，使任务调度得以有序展开。LST调度器结构如图3所示。

图3 LST调度器结构

按照任务关键性大小，设置3个优先等级，任务优先级档次随着关键性的增加而提升。相邻关键性任务调度的处理是以临界优先级作为调度依据，优先调度关键性较高的任务。然后确定任务优先级。按照一定时间间隔，从系统作业任务中获取松弛时间，运用优先级映射器计算松弛时间，以此确定任务的优先级。其中，松弛时间与任务优先级之间呈现负相关关系。最后，利用多级队列调度器，控制任务进入系统运行队列的先后顺序。

3.3 任务执行等级控制设计

任务执行等级控制以优先级映射器作业期间产生的时间间隔nTM为依据，根据nTM中的n，确定任务执行等级。当n值偏大时，优先级映射器作业期间占用处理器的资源较少，然而该条件也会导致松弛时间敏感度下降，部分任务执行期间容易错过时限。当n值偏小时，任务松弛时间不容易受其影响，能够以较小的松弛时间完成任务执行。通常情况下，这些任务执行关键性较高情况下，n的数值越小。因此，可以通过为n赋值，来控制任务执行等级。

4 算法应用测试分析

4.1 应用测试内容与方法

设置90个采样点，运用LST算法、PID-FC-LST算法控制监视器，从而获取任务错过率，并记录测试结果。同时，利用监视器采集空闲任务条件下的处理器占用率，而后计算处理器占用率。

4.2 测试结果分析

按照测试内容与方法，分别对两种算法应用期间产生的任务错过率、处理器总利用率展开测试，结果如表1—2所示。

表1中，LST算法应用期间任务错过率较高，最小值产生在样点30处，数值为2.06%。相比之下，PID-FC-LST算法的任务错过率明显降低，最大错过率为0.53%。所以，本文设计的算法能够有效控制任务错过问题。

表1 任务错过率测试结果

表2中，LST算法应用期间，处理器利用率随着采样点数量的增加而不断波动，利用率在99.2%以上，并且采样点40和采样点80的利用率达到了100.0%，严重超荷。增加反馈控制环节，即运用PID-FC-LST算法，降低了处理器利用率，9组实验测试中处理器利用率最大值为98.9%。由此看来，本算法的处理器资源利用更加合理。

表2 处理器总利用率测试结果

5 结语

本文针对系统作业实时调度问题展开探究，在LST算法基础上，增加反馈控制体系，借助嵌入式实时系统作业环境，设计一种新的任务调度算法PID-FC-LST。测试结果显示，PID-FC-LST算法不仅可以有效降低任务错过率，而且还能够合理利用处理器资源，避免处理器作业超荷问题的产生，有助于系统作业实时调度的有序开展。