Rate monotonic scheduling re-analysed

In this paper, we re-analyse the rate monotonic scheduler. Traditionally, the schedulability condition was obtained from the greatest lower bound of utilisation factors over all the task sets that (are schedulable and) fully utilise the processor. We argue that full utilisation is not very appropriate for this purpose. We re-establish Liu and Layland's classic schedulability theorem by finding the greatest lower bound of utilisation factors over all the unschedulable task sets instead. The merits of our approach include: Firstly, the fact that the bound is both sound and tight for schedulability follows directly from definition; Secondly, our proof is simpler technically.     

Sensitivity analysis for fixed-priority real-time systems

At early stages in the design of real-time embedded applications, the timing attributes of the computational activities are often incompletely specified or subject to changes. Later in the development cycle, schedulability analysis can be used to check the feasibility of the task set. However, the knowledge of the worst-case response times of tasks is often not sufficient to precisely determine the actions that would correct a non-schedulable design. In these situations, sensitivity analysis provides useful information for changing the implementation, by giving a measure of those computation times that must be reduced to achieve feasibility, or those that can be increased in case of a product extension, or providing the range of feasible periods for selecting the proper task activation rates. In this work, we exploit the concept of feasibility region to propose a faster and more concise solution to the sensitivity analysis problem with respect to existing techniques based on binary search. Furthermore, we show how the formalization of other problems in the feasibility domain, such as managing overloads through elastic scheduling, can be extended to the exact analysis.     

Iterative Learning Control for uncertain systems: Robust monotonic convergence analysis

In this paper, we present a novel Robust Monotonic Convergence (RMC) analysis approach for finite time interval Iterative Learning Control (ILC) for uncertain systems. For that purpose, a finite time interval model for uncertain systems is introduced. This model is subsequently used in an RMC analysis based on μ analysis. As a result, we can handle additive and multiplicative uncertainty models in the RMC problem formulation, analyze RMC of linear time invariant MIMO systems controlled by any linear trial invariant ILC controller, and formulate additional straightforward RMC conditions for ILC controlled systems. To illustrate the derived results, we analyze the RMC properties of linear quadratic (LQ) norm optimal ILC.     

Worst-case execution-time analysis for embedded real-time systems

In this article we give an overview of the worst-case execution time (WCET) analysis research performed by the WCET group of the ASTEC Competence Centre at Uppsala University. Knowing the WCET of a program is necessary when designing and verifying real-time systems. The WCET depends both on the program flow, such as loop iterations and function calls, and on hardware factors, such as caches and pipelines. WCET estimates should be both safe (no underestimation allowed) and tight (as little overestimation as possible). We have defined a modular architecture for a WCET tool, used both to identify the components of the overall WCET analysis problem, and as a starting point for the development of a WCET tool prototype. Within this framework we have proposed solutions to several key problems in WCET analysis, including representation and analysis of the control flow of programs, modeling of the behavior and timing of pipelines and other low-level timing aspects, integration of control flow information and low-level timing to obtain a safe and tight WCET estimate, and validation of our tools and methods. We have focussed on the needs of embedded real-time systems in designing our tools and directing our research. Our long-term goal is to provide WCET analysis as a part of the standard tool chain for embedded development (together with compilers, debuggers, and simulators). This is facilitated by our cooperation with the embedded systems programming-tools vendor IAR Systems.     

Power efficient rate monotonic scheduling for multi-core systems

More computational power is offered by current real-time systems to cope with CPU intensive applications. However, this facility comes at the price of more energy consumption and eventually higher heat dissipation. As a remedy, these issues are being encountered by adjusting the system speed on the fly so that application deadlines are respected and also, the overall system energy consumption is reduced. In addition, the current state of the art of multi-core technology opens further research opportunities for energy reduction through power efficient scheduling. However, the multi-core front is relatively unexplored from the perspective of task scheduling. To the best of our knowledge, very little is known as of yet to integrate power efficiency component into real-time scheduling theory that is tailored for multi-core platforms. In this paper, we first propose a technique to find the lowest core speed to schedule individual tasks. The proposed technique is experimentally evaluated and the results show the supremacy of our test over the existing counterparts. Following that, the lightest task shifting policy is adapted for balancing core utilization, which is utilized to determine the uniform system speed for a given task set. The aforementioned guarantees that: (i) all the tasks fulfill their deadlines and (ii) the overall system energy consumption is reduced.     

Rate monotonic schedulability tests using period-dependent conditions

Feasibility and schedulability problems have received considerable attention from the real-time systems research community in recent decades. Since the publication of the Liu and Layland bound, many researchers have tried to improve the schedulability bound of the RM scheduling. The LL bound does not make any assumption on the relationship between any of the task periods. In this paper we consider the relative period ratios in a system. By reducing the difference between the smallest and the second largest virtual period values in a system, we can show that the RM schedulability bound can be improved significantly. This research has also proposed a system design methodology to improve the schedulability of real time system with a fixed system load.

Design optimization for real-time systems with sustainable schedulability analysis

Real-Time Systems - The design of modern real-time systems not only needs to guarantee their timing correctness, but also involves other critical metrics such as control quality and energy...     

Quantitative analysis of hardware support for real-time operating systems

Microprocessor architects, supported by advances in VLSI technology, have been enormously successful at steadily accelerating the performance of application software. However, operating system performance has lagged due to a divergence between operating system and architectural trends. Unfortunately, some recent work in this area has targeted average-case performance improvements with little or no consideration for the worst-case behavior that must be considered for real-time applications. This paper explores whether one can improve the worst-case performance of operating systems, and as a result, the schedulability of real-time task-sets, using specific hardware-assisted operating system primitives without sacrificing flexibility. The Intel 80960XA Microprocessor, which directly supports basic operating system primitives in hardware, provides an excellent platform to explore operating system hardware and software boundary issues. This paper specifically analyzes the viability of an hardware-assisted fixed-priority scheduler. Using the Real-Time Mach operating system, we did two ports to the 80960XA: one representative of generic RISC implementations, and another which exploited the hardware-supported operating system primitives. We measured the performance of the operating system primitives in both cases and found an average performance improvement factor of 3 for the hardware accelerated version. We applied a formal scheduling model to evaluate the relative performance of the two implementations for two representative real-time applications. The hardware accelerated version reduced operating system burden by factors of 2.66 and 4.1 for the avionics and inertial navigational system task sets, respectively.     

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     

Transition-aware DVS algorithm for real-time systems using tree structure analysis

Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Many existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods have to compute the schedules with exponential time complexities in general. In this paper, we consider a set of jitter-controlled, independent, periodic, hard real-time tasks scheduled according to preemptive pinwheel model. Our approach constructs a tree structure corresponding to a schedule and maintains the data structure at each early-completion point. Our approach consists of off-line and on-line algorithms which consider the effects of transition time and energy. The off-line and on-line algorithm takes O(k + n log n) and O(k + (p_max/p_min)) time complexity, respectively, where n, k, p_max and p_min denotes the number of tasks, jobs, longest and shortest task period, respectively. Experimental results show that the proposed approach is effective in reducing computational complexity, transition time and energy overhead.     

Scheduling analysis based on model checking for multiprocessor real-time systems

Real-time systems (RTS) are omnipresent in several domains. The trend is to use multiprocessor architecture to satisfy the timing constraints of such systems. The model-checking methods have proven to be useful for making the development process reliable at a high abstraction level. Based on this approach, the present paper proposes a new technique for scheduling analysis of a partitioned multiprocessor RTS. Starting from a model with dynamic priority time Petri Nets modeling the system, we have proposed a generation of a reduced states graph. Thus, through the properties of the graph the schedulability is checked. Our approach provides an implementation of a Partition Checker tool, which produces an affirmation of the schedulability or a counterexample in the case of non-schedulable system to reduce the SW/HW space exploration.     

Focusing real-time systems analysis on user operations

A way is presented to model and validate complex, real-time systems by describing these systems from the viewpoints of the major parties in system development: the customer, the user, and the implementer. The models representing these points of view are called, respectively, the requirements model, the operations-concept model, and the implementation model. The focus is on how the concept of operations can be formally factored into established real-time system-analysis methods in terms a nontechnical user can understand. The approach integrates and refines several real-time-oriented modeling methods, including structured analysis, finite-state machines, and threads. Modeling needs are discussed, the multiview paradigm is presented, and an extensive example of a bottle-filling system is given to illustrate the use of the method     

Sensitivity analysis of complex embedded real-time systems

The robustness of an architecture to changes is a major concern in the design of efficient and reliable state-of-the-art embedded real-time systems. Robustness is important during design process to identify if and in how far a system can accommodate later changes or updates, or whether it can be reused in a next generation product. In the product life-cycle, robustness helps the designer to perform changes as a result of product updates, integration of new components and subsystems, or modifications of the environment. In this paper we determine robustness as a performance reserve, the slack in performance before a system fails to meet timing requirements. This is measured as design sensitivity. Due to complex component interactions, resource sharing and functional dependencies, one-dimensional sensitivity analysis might not cover all effects that modifications of one system property may have on system performance. One reason is that the variation of one property can also affect the values of other system properties requiring new approaches to keep track of simultaneous parameter changes. In this paper we present a framework for one-dimensional and multi-dimensional sensitivity analysis of real-time systems. The framework is based on compositional analysis that is scalable to large systems. The one-dimensional sensitivity analysis combines a binary search technique with a set of formal equations derived from the real-time scheduling theory. The multi-dimensional sensitivity analysis engine consists of an exact algorithm that extends the one-dimensional approach, and a stochastic algorithm based on evolutionary search techniques.     

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     

Scheduling for embedded real-time systems

The authors review several approaches to control-oriented and dataflow-oriented software scheduling to determine whether a given technique can satisfy deadlines, throughput, and other constraints for embedded real-time systems     

Concurrent engineering for real-time systems

The Incremental Prototyping Technology for Embedded Real-Time Systems (Iptes) project, which is part of ESPRIT II, is described. The goal of the project is to develop methodologies and tools for the distributed prototyping of real-time systems. The work concentrates on two areas of support for concurrent engineering: adapting graphical-animation techniques to real-time-system development and creating a mechanism for propagating changes within and between tasks     

Requirements-based monitors for real-time systems

Before designing safety- or mission-critical real-time systems, a specification of the required behavior of the system should be produced and reviewed by domain experts. After the system has been implemented, it should be thoroughly tested to ensure that it behaves correctly. This is best done using a monitor, a system that observes the behavior of a target system and reports if that behavior is consistent with the requirements. Such a monitor can be used both as an oracle during testing and as a supervisor during operation. Monitors should be based on the documented requirements of the system. If the target system is required to monitor or control real-valued quantities, then the requirements, which are expressed in terms of the monitored and controlled quantities, will allow a range of behaviors to account for errors and imprecision in observation and control of these quantities. Even if the controlled variables are discrete valued, the requirements must specify the timing tolerance. Because of the limitations of the devices used by the monitor to observe the environmental quantities, there is unavoidable potential for false reports, both negative and positive, This paper discusses design of monitors for real-time systems, and examines the conditions under which a monitor will produce false reports. We describe the conclusions that can be drawn when using a monitor to observe system behavior     

Conformance testing for real-time systems

We propose a new framework for black-box conformance testing of real-time systems. The framework is based on the model of partially-observable, non-deterministic timed automata. We argue that partial observability and non-determinism are essential features for ease of modeling, expressiveness and implementability. The framework allows the user to define, through appropriate modeling, assumptions on the environment of the system under test (SUT) as well as on the interface between the tester and the SUT. We consider two types of tests: analog-clock tests and digital-clock tests. Our algorithm for generating analog-clock tests is based on an on-the-fly determinization of the specification automaton during the execution of the test, which in turn relies on reachability computations. The latter can sometimes be costly, thus problematic, since the tester must quickly react to the actions of the system under test. Therefore, we provide techniques which allow analog-clock testers to be represented as deterministic timed automata, thus minimizing the reaction time to a simple state jump. We also provide algorithms for static or on-the-fly generation of digital-clock tests. These tests measure time only with finite-precision digital clocks, another essential condition for implementability. We also propose a technique for location, edge and state coverage of the specification, by reducing the problem to covering a symbolic reachability graph. This avoids having to generate too many tests. We report on a prototype tool called and two case studies: a lighting device and the Bounded Retransmission Protocol. Experimental results obtained by applying on the Bounded Retransmission Protocol show that only a few tests suffice to cover thousands of reachable symbolic states in the specification.