Many Artificial Intelligence algorithms (e.g. Convolutional Neural Networks - CNNs) can be modeled as a collection of functions which communicate with each other according to a directed acyclic graph. The main goal of this paper is to optimize the execution of CNNs on real-time embedded systems based on a multicore architecture with scratchpad memory. In a typical multicore platform, cores share a complex memory hierarchy with one or more levels of cache memories, leading to potential interference and contention on the shared communication buses. In these architectures, it is very difficult to bound the tasks' execution time and the communication delay, due to the unpredictable behavior of the cache subsystem. To reduce contention, it is possible to use architectures based on scratchpads, where every processor has a dedicated programmable fast memory to perform its local computations, and data is moved between the main memory and the local memories according to a timed schedule. In this paper, we study the problem of allocating CNN inference functions to processor cores, and scheduling the execution and memory communications. We propose an Integer Linear Programming (ILP) model that accounts for both the cost of copying data to and from scratchpad memories and the parallel computation costs on the cores, with the goal of meeting real-time temporal constraints. We propose an abstract model and two different optimization techniques, offering a trade-off between analysis time and performance. To evaluate our approach, we compare its effectiveness to classic techniques for accelerating matrix multiplication, using benchmarks from the literature. Our results demonstrate that our ILP constraints provide significant improvements in optimizing realistic CNNs.

We present here the main features and lessons learned from the first edition of what has now become the ECRTS industrial challenge, together with the final description of the challenge and a comparative overview of the proposed solutions. This verification challenge, proposed by Thales, was first discussed in 2014 as part of a dedicated workshop (FMTV, a satellite event of the FM 2014 conference), and solutions were discussed for the first time at the WATERS 2015 workshop. The use case for the verification challenge is an aerial video tracking system. A specificity of this system lies in the fact that periods are constant but known with a limited precision only. The first part of the challenge focuses on the video frame processing system. It consists in computing maximum values of the end-to-end latency of the frames sent by the camera to the display, for two different buffer sizes, and then the minimum duration between two consecutive frame losses. The second challenge is about computing end-to-end latencies on the tracking and camera control for two different values of jitter. Solutions based on five different tools - Fiacre/Tina, CPAL (simulation and analysis), IMITATOR, UPPAAL and MAST - were submitted for discussion at WATERS 2015. While none of these solutions provided a full answer to the challenge, a combination of several of them did allow to draw some conclusions.

Commercial-off-the-shelf (COTS) platforms feature several cores that share and contend for memory resources. In real-time system applications, it is of paramount importance to correctly estimate tight upper bounds to the delays due to memory contention. However, without proper support from the hardware (e.g. a real-time bus scheduler), it is difficult to estimate such upper bounds.This work aims at avoiding contention for a set of tasks modeled using the Predictable Execution Model (PREM), i.e. each task execution is divided into a memory phase and a computation phase, on a hardware multicore architecture where each core has its private scratchpad memory and all cores share the main memory. We consider non-preemptive scheduling for memory phases, whereas computation phases are scheduled using partitioned preemptive EDF. In this work, we propose three novel approaches to avoid contention in memory phases: (i) a task-level time-triggered approach, (ii) job-level time-triggered approach, and (iii) on-line scheduling approach. We compare the proposed approaches against the state of the art using a set of synthetic experiments in terms of schedulability and analysis time. Furthermore, we implemented the different approaches on an Infineon AURIX TC397 multicore microcontroller and validated the proposed approaches using a set of tasks extracted from well-known benchmarks from the literature.

Recent commercial hardware platforms for embedded real-time systems feature heterogeneous processing units and computing accelerators on the same System-on-Chip. When designing complex real-time applications for such architectures, the designer is exposed to a number of difficult choices, like deciding on which compute engine to execute a certain task, or what degree of parallelism to adopt for a given function. To help the designer exploring the wide space of design choices and tune the scheduling parameters, we propose a novel real-time application model, called HPC-DAG (Heterogeneous Parallel Condition Directed Acyclic Graph Model), specifically conceived for heterogeneous platforms. An HPC-DAG allows the system designer to specify alternative implementations of a software component for different processing engines, as well as conditional branches to modelif-then-elsestatements. We also propose a schedulability analysis for the HPC-DAG model and a set of heuristic allocation algorithms aimed at improving schedulability for latency sensitive applications. Our analysis takes into account the cost of preempting a task, which can be non-negligible on certain processors. We show the use of our approach on a realistic case study, and we demonstrate its effectiveness by comparing it with state-of-the-art algorithms previously proposed in literature.

Heterogeneous hardware platforms are often used for implementing complex critical real-time applications, like Advanced driver-assistance systems (ADAS) and autonomous driving. Typically, they are composed of CPU hosts and a set of accelerators. To better support real-time workloads, several hardware accelerators have evolved to allow preemption for computationally intensive tasks, such as GPUs. However, their preemption costs can be very high compared to classical CPU preemption, and therefore must be taken into account at design time and in the scheduling analysis. In this paper, we address mainly two tightly correlated problems: (i) task allocation for a set of real-time tasks, modeled by conditional directed acyclic graphs (C-DAG), onto multiprocessor platforms under partitioned preemptive Earliest Deadline First scheduling, assuming a non-negligible cost of preemption, and (ii) intermediate deadlines and offsets assignments to real-time C-DAGs, so to remove unnecessary preemption and reduce the total preemption overhead. The effectiveness of the proposed technique is evaluated using a large set of synthetic tasks sets.

Hardware platforms for real-time embedded systems are evolving towards heterogeneous architectures comprising different types of processing cores and dedicated hardware accelerators, which can be implemented on silicon or dynamically deployed on FPGA fabric. Such accelerators typically access a shared memory to exchange a significant amount of data with other processing elements. Existing COTS solutions focus on maximizing the overall throughput of the system, rather than guaranteeing the timing constraints of individual hardware accelerators. This paper presents the AXI budgeting unit (ABU), a hardware-based solution to implement a bandwidth reservation mechanism on top of the AMBA AXI standard infrastructure for hardware accelerators deployed on FPGAs. An accurate and tractable model, as well as the corresponding analysis, are also proposed to bound the response time of hardware accelerators in the presence of ABUs, in order to verify whether they can complete before their deadlines. Finally, a set of experiments are reported to evaluate the proposed approach on a state-of-the-art platform, namely the Zynq-7020 by Xilinx. The resource consumption of the ABU has been quantified to be less than 1% of the total FPGA resources of the Zynq-7020.

Many task models have been proposed to express and analyze the behavior of real-time applications at different levels of precision. Most of them target sequential applications with no support for parallelism. The digraph task model is one of the most general ones, as it allows modeling arbitrary directed graphs (digraphs) for sequential job releases. In this paper, we extend the digraph task model to support intra-task parallelism. For the proposed parallel multi-mode digraph model, we derive sufficient schedulability tests and a dichotomic search to improve the test pessimism for a set of n tasks onto a heterogeneous single-ISA multi-core platform. To reduce the computational complexity of the schedulability test, we also propose heuristics for (i) partitioning parallel digraph tasks onto the heterogeneous cores, and (ii) assigning core operating frequencies to reduce the overall energy consumption, while meeting real-time constraints. The effectiveness of the proposed approach is validated with an exhaustive set of simulations.

Summary In this paper, a mechanism is presented for reducing priority inversion in multiprogrammed computing systems. Contrary to well‐known approaches from the literature, this paper tackles cases where the dependency relationships among tasks cannot be known in advance to the operating system. The presented mechanism allows tasks to explicitly declare aforementioned relationships, enabling the operating system scheduler to take advantage of such information and trigger priority inheritance, resulting in reduced priority inversion. We present the prototype implementation of the concept within the Linux kernel in the form of modifications to the standard Portable Operating System Interface (POSIX) condition variable code, along with an extensive evaluation, including a quantitative assessment of the benefits for applications making use of the technique and comprehensive overhead measurements. In addition, we present an associated technique for the theoretical schedulability analysis of a system using the new mechanism, which is useful to determine whether all tasks can meet their deadlines or not, in the specific scenario of tasks interacting only through remote procedure calls and under partitioned scheduling.

Parametric Worst-case execution time (WCET) analysis of a sequential program produces a formula that represents the worst-case execution time of the program, where parameters of the formula are user-defined parameters of the program (as loop bounds, values of inputs, or internal variables, etc). In this article we propose a novel methodology to compute the parametric WCET of a program. Unlike other algorithms in the literature, our method is not based on Integer Linear Programming (ILP). Instead, we follow an approach based on the notion of symbolic computation of WCET formulae. After explaining our methodology and proving its correctness, we present a set of experiments to compare our method against the state of the art. We show that our approach dominates other parametric analyses and produces results that are very close to those produced by non-parametric ILP-based approaches, while keeping very good computing time.

We address the problem of schedulability analysis for a set of sporadic real-time tasks scheduled by the Global Earliest Deadline First (G-EDF) policy on a multiprocessor platform. State-of-the-art tests for schedulability analysis of multiprocessor global scheduling are often incomparable. That is, a task set that is judged not schedulable by a test may be verified to be schedulable by another test, and vice versa. In this paper, we first develop a new schedulability test that integrates the limited carry-in technique and Response Time Analysis (RTA) procedure for Global EDF schedulability analysis. Then, we provide an over-approximate variant of this test with better run-time efficiency. Later, we extend these two tests to self-suspending tasks. All schedulability tests proposed in the paper have provable dominance over their state-of-the-art counterparts. Finally, we conduct extensive comparisons among different schedulability tests. Our new tests show significant improvements for schedulability analysis of Global EDF.

The next generation of processor will contain an increasing number of cores, connected to the main memory and to each other using fast Network-on-Chip (NoC) organised in complex mesh structures. In order to analyse real-time programs running on such architectures, it is necessary to estimate the communication latency between processes running on different cores. The goal of this paper is to propose an analytic model for bounding the communication latency on NoC for many-core architectures. In particular, we introduce a new approach to analyse the communication latency on NoC with wormhole switching and credit-based virtual channel flow control. The proposed model is evaluated by comparing the results predicted by the model with real measurements obtained running a set of experiments on an Intel SCC platform.

We address the problem of schedulability analysis for a set of sporadic tasks with arbitrary deadlines running on a multiprocessor system with global fixed-priority preemptive scheduling.

Formal methods (e.g. Timed Automata or Linear Hybrid Automata) can be used to analyse a real-time system by performing a reachability analysis on the model. The advantage of using formal methods is that they are more expressive than classical analytic models used in schedulability analysis. For example, it is possible to express state-dependent behaviour, arbitrary activation patterns, etc. In this paper we use the formalism of Linear Hybrid Automata to encode a hierarchical scheduling system. In particular, we model a dynamic server algorithm and the tasks contained within, abstracting away the rest of the system, thus enabling component-based scheduling analysis. We prove the correctness of the model and the decidability of the reachability analysis for the case of periodic tasks. Then, we compare the results of our model against classical schedulability analysis techniques, showing that our analysis performs better than analytic methods in terms of resource utilisation. We further present two case studies: a component with state-dependent tasks, and a simplified model of a real avionics system. Finally, through extensive tests with various configurations, we demonstrate that this approach is usable for medium-size components.

When learning real-time programming, the novice is faced with many technical difficulties due to low-level C libraries that require considerable programming effort even for implementing a simple periodic task. For example, the POSIX Real-Time standard only provides a low level notion of thread, hence programmers usually build higher level code on top of the POSIX API, every time re-inventing the wheel. In this paper we present a simple C library that simplifies realtime programming in Linux by hiding low-level details of task creation, allocation and synchronization, and provides utilities for more high-level functionalities, like support for mode-change and adaptive systems. The library is released as open-source and it is currently being employed to teach real-time programming in university courses in embedded systems.

IEEE 802.11e HCCA reference scheduler guarantees Quality of Service only for Constant Bit Rate traffic streams, whereas its assignment of scheduling parameters (transmission time TXOP and polling period) is too rigid to serve Variable Bit Rate (VBR) traffic.

Quality of Service (QoS) provided by the IEEE 802.11e amendment and by the proposed HCF Controlled Channel Access (HCCA) reference scheduler is tailored for Constant Bit Rate traffic streams. Moreover the numerous alternative scheduling algorithms are not suitable to serve Variable Bit Rate (VBR) traffic streams with the required QoS and real-time guarantees. This paper presents Immediate Dynamic TXOP HCCA (IDTH), a new scheduling algorithm based on a bandwidth reclaiming mechanism suitable to cooperate with a HCCA real-time scheduler. IDTH recovers the portion of the transmission time unused by the scheduled stations to provide a further capacity for the next variable bit rate traffic streams. The transmission opportunity of the next scheduled station is assigned considering the available spare resources and the previously used ones. The scheduling analysis and the simulations results show that IDTH is suitable to reduce the delay experienced by VBR traffic streams, to efficiently deal with the variability of multimedia traffic and to avoid waste of resources.

The IEEE 802.11e standard introduces Quality of Service (QoS) support for wireless local area networks and suggests how to design a tailored HCF Controlled Channel Access (HCCA) scheduler. However the reference scheduling algorithm is suitable to assure service guarantees only for Constant Bit Rate traffic streams, whereas shows its limits for Variable Bit Rate traffic. Despite the numerous alternative schedulers proposed to improve the QoS support for multimedia applications, in the case of VBR traffic satisfactory real-time performance has not been yet achieved. This paper presents a new scheduling algorithm, Unused Time Shifting Scheduler (UTSS). It integrates a mechanism for bandwidth reclaiming into a HCCA real-time scheduler. UTSS assigns the unused portion of each transmission opportunity to the next scheduled traffic stream. Thanks to such feature, traffic variability is absorbed, reducing the waste of resources. The analytical evaluation, corroborated by the simulation results, shows that UTSS is suitable to reduce the delay experienced by VBR traffic streams and to increase the maximum burstiness sustainable by the network.

We propose an adaptive scheduling technique to schedule highly dynamic multimedia tasks on a CPU. We use a combination of two techniques: the first one is a feedback mechanism to track the resource requirements of the tasks based on “local” observations. The second one is a mechanism that operates with a “global” visibility, reclaiming unused bandwidth. The combination proves very effective: resource reclaiming increases the robustness of the feedback, while the identification of the correct bandwidth made by the feedback increases the effectiveness of the reclamation. We offer both theoretical results and an extensive experimental validation of the approach.

In this paper, the Multiprocessor Bandwidth Inheritance (M-BWI) protocol is presented, which constitutes an extension of the Bandwidth Inheritance (BWI) protocol to symmetric multiprocessor and multicore systems. Similarly to priority inheritance, M-BWI reduces priority inversion in reservation-based scheduling systems, it allows the coexistence of hard, soft and non-real-time tasks, it does not require any information on the temporal parameters of the tasks, hence, it is particularly suitable to open systems, where tasks can dynamically arrive and leave, and their temporal parameters are unknown or only partially known. Moreover, if it is possible to estimate such parameters as the worst-case execution time and the critical sections length, then it is possible to compute an upper bound to the task blocking time. Finally, the M-BWI protocol is neutral to the underlying scheduling scheme, since it can be implemented both in global and partitioned scheduling schemes.

In distributed real-time embedded systems (DRE), it is common to model an application as a set of task chains. Each chain is activated cyclically and must complete before an end-to-end deadline. Each task of the chain is bound to execute on a particular processing element. The complexity of designing and analyzing a DRE can be reduced by applying a component-based methodology: each pipeline can be seen as a component with its temporal characteristic summarized in its interface. Analysis can be carried out in two different steps: 1) derivation of the temporal interface of a component pipeline, 2) analysis of the whole system by integrating the temporal interfaces of the components. In this paper, we propose to describe the temporal interface of a task pipeline by a set of demand bound functions, one per each node on which the pipeline executes, and we describe an algorithm for computing the dbfs. First, we show that the scenario of strictly periodic activations is not the worst when the pipelines are sporadically activated. Then, we propose an exact algorithm for computing the dbfs. We show by experimental analysis that the computation time of the algorithm on pipelines with reasonable size is below one second on common PCs. Finally, we estimate the pessimism introduced by our analysis with respect to holistic analysis by an extensive set of simulations.

Software infrastructures for networked enterprises may need data coming from low-level pervasive devices, such as Wireless Sensor Networks (WSNs). However, the complex management of such tiny physical devices is not acceptable for high-level enterprise applications. Hence the need for a middleware layer that hides complexity and supports the management of heterogeneous real-time data coming from the environment. In our opinion, the Service Oriented Architecture (SOA) design paradigm is the most suitable for allowing a seamless and effective integration of pervasive technologies into enterprise information systems. In this paper we present a service-oriented, flexible and adaptable middleware that allows applications to configure WSN functionalities and exploit them in the form of Web Services.

Many distributed and multiprocessor real-time applications consist of pipelines of tasks that must complete before their end-to-end deadlines. Different schedulability analyses have been proposed for both Fixed Priority and Earliest Deadline First scheduling. All the schedulability analyses proposed so far assume that a global clock synchronization protocol is used to synchronize the deadlines of jobs allocated on different processors. This assumption may limit the applicability of EDF to such systems. In this paper, we propose the Distributed Deadline Synchronization Protocol (DDSP) for computing the absolute deadlines of jobs. The protocol is a non-trivial extension of the Release Guard Protocol proposed for fixed priority systems. DDSP does not require a global clock synchronization, yet existing schedulability analyses are valid for schedules generated by DDSP.

Hierarchical scheduling is a promising methodology for designing and deploying real-time applications, since it enables component-based design and analysis, and supports temporal isolation among competing applications. In hierarchical scheduling an application is described by means of a temporal interface. The designer faces the problem of how to derive the interface parameters so to make the application schedulable, at the same time minimizing the waste of computational resources. The problem is particularly relevant in multiprocessor systems, where it is not clear yet how the interface parameters influence the schedulability of the application and allocation on the physical platform. In this paper we present three novel contributions to hierarchical scheduling for multiprocessor systems. First, we propose the Bounded-Delay Multipartition (BDM), a new interface specification model that allows the designer to balance resource usage versus flexibility in selecting the virtual platform parameters. Second, we explore the schedulability region of a real-time application on top of a generic virtual platform, and derive the interface parameter. Finally, we propose Fluid Best-Fit, an algorithm that takes advantage of the extra degree of flexibility provided by the BDM to compute the virtual platform parameters and allocate it on the physical platform. The performance of the algorithm is evaluated by simulations.

The use of Wireless Multimedia Sensor Networks (WMSNs) in Intelligent Transportation Systems (ITS) can offer cost effective solutions for gathering data on urban traffic, vehicle velocity, parking, etc. These applications demand real-time image acquisition and computational intensive processing in order to collect relevant information. We present our hardware and software solution for detecting moving objects and evaluating their velocity based on line sensor technology which guarantees fast processing, low storage and bandwidth requirements.

We consider a dynamic set of soft real-time applications using a set of shared resources. Each application can execute in different modes, each one associated with a level of Quality-of-Service (QoS). Resources, in their turn, have different modes, each one with a speed and a power consumption, and are managed by a Reservation-Based scheduler enabling a dynamic allocation of the fraction of resources (bandwidth) assigned to each application. To cope with dynamic changes of the application, we advocate an adaptive resource allocation policy organized in two nested feedback loops. The internal loop operates on the scheduling parameter to obtain a resource allocation that meets the temporal constraints of the applications. The external loop operates on the QoS level of the applications and on the power level of the resources to strike a good tradeoff between the global QoS and the energy consumption. This loop comes into play whenever the workload of the application exceeds the bounds that permit the internal loop to operate correctly, or whenever it decreases below a level that permit more aggressive choices for the QoS or substantial energy saving.

We consider the problem of power-aware quality of service (QoS) control for soft real-time embedded systems. Applications can have time-varying and scarcely known resource requirements, and can be activated and terminated at any time. However, they have the capability to switch among a discrete set of operation modes with different QoS levels and resource requirements. In addition, the platform provides resources with power-scaling capabilities and may be subject to power constraints. We present a QoS control architecture achieving optimum trade-offs between overall QoS and power consumption of the system, based on two nested control loops. The external one decides dynamically the optimum configuration for the system, in terms of application QoS modes and resource power modes, while the internal one modulates the resource allocations on a job by job basis, so as to respect timing constraints. We demonstrate the effectiveness of the approach by extensive simulations with trace data of real multimedia applications.

In industrial contexts it might be useful to deploy Wireless Sensor Networks to constantly monitor the status of a plant. At early design stage of any monitoring application, it is envisaged to reinforce real-time paradigms both for task execution and node- to-node communication. Model driven applications are usually seamless provided the system description is complete and robust, and the code generation (platform specific) appropriately complies with the model. We present a demo where acceleration measurements gathered by sensor nodes are conveyed to a fixed location devoted to surveillance. A higher level control system or an operator can take action whenever these readings deviate from the expected behavior. We follow a model-based implementation of the system exploiting the Scilab/Scicos support for the ERIKA Enterprise real-time kernel. Timeliness at the node level is reinforced by the features of the kernel scheduler; moreover the recent implementation of the IEEE 802.15.4 wireless communication standard permits time bounded communications among the nodes.

Abstract This paper presents an architecture for quality of service (QoS) control of time‐sensitive applications in multi‐programmed embedded systems. In such systems, tasks must receive appropriate timeliness guarantees from the operating system independently from one another; otherwise, the QoS experienced by the users may decrease. Moreover, fluctuations in time of the workloads make a static partitioning of the central processing unit (CPU) that is neither appropriate nor convenient, whereas an adaptive allocation based on an on‐line monitoring of the application behaviour leads to an optimum design. By combining a resource reservation scheduler and a feedback‐based mechanism, we allow applications to meet their QoS requirements with the minimum possible impact on CPU occupation. We implemented the framework in AQuoSA (Adaptive Quality of Service Architecture (AQuoSA). http://aquosa.sourceforge.net ), a software architecture that runs on top of the Linux kernel. We provide extensive experimental validation of our results and offer an evaluation of the introduced overhead, which is perfectly sustainable in the class of addressed applications. Copyright © 2008 John Wiley & Sons, Ltd.

This article presents a general framework to analyze and design embedded systems minimizing the energy consumption without violating timing requirements. A set of realistic assumptions is considered in the model in order to apply the results in practical real-time applications. The processor is assumed to have as a set of discrete operating modes, each characterized by speed and power consumption. The energy overhead and the transition delay incurred during mode switches are considered. Task computation times are modeled with a part that scales with the speed and a part having a fixed duration, to take I/O operations into account. The proposed method allows to compute the optimal sequence of voltage/speed changes that approximates the minimum continuous speed, which guarantees the feasibility of a given set of real-time tasks, without violating the deadline constraints. The analysis is performed both under fixed and dynamic priority assignments.

Resource reservations are an effective technique to support hard and soft real-time applications in open systems. However, they generally focus on providing guarantees to real-time applications, without paying too much attention to the performance of non-real-time activities. In this paper, the main limitations encountered when using a conventional reservation-based scheduler for serving non-real-time tasks are described and formally analyzed. Then, a novel algorithm that overcomes these problems (called HGRUB) is proposed, and both theoretical and experimental evidence of its effectiveness is provided.

Industrial automation platforms are experiencing a paradigm shift. New technologies are making their way in the area, including embedded real-time systems, standard local area networks like Ethernet, Wi-Fi and ZigBee, IP-based communication protocols, standard service oriented architectures (SOAs) and Web services. An automation system will be composed of flexible autonomous components with plug & play functionality, self configuration and diagnostics, and autonomic local control that communicate through standard networking technologies. However, the introduction of these new technologies raises important problems that need to be properly solved, one of these being the need to support real-time and quality-of-service (QoS) for real-time applications. This paper describes a SOA enhanced with real-time capabilities for industrial automation. The proposed architecture allows for negotiation of the QoS requested by clients from Web services, and provides temporal encapsulation of individual activities. This way, it is possible to perform anapriorianalysis of the temporal behavior of each service, and to avoid unwanted interference among them. After describing the architecture, experimental results gathered on a real implementation of the framework (which leverages a soft real-time scheduler for the Linux kernel) are presented, showing the effectiveness of the proposed solution. The experiments were performed on simple case studies designed in the context of industrial automation applications.

This paper addresses the schedulability problem of periodic and sporadic real-time task sets with constrained deadlines preemptively scheduled on a multiprocessor platform composed by identical processors. We assume that a global work-conserving scheduler is used and migration from one processor to another is allowed during a task lifetime. First, a general method to derive schedulability conditions for multiprocessor real-time systems will be presented. The analysis will be applied to two typical scheduling algorithms: earliest deadline first (EDF) and fixed priority (FP). Then, the derived schedulability conditions will be tightened, refining the analysis with a simple and effective technique that significantly improves the percentage of accepted task sets. The effectiveness of the proposed test is shown through an extensive set of synthetic experiments.

When dealing with soft real-time tasks with highly variable execution times in open systems, an approach that is becoming popular is to use feedback scheduling techniques to dynamically adapt the bandwidth reserved to each task. According to this model, each task is assigned an adaptive reservation, with a variable budget and a constant period. The response times of the jobs of the task are monitored and if different from expected (i.e. much larger or much shorter than the task relative deadline), a feedback control law adjusts the reservation budget accordingly. However, when the feedback law algorithm demands an increase of the reservation budget, the system must run a schedulability test to check if there is enough spare bandwidth to accommodate such increase. The schedulability test must be very efficient, as it may be performed at each budget update, i.e. potentially at each instance of a task. In this paper, we tackle the problem of performing an efficient on-line schedulability test for Resource Reservation systems implemented through the Sporadic Server on Fixed Priority scheduling. We propose five different tests with different complexity and performance. In particular, we propose a novel on-line test, called Spare Pot algorithm which shows a good cost/performance ratio.

The recent introduction of multicore system-on-a-chip architectures for embedded systems opens a new range of possibilities for both increasing the processing power and improving the fault-robustness of real-time embedded applications. Fault-tolerance and performance are often contrasting requirements. Techniques to improve robustness to hardware faults are based on replication of hardware and/or software. Conversely, techniques to improve performance are based on exploiting inherent parallelism of multiprocessor architectures. In this paper, we propose a technique that allows the user to trade-off parallelism with fault-tolerance in a multicore hardware architecture. Our technique is based on a combination of hardware mechanisms and real-time operating system mechanisms. In particular, we apply hierarchical scheduling techniques to efficiently support fault-tolerant, fault-silent and non-fault-tolerant tasks in the same system.

In this paper we present a software tool for the simulation of distributed real-time embedded systems. Our tool is based on the popular NS-2 package for simulating the networking aspects, and on the RTSim package for the realtime operating system aspects. By reusing much of the existing code, our simulator covers a very wide range of network protocols and real-time mechanisms. After describing the architecture of our tool, we tested it in a simple wireless sensor networks scenario, and we measured the latency in transmitting and receiving messages due to the concurrent activities in the nodes. These effects have been tested against two node scheduling policies, and under different load conditions in the CPU of the nodes.

This paper presents a toolsuite for rapid prototyping and implementation of real-time applications on Wireless Sensor Networks. The work is motivated by the need to use WSNs in industrial control contexts, where the sampling rate, the workload is much higher than typical current applications of WSNs, and the real-time constraints are much tighter. We present a simulator for early evaluation of the real-time behavior of a WSN application; and a realtime operating system that implement appropriate real-time scheduling policies to allow timing analysis and guarantee timing constraints. We provide a demo based on a simple but realistic network scenario showing that simulation is in agreement with experimental results.

In this paper, we propose a methodology for developing component-based real-time systems based on the concept of hierarchical scheduling. Recently, much work has been devoted to the schedulability analysis of hierarchical scheduling systems, in which real-time tasks are grouped into components, and it is possible to specify a different scheduling policy for each component. Until now, only independent components have been considered. In this paper, we extend this model to tasks that interact through remote procedure calls. We introduce the concept of abstract computing platform on which each component is executed. Then, we transform the system specification into a set of real-time transactions and present a schedulability analysis algorithm. Our analysis is a generalization of the holistic analysis to the case of abstract computing platforms. We demonstrate the use of our methodology on a simple example.

Power consumption is an important issue in the design of real-time embedded systems. As many embedded systems are powered by batteries, the goal is to extend the autonomy of the system as much as possible. To reduce power consumption, modern processors can change their voltage and frequency at runtime. A power-aware scheduling algorithm can exploit this capability to reduce power consumption while preserving the timing constraints of real-time tasks. In this paper, we present GRUB-PA, a novel power-aware scheduling algorithm based on a resource reservation technique. In addition to providing temporal isolation and time guarantees and, unlike most of the power-aware algorithms proposed in the literature, GRUB-PA can efficiently handle systems consisting of both hard and soft, aperiodic, sporadic, and periodic tasks. We compared our algorithm with existing power-aware scheduling algorithms on an extensive set of simulation experiments on synthetic task sets. The results show that the performance of our algorithm is in line with the state-of-the-art power-aware algorithms. We also present the implementation of our algorithm in the Linux operating system and discuss practical implementation issues like switching overhead and power models. Finally, we show the results of experiments performed on a real testbed application

Multiprocessor hardware platforms are now being considered for embedded systems, due to their high computational power and little additional cost when compared to single processor systems. When scheduling real-time applications on multiprocessor platforms, a possibility is to use global scheduling, where a scheduling algorithm dynamically assign tasks to processors, and tasks can migrate from one processor to another during their execution. In this paper, we tackle the problem of schedulability analysis of sporadic tasks in global scheduling systems, where the scheduler is the earliest deadline first (EDF) algorithm. We provide two main contributions. First, we show that two recently proposed tests perform poorly when the task set contains heavy tasks (i.e. tasks with high utilization). We also show that neither test dominates the other. As a second contribution, we introduce a new schedulability test that improves significantly the percentage of accepted task sets, especially when considering task sets containing heavy tasks. We show the effectiveness of the proposed test through an extensive set of experiments.

This paper presents a general framework for analyzing and designing embedded systems with energy and timing requirements. A set of realistic assumptions is considered in the model in order to apply the results in practical realtime applications. For example, the processor is assumed to have as a set of discrete operating modes, each characterized by speed, power consumption. The transition delay between modes is considered. To take I/O operations into account, task computation times are modeled with a part that scales with the speed and a part having a fixed duration. Given a set of real-time tasks, the proposed method allows to compute the optimal sequence of voltage/speed changes that approximates the minimum continuous speed which guarantees the feasibility of the system. The analysis is performed both under fixed and dynamic priority assignments.

The development of software for complex reactive embedded systems requires automated support for the verification of functional and nonfunctional properties. Currently, a language (or a design methodology) that can provide both at the same time without incurring in excessive inefficiencies is not available and separation of concerns is the solution advocated by many. Most research and commercial languages and tools focus on providing support for the design and validation of functional properties. At a different level, models and theory have been developed for supporting the description of the threads and resources composing the software architecture, and schedulability analysis provides support for the validation of timing constraints. However, the design of the concurrent structure of the application is still done manually. The system designer has to decide the number of threads, their structure and interactions, without the possibility of evaluating the trade-off between different solutions. This paper presents a solution towards what we believe to be a key objective, that is the synthesis of the architecture-level design and the automated logical-to-architectural mapping. Our proposal tries to reduce the overheads and excessive priority inversions of existing solutions that map all functional blocks (or reactions) into a single thread or assign a thread of execution to each action or possibly to each active object. After presenting our algorithm, we compare it with existing solutions and provide a schedulability analysis of the resulting system.

In this paper we address the problem of schedulability analysis of distributed real-time transactions under EDF, where each transaction is a chain of precedence constrained tasks. We propose a new efficient methodology and a set of algorithms that explicitly take into account the offsets of the transactions. We show, with an extensive set of simulations, that our methodology provides improved schedulability conditions with respect to existing algorithms. Finally, we apply the methodology to an important class of systems: heterogeneous multiprocessor systems, with a general purpose processor and one or more coprocessors (DSPs).

Multiprocessors are now commonplace for efficiently achieving high computational power, even in embedded systems. A considerable research effort is being addressed to schedulability analysis of global scheduling in symmetric multiprocessor platforms (SMP), where there is a global queue of ready tasks, and preemption and migration are allowed. In many soft real-time applications (as e.g. multimedia and telecommunication) a bounded lateness is often tolerated. Unfortunately, when considering priority-driven scheduling of periodic/sporadic tasks, previous results only focused on guaranteeing all deadlines, and provided worst-case utilization bounds that are lower than the maximum available computational power. In particular, until now, the existence of an upper bound on the lateness of soft real-time tasks for a fully utilized SMP was still an open problem. In this paper we do solve this problem by providing an upper bound to the lateness of periodic/sporadic tasks - with relative deadlines equal to periods/minimum inter-arrival times - scheduled by EDF on a SMP, under the only assumption that the total utilization is no higher than the total system capacity

The design of embedded real-time systems requires skills from multiple specific disciplines, including, but not limited to, control, computer science, and electronics. This often involves experts from differing backgrounds, who do not recognize that they address similar, if not identical, issues from complementary angles. Design methodologies are lacking in rigor and discipline so that demonstrating correctness of an embedded design, if at all possible, is a very expensive proposition that may delay significantly the introduction of a critical product. While the economic importance of embedded systems is widely acknowledged, academia has not paid enough attention to the education of a community of high-quality embedded system designers, an obvious difficulty being the need of interdisciplinarity in a period where specialization has been the target of most education systems. This paper presents the reflections that took place in the European Network of Excellence Artist leading us to propose principles and structured contents for building curricula on embedded software and systems.

Minimizing energy consumption is an important issue in the design of real-time embedded systems. As many embedded systems are powered by rechargeable batteries, the goal is to extend, as much as possible, the autonomy of the system.Recently, many scheduling algorithms have been proposed in the literature to exploit the capability of some processor to dynamically change its operating voltage and frequency. The goal of the scheduling algorithm is to select not only the task to be scheduled, but also the operating frequency, so minimizing the energy consumed without jeopardizing the schedulability of the real-time tasks.In this paper we present GRUB-PA, a new scheduling algorithm for power-aware systems. The algorithm can efficiently handle systems consisting of hard and soft real-time tasks. In addition, tasks can be periodic, sporadic or aperiodic. The algorithm reclaims the spare bandwidth caused by periodic tasks that execute less than expected or by sporadic tasks that arrive less frequently, and use this information to lower the processor frequency. We show the effectiveness of the GRUB-PA algorithm in scheduling hard and soft real-time tasks with a set of simulations. Finally, we present the implementation of GRUB-PA in the Linux OS.

Summary form only given. If a periodic task system is scheduled upon an identical multiprocessor platform using the earliest deadline first scheduling algorithm, it is known that the "schedulable utilization" - the largest bound such that any periodic task system with cumulative utilization no larger than this bound is guaranteed to be successfully scheduled - is strictly less than the capacity of the platform. The issue of using the excess processing capacity (the difference between the platform capacity and the schedulable utilization) is addressed here, and an algorithm is presented, and proven correct, that uses this excess capacity to provide guaranteed real-time service to aperiodic jobs.

In this paper, we address the problem of adaptively reserving the CPU to concurrent soft real-time tasks, in order to meet target quality of service requirements. First, we present two new techniques inspired to the idea of stochastic control. Then, we present a flexible and modular software architecture suitable for adaptive scheduling, realised as a minimally invasive set of modifications to the Linux kernel. Finally, we show experimental results that validate our approach and prove its effectiveness in the context of multimedia applications.

In this paper we present a new algorithm for CPU resource reservation in real-time systems that allows the coexistence of hard, soft and non real-time tasks. The proposed algorithm is specifically designed to handle computational overload. A task that needs more CPU-time than reserved can reuse the spare bandwidth, without interfering with the others tasks. With respect to other reclamation schemes, the novelty of the proposed algorithm is that the spare bandwidth is fairly distributed among the needing servers. The effectiveness of the algorithm is demonstrated with an extensive set of experiments. We also propose a methodology to set scheduling parameters depending on the type of the task and on the time constraints needed.

In this paper, we present the BandWidth Inheritance (BWI) protocol, a new strategy for scheduling real-time tasks in dynamic systems, which extends the resource reservation framework to systems where tasks can interact through shared resources. The proposed protocol provides temporal isolation between independent groups of tasks and enables a schedulability analysis for guaranteeing the performance of hard real-time tasks. We show that BWI is the natural extension of the well-known priority inheritance protocol to dynamic reservation systems. A formal analysis of the protocol is presented and a guarantee test for hard real-time tasks is proposed that takes into account the case in which hard real-time tasks interact with soft real-time tasks.

When executing different real-time applications on a single processor system, one problem is how to compose these applications and guarantee at the same time that their timing requirements are not violated. A possible way of composing applications is through the resource reservation approach. Each application is handled by a dedicated server that is assigned a fraction of the processor. Using this approach, the system can be seen as a two-level hierarchical scheduler. A considerable amount of work has been recently addressed to the analysis of this kind of hierarchical systems. However, a question is still unanswered: given a set of real-time tasks to be handled by a server, how to assign the server parameters so that the task set is feasible? In this paper, we answer to the previous question for the case of fixed priority local scheduler by presenting a methodology for computing the class of server parameters that make the task set feasible.

HRT-HOOD has methodological strengths that deserve to be preserved in the face of the commercial decline of HOOD technology. The UML (Unified Modeling Language) meta-model, on the other hand, has a level of flexibility that makes it an especially attractive platform to express the specific real-time design minded features of the HRT-HOOD method. The object-oriented connotation of the method that results from mapping HRT-HOOD onto UML raises methodological issues that we deem of interest to the real-time community at large. This paper discusses three such issues in particular: the prevalence of objects over classes in real-time design, with the consequent inversion of the standard object-oriented development paradigm; the need to derive classes "by example", which arises from the demand to allow multiple, yet static, instances of real-time objects initially designed as singleton; the opportunity of reuse-oriented component-based real-time development, which descends from using interfaces instead of classes as the target of associations among objects.

When executing soft real-time tasks in a shared processor, it is important to properly allocate the computational resources such that the quality of service requirements of each task are satisfied. In this paper we propose Adaptive Reservations, based on applying a feedback scheme to a reservation based scheduler After providing a precise mathematical model of the scheduler, we describe how this model can be used for synthesising the controller by applying results from control theory. Finally, we show the effectiveness of our method by simulation and by experiments with an MPEG player running on a modified Linux kernel.

Abstract This paper presents an object‐oriented software tool, called RTSIM, aimed at simulating real‐time embedded controllers. The tool consists of a collection of C++ libraries permitting a separate specification of the functional behaviour of the controller and of the hardware/software architecture to be used for its deployment. In particular, it is possible to provide an accurate modelling of the concurrent architecture of the control tasks and of the run‐time support offered by the operating system for the real‐time scheduling of the shared resources (CPU, memory buffers and network links). In this way, it is possible to compare different scheduling solutions by evaluating their simulated performance directly in the domain of the control application. Moreover, the tool can be utilized to tune up design parameters such as the activation frequencies of the tasks. The application of the tool is shown in a meaningful case study. Copyright © 2002 John Wiley & Sons, Ltd.

An increasing number of real-time applications related to multimedia and adaptive control systems require greater flexibility than classical real-time theory usually permits. We present a novel scheduling framework in which tasks are treated as springs with given elastic coefficients to better conform to the actual load conditions. Under this model, periodic tasks can intentionally change their execution rate to provide different quality of service and the other tasks can automatically adapt their periods to keep the system underloaded. The proposed model can also be used to handle overload conditions in a more flexible way and to provide a simple and efficient mechanism for controlling a system's performance as a function of the current load.

The research on real-time software systems has produced algorithms that allow to effectively schedule system resources while guaranteeing the deadlines of the application and to group tasks in a very short number of non-preemptive sets which require much less RAM memory for stack. Unfortunately, up to now the research focus has been on time guarantees rather than the optimization of RAM usage. Furthermore, these techniques do not apply to multiprocessor architectures which are likely to be widely used in future microcontrollers. This paper presents a fast and simple algorithm for sharing resources in multiprocessor systems, together with an innovative procedure for assigning preemption thresholds to tasks. This allows to guarantee the schedulability of hard real-time task sets while minimizing RAM usage. The experimental part shows the effectiveness of a simulated annealing-based tool that allows to find a near-optimal task allocation. When used in conjunction with our preemption threshold assignment algorithm, our tool further reduces the RAM usage in multiprocessor systems.

In this paper, we present algorithm BandWidth Inheritance (BWI), a new scheduling strategy that extends the bandwidth reservation approach to systems where tasks can interact through shared resources. The proposed algorithm provides temporal isolation between independent groups of tasks, and enables a schedulability analysis for guaranteeing the performance of realtime tasks. After showing that BWI is the natural extension of the well-known Priority Inheritance Protocol to dynamic reservation systems, a formal analysis of the algorithm is presented, and simple guarantee tests for hard real-time tasks are proposed.

A framework for scheduling a number of different applications on a single shared pre-emptable processor is proposed, such that each application seems to be executing on a slower dedicated processor. A tradeoff is identified and evaluated between how precise a notion of real time (as measured by the granularity of its clock) an application needs to have supported on the one hand, and the added context-switch costs imposed by our scheduling framework on the other.

A framework for scheduling a number of different real-time applications on a single shared preemptable processor is proposed. This framework enforces complete isolation among the different applications, such that the behavior of each application is very similar to its behavior if it had been executing on a slower dedicated processor. A scheduling algorithm that implements this framework is presented and proved correct.

This paper focuses on the problem of providing isolation and real-time execution in scheduling multi-thread applications on a single processor. The proposed scheduling algorithm can be applied in a wide range of different situations, such as in a multimedia real-time systems, where applications may require a guaranteed level of Quality of Service, or in a network link, where different flows of packets may require a certain level of service. This algorithm does not require the exact knowledge of the service times and interarrival times of the tasks: hence, it is especially suited for soft real-time and multimedia environments.

In this paper, we address the problem of scheduling hybrid task sets consisting of hard periodic and soft aperiodic tasks that may share resources in exclusive mode in a dynamic environment, where tasks are scheduled based on their deadlines. Bounded blocking on exclusive resources is achieved by means of a dynamic resource access protocol which also prevents deadlocks and chained blocking. A tunable servicing technique is used to improve aperiodic responsiveness in the presence of resource constraints. The schedulability analysis is also extended to the case in which aperiodic deadlines vary at runtime. The results achieved in this paper can also be used for developing adaptive real-time systems, where task deadlines or periods can change to conform to new load conditions.

An increasing number of real time applications, related to multimedia and adaptive control systems, require greater flexibility than classical real time theory usually permits. We present a novel periodic task model, in which tasks' periods are treated as springs, with given elastic coefficients. Under this framework, periodic tasks can intentionally change their execution rate to provide different quality of service, and the other tasks can automatically adapt their periods to keep the system underloaded. The proposed model can also be used to handle overload conditions in a more flexible way, and provide a simple and efficient mechanism for controlling the quality of service of the system as a function of the current load.