Automatic synthesis and verification of real-time embedded software for mobile and ubiquitous systems

Currently available application frameworks that target the automatic design of real-time embedded software are poor in integrating functional and non-functional requirements for mobile and ubiquitous systems. In this work, we present the internal architecture and design flow of a newly proposed framework called Verifiable Embedded Real-Time Application Framework (VERTAF), which integrates three techniques namely software component-based reuse, formal synthesis, and formal verification. Component reuse is based on a formal unified modeling language (UML) real-time embedded object model. Formal synthesis employs quasi-static and quasi-dynamic scheduling with multi-layer portable efficient code generation, which can output either real-time operating systems (RTOS)-specific application code or automatically generated real-time executive with application code. Formal verification integrates a model checker kernel from state graph manipulators (SGM), by adapting it for embedded software. The proposed architecture for VERTAF is component-based which allows plug-and-play for the scheduler and the verifier. The architecture is also easily extensible because reusable hardware and software design components can be added. Application examples developed using VERTAF demonstrate significantly reduced relative design effort as compared to design without VERTAF, which also shows how high-level reuse of software components combined with automatic synthesis and verification increases design productivity.     

Monitoring and debugging distributed realtime programs

In this paper we describe the design and implementation of an integrated monitoring and debugging system for a distributed real-time computer system. The monitor provides continuous, transparent monitoring capabilities throughout a real-time system's lifecycle with bounded, minimal, predictable interference by using software support. The monitor is flexible enough to observe both high-level events that are operating system- and application-specific, as well as low-level events such as shared variable references. We present a novel approach to monitoring shared variable references that provides transparent monitoring with low overhead. The monitor is designed to support tasks such as debugging realtime applications, aiding real-time task scheduling, and measuring system performance. Since debugging distributed real-time applications is particularly difficult, we describe how the monitor can be used to debug distributed and parallel applications by deterministic execution replay.     

Rapid Prototyping with Constraints-based Scheduling for Multimedia Applications

With the increased demand in multimedia applications, the need to provide better system support is greater than ever. Multimedia applications have an added dimension of time in their execution which results in stringent timing requirements. Existing systems incorporate such stringent timing requirements either at the system-level or the application-level. System-level supports are typically operating-system-dependent whereas application-level supports are achieved by building timing controls into the application itself. This lengthens the application development time and fails to take full advantage of operating system's capabilities. In this paper, we propose a framework that resides between the system-level and application-level support. The framework consists of two layers: an interface layer that incorporates high-level end-to-end timing constraints, and a system layer that implements a host-end scheduling mechanism to support high-level end-to-end timing specifications. Two applications have been developed using this framework. The results indicate that the framework is able to support rapid-prototyping of multimedia applications with stringent timing requirements.     

实时UML及其在月球车实时软件开发中的应用

实时UML(UML-RT)是统一建模语言(Unified Modeling Language,UML)在实时系统的扩展和应用,其简洁清晰的面向对象可视化建模方法可以有效解决实时系统中的复杂建模问题;分析了应用实时UML概念和原理进行实时系统可视化建模的问题和方法,并以包含多个子系统的复杂实时系统-月球车系统为例,论述了应用实时UML进行实际软件设计的过程和问题;使用实时UML使得设计过程形象和易于组织,同时方便了项目成员间的交流,大大加快了软件开发的进程。     

Scheduling for reactive real-time systems

In designing Chinook, a hardware-software cosynthesis system for reactive real-time controllers, the impact of timing constraints on software scheduling has been a central concern. By dividing constraints into two levels, corresponding to low-level interactions with device interfaces and high-level real-time response and rate requirements, we have developed solutions tailored to each aspect. These scheduling techniques enable Chinook to map a high-level specification onto a specified collection of processors and peripheral devices while respecting performance requirements     

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     

Complete worst-case execution time analysis of straight-line hard real-time programs

In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a hard real-time program is addressed. The analysis is focused on straight-line code (without loops and recursive function calls) which is quite commonly found in synthesised code for embedded systems. A comprehensive timing analysis system covering both low-level (assembler instruction level) as well as high-level aspects (programming language level) is presented. The low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. The high-level analysis uses the results from the low-level to compute the final estimate on the WCET. This is done by a heuristic for searching the longest really executable path in the control flow, based on the functional dependencies between various program parts.     

一种SysML模型到AADL模型的自动转换方法

安全关键系统的实现需要通过需求、设计、集成、验证和测试等多个阶段。近年来,模型驱动开发方法逐渐成为安全关键系统设计与开发的重要手段。由于还没有一个建模语言能够支持整个安全关键系统开发生命周期,因此选择集成使用2种广泛使用的标准语言:系统建模语言(SysML)和嵌入式实时系统体系结构分析与设计语言(AADL)。SysML和AADL提供了同一系统的2个不同视图,SysML模型为系统工程师提供了一个系统视图,AADL为架构设计师建立一个较低层次的设计视图,它结合了实现所有功能的硬件、操作系统和代码。提出一种SysML模型到AADL模型的自动转换方法。首先,定义SysML子集SubSysML,主要包括模块定义图(BDD)、内部模块图(IBD)、活动图(ACT)子集和从IBD和BDD扩展的AADL Profile;其次,定义SubSysML到AADL的转换规则并设计转换算法;然后,对生成的AADL初始模型进行精化;最后,使用EMF框架技术实现SubSysML到AADL的模型转换工具并通过雷达案例验证所提方法的有效性。     

A toolset in Java2 for modelling, prototyping and implementing communicating real-time state machines

This paper proposes an approach to the development of real-time systems which depends on Communicating Real-Time State Machines (CRSMs) as the specification language, and on a customisable actor kernel for prototyping, analysis and implementation of a modelled system. CRSMs offer an intuitive and distributed specification of a system in terms of a collection of co-operating state machines interacting with one another through timed CSP-like I/O commands. On the other hand, the underlying actor framework provides a time-sensitive scheduling structure which can be tuned to CSRMs in order to support temporal validation through assertions on the recorded time-stamped event histories. The approach can be practically used through a graphical environment (jCRSM) which has been realised using Java2. The toolset facilitates editing, testing and implementation in Java of CRSM systems. The proposed methodology is novel in that it provides a seamless system development life cycle where the specification, analysis, design and implementation phases are unified by a common representation of machines in terms of actors. The paper demonstrates the use of CRSM based software components by means of examples.     

The ABS tool suite: modelling, executing and analysing distributed adaptable object-oriented systems

Modern software systems must support a high degree of variability to accommodate a wide range of requirements and operating conditions. This paper introduces the Abstract Behavioural Specification (ABS) language and tool suite, a comprehensive platform for developing and analysing highly adaptable distributed concurrent software systems. The ABS language has a hybrid functional and object- oriented core, and comes with extensions that support the development of systems that are adaptable to diversified requirements, yet capable to maintain a high level of trustworthiness. Using ABS, system variability is consistently traceable from the level of requirements engineering down to object behaviour. This facilitates temporal evolution, as changes to the required set of features of a system are automatically reflected by functional adaptation of the system’s behaviour. The analysis capabilities of ABS stretch from debugging, observing and simulating to resource analysis of ABS models and help ensure that a system will remain dependable throughout its evolutionary lifetime. We report on the experience of using the ABS language and the ABS tool suite in an industrial case study.     

带有时钟变量的线性时序逻辑与实时系统验证

为了描述实时系统的性质和行为,10多年来,各种不同的时序逻辑,如Timed Computation Tree Logic,Metric Interval Temporal Logic和Real-Time Temporal Logic等相继提出来.这些时序逻辑适于表示实时系统的性质和规范,但不适于表示实时系统的实现模型.这样,在基于时序逻辑的实时系统的研究中,系统的性质和实现通常是用两种不同的语言来表示的.定义了一个带有时钟变量的线性时序逻辑(linear temporal logic with clocks,简称LTLC).它是由Manna和Pnueli提出的线性时序逻辑在实时情况下的一个推广.LTLC既能表示实时系统的性质,又能很方便地表示实时系统的实现.它能在统一的语义框架中表示出从高级的需求规范到低级的实现模型之间的不同抽象层次上的系统描述,并且能用逻辑蕴涵来表示不同抽象层次的系统描述之间的语义一致性.LTLC的这个特点将有助于实时系统的性质验证和实时系统的逐步求精.     

Portable real-time software for 8-bit microprocessors

This paper discusses a method for developing efficient and portable software for 8-bit microprocessors used in real-time applications. The technique used is to design an ‘intermediate level language’ (ILL) which defines low-level primitives to support the real-time application programming and the constructs of high level languages. Thus, the high level language (HLL) program goes through two stages of translation; first to the ILL code and then to the machine code of a microprocessor. The ILL instruction set developed bridges the gap between high level languages and the poor instruction set of microprocessors. This allows the development of optimized and portable code for the microprocessors. The ILL operations, data types, data organization, control structures, synchronization, communication and multi-tasking facilities are described. The effectiveness of this technique is shown by comparing the code generated by the ILL approach with the code available for a sample real-time application written directly in assembly level language.     

Resource management policies for real-time Java remote invocations

A way to deal with the increasing cost of next generation real-time applications is to extend middleware and high-level general-purpose programming languages, e.g. Java, with real-time support that reduces development, deployment, and maintenance costs. In the particular path towards a distributed real-time Java technology, some important steps have been given into centralized systems to produce real-time Java virtual machines. However, the integration with traditional remote invocation communication paradigms is far from producing an operative solution that may be used to develop final products. In this context, the paper studies how The Real-Time Specification for Java (RTSJ), the leading effort in real-time Java, may be integrated with Java’s Remote Method Invocation (RMI) in order to support real-time remote invocations. The article details a specific approach towards the problem of producing a predictable mechanism for the remote invocation–the core communication mechanism of RMI–via having control on the policies used in the remote invocation. Results obtained in a software prototype help understand how the key entities defined to control the performance of the remote invocation influence in the end-to-end response time of a distributed real-time Java application.     

Opportunities and obligations for physical computing systems

The recent confluence of embedded and real-time systems with wireless, sensor, and networking technologies is creating a nascent infrastructure for a technical, economic, and social revolution. Based on the seamless integration of computing with the physical world via sensors and actuators, this revolution will accrue many benefits. Potentially, its impact could be similar to that of the current Internet. We believe developers must focus on the physical, real-time, and embedded aspects of pervasive computing. We refer to this domain as physical computing systems. For pervasive computing to achieve its promise, developers must create not only high-level system software and application solutions, but also low-level embedded systems solutions. To better understand physical computing's advantages, we consider three application areas: assisted living, emergency response systems for natural or man-made disasters, and protecting critical infrastructures at the national level.     

Action-Level Real-Time Network-on-Chip Modeling

To simulate time-constrained operations and scheduling for Network-on-Chip (NoC) systems, we introduce a new set of component specifications at flit level grounded in Action-Level Real-Time DEVS formalism. These models capture the dynamics of NoC systems through action-based behavior under strict execution time intervals. These DEVS-based models are well-suited for development and simulation of asynchronous NoC architectures. This is achieved by extending the DEVS-Suite simulator to support real-time executions of ALRT-DEVS models. Representative simulation models capturing structure and behavior of prototypical Mesh NoC systems are developed. A set of experiments are designed, implemented, executed, and analyzed to show the kind of real-time simulation capabilities that can be achieved for Network-on-Chip systems.     

SystemC中抢占式进程调度的建模

近来用SystemC进行嵌入式软件建模研究非常活跃，目前尚不能用SystemC直接模拟嵌入式软件中常见的抢占式进程调度的行为。本文在详细的分析了SystemC模拟内核的基础上，提出将进程划分为一个一个不可分割的原子进程单元(APUs)，作为进程调度的最小单位，并构造出一个RTOS抽象层实现任务抢占、实时调度、中断处理等功能，用以实现抢占式进程调度行为的建模和验证。实例表明，采用文中提出的方法，设计者在系统抽象层就可以进行多任务系统的动态调度如中断、抢占的模拟和验证，有效地提高了设计能力。     

Application-specific models and pointcuts using a logic metalanguage

In contemporary aspect-oriented languages, pointcuts are usually specified directly in terms of the structure of the source code. The definition of such low-level pointcuts requires aspect developers to have a profound understanding of the entire application's implementation and often leads to complex, fragile and hard-to-maintain pointcut definitions. To resolve these issues, we present an aspect-oriented programming system that features a logic-based pointcut language that is open such that it can be extended with application-specific pointcut predicates. These predicates define an application-specific model that serves as a contract that base program developers provide and aspect developers can depend upon. As a result, pointcuts can be specified in terms of this more high-level model of the application which confines all intricate implementation details that are otherwise exposed in the pointcut definitions themselves.