一种面向分布式系统的任务可调度性验证方法

摘要

本发明公开了一种面向分布式系统的任务可调度性验证方法，包含以下步骤：步骤一、采用基于时间自动机模型的处理器模型、任务模型、调度模型以及网络总线模型四个方面对分布式系统进行仿真；其中，任务模型在任务下达后将任务置于就绪状态，并根据调度模型的调度以及任务的属性对任务的状态进行调整；调度模型根据调度规则将任务调度到处理器模型或者网络总线模型上；处理器模型或网络总线模型在将收到调度模型分配的任务后根据自身模拟的处理器或总线进行空闲和占用状态的切换；步骤二、借助仿真分析工具对任务是否在截至时间完成、总线的占用情况以及处理器的占用情况进行验证与分析，从而对分布式系统的任务可调度性作出判断。

说明书

技术领域

本发明涉及一种面向分布式系统的任务可调度性建模仿真验证方法。

背景技术

对分布式系统而言，任务的可调度性是其重要特性，它对整个分布式系统的安全运行有着至关重要的影响。在机载领域的分布式系统，不仅要求任务运行结果的正确性，同时也要求其满足时间约束，因此机载分布式系统的任务可调度性分析是保证系统正确运行的关键步骤。

伴随着技术的发展与更迭，航空电子系统架构从联合式发展到综合模块式再到分布式综合模块式，机载场景越发复杂、功能应用不断增多。与此同时，随着具有时间和空间分区隔离特征的ARINC653标准和涉及任务分配与核间调度等复杂情况的多核处理器的应用与推广，任务间的交联关系从上到下越发复杂，信息传输时延的不确定性因素也越来越多，系统实时特性的判断与验证的难度变得越来越大。这都对机载环境下的嵌入式实时系统的任务可调度性增添了新的挑战。

有限状态自动机(finite state automaton)是一种形式化的计算模型，其拥有有限数量的状态，状态间可根据条件进行迁移。时间自动机是带有一个有限时钟集合的有限自动机，每个时钟都是一个取值范围为0或正数的变量，此外其还附带了若干的实值变量，自动机状态之间的转换要满足时钟等约束条件才会发生。UPPAAL是针对时间自动机的建模、仿真和验证工具，由Uppsala大学和Aalborg大学共同开发，在实时系统模拟验证方面有较多的应用。

发明内容

本发明的发明目的在于针对机载环境下的分布式航空电子系统架构，提出一种面向分布式系统的任务可调度性验证方法。基于时间自动机形式化建模语言，建立分布式系统各环节的关键模型，通过仿真评估分布式系统任务的可调度性，由此促进系统实时性能的优化、降低潜在的系统风险。

本发明的发明目的通过以下技术方案实现：

一种面向分布式系统的任务可调度性验证方法，包含以下步骤：

步骤一、采用基于时间自动机模型的处理器模型、任务模型、调度模型以及网络总线模型四个方面对分布式系统进行仿真；其中，任务模型在任务下达后将任务置于就绪状态，并根据调度模型的调度以及任务的属性对任务的状态进行调整；调度模型根据调度规则将任务调度到处理器模型或者网络总线模型上；处理器模型在将收到调度模型分配的任务后根据自身模拟的处理器进行空闲和占用状态的切换，网络总线模型在将收到调度模型分配的任务后根据自身模拟的总线进行空闲和占用状态的切换；

步骤二、借助仿真分析工具对任务是否在截至时间完成、总线的占用情况以及处理器的占用情况进行验证与分析，从而对分布式系统的任务可调度性作出判断。

本发明的有益效果在于：

1基于处理器、总线、任务和调度模型，能够仿真包括基于ARINC653标准的分区调度、基于同构多核负载均衡的动态调度、基于处理器核绑定的静态调度等多种分层调度，评估计算资源占用情况和处理器任务可调度性；

2通过任务模型的属性描述，可以体现包括共享资源占用、相关任务依赖、信息传输缓冲、处理器核绑定等多种情况，让系统仿真更贴近实际情况；

3通过建立通信总线传输模型，能够仿真包含有仲裁式总线和交换式总线的分布式系统，并借助仿真工具对系统状态、可达性、延时分布进行仿真分析，从而为复杂分布式系统架构的时间特性评估优化提供支持。

附图说明

图1是一种面向分布式系统的任务可调度性验证方法的总体流程示意图。

图2是ARINC653分区调度模型示意图。

图3基于优先级的抢占式调度模型示意图。

图4分区0内任务模型示意图。

图5分区1内任务模型示意图。

图6分区2内任务模型示意图。

图7ARINC653系统调度仿真甘特图。

图8仲裁式总线模型示意图。

图9仲裁式总线信息传输时延仿真示意图。

图10分布式系统信息传输模型。

图11分布式系统信息传输端到端时延仿真。

图12系统端到端传输耗时仿真统计。

具体实施方式

下面结合附图和实施例对本发明作进一步的详细说明。

由于分布式系统是一个复杂系统，由若干个分区组成，每个分区上布置的任务需要有调度程序将任务调度到总线上进行数据传输或调度到处理器进行处理才能完成，参见图1所示，本实施例所示的一种面向分布式系统的任务可调度性验证方法，先采用基于时间自动机模型的处理器模型、任务模型、调度模型以及网络总线模型四个方面对分布式系统进行仿真。其中，任务模型在任务下达后将任务置于就绪状态，并根据调度模型的调度以及任务的属性对任务的状态进行调整；调度模型根据调度规则将任务调度到处理器模型或者网络总线模型上；处理器模型在将收到调度模型分配的任务后根据自身模拟的处理器进行空闲和占用状态的切换，网络总线模型在将收到调度模型分配的任务后根据自身模拟的总线进行空闲和占用状态的切换。

再借助仿真分析工具对任务是否在截至时间完成、总线的占用情况以及处理器的占用情况进行验证与分析，从而对分布式系统的任务可调度性作出判断。

一、任务模型

任务即分布式系统需要完成的事务，如信号的采集、数据的显示、控制命令的下达等，任务的执行涉及到分布式系统一系列环节，系统架构各环节的性能和不同任务间的关联性都将直接影响任务的完成情况。

任务的属性包含基础属性和依赖属性。任务的基础属性包括周期、执行时间、截至时间和优先级。任务的依赖属性包含任务对指定处理器/核的绑定，任务间的依赖关系：和其他任务公用某些资源、存在资源的抢占与等待，以及任务执行的先后顺序等。

在基础型的任务模型中，以任务的就绪、执行、完成和错误作为基本状态，以任务的基础属性作为任务模型的状态转移的条件。例如，在某个任务下达后，任务模型将该任务置于就绪状态，调度模型便会根据调度规则将其排入待处理队列；待调度模型给任务分配了处理器资源或总线资源后，任务模型将该任务置于执行状态；当任务的实际执行时间达到其基础属性注明的执行时间后，认为该任务处理完毕，任务模型将该任务置于完成状态；若在一个规定的周期内，任务在上述流程累计耗费的时间超过了设定的截至时间，则认为任务未在规定时间内执行完毕，任务执行失败，任务模型将该任务置于错误状态。

在分布式系统下，除了要考虑任务的基础属性外还需要考虑任务的依赖属性，例如在多处理核环境下任务对指定处理器/核的依赖，某些任务是否预先绑定到指定的处理核上；分区内部或分区间的任务间的依赖关系，例如某些任务会共同占用同一个公共资源，由此造成资源抢占与等待的问题，某些任务之间具有先后执行的逻辑关系，因此任务间存在等待；以及多任务通过总线进行传递时，也可能存在排队、仲裁等等状况。因此，可以在基础型的任务模型中加入若干个与依赖属性相关的状态和转移条件。

以依赖属性中有抢占的任务的任务模型为例举例说明，可在基础的任务模型上增加一个暂停状态，当处于执行状态的任务被调度模型提出要求释放资源时，则任务模型将该任务的置于暂停状态，待调度模型再次给任务分配了处理器资源或总线资源后，任务模型将该任务的置于执行状态。其它依赖属性与此相似，不展开一一说明了。

二、处理器模型

处理器主要为任务提供必要的处理资源，分布于分布式系统的多个环节，处理器模型的状态分为空闲和占用二种，在空闲状态下接收调度模型对其派分任务并将状态变为占用，而对应的任务模型则从就绪变为执行状态；根据模拟的处理器的处理能力判断处理任务的耗时时间，从而在对应的时间点将占用状态变为空闲状态。

三、网络总线模型

分布式系统的网络总线模型，可以划分为接收、传播和发送三类。

接收、传播和发送三类的网络总线模型的状态均可分为空闲和占用二种，在空闲状态下接收调度模型对其派分任务并将状态变为占用，而对应的任务模型则从就绪变为执行状态；根据模拟的网络总线的处理能力判断处理任务的耗时时间，从而在对应的时间点将占用状态变为空闲状态。

其中发送类的网络总线模型的处理能力与发送端口的信息量和速率有关。

接收类的网络总线模型的处理能力与接收端口的信息量和速率有关。

传播类的网络总线模型的处理能力除了考虑传输路径的固有传播时延外，还与网络机理息息相关。

网络总线模型在接收到任务后，根据不同的网络类型会有不同的执行判据进行状态切换，可分为抢占仲裁式和路由转发式两种模型。前者的网络在接收到多个任务时，需要对当前等待执行的任务进行仲裁选择，其规则类似于基于优先级的资源调度策略，消息的发送传播模型需考虑总线状态以及仲裁情况；后者在接收到任务后按照对应端口完成传输即可，任务间不存在仲裁过程，其传播模型需考虑交换机转发产生的延迟。

四、调度模型

在航空电子系统的时间关键性应用中，任务调度的模型化描述可以抽象表示为处理器或网络总线针对目标任务分配处理资源完成任务处理，而整个过程中所涉及的关键属性即时间，对于强实时系统而言，任务必须在规定的时间内处理完毕，否则将认为任务调度失败。

简单来说，调度模型接收就绪的任务，查询相应的处理器模型或网络总线模型，若空闲即将任务调度给处理器模型或网络总线模型。

具体而言，任务调度类型可主要分为单层和多层调度、抢占式和非抢占式调度。

其中单层的抢占式调度是在接收到多个任务时，需要对当前将执行的任务进行排序仲裁。任务排序规则主要有单调速率排序、轮询排序、基于固定优先级的排序、基于距离截止时间最近的排序等策略。其中单调速率排序策略将众多任务按照周期长短分配优先级，处理器资源或总线资源优先分配给高优先级任务；轮询策略则依照初始序列顺序重复遍历任务队列。

多层调度在航空领域当前主要是基于ARINC653标准的双层调度，该系统调度模型包含一个总体时间框架，其被分成几个固定的时间片，时间片们具有明确的时间段和次序，每个时间片内的任务则遵循该片内的任务调度策略。

此外，多核系统还存在处理器核间调度的问题，对于多核处理器，又分为同构多核和异构多核两种情况，其中同构多核的核间任务调度当前主要关注基于负载均衡的任务调度和固定绑定的任务调度策略，基于负载均衡的任务调度需在多核间建立动态调度模型，固定绑定的任务调度则建立固定式的静态调度模型。异构多核的任务调度则建立固定式的静态调度模型。

本实施例以一种基于ARINC653的分布式系统进行举例说明。在本实施例中采用双层调度模型，上层调度模型为ARINC653分区调度模型，下层调度模型为各分区的分区内调度模型。

(1)ARINC653分区调度模型

ARINC653分区调度模型采用非抢占式调度模型，根据总时间框架和每个时间片的起始时间调度三个分区各自的分区内调度模型，如图2所示。

(2)分区内调度模型

每个分区内的任务基于不同的调度策略：分区0内的任务基于优先级的抢占式调度；分区1内的任务基于单调速率调度的抢占式调度；分区2内的任务就绪即执行的非抢占式调度。

分区内任务调度的时间自动机模型包含的判断要素有：分区是否就绪/结束、分区内任务是否就绪/结束、抢占是否发生及队列的排序。不同调度策略的区别主要体现在任务队列排序的规则，基于优先级抢占式调度的分区0的调度模型如图3所示。

(3)任务模型

不同分区、调度策略下的任务类型会有不同的时间自动机模型，本实施例包含三种任务模型。

a.分区0内的任务模型

本实施例中分区0内包含3个任务，除任务周期、截止时间、执行时间等基础属性外，还包含有任务偏移量和任务间的依赖属性，具体在任务特性数据表中描述。在任务的时间自动机模型中，其包含有Ready、Running、Blocked、Error等基础状态用于描述任务的就绪、执行、抢占和错误，还包含Dependency和Delay来表示任务的依赖，在运行过程中，会涉及到偏移量、分区状态、队列优先级、执行时间、任务依赖状态等条件判断，其模型如图4所示。

b.分区1内的任务模型

分区1内包含3个任务，任务参数涉及到任务周期、截止时间、执行时间等基础属性，任务的状态变迁涉及到分区状态、执行时间、队列优先级等判断，其模型如图5所示。

c.分区2内的任务模型

分区2内仅包含1个任务，就绪即执行，其时间自动机模型如图6所示。

在完成对分布式系统的仿真，就可借助仿真分析工具对任务是否在截至时间完成、总线的占用情况以及处理器的占用情况进行验证与分析，从而对分布式系统的任务可调度性作出判断。

1分布式系统模型动态仿真

通过在UPPAAL中命令，可以对该实施例的模型运行状态进行动态模拟仿真，其动态仿真Gantt图如图7所示。该图7能够显示模型基于ARINC653的时间片调度情况，每个分区内任务调度的状态，以及处理器计算资源占用的情况。

2基于TCTL的模型状态可调度性验证

对于模型的可调度性验证，借助于TCTL语言，查询系统的所有任务是否会发生错误(即任务的执行时间超过截止时间限制)情况的发生：A[]forall(i:Tid_t)not P0Task(i).Error&&forall(j:Qid_t)not P1Task(j).Error&¬ P2Task.Error，验证结果为“Property is satisfied”，即该实施例模型的可调度性符合要求。

3包含仲裁式总线的信息传输时延仿真分析

含有总线的信息传输模型，涉及到发送设备、总线和接收设备，其时间属性主要包含信息的发送、总线调度传输和信息的接收。当发送设备想通过总线发送消息时，首先向总线发送请求，总线如果当前处于空闲状态则建立通信传输；若处于使用中则需等待；若同时存在多个申请，总线会根据某种规则进行仲裁，将权限分配给优先级最高的一路发送设备，其余设备等待。该机制的时间自动机模型如图8所示：

通过仿真软件的仿真验证，可以模拟信息传输的动态时序，本实施例中包含四个发送设备、一个仲裁式总线和两个接收设备，图9即是其Gantt图。

4分布式系统信息传输端到端时延仿真分析

对于分布式系统，涉及多个分布式设备的任务调度处理以及总线网络。本实施例的分布式系统，主要包含信号接收、处理、显示三个分布式设备，以及一个采用交换机的通信网络。信息端到端传输时延涉及到的关键要素主要包含分布式设备的任务调度、消息发送和传输产生的排队与传播时延等，本实施例的时间自动机模型如图10所示。

分布式系统消息传输Gantt图如11所示

对于分布式系统的实时性，除了验证其可调度性外，还需对该分布式系统模型的传输时延作评估，通过在仿真的分布式系统中加入时间注入模型，给消息传输打时间戳，统计系统端到端传输耗时，图12是1000次采样统计结果，根据仿真，结合系统设计需求对该分布式系统架构进行优化调整。

可以理解的是，对本领域普通技术人员来说，可以根据本发明的技术方案及其发明构思加以等同替换或改变，而所有这些改变或替换都应属于本发明所附的权利要求的保护范围。