Timed Wp-method: testing real-time systems

Real-time systems interact with their environment using time constrained input/output signals. Examples of real-time systems include patient monitoring systems, air traffic control systems, and telecommunication systems. For such systems, a functional misbehavior or a deviation from the specified time constraints may have catastrophic consequences. Therefore, ensuring the correctness of real-time systems becomes necessary. Two different techniques are usually used to cope with the correctness of a software system prior to its deployment, namely, verification and testing. In this paper, we address the issue of testing real-time software systems specified as a timed input output automaton (TIOA). TIOA is a variant of timed automaton. We introduce the syntax and semantics of TIOA. We present the potential faults that can be encountered in a timed system implementation. We study these different faults based on TIOA model and look at their effects on the execution of the system using the region graph. We present a method for generating timed test cases. This method is based on a state characterization technique and consists of the following three steps: First, we sample the region graph using a suitable granularity, in order to construct a subautomaton easily testable, called grid automaton. Then, we transform the grid automaton into a nondeterministic timed finite state machine (NTFSM). Finally, we adapt the generalized Wp-method to generate timed test cases from NTFSM. We assess the fault coverage of our test cases generation method and prove its ability to detect all the possible faults. Throughout the paper, we use examples to illustrate the various concepts and techniques used in our approach.     

Timed verification of hierarchical communicating real-time state machines

Hierarchical Communicating Real-Time State Machines (H-CRSM) is a formal modelling language for the modular development of distributed real-time systems. The formalism is characterized by the use of state transitions with guarded commands and timing constraints, the adoption of a few distilled statecharts constructs, and the modular specification of timing constraints along a state hierarchy. This paper proposes a translation of H-CRSM into Uppaal which enables model checking. Translation rests on unfolding a hierarchical model on a flat representation. The resultant approach is demonstrated by means of a case study.     

Correctness verification and performance analysis of real-time systems using stochastic preemptive time Petri nets

Time Petri nets describe the state of a timed system through a marking and a set of clocks. If clocks take values in a dense domain, state space analysis must rely on equivalence classes. These support verification of logical sequencing and quantitative timing of events, but they are hard to be enriched with a stochastic characterization of nondeterminism necessary for performance and dependability evaluation. Casting clocks into a discrete domain overcomes the limitation, but raises a number of problems deriving from the intertwined effects of concurrency and timing. We present a discrete-time variant of time Petri nets, called stochastic preemptive time Petri nets, which provides a unified solution for the above problems through the adoption of a maximal step semantics in which the logical location evolves through the concurrent firing of transition sets. We propose an analysis technique, which integrates the enumeration of a succession relation among sets of timed states with the calculus of their probability distribution. This enables a joint approach to the evaluation of performance and dependability indexes as well as to the verification of sequencing and timeliness correctness. Expressive and analysis capabilities of the model are demonstrated with reference to a real-time digital control system.     

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

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

An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

The current literature of fixed-priority scheduling algorithms relies on sufficient tests to determine if a set of mixed-criticality sporadic tasks is schedulable on a single processor. The drawback of these safe tests is their pessimism, a matter that could be solved if an exact schedulability analysis is used. However, because of the non-deterministic behavior of tasks in the mentioned setups, exact quantification of worst-case response times, needed for the test, is a difficult problem; more precisely, such a quantification needs evaluation of enormous sequences of job executions. The core problem is thus to merge such sequences to make the analysis practical. This paper, for the first time, gives an algorithm for exact worst-case response time characterization of mixed-criticality sporadic real-time tasks executing according to a given fixed-priority scheduler. We use a set of techniques which carefully consider the task properties and their relation to the worst scenarios to prune the analysis state space. We also show an interesting result that if an exact schedulability test is used, the Audsley’s optimal priority assignment algorithm is not applicable to the mixed-criticality case. Accordingly, we need new priority assignment algorithms to work with the exact test; we give a simple task priority assignment algorithm to this aim. The performance of the proposed exact test (in terms of time complexity) is examined and the effectiveness of some heuristic priority assignment algorithms using the test (in terms of the ratio of task sets which are deemed schedulable) are compared.     

Techniques to increase the schedulable utilization of cache-based preemptive real-time systems

Nowadays, cache memories are applicable to real-time systems with the help of tools that obtain the worst-case execution time (WCET) of cached programs. However, these tools do not allow preemption, because from the point of view of program analysis, the number of preemptions is unknown. To face this problem, the cache-related preemption cost can be considered in the schedulability analysis, or annulled by the use of private cache partitions. This paper comprises a number of techniques using the first or both solutions. This paper also explores the harmonic relationships among tasks to improve the estimation of the cache interference in the analysis.     

Deterministic preemptive scheduling of real-time tasks

Algorithms for the preemptive scheduling of deterministic, real-time tasks can have applications in providing quality-of-service guarantees to packet flows in multichannel optical networks     

A new orthogonal series approach to state space analysis ofbilinear systems

In this note, a new orthogonal series approach to state space analysis of bilinear time-invariant systems is presented. The present approach involves only multiplications of matrices of small dimensions. Known techniques involve the solution of an algebraic system with a very large number of equations     

Commentary to: An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

Real-Time Systems - In this paper we point to some errors in recent paper by Asyaban et al. in which they devise an exact schedulability test. These errors are critical for the correct operation of...     

Convex invertible cones of state space systems

In the paper [CL1] the notion of a convex invertible cone,cic, of matrices was introduced and its geometry was studied. In that paper close connections were drawn between thiscic structure and the algebraic Lyapunov equation. In the present paper the same geometry is extended to triples of matrices andcics of minimal state space models are defined and explored. This structure is then used to study balancing, Hankel singular values, and simultaneous model order reduction for a set of systems. State spacecics are also examined in the context of the so-called matrix sign function algorithm commonly used to solve the algebraic Lyapunov and Riccati equations.     

Observable state space realizations for multivariable systems

This paper derives two canonical state space forms (i.e., the observer canonical form and the observability canonical form) from multiple-input multiple-output systems described by difference equations. The state space model is expressed by the first-order difference equation and is equivalent to the input–output representation. More specifically, by setting the different state variables, the difference equations or the input–output representations can be transformed into two observable canonical forms and the canonical state space model can be also transformed into the difference equations. Finally, two examples are given.     

Canonical state space representations for multivariable systems

The problem of state space representations for multiple-input, multiple-output linear time-invariant systems is considered. The known definitions of the first and second canonical forma for scalar systems are used to facilitate the derivation of explicit canonical expressions for multivariable systems.     

Structural state space sensitivity in linear systems

The concept of transformation independent noise is introduced to define a general class of structurally insensitive state space realizations of a given transfer function. A performance measure is minimized subject first to only an t₂-scaling constraint on the norm of each state node. This constraint normalizes the contribution of each state in the performance measure. Later additional constraints are imposed on the class of allowable state space structures. One constraint requires a covariance decoupled structure while another imposes a constraint on the Markov parameters of a partitioned substructure.     

Optimization of rule-based systems using state space graphs

Embedded rule-based expert systems must satisfy stringent timing constraints when applied to real-time environments. The paper describes a novel approach to reduce the response time of rule-based expert systems. The optimization method is based on a construction of the reduced cycle-free finite state space graph. In contrast with traditional state space graph derivation, the optimization algorithm starts from the final states (fixed points) and gradually expands the state space graph until all of the states with a reachable fixed point are found. The new and optimized system is then synthesized from the constructed state space graph. The authors present several algorithms implementing the optimization method. They vary in complexity as well as in the usage of concurrency and state-equivalency-both targeted toward minimizing the size of the optimized state space graph. Though depending on the algorithm used, optimized rule-based systems: (1) in general have better response time in that they require fewer rule firings to reach the fixed point; (2) are stable, i.e., have no cycles that would result in the instability of execution; and (3) have no redundant rules. They also address the issue of deterministic execution and propose optimization algorithms that generate the rule-bases with single corresponding fixed points for every initial state. The synthesis method also determines the tight response time bound of the new system and can identify unstable states in the original rule-base     

Static analysis of real-time distributed systems

A static analysis for reasoning about the temporal behaviors of programs in real-time distributed programming languages is proposed. The analysis is based on the action set semantics using the pure maximal parallelism model. It is shown how to specify and verify various timing properties of real-time programs. The approach provides only an approximate timing behavior, because the state information is ignored. However, many interesting properties such as parallel actions, deadlocks, livelocks, terminations, temporal errors, and failures, can be identified. Furthermore, the approach is compositional and thus makes it possible to reason about the timing properties incrementally. The method not only leads to efficient algorithms for the static analysis of CSP programs but also applies to many other languages     

A state space analysis of propose-and-revise

A central research topic in the area of knowledge engineering is the reuse of problem-solving methods for developing knowledge based systems. For being able to reuse a problem-solving method it is important to know under which restrictions a problem-solving method is appropriate to solve a given problem. This paper describes the problem-solving method propose-and-revise as well as the way this problem-solving method searches in its problem space for a solution. A quantitative analysis of the efficiency of this search process is given. Additionally, task and domain specific properties and restrictions and their influence on the efficiency of the search process are considered. For these purposes an instance of the problem-solving method is transformed to a corresponding instance of a Stanford Research Institute Problem Solver (STRIPS) planning system. Then the problem-solving method is considered as an additional control strategy for such a planning system. By this way the various insights and analysis results which are available in the area of planning systems may be exploited for the analysis of problem-solving methods. ©1999 John Wiley & Sons, Inc.     

Minimal state space search in parallel production systems

A methodology for transforming the original search space into an equivalent but minimal search space is proposed. First, the concept of dependences leads to a procedure for reduction of the search space. The search procedure using this method can produce a minimal and complete search space. It is shown that this method is applicable to parallel search as well. An added advantage of this method is that it does not exclude the use of heuristics. π-λ transformation is introduced to reduce the parallel search space     

Design space exploration for partially reconfigurable architectures in real-time systems

In this paper, we introduce FoRTReSS (Flow for Reconfigurable archiTectures in Real-time SystemS), a methodology for the generation of partially reconfigurable architectures with real-time constraints, enabling Design Space Exploration (DSE) at the early stages of the development. FoRTReSS can be completely integrated into existing partial reconfiguration flows to generate physical constraints describing the architecture in terms of reconfigurable regions that are used to floorplan the design, with key metrics such as partially reconfigurable area, real-time or external fragmentation. The flow is based upon our SystemC simulator for real-time systems that helps develop and validate scheduling algorithms with respect to application timing constraints and partial reconfiguration physical behaviour. We tested our approach with a video stream encryption/decryption application together with Error Correcting Code and showed that partial reconfiguration may lead to an area improvement up to 38% on some resources without compromising application performance, in a very small amount of time: less than 30 s.