Modern HPC systems must be designed considering different parameters, which include cost, performance, and throughput, as well as non-functional properties, such as power/energy consumption and reliability. This paper describes the work performed and the results achieved by the partners of the Italian National Research Center for HPC, Big Data and Quantum Computing in the frame of the sub-project dealing with Future HPC architectures and solutions. The work in this subproject focused on advanced design and monitoring techniques for devising energy- and power-efficient, reliable parallel architectures based on open standards (e.g., RISC-V) and design space exploration techniques and tools. This paper provides a summary of the achieved results and developed products stemming from the activities of the different partners.

Chains of tasks are ubiquitous and used in a broad spectrum of applications. In these chains, tasks execute according to their timing. Then, they communicate by writing to and reading from shared memory. The schedule of tasks and the read/write instants are naturally subject to uncertainties (variability in the execution time, interference due to shared resources of higher priority tasks, etc.). Despite the impact of uncertainties, we believe that current analysis of task chains cannot handle them properly. In this paper, we borrow the notion of jitter to model uncertainties and we propose a novel event model that explicitly captures jitter in read and write operations, decoupled from task scheduling. We develop a (linear-time complexity) compositional analysis framework that tracks how this jitter propagates across chains and impacts metrics such as reaction time, data age, and end-to-end latency. Our model supports arbitrary communication paradigms (e.g., implicit, LET, mid-execution) and is applicable to the analysis of real-world frameworks such as ROS2 without requiring intrusive changes.

Abstract Reconciling the constraint of guaranteeing to always meet deadlines with the optimization objective of reducing waste of computing capacity lies at the heart of a large body of research on real-time systems. Most approaches to doing so require the application designer to specify a deeper characterization of the workload (and perhaps extensive profiling of its run-time behavior), which then enables shaping the resource assignment to the application. In practice, such approaches are weak as they load the designer with the heavy duty of a detailed workload characterization. We seek approaches for reducing the waste of computing resources for recurrent real-time workloads in the absence of such additional characterization, by monitoring the minimal information that needs to be observable about the run-time behavior of a real-time system: its response time. We propose two resource control strategies to assign resources: one based on binary-exponential search and the other, on principles of control. Both approaches are compared against the clairvoyant scenario in which the average/typical behavior is known. Via an extensive simulation, we show that both techniques are useful approaches to reducing resource computation while meeting hard deadlines.

The fifteen papers in this special section focus on real-time systems. They present state-of-the-art work in theory, design, analysis, implementation, and evaluation of real-time systems. All the papers address some form of real-time requirements such as deadlines, response times or delays/latency and consider not only hard real-time systems but also time-sensitive systems in general. Following an open call for papers, authors from all over the globe sent 53 submissions on a broad range of topics. The review committee of top experts worldwide conducted rigorous professional reviews. Each paper at least 3 reviews in the first round. Approximately 50 reviews were performed in the second round to evaluate the revised submissions.

In embedded computing domains, including the automotive industry, complex functionalities are split across multiple tasks that formtask chains. These tasks are functionally dependent and communicate partial computations through shared memory slots based on theLogical Execution Time(LET) paradigm. This paper introduces a model that captures the behavior of a producer-consumer pair of tasks in a chain, characterizing the timing of reading and writing events. Using ring algebra, the combined behavior of the pair can be modeled as a single periodic task. The paper also presents a lightweight mechanism to eliminate jitter in an entire chain of any size, resulting in a single periodic LET task with zero jitter. All presented methods are available in a public repository.

Scheduling algorithms are called “global” if they can migrate tasks between cores. Global scheduling algorithms are the de-facto standard practice for general purpose Operating Systems, to balance the workload between cores. However, the exact schedulability analysis of real-time applications for these algorithms is proven to be weakly NP-hard. Despite such a hardness, the research community keeps investigating the methods for an exact schedulability analysis for its relevance and to tightly estimate the execution requirements of real-time systems. Due to the NP-hardness, the available exact tests are very time and memory demanding even for sets of a few tasks. On another hand, the available sufficient tests are very pessimistic, despite consuming less resources. Motivated by these observations, we propose an exact schedulability test for constrained-deadline sporadic tasks under global multiprocessor fixed-priority scheduling scheduler, which is significantly faster and consumes less memory, compared to any other available exact test. To derive a faster test, we exploit the idea of a state-space pruning, aiming at reducing the number of feasible system states to be examined by the test. The resulted test is multiple orders of magnitude faster with respect to other state-of-the-art exact tests. Our C++ implementation is publicly available.

High throughput applications with real-time guarantees are increasingly relevant. For these applications, parallelism must be exposed to meet deadlines. Directed Acyclic Graphs (DAGs) are a popular and very general application model that can capture any possible interaction among threads. However, we argue that by constraining the application structure to a set of composable “skeletons”, at the price of losing some generality w.r.t. DAGs, the following advantages are gained: (i) a finer model of the application enables tighter analysis, (ii) specialised scheduling policies are applicable, (iii) programming is simplified, (iv) specialised implementation techniques can be exploited transparently, and (v) the program can be automatically tuned to minimise resource usage while still meeting its hard deadlines. As a first step towards a set of real-time skeletons we conduct a case study with the job farm skeleton and the hard real-time XMOS xCore-200 microcontroller. We present an analytical framework for job farms that reduces the number of required cores by scheduling jobs in batches, while ensuring that deadlines are still met. Our experimental results demonstrate that batching reduces the minimum sustainable period by up to 22%, leading to a reduced number of required cores. The framework chooses the best parameters in 83% of cases and never selects parameters that cause deadline misses. Finally, we show that the overheads introduced by the skeleton abstraction layer are negligible.

Despite the creativity of the scientific community and the funding agencies, the underlying model of computation behind IoT, WSN, cloud, edge, fog, and mist is fundamentally the same; Computational nodes which are dynamically interconnected to form a system in where both processing capacity and connectivity may vary over time. On top of such a system, we consider applications that need packets to flow along a path and adhere to end-to-end deadlines. This application model is motivated by both control and automation systems, as well as telecom systems. The challenge is to guarantee end-to-end deadlines when allowing nodes and applications to join or leave. The mainstream, and to some extent natural, approach to this is to relax the stringency of the constraint (e.g. use probabilistic guarantees, soft deadlines). In this paper we take a different approach and keep the end-to-end deadlines as hard constraints and instead partially limit the freedom of how nodes and applications are allowed to leave and join. We present a theoretical framework for modeling such systems along with proofs that deadlines are always honored.

Together with Fixed Priority Scheduling, Earliest Deadline First (EDF) is the second leg on top of which a large portion of the research on real-time systems stands. At the heart of the EDF exact schedulability test, a pivotal role is played by the demand bound function test, which requires to evaluate whether the amount of work required to complete a set of jobs is less than or equal to the amount of time available. Such a test is checked over a set of time instants. In this paper, it is proposed a method that cuts drastically the set of constraints to be checked. Such a method is applicable also to tasks with release offset. Notably, it is proved that such a reduced set of constraints is minimal: it is not possible to reduce the set any further without losing the sufficiency of the test. The code to make this reduction is publicly available on GitHub.

A system is said to be resilient if slight deviations from expected behavior during run-time does not lead to catastrophic degradation of performance: minor deviations should result in no more than minor performance degradation. In mixed-criticality systems, such degradation should additionally be criticality-cognizant. The applicability of control theory is explored for the design of resilient run-time scheduling algorithms for mixed-criticality systems. Recent results in control theory have shown how appropriately designed controllers can provide guaranteed service to hard-real-time servers; this prior work is extended to allow for such guarantees to be made concurrently to multiple criticality-cognizant servers. The applicability of this approach is explored via several experimental simulations in a dual-criticality setting. These experiments demonstrate that our control-based run-time schedulers can be synthesized in such a manner that bounded deviations from expected behavior result in the high-criticality server suffering no performance degradation and the lower-criticality one, bounded performance degradation.

To remain competitive in the field of manufacturing today, companies must constantly improve the automation loops within their production plants. This can be done by augmenting the automation applications with "smart services" such as supervisory-control applications or machine-learning inference algorithms. The downside is that these smart services are often hosted in a cloud infrastructure and the automation applications require a low and predictable end-to-end latency. However, with the 5G technology it will become possible to establish a low-latency connection to the cloud infrastructure and with proper control of the capacity of the smart services, it will become possible to achieve a low and predictable end- to-end latency for the augmented automation applications. In this work we address the challenge of controlling the capacity of the smart services in a way that achieves a low and predictable end- to-end latency. We do this by deriving a mathematical framework that models a network of smart services that is hosting several automation applications. We pro- pose a generalized AutoSAC (automatic service- and admission controller) that builds on previous work by the authors. In the previous work the system was only capable of handling a single set of smart services, with a single application hosted on top of it. With the contributions of this paper it becomes possible to host multiple applications on top of a larger, more general network of smart services.

As the density of sensing/computation/actuation nodes is increasing, it becomes more and more feasible and useful to think at an entire network of physical devices as a single, continuous space-time computing machine. The emergent behaviour of the whole software system is then induced by local computations deployed within each node and by the dynamics of the information diffusion. A relevant example of this distribution model is given by aggregate computing and its companion language field calculus, a minimal set of purely functional constructs used to manipulate distributed data structures evolving over space and time, and resulting in robustness to changes. In this paper, we study the convergence time of an archetypal and widely used component of distributed computations expressed in field calculus, called gradient: a fully-distributed estimation of distances over a metric space by a spanning tree. We provide an analytic result linking the quality of the output of a gradient to the amount of computing resources dedicated. The resulting error bounds are then exploited for network design, suggesting an optimal density value taking broadcast interferences into account. Finally, an empirical evaluation is performed validating the theoretical results.

Today, many control applications in cyber-physical systems are implemented on shared platforms. Such resource sharing may lead to complex timing behaviors and, in turn, instability of control applications. This paper highlights a number of anomalies demonstrating complex timing behaviors caused as a result of resource sharing. Such anomalous scenarios, then, lead to a dramatic increase in design complexity, if not properly considered. Here, we demonstrate that these anomalies are, in fact, very improbable. Therefore, design methodologies for these systems should mainly be devised and tuned towards the majority of cases, as opposed to anomalies, but should also be able to handle such anomalous scenarios.

There is a strong industrial drive to use cloud computing technologies and concepts for providing timing sensitive services in the networking domain since it would provide the means to share the physical resources among multiple users and thus increase the elasticity and reduce the costs. In this work, we develop a mathematical model for user-stateless virtual network functions forming a forwarding graph. The model captures uncertainties of the performance of these virtual resources as well as the time-overhead needed to instantiate them. The model is used to derive a service controller for horizontal scaling of the virtual resources as well as an admission controller that guarantees that packets exiting the forwarding graph meet their end-to-end deadline. The Automatic Service and Admission Controller (AutoSAC) developed in this work uses feedback and feedforward making it robust against uncertainties of the underlying infrastructure. Also, it has a fast reaction time to changes in the input.

Operating systems code is often developed according to principles like simplicity, low overhead, and low memory footprint. Schedulers are no exceptions. A scheduler is usually developed with flexibility in mind, and this restricts the ability to provide real-time guarantees. Moreover, even when schedulers can provide real-time guarantees, it is unlikely that these guarantees are properly quantified using theoretical analysis that carries on to the implementation. To be able to analyze the guarantees offered by operating systems’ schedulers, we developed a publicly available tool that analyzes timing properties extracted from the execution of a set of threads and computes the lower and upper bounds to the supply function offered by the execution platform, together with information about migrations and statistics on execution times. rt-muse evaluates the impact of many application and platform characteristics including the scheduling algorithm, the amount of available resources, the usage of shared resources, and the memory access overhead. Using rt-muse , we show the impact of Linux scheduling classes, shared data and application parallelism, on the delivered computing capacity. The tool provides useful insights on the runtime behavior of the applications and scheduler. In the reported experiments, rt-muse detected some issues arising with the real-time Linux scheduler: despite having available cores, Linux does not migrate SCHED_RR threads which are enqueued behind SCHED_FIFO threads with the same priority.

In operating systems, resource managers are developed according to simplicity, low overhead, low memory footprint, extensibility and efficiency. Thread schedulers are designed and developed following these implementation-related guidelines. The performance of the implementation is then tested over a set of benchmarks. However, the ability to provide real-time guarantees of these policies is rarely properly quantified. To respond to this need, we developed a publicly available tool (rt-muse), that analyzes timing properties extracted from the execution of a set of threads and it computes the lower/upper bounds to the supply function offered by the execution platform. Also, rt-muse evaluates the impact of many application and platform characteristics including the scheduling algorithm, the amount of available resources, the usage of shared resources, the memory access overhead, etc. In the experiments, we show the impact of Linux scheduling classes, shared data and application parallelism, on the delivered computing capacity. The tool provides useful insights on the runtime behavior of the applications and scheduler. For example, we detected unexpected starvation of threads scheduled by the Linux round-robin class.

Today, a considerable portion of embedded systems, e.g., automotive and avionic, comprise several control applications. Guaranteeing the stability of these control applications in embedded systems, or cyber-physical systems, is perhaps the most fundamental requirement while implementing such applications. This is different from the classical hard real-time systems where often the acceptance criterion is meeting the deadline. In other words, in the case of control applications, guaranteeing stability is considered to be a main design goal, which is linked to the amount of delay and jitter a control application can tolerate before instability. This advocates the need for new design and analysis techniques for embedded real-time systems running control applications. In this paper, the analysis and design of such systems considering a server-based resource reservation mechanism are addressed. The benefits of employing servers are manifold: providing a compositional and scalable framework, protection against other tasks' misbehaviors, and systematic bandwidth assignment and co-design. We propose a methodology for designing bandwidth-optimal servers to stabilize control tasks. The pessimism involved in the proposed methodology is both discussed theoretically and evaluated experimentally.

We consider a real-time system of multiple tasks, each task having a plant to control. The overall quadratic control cost is to be optimized. We exploit the periodicity of the task response time, which corresponds to a periodic delay pattern in the feedback control loop. Perturbed periods are used as a tool to find a finite hyper period. We present an analytical procedure to design a periodic linear-quadratic-Gaussian (LQG) controller for tasks with fixed execution times as well as a numerical solution to the periodic -- stochastic LQG problem for tasks with variable execution times. The controllers are evaluated using simulations in real-time scheduling and control co-design examples.

The response time analysis (RTA) is one of the fundamental tools used to guarantee the schedulability of sets of real-time tasks scheduled by Fixed Priorities. Also, several analysis methods inspired by RTA have been successfully developed to address more sophisticated execution platforms (distributed systems, multiprocessor) and application models (DAGs). The major issue with RTA is its time complexity, which is NP-hard. Such a complexity shows up when the task set has high utilization and RTA needs to check all jobs until the first idle instant. In this paper, we propose a continuous upper bound to the response time with quadratic time complexity in the number of tasks. Such an upper bound is demonstrated to be tighter than previously proposed ones with linear time complexity. In addition, with two tasks only, we prove that the proposed bound is the tightest continuous function upper bounding the exact response time of sets of tasks with full utilization. Whether or not this property holds with more than two tasks is still an open problem.

In high throughput applications, such as in multimedia, it is preferable to fully utilize computing resources, even at the price of some (bounded) delay. However, in real-time systems, where the maximum admissible delay is modeled by a deadline, most of the theory is developed with the assumption of a task deadline smaller than or equal to the task period. The reason of this limitation is in the intrinsic difficulty of the schedulability analysis in the arbitrary deadline case. The most notable guarantee test for sets of arbitrary deadline tasks was due to Lehoczky in 1990. In this paper, we propose the quadratic utilization bound applicable to tasks with arbitrary deadline, which extends Lehoczky’s result. The improvement is made possible by providing some information about the task periods.

Real-time Ethernet (RTE) technologies are becoming increasingly popular, as they provide high bandwidth and are able to meet the requirements of industrial real-time communications. Among RTE protocols, the EtherCAT standard is suitable for motion control and closed-loop control applications, which require very short cycle times. As EtherCAT was specifically devised for periodic traffic, aperiodic real-time transmissions are far from being efficient, as they entail long cycle times. To overcome this limitation, this paper presents a general framework for priority-driven swapping (PdS)-based scheduling of aperiodic real-time messages over EtherCAT networks, which uniformly covers both dynamic and static priority and allows for very short cycle times. This paper provides a description of the PdS framework, a schedulability analysis for both static priority and dynamic priority scheduling, and simulative assessments obtained through OMNeT++ simulations.

Many cyber-physical systems comprise several control applications implemented on a shared platform, for which stability is a fundamental requirement. This is as opposed to the classical hard real-time systems where often the criterion is meeting the deadline. However, the stability of control applications depends on not only the delay experienced, but also the jitter. Therefore, the notion of deadline is considered to be artificial for control applications that promotes the need for new techniques for designing cyber-physical systems. The approach in this paper is built on a server-based resource reservation mechanism, which provides compositionality, isolation, and the opportunity of systematic controller-server co-design. We address the controller-server co-design of such systems to obtain design solutions with the minimal bandwidth to guarantee stability.

In automotive systems, some of the engine control tasks are triggered by specific crankshaft rotation angles and are designed to adapt their functionality based on the angular velocity of the engine. This paper proposes a new task model for specifying such a type of real-time activities and presents an approach for analyzing the system feasibility under deadline scheduling for different scenarios. In particular, a feasibility test is derived for tasks under steady-state conditions (constant speed), as well as in dynamic conditions (constant acceleration). A design method is also discussed to determine the most suitable switching speeds for adapting the functionality of tasks without exceeding a desired utilization. Finally, a number of research directions are highlighted to extend the current results to more complex and realistic scenarios.

In embedded real-time systems, task priorities are often assigned to meet deadlines. However, in control tasks, a late completion of a task has no catastrophic consequence; rather, it has a quantifiable impact in the control performance achieved by the task. In this article, we address the problem of determining the optimal assignment of priorities and periods of sampled-data control tasks that run over a shared computation unit. We show that the minimization of the overall cost can be performed efficiently using a branch and bound algorithm that can be further speeded up by allowing for a small degree of suboptimality. Detailed numerical simulations are presented to show the advantages of various branching alternatives, the overall algorithm effectiveness, and its scalability with the number of tasks.

The management of resources among competing QoS-aware applications is often solved by a resource manager (RM) that assigns both the resources and the application service levels. However, this approach requires all applications to inform the RM of the available service levels. Then, the RM has to maximize the "overall quality" by comparing service levels of different applications which are not necessarily comparable. In this paper we describe a Linux implementation of a game-theoretic framework that decouples the two distinct problems of resource assignment and quality setting, solving them in the domain where they naturally belong to. By this approach the RM has linear time complexity in the number of the applications. Our RM is built over the SCHED_DEADLINE Linux scheduling class.

Guaranteeing stability of control applications in embedded systems, or cyber-physical systems, is perhaps the alpha and omega of implementing such applications. However, as opposed to the classical real-time systems where often the acceptance criterion is meeting the deadline, control applications do not primarily enforce hard deadlines. In the case of control applications, stability is considered to be the main design criterion and can be expressed in terms of the amount of delay and jitter a control application can tolerate before instability. Therefore, new design and analysis techniques are required for embedded control systems. In this paper, the analysis and design of such systems considering server-based resource reservation mechanism are addressed. The benefits of employing servers are manifold: (1) providing a compositional framework, (2) protection against other tasks misbehaviors, and (3) systematic bandwidth assignment. We propose a methodology for designing bandwidth-efficient servers to stabilize control tasks.

Often real-time systems can run in different modes depending on the external environment or their internal state. Each operational mode is characterized by a set of tasks with different computational demand, resource requirements, and resource availability. When resource reservation is used to achieve temporal isolation among applications, the reservation parameters may need to change from mode to mode. Hence, an additional guarantee is required to ensure feasibility not only of the applications, but also of the reservations. This paper presents a schedulability analysis to predict the timing behavior of a multi-moded resource reservation, whose parameters may change due to a mode transition. Resource provisioning is analyzed in all the operational modes and also during mode-changes in order to guarantee a minimum amount of resources and derive a feasibility condition for realtime applications and reservations. Theoretical results are also illustrated with examples and test cases.

A full exploitation of the computational power available in a multicore platform requires the software to be specified in terms of parallel execution flows. At the same time, modern embedded systems often consist of more parallel applications with timing requirements, concurrently executing on the same platform and sharing common resources. To prevent reciprocal interference among critical activities, a resource reservation mechanism is highly desired in the kernel to achieve temporal isolation. In this paper, we propose a general methodology for abstracting the total computing power available on a multicore platform by a set of virtual processors, to allocate applications independently of the physical platform. The application, described as a set of tasks with precedence relations expressed by a directed acyclic graph, is automatically partitioned into a set of subgraphs that are selected to minimize either the overall bandwidth consumption or the required number of cores.

A full exploitation of the computational power available in a multi-core platform requires the software to be specified in terms of parallel execution flows. At the same time, modern embedded systems often consist of more parallel applications with timing requirements, concurrently executing on the same platform and sharing common resources. To prevent reciprocal interference among critical activities, a resource reservation mechanism is highly desired in the kernel to achieve temporal isolation. In this paper, we propose a general methodology for partitioning the total computing power available on a multi-core platform into a set of virtual processors, which provide a powerful abstraction to allocate applications independently of the physical platform. The application, described as a set of tasks with precedence relations expressed by a directed acyclic graph, is automatically partitioned into a set of sub graphs that are selected to minimize either the overall bandwidth consumption or the fragmentation of the partition expressed by the so-called “λ-factor” in uniform multiprocessor scheduling).

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.

In resource-constrained systems, the interference generated by the concurrent execution of multiple controller tasks leads to extra delay and jitter, which degrade control performance and may even jeopardize the stability of the controlled system. This work presents a general methodology that integrates control issues and real-time schedulability analysis to improve the control performance in embedded systems with time and resource constraints. The performance increase is achieved by properly selecting task periods and deadlines under feasibility constraints.

Multi-core platforms are becoming the dominant computing architecture for next generation embedded systems. Nevertheless, designing, programming, and analyzing such systems is not easy and a solid methodology is still missing. In this paper, we propose two powerful abstractions to model the computing power of a parallel machine, which provide a general interface for developing and analyzing real-time applications in isolation, independently of the physical platform. The proposed abstractions can be applied on top of different types of service mechanisms, such as periodic servers, static partitions, and P-fair time partitions. In addition, we developed the schedulability analysis of a set of real-time tasks on top of a parallel machine that is compliant with the proposed abstractions.

A new abstraction — the Parallel Supply Function (PSF) — is proposed for representing the computing capabilities offered by virtual platforms implemented atop identical multiprocessors. It is shown that this abstraction is strictly more powerful than previously-proposed ones, from the perspective of more accurately representing the inherent parallelism of the provided computing capabilities. Sufficient tests are derived for determining whether a given real-time task system, represented as a collection of sporadic tasks, is guaranteed to always meet all deadlines when scheduled upon a specified virtual platform using the global EDF scheduling algorithm.

Since worst case response times must be determined repeatedly during the interactive design of real-time application systems, repeated exact computation of such response times would slow down the design process considerably. In this research, we identify three desirable properties of estimates of the exact response times: continuity with respect to system parameters, efficient computability, and approximability. We derive a technique possessing these properties for estimating the worst-case response time of sporadic task systems that are scheduled using fixed priorities upon a preemptive uniprocessor.

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.

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.

Control systems are typically designed assuming an ideal behavior of the computing infrastructure where controllers execute. In practice, however, in highly loaded computing systems consisting of multiple concurrent controllers, resource constraints may introduce delays and jitter in control loops that may degrade control performance significantly. Hence, taking resource constraints into account since the beginning of the design cycle is crucial for optimizing the performance of a control system. In this paper, we propose a general framework for evaluating the performance of a control system as a function of multiple timing attributes (e.g., sampling frequencies, delays and jitter) and for selecting the proper control task parameters (e.g., periods and deadlines) taking resource constraints into account. The proposed framework is illustrated using a real control plant.

We consider the problem of optimal static period assignment for multiple independent control tasks executing on the same CPU. Previous works have assumed that the control performance can be expressed as a function of the sampling rate only. Arguing that the control delay has a large impact on the control performance, in this work we include the control delay in the cost function. The delay is estimated using an approximate response-time analysis. Assuming linear cost functions for the controllers then allows us to solve the optimal period assignment problem analytically. The performance improvements over previous methods are verified in evaluations on synthetic task sets as well as detailed co- simulations of the controllers, the plants, and the scheduler.

The standard design of control systems is based on theperiodic sampling. Every period the data is read from theinput, the control law is computed, and the output is writtento the actuators. However the periodicity of the samplinginstants is a constraint that arises from the ease of implementationand it is not strictly necessary in the control system.In this paper we present an execution model that samplesthe input "when needed". This model saves a considerableamount of computational resources. We show the schedulabilityanalysis for a set of control-driven tasks using bothFixed Priority (FP) and Earliest Deadline First (EDF).

It is well known that the performance of computer controlled systems is heavily affected by delays and jitter occurring in the control loops, which are mainly caused by the interference introduced by other concurrent activities. A common approach adopted to reduce delay and jitter in periodic task systems is to decrease relative deadlines as much as possible, but without jeopardising the schedulability of the task set. In this paper, we formally characterise the region of admissible deadlines so that the system designer can appropriately select the desired values to maximise a given performance index defined over the task set. Finally we also provide a sufficient region of feasible deadlines which is proved to be convex.

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.

The availability of programmable hardware devices with high density of logic elements and the possibility of implementing CPUs (called softcores) using a fraction of the FPGA area offers additional flexibility for the implementation of embedded applications with real-time constraints. When implementing functions on such devices, designers can choose between hardware and software. Also, the designer can select the number of CPUs that must be created to best support the execution of the real-time software. In this paper, we define a design optimization procedure for hard real-time systems, in which each functional block can be implemented in HW, using the logic elements available on the FPGA, or in SW, by means of a real-time task executed by a softcore. The optimizer allocates the functions and the softcores such that the HW implemented part is mapped within the area constraints and the software part is allocated so that schedulability can be guaranteed. When feasible solutions exist, the minimum utilization solution is computed

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

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.

The constant bandwidth server (CBS) is an effective scheduling technique frequently used to handle overruns and implement resource reservation in real-time systems where tasks have variable execution requirements. The behavior of the server is tuned by two parameters: the server bandwidth, which defines the fraction of the processor allocated to the task, and the server period, which defines the time granularity of the allocation. The effect of the granularity on task executions has never been studied before, so it is typically assigned using ad-hoc considerations. This paper presents a statistical study to evaluate the effects of the server parameters on task response times, and proposes a technique to compute the best parameters that minimize the average response time of the served tasks

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 design phase of any real-time system requires balancing the limited computational resources against the functional requirements and the performance of the application. The optimal design solution can be obtained by solving an optimization problem where the system performance is maximized within the schedulability constraints. In this paper, we provide a procedure that finds the task activation rates maximizing a performance function within the deadline constraints in systems scheduled by fixed priorities. First, we describe the exact feasibility region in the domain of task frequencies. Then, we introduce a procedure that starts by finding an initial solution, and incrementally improves it by using an original branch and bound search, until the global optimum is reached. Experiments show that our algorithm finds the optimal task periods for practical problems with a remarkable speedup, if compared with existing techniques. When the size of the problem makes the global search intractable, the experiments show that the algorithm can still find a high quality solution in the very early steps.

Feasibility analysis of fixed priority systems has been widely studied in the real-time literature and several acceptance tests have been proposed to guarantee a set of periodic tasks. They can be divided in two main classes: polynomial time tests and exact tests. Polynomial time tests can efficiently be used for online guarantee of real-time applications, where tasks are activated at runtime. These tests introduce a negligible overhead, when executed upon a new task arrival, however provide only a sufficient schedulability condition, which may cause a poor processor utilization. On the other hand, exact tests, which are based on response time analysis, provide a necessary and sufficient schedulability condition, but are too complex to be executed on line for large task sets. As a consequence, for large task sets, they are often executed off line. This paper proposes a novel approach for analyzing the schedulability of periodic task sets on a single processor under an arbitrary fixed priority assignment: Using this approach, we derive a new schedulability test which can be tuned through a parameter to balance complexity versus acceptance ratio, so that it can be used on line to better exploit the processor, based on the available computational power. Extensive simulations show that our test, when used in its exact form, is significantly faster than the current response time analysis methods. Moreover the proposed approach, for its elegance and compactness, offers an explanation of some known phenomena of fixed priority scheduling and could be helpful for further work on schedulability analysis.

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.

We propose a novel schedulability analysis for verifying the feasibility of large periodic task sets under the rate monotonic algorithm when the exact test cannot be applied on line due to prohibitively long execution times. The proposed test has the same complexity as the original Liu and Layland (1973) bound, but it is less pessimistic, thus allowing it to accept task sets that would be rejected using the original approach. The performance of the proposed approach is evaluated with respect to the classical Liu and Layland method and theoretical bounds are derived as a function of n (the number of tasks) and for the limit case of n tending to infinity. The analysis is also extended to include aperiodic servers and blocking times due to concurrency control protocols. Extensive simulations on synthetic tasks sets are presented to compare the effectiveness of the proposed test with respect to the Liu and Layland method and the exact response time analysis.

Feasibility analysis of fixed priority systems has been widely studied in the real-time literature and several acceptance tests have been proposed to guarantee a set of periodic tasks. They can be divided into two main classes: polynomial time tests and exact tests. Polynomial time tests are used for an online guarantee of dynamic systems, where tasks can be activated at runtime. These tests introduce negligible overhead when executed on a new task arrival, but provide only a sufficient schedulability condition, which may cause poor processor utilization. On the other hand, exact tests, which are based on response time analysis, provide a necessary and sufficient schedulability condition, but are too complex to be executed on line for large task sets. As a consequence, for large task sets, they are often executed offline. This paper proposes a novel approach for analyzing the schedulability of periodic task sets under rate monotonic priority assignment. Using this approach, we derive a new schedulability test which can be tuned through a parameter to balance the complexity vs. acceptance ratio, so that it can be used online to better exploit the processor based on available computational power. Extensive simulations show that our test, when used in its exact form, is significantly faster than current response time analysis methods. Moreover, the proposed approach, for its elegance and compactness, offers an explanation of known phenomena of fixed priority scheduling and could be helpful for further work on rate monotonic analysis.

In this paper we propose a novel schedulability analysis for verifying the feasibility of large periodic task sets under the rate monotonic algorithm, when the exact test cannot be applied on line due to prohibitively long execution times. The proposed test has the same complexity as the original Liu and Layland bound but it is less pessimistic, so allowing to accept task sets that would be rejected using the original approach. The performance of the proposed approach is evaluated with respect to the classical Liu and Layland method, and theoretical bounds are derived as a function of n (the number of tasks) and for the limit case of n tending to infinity. The analysis is also extended to include aperiodic servers and blocking times due to concurrency control protocols. Extensive simulations on synthetic tasks sets are presented to compare the effectiveness of the proposed test with respect to the Liu and Layland method and the exact response time analysis.