分布式实时嵌入式系统的能耗建模与分析

为支持分布式实时嵌入式(DRE)系统的能耗分析,提出了一种能耗时延Petri网(ECTPN)对系统的模块、任务、任务间关系、通信协议等进行建模。基于所建DRE的ECTPN模型,分析系统的可调度性和能耗约束,并给出启发式算法来计算满足时间约束和能耗约束的可行调度。最后应用一个实例模拟系统的建模和分析过程,从而直观地展示了该方法的可行性。     

基于RT-UML模型的实时系统可调度性分析

简要回顾实时系统的开发现状,对实时系统可调度性相关理论进行探讨.提出一种基于实时统一建模语言对实时系统可调度性进行分析的方法.通过将系统RT-UML模型中实时任务的相关数量信息提取出来,在相应分析工具中进行可调度性分析,分析结果自动反馈到模型中去,实现了对实时系统可调度性进行系统实现前的离线分析.     

支持缓存划分的全局EDF实时系统调度策略

由于多核处理器争用共享缓存导致的不确定性为实时系统带来极大的挑战.为解决这个问题,现代处理器引入了缓存划分技术,通过隔离处理器核对缓存的访问从而提高了时间可预测性.但是,这种隔离技术可能导致实时任务因缓存分区的数量不足而被阻塞,而传统的实时调度算法与分析方法无法有效应对这种情况.因此,提出了支持缓存划分的可抢占全局最早截止期优先(EDF)实时调度算法gEDFca,并结合最新的缓存敏感调度理论针对这种调度算法进行了可调度性分析,提出了一种基于线性规划的可调度性判定条件.还提出了一种具有线性时间复杂度的优化算法,进一步提高了分析方法的性能.随机生成任务的仿真实验表明,提出的可调度性判定方法具有较高的效率.同时,优化算法提高了算法可调度性.     

基于RMA的雷达数据处理任务可调度性判定

实时系统中任务的可调度性是系统正确的关键.单调速率调度算法RMA是任务调度的重要算法,通过对雷达数据处理任务的时间需求模型的分析,使用RMA对该任务进行了可调度性判定.在分析任务两种不同的实现方法及相应时间开销的基础上,给出了这两种实现方法在RMA下可调度性判定的充分必要条件.     

考虑缓存预热时间的多核调度系统验证

随着多核架构在实时系统中的应用,多核实时调度已成为研究热点.在多核全局调度中,任务在多核间迁移通常会引起缓存预热.在严格实时调度中,这部分时间可能导致任务错过截止时间.为此基于调度理论的测试方法比较悲观,在作可调度性判定时,引入模型检测.考虑缓存预热时间的抽象模型仅局限在双核,提出一种建模方法,能够在更多核的条件下,验证调度系统的正确性和可调度性.     

基于AADL的汽车防滑控制系统可调度性分析

针对设计阶段难以对汽车防滑控制系统进行可调度性分析的问题,利用AADL为该系统建模.根据实时系统中任务调度与线程、计算时间、处理器性能之间的关系,在任务数不变的情况下选取不同性能的处理器,通过OSATE对该系统模型进行分析.结果表明此方法可有效解决这一问题,该建模方法为系统的可调度性分析和优化设计提供了一条新的途径.     

An Efficient Real-Time Fault-Tolerant Scheduling Algorithm Based on Multiprocessor Systems

In the context of real-time fault-tolerant scheduling in multiprocessor systems, Primary-backup scheme plays an important role. A backup copy is always preferred to be executed as passive backup copy whenever possible because it can take the advantages of backup copy de-allocation technique and overloading technique to improve schedulability. In this paper, we propose a novel efficient fault-tolerant ratemonotonic best-fit algorithm efficient fault-tolerant rate-monotonic best-fit （ERMBF） based on multiprocessors systems to enhance the schedulability. Unlike existing scheduling algorithms that start scheduling tasks with only one processor. ERMBF pre-allocates a certain amount of processors before starting scheduling tasks, which enlarge the searching spaces for tasks. Besides, when a new processor is allocated, we reassign the task copies that have already been assigned to the existing processors in order to find a superior tasks assignment configuration. These two strategies are all aiming at making as many backup copies as possible to be executed as passive status. As a result, ERMBF can use fewer processors to schedule a set of tasks without losing real-time and fault-tolerant capabilities of the system. Simulation results reveal that ERMBF significantly improves the schedulability over existing, comparable algorithms in literature.     

面向动态演化的复杂网构软件系统可靠性分析方法

 网构软件是Internet上各种软件实体以各种协同方式实现跨网络的互连、互通和协作的软件系统，动态演化是其基本特征，演化过程中会导致软件系统失效，面向动态演化的网构软件可靠性分析成为新的技术难题。首先分析构件接口交互之间的协议关系和网构软件动态演化错误传播可达性，提出通过错误传播可达图来界定构件动态演化错误的影响范围，并建立错误传播可达图生成过程模型；其次，为有效解决Markov状态空间“爆炸”的问题，利用错误传播可达图来生成Markov状态转移图，提出基于Markov的网构软件动态演化可靠性分析方法；最后通过案例分析来验证该方法的有效性。     

离散线性随机系统输入—输出关系的数学描述

研究离散线性随机系统输入-输出间的关系,证明了任何线性随机系统输出方差与其输入无关.因此在任何意义下由方差极小化而得最优控制是不可能的,且已证明,输出与其集点间的期望差依赖于控制信号的选择,得到了最小偏差控制器,考虑了与线性随机系统输入-输出关系有关的所谓完全i-步输出可达性这一重要概念,并给出了以输入-输出随机差分方程所描述的多变量随机系统的完全i-步输出可达性的充要条件,并可由此得到输出可达性的简易检验方法.     

一种无线网络控制系统概率性任务实时调度算法

传统无线网络控制系统中概率性任务调度算法存在效率低下、延迟时间长的问题．利用概率模型来解决时间和优先级问题,并提出了一种高效的任务调度算法,即通过判断队列的可调度性,提高调度的成功率．仿真实验表明,该算法适用于实时系统调度问题,且较已有的传统算法在性能上有一定的提高．     

Reduction Method for Reachability Analysis of Petri Nets

Reachability analysis is an important approach for acquiring Petri net (PN) properties. The reachability tree and the solution of the state equation are two commonly used methods for reachability analysis, but they can result in state explosion and spurious solutions in some cases. As a significant complementary method, the PN reduction technique simplifies the reachability analysis by reducing the net size while preserving the reachability. This paper introduces several useful reduction rules and defines a reduction process for the analysis of reachability which is easy to understand and implement. Some examples are given to explain the method to solve the reachability problem. The analysis shows that the proposed reduction method preserves the visualization feature of PN and can be easily used.     

一种基于时间片的抢占控制模型

针对实时系统中任务调度问题,提出了一种基于时间片的抢占控制模型.该模型以抢占次数上限为特征参数,在满足任务集可调度的前提下,由该特征参数计算出任务时间片并按片内不可抢占的限制条件优化任务抢占次数.采用遗传算法对该抢占控制模型进行了离线实现,同时使用惩罚函数来保证整个任务集的可调度性.通过仿真实验,验证了该模型的有效性.     

基于时间Petri网和启发式搜索的柔性制造系统调度算法

利用库所延迟Petri网对柔性制造系统进行建模,在Petri网激发变迁生成的可达树中进行启发式搜索,求解最小完成时间调度策略,并改进了现有计算机器剩余时间的启发式函数,对剩余加工操作进行准确分类,以保证算法的最优性.为了提高算法的求解效率,改进后的启发式函数考虑了未产成操作的剩余时间,以使预测值更加准确并减少了计算量.同时,利用实验验证了所提出方法的正确性和有效性.     

Buck变换器混杂动态系统的能控性和能达性

尝试在Buck变换器的能控性和能达性研究中引入混杂动态系统和切换线性系统的概念．首先建立Buck变换器的切换线性系统模型;然后根据该模型的特点,给出系统矩阵定常、输入矩阵切换的切换线性系统的能控性和能达性定义和定理,并严格证明了Buck变换器的能控性和能达性;最后讨论了能控性和能达性与输出能控性的关系,指出能控性、能达性和输出能控性是一致的,同时对Buck变换器的能控性进行实验验证,结果表明,在负载阶跃变化的情况下,变换器的输出完全可以控制并且稳定在设计值,这和Buck变换器作为切换线性系统模型的能控性分析结果是一致的．本文的研究方法也可用于其他功率变换器的能控性和能达性的研究．     

一种支持实时软件时间建模的形式化方法

随着实时系统非功能性质研究的深入,为了分析软件对系统执行时间的影响并对其进行定量分析,提出了一种支持实时软件时间建模的形式化方法。通过扩展时间通信顺序进程的时间语义,将实时系统指令执行的时间映射成为时间通信顺序进程的时间,利用时间通信顺序进程对实时软件时间建模并进行量化分析。提出的时间最优调度算法可以判断时间通信顺序进程的可达性并计算时间最优路径。通过实例验证表明,该方法可以从很大程度上提高实时系统执行时间计算的准确性,计算结果有助于实时系统执行时间的量化分析与优化设计。     

嵌入式实时系统中抢占控制策略及其优化

任务的抢占在保证了系统可调度性的同时,也带来了必然的抢占开销.而对于资源受限的嵌入式实时系统来说,控制任务的抢占次数,降低抢占引起的资源消耗具有重要的意义.提出了一种基于时间片的抢占控制模型,为每个任务分配一个可抢占次数的上限.由于抢占控制会对系统的可调度性造成影响,因此通过遗传算法对任务的抢占次数上限进行优化,使其在满足任务可调度的前提下取值最小.通过仿真实验,分析了优化算法的性能,并从对任务调度的统计结果中可以看出,采用本文提出的抢占控制策略可以有效地减少任务执行中的抢占次数.     

多速率混合系统的符号化可达性分析

针对目前还没有专门的数据结构处理多速率混合系统的符号化可达性问题，定义了多速率区域来表示和处理多速率自动机的无穷状态空间，从而把多速率混合系统的符号化可达性分析等价地转化成多速率区域上的3种操作，即并操作、变量重赋值操作和控制状态上的时间流逝操作．从理论上证明了多速率区域在这3种操作上的封闭性，同时定义了矩阵数据结构不同上限矩阵（DCM），并用其存储多速率区域，这样就得到了一种专门处理多速率混合系统符号化可达性分析的数据结构．理论上证得，DCM可以大大降低可达性分析算法的复杂度．     

有限网格上一类二维系统的线段能达性和能控性

T.Kaczorek等研究了定义在两条射线组成的区域内通常边界条件下一般奇异模型(GSM)的局部能达性和能控性.本文讨论了有限网格上二维GSM，它是图象处理和工程应用中的另一类边界问题．利用Z变换，我们得到一个定义在矩形区域上的模型的状态响应公式，与有线网格上系统的非因果关系一致，进而定义和研究了线段的能达性和能控性，推广了[1，2]关于局部的直线段能达性和能控性的结果．本研究扩大了二维系统模型边界条件类型的应用范围．     

基于G-EDF的DAG并行任务多核响应时间分析

由于未考虑DAG(directed acyclic graph)任务的自身结构, 基于G-EDF(global earliest deadline first)的DAG并行任务模型的可调度性分析存在很大的悲观性,因此本文针对DAG任务集在多处理器系统中采用G-EDF调度策略下的响应时间分析进行了研究.首先针对carry-in任务实例执行的情况提出更加精确的carry-in工作量估算方法.基于该carry-in工作量估算方法提出一种基于完成时间的问题窗口工作量估算方法.最后,结合上述两个改进策略提出了基于G-EDF的DAG任务响应时间分析方法.仿真实验表明,所提出的方法较目前已知的调度策略方法可调度性至少提高15%,最高可达25%.     

多变量变结构控制系统的几何法设计

本文基于控制系统状态空间的几何分析方法,提出了用于一类多变量变结构系统的滑模控制方案.文中分析和讨论了任意配置开关矩阵C的可能性以及多变量变结构控制系统的滑模存在性和可达性,同时也给出了非全状态反馈系统的滑模控制条件.文中所列的算例表明了该滑模控制方案的有效性.