一种不精确离散事件系统建模与仿真

2022-04-20李妮

微型电脑应用 2022年3期

李妮

(西安明德理工学院，通识教育学院，陕西，西安 710124)

0 引言

实时(Real Time,RT)系统通常由嵌入在硬件中的软件组件构建，这些软件组件与环境以满足时序约束的方式进行交互。RT系统主要应用于自动驾驶仪、电厂控制、运输和电信到客户电子设备、医疗设备、智能和自动化系统等领域[1-2]。

近年来，RT系统在数量、复杂性、安全性、可靠性、容错性、功耗等方面需求不断增长，这对RT系统的设计提出了新的挑战[3-4]。为此，众多学者提出了不同的形式化方法来设计和开发RT系统。王高才等[5]基于随机模型研究了软实时系统中任务的可调度性特征，并提出了期望可调度性的概念。夏平等[6]基于安全分级思想，构建了一个适应动态安全需求的实时调度模型。吴尧辉等[7]针对供电综合保护器任务多且前后台系统实时性差的问题，提出了一种针对实时操作系统的中断管理机制，同时进行多任务中断管理设计。上述方法设计时进行了形式化说明和分析，这有助于提高最终系统的可靠性，但是增加了设计的复杂性及可靠性开发成本。此外，部分方法设计时未考虑系统溢出问题，由此高计算峰值将对系统性能产生严重影响。

本文形式化定义了含不精确计算(Imprecise Computing,IC)技术的离散事件模型，将系统的行为分为强制和可选两部分，为用户提供了灵活性，从而实现处理器更可靠的RT任务调度过程。

1 相关概念

1.1 实时系统及不精确计算

IC技术是处理瞬时过载下RT系统调度问题的有效方法[8]。该方法将任务的关键(强制)部分与其非关键(可选)部分分离，从而使RT系统能够接受更多的任务，同时尝试运行尽可能多的可选子任务。这允许动态配置系统，以便在系统处理流量较大时，通过生成不太准确的结果来接受更多的任务；另一方面，在系统负担较低时，完全执行任务以生成准确的结果。

考虑到可抢占任务的任务集为T=(T1,T2,…,Tn)，针对每个任务Ti(i∈[1,n])定义以下参数：ri是任务Ti释放的时间；di是任务Ti必须完成的截止日期；ti是任务Ti所需的处理时间；wi是任务Ti的权重，表示该任务的相对重要程度。

每个任务Ti由2个子任务组成：强制和可选,则有

mi+oi=ti

(1)

其中，mi为强制子任务Mi需要处理时间，ti为oi可选子任务Oi的需要处理时间。

在可调度RT系统中，当相关作业中包括的每个任务Ti的至少所有强制子任务被执行时(作业是在执行期间发生的任务的实例)，则每个任务Ti处于正在执行阶段。任务Ti的可选子任务只有在Ti的强制子任务正确执行时才可执行。调度器可以在可选子任务执行期间的任何时间终止该子任务。基于这个定义，完美硬RT系统是所有任务都由强制子任务组成的系统，完美软RT系统是所有子任务都是可选的系统。RT系统中的一个常见问题是，当系统没有足够的处理资源来完成所有请求进程时，会出现溢出情况。这个问题将给被控机器带来严重威胁，并可能导致灾难性的后果。

1.2 离散事件系统模型

离散事件系统(Discrete Event System,DEVS)模型[9-10]可描述为一组基本的原子模型和复合模型。原子模型仍然是最基本的结构，它可以与其他模型组合成复合模型。DEVS原子模型具有以下结构，

AM=〈XM,YM,S,δext,δint,δcon,λ,ta〉

(2)

假定在任意时间内，基本模型处于s状态。在没有外部事件的情况下，它将在ta(s)定义的一段时间内保持该状态。当发生内部状态转换时，系统输出值为λS，此时状态更新为δint(S)。如果外部事件E={x1,x2,…,xn/x∈XM}在ta(s)过期之前发生，即当系统处于e≤ta(s)的状态(s,e)时，新的状态将由δext(s,e,E)给出。假设一个外部转移和一个内部转移同时到达，即当e=ta(s)时，一个外部事件E发生，新系统的状态可以由δext(δint(s),e,E)或δint(δext(s,e,E))给出。需注意，可采用δcon函数定义模型最合适的行为。因此，新系统的状态将由δcon(s,E)定义。

复合模型指将基本模型连接在一起形成的新模型。这个模型本身可以作为一个更大的复合模型组成更加复杂的模型层次结构。复合模型定义为

CM=〈X,Y,D,EIC,EOC,IC〉

(3)

其中，X是输入端口和值的集合，Y是输出端口和值的集合，D是组件名称的集合，EIC(外部输入复合)将复合模型本身的输入事件连接到其组件的一个或多个输入事件，EOC(外部输出复合)将组件的输出事件连接到复合模型本身的输出事件，IC(内部复合)将组件的输出事件连接到其他组件的输入事件。

2 不精确离散事件系统

本文在RT任务调度中引入不精确离散事件模型，结合离散事件的动态优势和形式化建模方法的严密性，同时利用不精确计算用来处理由于系统中发生过载溢出情况产生的错误问题。

2.1 RT-DEV

实时系统离散事件驱动模型(RT-DEVS)运行时引擎中的主要计算发生在状态转换函数(即模型者在原子模型中定义的函数)以及调度和消息传输[11]。该模型为实时系统提供了一种基于建模与仿真的设计方案方法，可以在实际开发和部署之前对系统组件进行仿真，并进行形式化分析。

实时系统的最关键特性是在规定的截止日期内输出的可用性[12]。RT-DEVS为原子组件中的每个输出指定一个截止日期，并验证相关输出生成时的截止日期。因此，将概念引入形式化模型，并在抽象的仿真机制中实现。RT-DEVS具体定义如，

AMRT=〈X,S,δext,δint,δcon,λ,ta,d〉

(4)

假设消息传输具有与系统中标准任务之间的上下文切换相关的开销，那么RT-DEVS系统中的任务集由转换和输出函数组成。此信息用于将实时系统模拟器运行的DEV函数(δext，δint，δcon和λ)映射到实时系统内核和调度器中。RT-DEVS系统中的一组任务由状态转移和实时系统模拟器运行的输出函数(δext，δint和λ)组成。图1显示了在状态转换期间一个RT-DEVS系统中原子组件的处理任务示意图。假设每个转换函数占用1个时间单位，且各函数之间的上下文本切换忽略不计，图中显示了将DEV转换函数映射到调度时间表的具体过程。

图1 原子组件的处理任务示意图

如图1所示，外部转换(δext)映射到TX任务中，该任务启动状态S。此时任务的释放时间等于输入到达系统的时间。需注意，由于TX是一个可以随时到达的输入，因此不设截止日期。考虑到DEVS中的输出总是紧跟着内部转换，故输出任务Tλ和内部转换δint任务TI将同时执行，形成了TλTI任务。任务TλTI的释放时间等于状态S的结束时间，且由ta(s)指定(即图2中的T)。

图2 一个典型的多输入过载场景

假设系统接收大量输入，因此系统需要执行许多转换并生成相应的输出，从而使输出任务延迟，严重时将超过某些状态截止日期。图2所示为一个典型的包含4个输入的过载场景，系统在不同的原子组件上开始执行外部转换。Ti(i∈[1,4])为每个任务的时间推进函数ta(s)触发的任务发布时间。di(i∈[1,4])为每个任务的相关截止日期。假定系统中只有一个处理器执行转换函数(时间线下显示为黄色/绿色/红色)。可以看出，Tλ1、Tλ2和Tλ4满足了截止日期期限；与之相反，Tλ3和Tλ2(在系统时间18时由内部转换产生的第二个实例)并没有满足截止日期期限。内部转换任务TI2生成一个新状态，其ta(s)为4个时间单位，超过了时间17的截止日期。如果连续发生多个内部转换任务，则可以避免这种情况。然而，如果系统能够尽早检测到过载情况，从而应用基于不精确的调度，则可以防止这种情况的发生。

为了避免这种过载情况，将任务分为强制部分和可选部分。原子模型的状态分为强制状态和可选状态。强制状态将导致强制输出函数(表示为输出任务)，而可选状态将导致可选输出任务。假设输入TX任务始终是强制性的(以避免丢失任何输入)，由Tλ表示的非关键输出是可选的。可选TλT1任务的Tλ子任务可以在瞬时重载下终止。换句话说，在超限情况下，系统跳过可选输出以节省时间和资源。例如，在有大量侦察和控制任务的紧急任务情况下，飞机或汽车控制系统可以放弃信息娱乐任务以响应紧急控制命令。类似的情况也可以发生在任何实时系统中，即可以跳过一系列非关键输出，通过保持所需的输出按时产生来减轻过载情况。

2.2 I-DEVS

本节目的是为工作到达时间未知的应用程序提供一个不精确离散事件系统(I-DEVS)框架。该方法试图在系统繁忙时平衡计算，另一方面又不降低其性能，同时尽可能降低实现的运行时开销。该方法思路是将不精确理论概念与DEVS建模相结合。

在RT-DEV模型基础上，I-DEVS为每个状态添加强制或可选条件，具体描述为

AM=〈X,Y,δext,δint,δcon,λ,ta,d〉

(5)

原子模型的状态分为强制状态和可选状态。强制状态将具有强制输出函数(表示为输出任务)，而可选状态将生成可选输出任务。在状态机级别定义强制性任务和可选任务时，这种抽象允许建立不精确的模型，而不涉及较低级别任务系统的细节。这个工件允许实现一个执行模型的实时引擎，使执行机制(在模拟模式下运行的“模拟器”，或在实时模式下运行的“实时引擎”)独立于模型规范，使这些执行工件和相关可调度性测试更容易实现。

3 案例与分析

本节将以实际案例建立一个复杂实时系统模型，该系统包含20个原子组件，每个组件都配有输入端口和输出端口。复合模型基本结构如图3(a)所示，系统连接原子组件将输入传播到其他组件，由此频繁创建Tλ和TI任务群将导致溢出情况。当I-DEVS执行引擎检测此类情形时，系统可根据提出的基于IC方法进行计算处理。

原子组件遵循图3(b)中的DEVS图。模型由初始状态、可选状态和强制状态组成。每当有输入时，模型就从“空闲”状态转换到“强制”状态，在500 ms(状态生存期)之后，它产生一个输出并转换到“可选”状态(因为这是一个复合模型，输入和输出值也是复合的；在示例中的DEVS图中，它接收并发送一个值1)。该模型在“强制”和“可选”状态之间切换，每500 ms产生一次输出，用于进行综合性能测试，比较不精确执行和精确执行的结果。在精确执行的情况下，系统默认所有的值都是强制性的。此外，假定输入在执行1 s后注入到模型中，以便触发状态变换和输出信息。

图3 复合模型基本结构

图4所示为不同模式下的强制任务平均响应时间，其中执行时间分别为20 s、50 s、70 s、120 s和180 s，处理时间为10 s(对于Tλ)，处理时间为5 s(对于TI)。可以看出，由于丢弃可选任务作为防止一次溢出的措施，非精确模式下的平均响应时间小于精确模式。此外，图4还显示了丢弃的可选Tλ任务的数量。结果表明，早期检测策略在减少强制性任务的响应时间方面是有效的。

图4 不同模式下任务平均响应时间及可丢弃任务数量

图5所示为强制任务的平均响应时间以及可选丢弃的Tλ任务的数量:对于TI任务，处理时间为零；对于Tλ任务，处理时间为100 ms、10 ms、1 ms和100 μs，执行时间为20 s。同样，图5表明当不精确处理生效时，强制任务响应时间随之下降。可以看出，Tλ任务的处理时间越长，平均响应时间下降的幅度越大。

图5 强制任务平均响应时间及可丢弃任务数量

图6所示为在20 s执行时间内CPU利用率与Tλ的处理时间的关系。可以看出，在不精确模式下CPU利用率显著下降，这是由于丢弃可选Tλ节省了部分时间。同时，随着Tλ任务的处理时间减少，CPU利用率也随之降低。分析其原因是系统的空闲时间(500 ms状态生存期)的增加与其处理时间成正比。因此，运行所提方案后，CPU的使用大大减少，降低了超限情况的概率。