Timing Constraints of Real-Time Systems: Constructs for Expressing Them, Methods of Validating Them

This paper examines timing constraints as features of realtime systems. It investigates the various constructs required in requirements languages to express timing constraints and considers how automatic test systems can validate systems that include timing constraints. Specifically, features needed in test languages to validate timing constraints are discussed. One of the distinguishing aspects of three tools developed at GTE Laboratories for real-time systems specification and testing is in their extensive ability to handle timing constraints. Thus, the paper highlights the timing constraint features of these tools.     

A UML package for specifying real-time objects

The Unified Modeling Language (UML) provides a robust set of tools for modeling software systems. However, these tools do not directly address the requirements of real-time systems. Many real-time systems require the specification of data that has strict timing constraints. This paper presents a UML package for specifying real-time objects called RT-Object. The constructs in the package are based on the objects of the Real-Time Semantic Objects Relationships And Constraints (RTSORAC) model. The RT-Object package has been used to design real-time objects in a Real-Time Multi-User Virtual Environment (RTMUVE), in which widely distributed users collaborate in time-critical planning and decision making.     

A Process Algebraic Approach to the Schedulability Analysis of Real-Time Systems

To engineer reliable real-time systems, it is desirable to detect timing anomalies early in the development process. However, there is little work addressing the problem of accurately predicting timing properties of real-time systems before implementations are developed. This paper describes an approach to the specification and schedulability analysis of real-time systems based on the timed process algebra ACSR-VP, which is an extension of ACSR with value-passing communication and dynamic priorities. Combined with the existing features of ACSR for representing time, synchronization and resource requirements, ACSR-VP is capable of specifying a variety of real-time systems with different scheduling disciplines in a modular fashion. Moreover, we can use VERSA, a toolkit we have developed for ACSR, to perform schedulability analysis on real-time systems specified in ACSR-VP automatically by checking for a certain bisimulation relation.     

A tool for analyzing and fine tuning the real-time properties of an embedded system

This paper describes a computer-aided software engineering (CASE) tool that helps designers analyze and fine-tune the timing properties of their embedded real-time software. Existing CASE tools focus on the software specification and design of embedded systems. However, they provide little, if any, support after the software has been implemented. Even if the developer used a CASE tool to design the system, their system most likely does not meet the specifications on the first try. This paper includes guidelines for implementing analyzable code, profiling a real-time system, filtering and extracting measured data, analyzing the data, and interactively predicting the effect of changes to the real-time system. The tool is a necessary first step towards automating the debugging and fine tuning of an embedded system's temporal properties.     

TCBV:一种构件时序行为建模与相容性验证工具

利用形式化方法对复杂实时构件系统的时序行为进行建模与验证对于提高安全攸关实时构件系统的正确性、可靠性与安全性具有重要意义。介绍了基于时间行为协议的构件时序行为的形式化建模和相容性验证方法,给出了时间行为协议建模与相容性验证工具TCBV的系统架构与功能模块。TCBV应用方便,能够实现实时构件时序行为模型的图形化表示,并可对复杂交互行为的相容性进行自动验证。结合应用实例,介绍了如何利用TCBV对复杂实时构件系统的时序行为进行建模和验证。最后,将TCBV与其它相关工具进行了比较。     

分布式实时系统UECnet的描述工具──配置说明语言UECspec

大型、复杂的分布式实时系统除了有严格的时间要求外，还需要有更大的灵活性、可预测性和可靠性．本文提出一个分布式实时系统的描述工具─—配置说明语言ＵＥＣｓｐｅｃ，用来描述分布式实时系统ＵＥＣｎｅｔ应用层的逻辑同结构、进程间的通信链接关系．以及各进程的实时特性．ＵＥＣｎｅｔ系统根据ＵＥＣｓｐｅｃ描述自动完成对应用系统的配置分析，初始分配及重配置．     

Requirements specification of real-time systems: temporal parameters and timing-constraints

The development of high-quality real-time systems depends on their correct requirements specification, which includes the analysis and specification of timing issues. This paper focuses on requirements specification of real-time systems, presenting a set of temporal parameters and timing-constraints related to the execution of systems processes. Timing-constraints are expressed by formulas, being useful for defining, representing, and validating the system temporal behavior, particularly in hard real-time systems specifications. The primary contribution over previous studies is the proposal of a more generic and complete set of timing-constraints, applied to the area of requirements engineering for real-time systems, which has not been sufficiently explored.     

Timed Property Sequence Chart

Property Sequence Chart (PSC) is a novel scenario-based notation, which has been recently proposed to represent temporal properties of concurrent systems. This language balances expressive power and simplicity of use. However, the current version of PSC just represents the order of events and lacks the ability to express timing properties. In real-time systems, it is well known that these timing requirements are very important and need to be specified clearly. Thus, in this paper, we define timed PSC (TPSC) and give the semantics of TPSC in terms of Timed Büchi Automaton (TBA). Then, we measure the expressive power of TPSC based on the recently proposed real-time specification patterns. Finally, we illustrate the use of TPSC in the context of a web service application which requires timing requirements.     

Hardware/software codesign and rapid prototyping of embeddedsystems

The complexity and the short time to market of embedded systems require the use of automated techniques during the specification, implementation, and testing phases of such systems. Due to the cost requirements and the timing constraints of such systems, application-specific hardware solutions are often needed, making the codesign of hardware and software a major topic for the design automation of embedded systems. This article describes tools for the analysis, synthesis, and rapid prototyping of distributed embedded real-time systems and presents a complete design flow from specification to implementation     

The design and analysis of real-time systems using the ASTRAL software development environment

ASTRAL is a formal specification language for real-time systems. It is intended to support formal software development and, therefore, has been formally defined. The structuring mechanisms in ASTRAL allow one to build modularized specifications of complex systems with layering. A real-time system is modeled by a collection of state machine specifications and a single global specification. This paper discusses the ASTRAL Software Development Environment (SDE), which is an integrated set of design and analysis tools based on the ASTRAL formal framework. The tools that make up the support environment are a syntax-directed editor, a specification processor, a verification condition generator, a browser kit, a model checker, and a mechanical theorem prover. This revised version was published online in June 2006 with corrections to the Cover Date.     

Modechart: a specification language for real-time systems

Present a specification language for real-time systems called Modechart. The semantics of Modechart is given in terms of real-time logic (RTL), which is especially amenable to reasoning about the absolute (real-time clock) timing of events. The semantics of Modechart has an important property that the translation of a Modechart specification into RTL formulas results in a hierarchical organization of the resulting RTL assertions. This gives us significant leverage in reasoning about properties of a system by allowing us to filter out assertions that concern lower levels of abstraction. Some results about desirable properties of Modechart specifications are given. A graphical implementation of Modechart has been completed     

基于对象分布式实时系统约束的一致性研究

在分布式实时系统中,时间约束规格的一致性是解决任务分配和调度等关键问题的必要前提。该文给出了一种基于对象分布式实时系统调度的通用模型,并对该模型进行了形式化描述。该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时约束的不足,允许从方法和活动上描述所需的约束,降低了单一约束描述的繁杂程度。为了解决使用该模型进行约束规格的一致性问题,该文给出了绝对时间约束、相对时间约束、一致性约束以及相对时间约束和一致性约束之间的一致性判定的必要条件。     

Specification and analysis of timing requirements for real-time systems in the CBD approach

In real-time software, not only computation errors but also timing errors can cause system failures, which eventually result in significant physical damages or threats to human life. To efficiently guarantee the timely execution of expected functions, it is necessary to clearly specify and formally verify timing requirements before performing detailed system design. With the expected benefit of reusability and extensibility, component technology has been gradually applied to developing industrial applications including real-time systems. However, most of component-based approaches applied to real-time systems lack in a systematic and rigorous approach to specifying and verifying timing requirements at an earlier development stage. This paper proposes a component-based approach to specifying and verifying timing requirements for real-time systems in a systematic and compositional manner. We first describe behaviors of the constituent components including timing requirements in UML diagrams, and then translate the UML diagrams into MTER nets, an extension of TER nets, to perform timing analysis in a compositional way. The merit of the proposed approach is that the specification and analysis results can be reused and independently maintained.     

Temporal Proof Methodologies for Timed Transition-Systems

We extend the specification language of temporal logic, the corresponding verification framework, and the underlying computational model to deal with real-;time properties of reactive systems. The abstract notion of timed transition systems generalizes traditional transition systems conservatively: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound timing constraints on transitions. This framework can model real-time systems that communicate either through shared variables or by message passing and real-time issues such as timeouts, process priorities (interrupts), and process scheduling. We exhibit two styles for the specification of real-time systems. While the first approach uses time-bounded versions of the temporal operators, the second approach allows explicit references to time through a special clock variable. Corresponding to the two styles of specification, we present and compare two different proof methodologies for the verification of timing requirements that are expressed in these styles. For the bounded-operator style, we provide a set of proof rules for establishing bounded-invariance and bounded-responce properties of timed transition systems. This approach generalizes the standard temporal proof rules for verifying invariance and response properties conservatively. For the explicit-clock style, we exploit the observation that every time-bounded property is a safety property and use the standard temporal proof rules for establishing safety properties.     

A formal framework for modeling and validating Simulink diagrams

Simulink has been widely used in industry to model and simulate embedded systems. With the increasing usage of embedded systems in real-time safety-critical situations, Simulink becomes deficient to analyze (timing) requirements with high-level assurance. In this article, we apply Timed Interval Calculus (TIC), a real-time specification language, to complement Simulink with TIC formal verification capability. We elaborately construct TIC library functions to model Simulink library blocks which are used to compose Simulink diagrams. Next, Simulink diagrams are automatically transformed into TIC models which preserve functional and timing aspects. Important requirements such as timing bounded liveness can be precisely specified in TIC for whole diagrams or some components. Lastly, validation of TIC models can be rigorously conducted with a high degree of automation using a generic theorem prover. Our framework can enlarge the design space by representing environment properties to open systems, and handle complex diagrams as the analysis of continuous and discrete behavior is supported.     

Analyzing partially-implemented real-time systems

Most analysis methods for real-time systems assume that all the components of the system are at roughly the same stage of development and can be expressed in a single notation, such as a specification or programming language. There are, however, many situations in which developers would benefit from tools that could analyze partially-implemented systems: those for which some components are given only as high-level specifications while others are fully implemented in a programming language. In this paper, we propose a method for analyzing such partially-implemented real-time systems. We consider real-time concurrent systems for which some components are implemented in Ada and some are partially specified using regular expressions and graphical interval logic (GIL), a real-time temporal logic. We show how to construct models of the partially-implemented systems that account for such properties as run-time overhead and scheduling of processes, yet support tractable analysis of nontrivial programs. The approach can be fully automated, and we illustrate it by analyzing a small example     

Timing analysis and validation with UML: the case of the embedded MARS bus manager

This paper presents a case study in UML-based modeling and validation of the intricate timing aspects arising in a small but complex component of the airborne Medium-Altitude Reconnaissance System produced by the Netherlands National Aerospace Laboratory. The purpose is to show how automata-based timing analysis and verification tools can be used by field engineers for solving isolated hard points in a complex real-time design, even if the press-button verification of entire systems remains a remote goal. We claim that the accessibility of such tools is largely improved by the use of an UML profile with intuitive features for modeling timing and related properties. This work has been partially funded by the European OMEGA project (IST-2001-33522). Iulian Ober and Ileana Ober: performed work while at VERIMAG, Grenoble, France. Y. Yushtein: at the moment of writing in National Aerospace Laboratory NLR.     

基于DTPN的时间Petri网的组件级化简规则

时间Petrl网(TPNs)是实时系统时间特性常用的描述和验证的Petri网模型.组件级化简方法是TPN模型常用的分析方法,在保持外部可观察时间特性的前提下,将组件TPN模型化简成一个很简单的TPN模型.然而它却失去了组件内部的性质,如冲突和并发等性质.文中引人延迟时间Petri网(DTPN),通过组件TPN模型向DTPN模型转化,使化简后模型既保持外部可观察时间特性,又保持组件内部的冲突和并发等性质.为了分析化简后的DTPN模型,文中还提出了一种新的DT-PN调度分析方法.最后通过对一个C2系统的组件TPN模型的分析实例,验证该方法的有效性.     

Combining static worst-case timing analysis and program proof

This paper describes SPATS—a new toolset for the development of safety-critical and hard real-time systems. SPATS integrates the analysis traditionally offered by program proof and static timing analysis tools through analysis of program basic-path graphs. This paper concentrates on SPATS' facilities for high-level static timing analysis and analysis of worst-case stack usage. The integration of timing analysis and program proof allows timing analysis to be performed where worst-case execution time (WCET) depends on a program's input data, and allows timing annotations to be formally verified. The approach is developed and illustrated with a worked example. The implementation and experimental application of SPATS to realistic industrial case-studies are also described. We conclude that SPATS offers a novel new approach to static timing analysis, offers several new analyses not seen in previous systems, and can be implemented in a useful and efficient toolset.This work was completed while Rod Chapman was with the Dependable Computing Systems Centre at the University of York.