嵌入式自动测试系统实时调度研究

沈玲玲 李晓明

摘 要：

在嵌入式自动测试平台的开发中，为保证测试过程中系统实时调度的稳定性与及时性，文章提出了一种基于最优优先级分配（OPA）算法的调度改进算法。首先通过任务建模和任务分解，将任务转化为线程形式，并应用基于OPA算法的调度改进算法根据任务截止期等对任务队列迭代任务排序，得到最佳调度排序以实现高效的调度状态。改进算法对比实验结果验证了该算法相较于原算法具有更好的性能，包括提高系统的利用情况及任务平均计算时间，满足系统测试过程的实时性需求。

关键词：实时系统；调度算法；OPA算法；自动测试系统

中图分类号：TP316  文献标志码：A

0 引言（Introduction）

随着信息化时代的不断发展，计算机技术已经深入渗透各个领域，其中实时系统［1］作为一项重要的技术，在航空航天、工业控制、交通管理等领域得到广泛的应用。实时系统的重要性在于它能够确保任务在特定时间范围内得到及时响应和完成，而不同于一般的操作系统，实时系统的主要关注点不是高吞吐量，而是对任务响应时间和截止期的严格控制。

本文的嵌入式自动测试系统［2＼|3］是一种高效且灵活的测试系统，它由硬件和软件两部分组成，旨在实现自动化测试。嵌入式自动测试系统的主机运行的Linux操作系统是非实时的操作系统，为了达到实时性要求，以往都是采用给操作系统打补丁的方式改进其实时性，通过实时抢占补丁改善实时性问题。实时抢占补丁是通过中断线程化、高精度时钟、临界区可抢占以及优先级继承等方法改善Linux内核的实时性［4］。但是，随着测试任务的复杂程度逐渐增大，为确保系统满足实时性要求，需要选择合适的调度算法应用于嵌入式自动测试系统。目前，实时调度算法有最早截止期优先（EDF）算法、最高优先级优先（HPF）算法、最低松弛度优先（LLF）算法及最优优先级分配（OPA）算法等。陈国良等［5］基于EDF算法实现了最小松弛度优先调度算法，并对其进行了改进，包括降低任务上下文切换频率和最小化松弛度计算，以减轻调度过程中的颠簸现象。同时，李辉等［6］同样基于EDF算法引入了半划分调度的概念。经过改进的算法在实时任务处理器利用率存在较大差异时仍能调度成功，增强了Linux实时任务的可调度性，同时降低了上下文切换频率，进而减少了系统开销。

然而，鉴于所研究的实时系统［7］中存在任务间的依赖关系及相关优先级，最早截止期优先、最高优先级及最低松弛度优先3个算法与目前系统调度切换条件不匹配，综合考虑多个因素后，决定采用最优优先级分配算法［8］进行扩展，达到提升系统的实时性目的。应用改进的OPA算法，期望能够有效地管理测试任务的优先级，优化任务的执行顺序，确保测试任务在其截止期前得到及时响应和完成，同时提高测试系统的可调度性和性能。

1 任务建模（Task modelling）

在本文研究的系统中，任务的运行由系统中的组件［9］完成。每个组件代表一个独立的执行单元，在其内部完成特定的任务或功能，并与其他组件协同工作，实现系统的整体功能。因此，组件在系统中起到类似线程的作用，通过并发执行有效地提高了系统的整体效率和性能。在此背景下，研究人员将对这些组件类型进行详细分类，以便全面理解其在系统中的功能和起到的作用。

作业组件类型可根据数据传输方式分为5类。第一类组件仅接收输入数据并进行处理；第二类组件专门负责数据输出，无外部输入，它将内部处理后的数据输出至指定目标；第三类组件需接收外部输入数据，并在内部处理后输出结果；第四类组件（虚拟连接组件）结合了第一类组件和第二类组件的功能，两个作业共享内存地址，使输入数据可直接传递给另一组件，实现了连续的数据流动；第五类组件（TCPClient）虽然有输入、输出属性，但是二者无直接关联，输入数据在运行时保持独立，不影响输出结果。根据组件属性构成的任务集合模型如图1所示。

2.1 任务分解

根据任务集合模型，每个节点代表一个线程τi，各线程之间的相互依赖关系可以通过有向边表示。研究人员将任务进行分解，形成多个子任务集合，然后根据线程之间的依赖性，为每个线程分配适当的偏移值和截止期［10］。Di表示任务的相对截止期，即任务在每个周期内必须完成的时间范围。故可将线程τi表示为（Ci，Di，αi）。其中：Ci和Di分别对应线程的最坏运行时间与截止期，αi表示线程对应的偏移量，初始任务偏移量为0。ri为任务开始时间，如果τi在ri点运行，那么依赖于τi的下一个作业τp将在rp=ri+Di点运行，其绝对截止期dp=rp+Dp，任务τp的执行时间窗口是（rp，dp］。任务分解示意图如图2所示。

2.2 算法设计

基于所提供的任务集合，在分解任务后，各个线程被赋予了适当的偏移时间和截止期，而不需要考虑线程之间的依赖关系，下一步的研究目标是为每个线程τi分配优先级。为了实现该目标，本研究采用改进的OPA算法。在OPA算法中，每个任务都有一个截止期，表示任务必须在截止时间之前完成。此外，每个任务还有一个执行时间，表示任务完成所需的时间。OPA算法的核心是为每个任务分配一个合适的优先级，以便满足其截止时间的要求。这个分配过程是在考虑任务的截止时间和执行时间等因素的基础上进行的。通常，截止时间紧迫的任务，会被分配更高的优先级，确保它们在截止时间之前执行。

改进后算法的核心思想是按优先级递增的顺序对所有线程进行迭代，并为它们分配优先级。初始状态下，任务集合τ中的所有任务均未分配优先级。经过第i次迭代后，将任务集合τ划分为两个子集合O（i）和R（i）。其中，O（i）包含在进行到第i步之前已经成功分配优先级的任务，而R（i）则包含尚未被分配优先级的任务。

在进行任务的优先级分配之前，必须确保各线程的截止期早于任务的整体截止期，并评估任务集合的可调度性。目前，系统的处理器为双核处理器，根据作业调度算法，当每个线程τi满足以下不等式时，任务集合将具备可调度性，可以用如下公式表示：

∑αi≠αkWi（Di）+WK（Dk）<2×（Dk-Ck+1）[JZ）][JY]（1）

其中：WK（Dk）为任务集αk中优先级高于线程τk的其他所有线程的最大负载，Wi（Di）为在任务集αi中优先级高于线程τk的其他所有线程工作负载之和。

WK（Dk）=∑min（WK（Dk，Ok），Dk-Ck+1）[JZ）][JY]（2）

算法的总体设计思路如下：利用算法1分配线程优先级。若此分配未能成功，则随之调整部分线程的偏移与截止期，确保某些线程可以成功获得优先级分配。如果这样的调整方法能够找到可分配优先级的线程，那么继续运用算法1进行优先级分配，否则，将此情况视为分配失败。最终，算法的输出结果为成功分配优先级的调度状态。线程的富余时间则被定义为线程结束时间与截止期之间的最小间隔，可以用如下公式表示：

Si=Dk-Ck-∑αi≠αkWi（Di）+WK（Dk）2[JZ）][JY]（3）

定义线程的归一化富余时间S′[KG-1mm]i=Si/Dk。在本研究中，对任务模型进行了更全面的考虑，将线程的截止期调节变换为线程的富余时间调节，富余时间较多的线程将部分富余时间赠予时间紧缺的线程。在这一机制下，富余时间充裕的线程被称为赠予线程，而接收富余时间的线程则被称为受赠线程。

3 实验验证（Experimental validation）

3.1 实验环境

本文介绍的嵌入式自动测试系统在3个独立的工作环境中进行了部署，分别为上位机环境、主机环境和前端环境，整体软件采用Java技术及Eclipse RCP平台框架搭建而成。系统提供了用户创建、编辑和部署上位机测试应用、主机测试应用和前端数字信号处理（DSP）程序等功能。实验室自主研发的通用嵌入式测试仪器系统如图3所示。测试系统平台结构如图4所示。

此外，该系统还负责对前端资源进行管理，执行测试流程、监督测试过程、显示测试结果。实验任务集的生成通常由上位机实现，在上位机环境中，用户可以通过交互式界面创建任务。系统采用图形化的编程方法，通过将各种功能组件进行组合，以拖放和连线的方式实现测试功能。所有的功能组件按照时间片的方式并行运行，同时根据端口之间的连线确定数据交互的内容。每个任务组件的执行过程类似于一个线程任务，这些任务组件可以自由地拖放以构建所需的任务集合。任务集的生成示例如图5所示。编辑得到的应用程序同样基于XML文件存储，并可以被运行平台加载运行。

在每次实验运行中，将生成的任务集加载到系统中，并执行这些任务，模拟任务执行期间资源工作条件，包括可能的竞争条件、资源争用等。任务应按照其属性和生成顺序依次执行。对于每个任务，记录其完成时间，即任务开始执行到任务完成的时间。为了获得可靠的结果，可以实验运行多次，每次运行需要使用不同的随机任务集。

3.2 实验结果与分析

为了充分评估本文所提算法的性能，研究人员将其与基本的OPA算法、原系统调度算法的性能进行横向比较，以全面观察所提出算法的优越性和改进效果，以便研究人员深入理解算法的性能，并进行合理评估。

为了综合评估本文所提算法对任务性能的影响，设计了两个测试指标，分别是算法性能和任务计算时间。进行多次随机实验对算法在不同情境下的调度性能进行评估与比较。在第一组实验中，研究人员通过系统利用情况（U*）评估算法的调度性能。分别采用原系统调度算法、基本的OPA算法及改进的算法对系统利用情况进行测试，在测试平台上随机生成任务，图6中的结果显示改进的算法检测率上升明显，得出改进的调度算法的性能得以提升的结论。

使用改进算法后，随着节点数量增加，运行速率明显比改进前有大幅上升，表示改进算法性能明显高于原系统算法。

4 结论（Conclusion）

本研究基于实验室自行研发的嵌入式自动化测试平台，针对其运行过程中的调度问题提出了一种基于优先级分配算法的改进算法。通过任务建模和算法设计，将系统的任务进行细致的分解，将其转化为线程级别的调度问题，并采用优先级迭代策略生成最终的调度状态。实验结果表明，改进的算法在两个关键性能指标，即系统利用率和节点总数量方面，都取得了显著的提升。总的来看，本文提出的改进算法在不同情境下均表现出良好的性能，为提升实时系统的任务调度效率提供了有益的思路和方法。这项研究不仅在理论层面丰富了实时系统调度领域的知识体系，还在实际应用中展示出了较高的实用价值。

参考文献（References）

［1］ 王颖洁，周宽久，李明楚. 实时嵌入式系统的WCET分析与预测研究综述［J］. 计算机科学，2019，46（S1）：16＼|22.

［2］ 齐永龙，宋斌，刘道煦. 国外自动测试系统发展综述［J］. 国外电子测量技术，2015，34（12）：1＼|4，7.

［3］ 曹晟. 面向嵌入式智能设备的多核操作系统任务调度算法的研究与实现［D］. 北京：北京邮电大学，2021.

［4］ 王朴，周晴. 基于龙芯1E的嵌入式Linux实时性的优化与可靠性设计［J］. 微电子学与计算机，2019，36（11）：11＼|15.

［5］ 陈国良，朱艳军. 基于Linux的多核实时任务调度算法改进［J］. 计算机测量与控制，2020，28（11）：238＼|241，246.

［6］ 李辉，刘志红. 基于半划分调度的Linux实时调度算法改进［J］. 计算机与数字工程，2022，50（7）：1615＼|1619.

［7］ 李欣，白兴武. 基于Linux的嵌入式实时操作系统任务调度算法优化［J］. 自动化与仪器仪表，2020（9）：48＼|51.

［8］ DAVIS R I，BURNS A. Improved priority assignment for global fixed priority pre＼|emptive scheduling in multiprocessor real＼|time systems［J］. Real＼|time systems，2011，47（1）：1＼|40.

［9］ 叶可欣. 仪器功能组件可视化管理及应用编程方法研究［D］. 杭州：浙江大学，2017.

［10］ [ZK（]EKBERG P，YI W. Bounding and shaping the demand of generalized mixed＼|criticality sporadic task systems［J］. Real＼|time systems，2014，50（1）：48＼|86.

作者简介：

沈玲玲（1999＼|），女，硕士生。研究领域：嵌入式软件开发。

李晓明（1976＼|），男，博士，副教授。研究领域：机电系统集成，软件开发。