基于PRET的编程模型

时间可预测性在信息物理系统设计领域正变得越来越重要,目前时间可预测性系统的设计分为编程模型和体系结构两个层次,编程模型的研究往往是基于传统RTOS而提出新的时间模型,体系结构层则是现有体系结构,设计的具有时间属性的指令集、流水线等等.基于时间可预测体系结构PRET和可预测时间模型LET的研究,提出将PRET和LET模型相结合的编程模型,并通过分析和实验证明了这种设计的可行性和优势,进一步证明了时间在系统设计中的重要性.     

服务体执行流模型中消息通信的时间可预测性分析

Minicore是基于服务体执行流模型的新型微内核,它有效的将操作系统中的存储模型和运行模型相分离.微内核的高度模块化的设计使Minicore对服务体(Minicore的基本单元)间的消息通信的依赖度极高.于是对于Minicore操作系统的时间可预测性分析也无可避免的依赖于通信模块的时间可预测性.本文的工作即是通过计算Minicore通信模块的WCET,分析消息通信的时间可预测性,为未来实现时间可预测的通信机制并分析Minicore的时间可预测性提供基础.对通信模块的WCET分析计算采用静态WCET分析中的基于路径的算法,应用到Minicore系统的通信模块,包括四个阶段:提取目标代码片段,程序控制流分析,处理器特征分析和WCET计算.基于WCET计算结果本文定义配置相关的时间可预测性(CIPr)作为评估消息通信时间可预测性的指标.     

Timed SEFM:面向嵌入式实时控制系统的编程模型

实时任务的功能和其完成时间共同影响嵌入式控制系统的物理行为。传统的进程/线程模型缺乏时间语义,时间属性只能用优先级间接表达,任务的实际完成时间不具有确定性。Henzinger提出的LET(Logical Execution Time)编程模型用协作式的时间触发语义明确描述时间需求,但其所基于的操作系统仍沿用进程/线程模型,仍会引入时间不确定性。结合服务体/执行流模型SEFM(Servant/Exe-Flow Model)和LET模型,定义了一种时间确定的编程模型Timed SEFM,用改进的SEFM模型描述系统的功能行为,用LET描述系统的时间行为。把智能小车控制系统的实现作为研究实例。     

LET模型的时间语义编程语言

嵌入式实时系统的正确性不仅取决于计算结果的正确性,更取决于产生结果时间的正确性.然而软件不确定的并发执行带来系统时间行为不可预测问题,使得验证复杂度升高,成本增加,为此实时系统领域提出了许多实时编程语言来提高系统的时间可预测性.LET(logical execution time)模型结合了同步模型ZET(zero e...     

面向逻辑执行时间模型的Minicore的内存管理

随着实时系统在时间关键和安全关键的行业的广泛应用,程序的时间属性受到越来越广泛的关注. Henzinger提出了LET(Logical Execution Time)编程模型,提供了明确描述时间属性的机制,确保了系统的时间确定性.但传统的实时操作系统模型采用了与LET截然不同的抽象,难以很好地支持LET编程模型. Minicore是一种新型操作系统模型,程序由一组内部没有同步点的服务组成,具有较好的时间确定性和可控性,与LET编程模型的思想更吻合.将LET的控制模型和Minicore的运行模型相结合,可形成一种具有时间确定性的新型编程框架.主要描述了该框架的内存管理机制的设计和实现.文末以智能小车控制系统的实现作为研究实例验证本系统的可行性.     

嵌入式操作系统混合任务调度技术与策略研究

针对当前嵌入式系统中时间触发与事件触发混合任务的特点,以μC/OS-II操作系统架构为基础,设计了一种能够同时支持时间触发与事件触发的混合操作系统内核架构。该架构符合OSEK/VDX标准,具有良好的可移植性。针对混合任务调度问题,提出了一种静态周期性可抢占式混合任务调度策略,该策略同时支持中断级与任务级的任务切换,并采用EDF（最早截止时间优先）算法对被抢占的时间触发任务进行恢复,相比OSEKtime OS只能在中断级进行任务切换以及FIFO（先进先出）恢复算法,能够提高系统资源利用率,并最大限度保证任务实时性。实验分析结果表明,所设计的混合操作系统架构移植方便,所提出的混合任务调度策略可行有效,调度过程具有良好的可预测性。     

一种支持可重构混成系统的操作系统设计与实现

可重构硬件和指令集处理器构成的混成系统兼有运算速度高和编程灵活的优点,是近年来学术界研究的热点.已有的面向该类系统的操作系统由于受到传统抽象模型的制约,不能充分发挥可重构硬件的优势.文中在分析该类系统对操作系统的需求和已有运行模型缺陷的基础上,提出了一种基于服务体/执行流模型的操作系统SEF-OSHRS.它具有统一的系统对象抽象和通信接口,并可支持控制流的直接转换,因而能充分发挥混成系统的优势.文中详细介绍了该操作系统的基本抽象、系统结构和运行方式,并通过实验结果说明了该系统的可用性和高效性.     

信息物理系统中组件的时间行为可组合研究综述

组件的可组合性是组件化软件开发方法中的关键核心问题,尤其在针对具有安全关键属性的信息物理系统(Cyber Physical Systems, CPS)的开发过程中,如何建模、分析及验证系统中组件在时间行为上的可组合性,已成为保证系统正确性、安全性的的关键.本文首先介绍了传统组件化软件开发的基本思想,包括组件定义、组件的组合操作,以及组件可组合性的形式化定义等内容.进一步的,重点阐述在具有安全关键的信息物理系统中组件时间行为建模与分析的主要研究进展,对时间行为可组合的形式化定义进行归纳,讨论几种典型的系统组件模型,并分析了3种可以提升组件时间行为可组合性、可预测性的编程范式.最后,探讨了组件在时间行为可组合问题上存在的挑战,并对未来发展方向做出了展望.     

多粒度时间部分周期模型

时间的描述和划分是时态数据采掘中一个非常重要的方面,针对目前时态数据采掘中缺少对多粒度时间等的研究的现状,提出了多粒度时间,粒度转换,时态序等的严格数学定义,并研究和证明了它们的相关性质.以此为基础引出了一个多粒度时间部分周期模型,对模型的支持度和置信度等性质进行了详细讨论,并将多粒度时间下的部分周期模型运用到股票数据实验中,实验表明所提出的模型对于研究时态数据采掘具有重要意义.     

宏观交通运输系统的复杂度与可预测性

宏观交通运输系统复杂度与可预测性的关系需要定量描述。为测度宏观交通运输系统的复杂性,引入符号动力学的Lempel-Ziv算法。针对该算法的应用误区,提出改进的“通用试凑算法”。应用ARIMA模型,对宏观交通量时间序列进行模型估计和预测。计算5个实测时间序列的复杂度和预测误差,通过其结果比较,推论出一个假设:宏观交通运输系统的复杂度与可预测性存在负相关关系。     

Relative predictability of failure event occurrences and its opacity-based test algorithm

In this paper, the problem of relative predictability of failure event occurrences is investigated. The notion of relative predictability is proposed for logical automata and the concept of predictable rate is introduced to characterise the predictability property of a discrete-event system, which takes values in the interval [0, 1]. Intuitively, a discrete-event system being relatively predictable means that there exist some failure events which can be predicted from the observations of the system. The relationship between relative predictability and predictability introduced by Sahika Genc et al. analysed and the analysis shows that relative predictability is weaker than predictability for discrete-event systems. Furthermore, a necessary and sufficient condition for relative predictability is presented. In particular, an opacity-based algorithm is developed to test the relative predictability, which is polynomial in the number of states of the system. Also, some examples are provided to illustrate the presented results.     

多处理器系统实时调度的可预测性

在多处理器实时系统中,由于调度的不规则性,系统的可预测性判定问题尤为重要。针对多处理器系统中实时任务调度的可预测性问题,给出了不可预测的实时任务集反例,证明了一种可预测的实时任务集合。对于多处理器实时系统中常用的最早截止期零松弛调度算法(earliest deadline zero laxity,EDZL)的可预测性,利用EDZL算法的基本性质,用一种简捷的方法证明了EDZL算法是可预测的。通过仿真系统验证了证明的正确性,该方法可用于多处理器及分布式实时系统的设计和验证。     

Graph-based predictable feature analysis

We propose graph-based predictable feature analysis (GPFA), a new method for unsupervised learning of predictable features from high-dimensional time series, where high predictability is understood very generically as low variance in the distribution of the next data point given the previous ones. We show how this measure of predictability can be understood in terms of graph embedding as well as how it relates to the information-theoretic measure of predictive information in special cases. We confirm the effectiveness of GPFA on different datasets, comparing it to three existing algorithms with similar objectives—namely slow feature analysis, forecastable component analysis, and predictable feature analysis—to which GPFA shows very competitive results.     

Definitions of predictability for Cyber Physical Systems

With the recent proliferation of different types of Cyber Physical Systems (CPS), it is critically important to investigate the predictability of such systems. Along with functional correctness of the components, these systems must also ensure that timing and delay constraints of components are properly for the entire system to behave in a predictable manner in presence of various kinds of uncertainties. While the functional correctness of the CPS components has been investigated in the past, very little is available about the timing issues. The objective of this paper is to conduct an investigation of key issues involved to ensure the predictability of the system, introduce rigorous definitions of performance parameters, and propose metrics for their evaluation and analyze their suitability to be used in the presence of uncertainties in which CPS operate. The results are expected to provide greater insight into the time critical behavior of CPS components.     

What is predictability for real-time systems?

Conclusion In summary, predictability in real-time systems has been defined in many ways. For static real-time systems we can predict the overall system performance over large time frames (even over the life of the system) as well as predict the performance of individual tasks. If the prediction is that 100% of all tasks over the entire life of the system will meet their deadlines, then the system is predictable without resorting to any stochastic evaluation. In dynamic real-time systems we must resort to a stochastic evaluation for part of the performance evaluation. Predictability for these systems should mean that we are able to satisfy the timing requirements of critical tasks with 100% guarantee over the life of the system, be able to assess overall system performance over various time frames (a stochastic evaluation), and be able to assess individual task and task group performance at different times and as a function of the current system state. If all these assessments meet the timing requirements, then the system is predictable with respect to its timing requirements.This work was supported by ONR under contract N00014-85-K-0389 and NSF under grants DCR-8500332 and IRI-8908693.     

Scheduling component replacement for timely execution in dynamic systems

Timely run‐time software replacement techniques are a corner stone for reconciling real‐time systems development and dynamic behavior. Typical real‐time systems do not consider dynamic behavior because it deeply challenges predictability and timeliness. Current efforts are starting to merge the safe and predictable execution with a controllable level of dynamicity by imposing a set of bounds and limitations to the system dynamic behavior. One of the obstacles for this is how to time‐bound the different operations required to effectively implement component replacement. In this paper, the main challenges for this problem are identified, and a model to ensure that components can be replaced at run time preserving the temporal properties of the system is provided that also avoids failures in replacements. A real example and simulations of our replacement model are provided that validate the presented ideas. Copyright © 2013 John Wiley & Sons, Ltd.     

实时对象模型及其可预测调度研究

从实时系统建模的角度,文中给出了一种实时对象模型,该模型能够保证开发的实时系统具有可预测性,灵活性,集成性的特点,文中同时给出了分析对象能力的计算公式,并对实时对象模型行为的可预测性调度进行了讨论。     

Surrogate measures to optimize structures for robust and predictable progressive failure

Optimizing complex structures for robust and predictable progressive failure using probabilistic approaches is computationally expensive. In this paper we investigate the progressive failure characteristics of structures subjected to random variability and deduce patterns to identify surrogate measures that correlate with robustness and predictability of the design’s progressive failure. The procedure is demonstrated for the optimization of robustness and predictability in progressive failure of truss structures. Deterministic optimization of trusses was used to generate candidate designs to compare and contrast robustness and predictability. The stochastic analyses of the candidate designs are then used to identify surrogate features that correlate to robustness and predictability of progressive failure response. These features are converted to numerical surrogate objectives or constraints and used in optimization to demonstrate their effectiveness and computational efficiency. The example shows that surrogate measures can be developed for robustness and predictability optimization, and that such measures are computationally efficient compared to robustness optimization using sampling based methods.