AADL分级调度模型的分析与验证

针对嵌入式系统体系结构分析设计语言(architecture analysis and design language,AADL)分级调度模型的分析问题,提出了基于模型检验的可调度性分析和验证方法.基于时间自动机理论,将AADL分级调度模型转换为时间自动机网络,将待验证性质描述为时序逻辑公式,通过模型检验工具对可调度性进行分析和验证.研究结果表明,使用模型检验方法来分析AADL分级调度模型的可调度性是可行的.相对其他方法而言,该方法利用了形式化方法的穷举性来分析系统的性质,分析结果更加精确.     

基于仿真方法的任务集可调度性判定工具

针对含有纯周期任务的任务集可调度性判定问题,提出一种基于仿真方法的任务集可调度性判定工具。通过设定时钟变量,模拟任务调度过程中的系统时钟,在时钟变量值增长的过程中,根据任务优先级从高到低的顺序,分析各个任务的截止时间限,判定任务集的可调度性。实例分析证明了该工具的可调度性判定结果正确。     

面向AADL模型的存储资源约束可调度性分析

嵌入式实时系统在安全关键领域变得越来越重要,其广泛应用于航空航天、汽车电子等具有严格时间约束的实时系统中.随着嵌入式系统的复杂度越来越高,在系统开发的早期设计阶段就需要对其可调度性进行分析评估.系统中的存储资源会对可调度性产生一定影响,在抢占式实时嵌入式系统引入缓存后,任务的最坏执行时间可能发生变化.因此,分析缓存相关抢占延迟对实时嵌入式系统的可调度性影响一直以来是困扰大规模复杂系统架构设计的一个技术难题.本文提出了一种面向软件架构级别、基于抢占调度序列的缓存相关抢占延迟计算方法,用来分析缓存相关抢占延迟约束下AADL （架构分析和设计语言）模型的可调度性.论文扩展了AADL关于存储资源架构设计的模型元素,来支持对缓存属性进行建模,提出了一种基于模型构件进行抢占序列排序、缓存相关抢占延迟时间计算和被抢占任务最坏执行时间的估算方法,来对系统架构各功能构件在共享系统存储资源下系统的可调度性进行分析.论文还实现了分析缓存相关抢占延迟约束下的系统任务可调度性分析工具原型,并以某型飞机机载开放式智能信息系统为例,在航空电子系统架构设计中进行尝试,验证了该方法的在复杂系统设计中的对实时性分析的可行性.     

复杂实时系统可调度性判定工具的研究与实现

针对包含多处理器、多分区结构的复杂实时系统存在的可调度性判定问题,提出一种基于仿真方法的任务集可调度性判定工具。通过设定时钟变量模拟任务调度过程,依据纯周期任务集的特性确定仿真区间,调用优化的判定算法,判定任务集的可调度性。测试结果及实例分析表明,该工具能自动、准确、快速地判定任务集的可调度性,并以甘特图的方式绘制任务调度过程,较现有工具更为高效、直观。     

基于分区的航电系统调度分析工具实现

针对仅含纯周期任务集合、符合ARINC653多分区构架航电系统两级调度模型的可调度性判定问题,提出一种基于分区的航电系统调度分析工具。通过设定时钟变量模拟航电系统各分区中任务集调度过程,依据纯周期任务集及分区航电系统时间片分派特性确定仿真区间,设计优化的调度分析算法,判定航电系统分区级时间片分派的正确性及各分区中任务集的可调度性。测试及实例分析结果表明,该工具能自动、准确、快速地判定航电系统分区以及任务级调度模型的可调度性,并能以甘特图的方式绘制系统调度过程,较现有工具更为直观、高效。     

针对AADL模型的可调度性分析方法研究

AADL(Architecture Analysis＆Design Language)语言是美国SAE(Society of AutomotiveEngineers)组织定义的一组满足航空电子综合化设计用的建模语言.它可以描述安全关键嵌入式实时系统功能和非功能性属性,非功能属性包括可靠性、安全性、可调度性等.通过对这些非功能属性进行分析,可以在设计阶段而不是实现阶段纠正系统设计缺陷,缩短系统开发周期和降低开发成本.总结了AADL语言对可调度性分析方面提供的支持,并分析比较了几种针对AADL模型的可调度性分析工具,在此分析和比较基础上,识别它们各自的优缺点,方便使用者根据需要选择合适的工具使用.     

嵌入式系统的细粒度多处理器实时抢占式调度算法

现有的嵌入式实时系统调度算法一般以任务级为调度单位,对此提出一种细粒度的线程级多处理器实时调度算法。采用DAG图描述实时系统的任务,并采用任务分解法将其分解为线程形式;为任务级调度采用基于干扰的可调度性分析,为线程级调度采用基于工作负载的可调度性分析;将线程的偏移、截止期与优先级作为三个调度目标,设计混合线程级调度算法。仿真实验结果表明,算法对于多线程任务的实时系统具有较好的性能。     

ARINC653实时任务可调度性验证方法

针对综合模块化航空电子系统(Integrated Modular Avionics,IMA)存在周期任务和非周期任务,以及任务间依赖关系,传统方法不能准确验证其实时任务可调度性的问题,本文提出了一种基于Stopwatch时间自动机的ARINC653实时任务可调度性验证方法,利用模型检验工具UPPAAL对IMA系统进行建模仿真,并结合统计模型检验(Statistical Model Checking,SMC)与符号模型检验(Symbolic Model Checking,MC)来验证其可调度性。实验结果表明,该方法不仅快速验证了IMA系统的可调度性,而且能够准确定位不可调度任务。     

基于随机模型的软实时系统的任务期望可调度性

本文基于随机模型研究了软实时系统中任务的可调度性特征,提出了期望可调度性的概念. 期望可调度性是与实时任务到达时间t相关的, 因此, 提出的方法能研究任务子集在任意给定时间间隔的可调度性特征. 本文给出了期望可调度性的条件, 如果任务的持续时间满足该条件, 则实时任务具有期望可调度性. 基于理论结果的数值分析与模拟结果是一致的,这表明当软实时系统的负载率小于69%(某些确定性模型提供的)时, 实时任务总是期望可 调度的. 这一结果也表明基于随机模型的期望可调度性方法能为软实时系统的任务可调度性分析提供一个更大的阈值和更好的适应性.     

基于改进型统一调度算法改善任务集的可调度性

实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。     

Task automata: Schedulability,decidability and undecidability

We present a model, task automata, for real time systems with non-uniformly recurring computation tasks. It is an extended version of timed automata with asynchronous processes that are computation tasks generated (or triggered) by timed events. Compared with classical task models for real time systems, task automata may be used to describe tasks (1) that are generated non-deterministically according to timing constraints in timed automata, (2) that may have interval execution times representing the best case and the worst case execution times, and (3) whose completion times may influence the releases of task instances. We generalize the classical notion of schedulability to task automata. A task automaton is schedulable if there exists a scheduling strategy such that all possible sequences of events generated by the automaton are schedulable in the sense that all associated tasks can be computed within their deadlines. Our first technical result is that the schedulability for a given scheduling strategy can be checked algorithmically for the class of task automata when the best case and the worst case execution times of tasks are equal. The proof is based on a decidable class of suspension automata: timed automata with bounded subtraction in which clocks may be updated by subtractions within a bounded zone. We shall also study the borderline between decidable and undecidable cases. Our second technical result shows that the schedulability checking problem will be undecidable if the following three conditions hold: (1) the execution times of tasks are intervals, (2) the precise finishing time of a task instance may influence new task releases, and (3) a task is allowed to preempt another running task.     

Schedulability analysis of fixed-priority systems using timed automata

In classic scheduling theory, real-time tasks are usually assumed to be periodic, i.e. tasks are released and computed with fixed rates periodically. To relax the stringent constraints on task arrival times, we propose to use timed automata to describe task arrival patterns. In a previous work, it is shown that the general schedulability checking problem for such models is a reachability problem for a decidable class of timed automata extended with subtraction. Unfortunately, the number of clocks needed in the analysis is proportional to the maximal number of schedulable task instances associated with a model, which is in many cases huge. In this paper, we show that for fixed-priority scheduling strategy, the schedulability checking problem can be solved using standard timed automata with two   extra clocks in addition to the clocks used in the original model to describe task arrival times. The analysis can be done in a similar manner to response time analysis in classic Rate-Monotonic Analysis (RMA). The result is further extended to systems with data-dependent control, in which the release time of a task may depend on the time-point at which other tasks finish their execution. For the case when the execution times of tasks are constants, we show that the schedulability problem can be solved using n+1$n+1$ extra clocks, where n$n$ is the number of tasks. The presented analysis techniques have been implemented in the Times tool. For systems with only periodic tasks, the performance of the tool is comparable with tools implementing the classic RMA technique based on equation-solving, without suffering from the exponential explosion in the number of tasks.     

Schedulability of asynchronous real-time concurrent objects

We present a modular method for schedulability analysis of real time distributed systems. We extend the actor model, as the asynchronous model for concurrent objects, with real time using timed automata, and show how actors can be analyzed individually to make sure that no task misses its deadline. We introduce drivers to specify how an actor can be safely used. Using these drivers we can verify schedulability, for a given scheduler, by doing a reachability check with the Uppaal model checker. Our method makes it possible to put a finite bound on the process queue and still obtain schedulability results that hold for any queue length.     

多处理器实时系统可调度性分析的UPPAAL模型

随着多处理器实时系统在安全性攸关系统中的广泛应用,保证这类系统的正确性成为一项重要的工作.可调度性是实时系统正确性的一项关键性质.它表示系统必须满足的一些时间要求.传统的可调度性分析方法结论保守或者不完备,为了避免这些方法的缺陷,提出使用模型检测的方法来实现可调度性分析.提出了一个用于多处理器实时系统可调度性分析的模板,将与系统可调度性相关的部分包括实时任务、运行平台和调度管理模块都用时间自动机建模,并使用UPPAAL验证可调度的性质是否总被满足.符号化模型检测方法被用于推断可调度性,但是由于秒表触发的近似机制,符号化模型检测方法不能用于证明系统不可调度.作为补充,统计模型检测方法被用于估算系统不可调度的概率,并在系统不可调度时生成反例.此外,在系统可调度时,通过统计模型检测方法获取一些性能相关的信息.     

基于Uppaal的实时系统AADL数据流模型的转换与验证

体系结构分析设计语言AADL是一种可支持软硬件一体化建模及同一模型多元分析的形式化与图形化建模语言。采用时间自动机形式化模型检验方法对AADL模型中的数据流进行转换和验证。考虑到单一数据流与混合数据流的差异性,分别设计了数据流到时间自动机模型的转换规则,并通过时间自动机网络实现数据流的综合分析。设计开发了自动化模型转换的插件AADLToUppaal Plug-in,将其嵌入到OSTATE工具中,使用时间自动机建模与验证工具Uppaal对转换得到的时间自动机进行模拟和验证,等价地验证所设计的AADL模型数据流时延是否满足系统实时性要求。仿真实验结果表明,所设计的数据流模型转换方法能有效地将AADL模型转换到时间自动机模型,并能在Uppaal中正确地分析原模型的数据流时延特性。     

信息物理融合系统控制软件的统计模型检验

信息物理融合系统常采用嵌入式实时多任务系统作为其控制软件,这类软件的并发和非确定性给验证带来了困难.提出了一种利用统计模型检验技术分析多任务系统的功能正确性的方法.该方法构造的时间自动机模型以模块化的方式描述了实时多任务系统中的主要成分,包括实时操作系统、周期性任务、偶发任务、共享资源以及物理环境,能够展现多任务系统的细粒度的运行过程及其对物理环境的实时响应.应用该方法分析了玉兔号月球车控制软件的一个早期版本,发现了系统运行中出现的一个特殊错误,识别了实际系统出现错误的条件,再现了出现错误的场景.     

Scheduling with timed automata

In this work, we present timed automata as a natural tool for posing and solving scheduling problems. We show how efficient shortest path algorithms for timed automata can find optimal schedules for the classical job-shop problem. We then extend these results to synthesize adaptive scheduling strategies for problems with uncertainty in task durations.