Industrial plants are major sources of environmental noise, producing complex and high-intensity acoustic emissions that vary across different operational conditions.Automatically characterizing the sources that generate harmful acoustic emissions is crucial to take the necessary actions to reduce them.However, manually labeling these sounds is impractical due to their volume and variability.In this study, we employ an unsupervised deep learning framework for clustering industrial sound emissions in steelmaking plants, focusing on areas such as the hot rolling mill, Electric Arc Furnace, and scrapyard.The approach integrates Variational Autoencoders with Gaussian Mixture Models to learn compact latent representations from Mel-spectrogram features of raw, unlabelled audio data.We compare this approach to traditional clustering techniques such as K-means and GMM, as well as Deep Embedding Clustering.The results demonstrate that the approach significantly outperforms traditional methods, offering reliable and interpretable clustering of industrial acoustic events.This research contributes to the development of automated, efficient, and sustainable noise-monitoring systems for industrial operations, addressing key challenges in environmental noise monitoring.* The work described in the present paper was developed within the project Real-time acoustic sensorS and artificial Intelligence appLications for the rEduction of local eNvironmental impaCt due to noise Emissions (SILENCE) (Grant agreement No. 101112516) -that has received funding from the RFCS programme, which is gratefully acknowledged.The sole responsibility of the issues treated in the present paper lies with the authors; the Commission is not responsible for any use that may be made of the information contained therein.

Recently, the outstanding performance reached by neural networks in many tasks has led to their deployment in autonomous systems, such as robots and vehicles. However, neural networks are not yet trustworthy, being prone to different types of misbehavior, such as anomalous samples, distribution shifts, adversarial attacks, and other threats. Furthermore, frameworks for accelerating the inference of neural networks typically run on rich operating systems that are less predictable in terms of timing behavior and present larger surfaces for cyber-attacks. To address these issues, this paper presents a software architecture for enhancing safety, security, and predictability levels of learning-based autonomous systems. It leverages two isolated execution domains, one dedicated to the execution of neural networks under a rich operating system, which is deemed not trustworthy, and one responsible for running safety-critical functions, possibly under a different operating system capable of handling real-time constraints. Both domains are hosted on the same computing platform and isolated through a type-1 real-time hypervisor enabling fast and predictable inter-domain communication to exchange real-time data. The two domains cooperate to provide a fail-safe mechanism based on a safety monitor, which oversees the state of the system and switches to a simpler but safer backup module, hosted in the safety-critical domain, whenever its behavior is considered untrustworthy. The effectiveness of the proposed architecture is illustrated by a set of experiments performed on two control systems: a Furuta pendulum and a rover. The results confirm the utility of the fall-back mechanism in preventing faults due to the learning component.

Unmanned Aerial Vehicles enable a wide range of applications, including search and rescue, environmental monitoring, and disaster response. These aerial platforms can form dynamic flying ad hoc networks to support both sensing and data communication. In particular, UAVs can establish a resilient communication backbone that adapts to varying propagation conditions and fluctuating traffic demands. However, maintaining reliable performance in such highly dynamic and unpredictable environments remains a critical challenge. This work investigates online link quality estimation by autonomous agents, with a focus on real-time detection of link model changes (e.g., due to mobility or interference) through model drift. Building on this, we propose and evaluate adaptive formation control strategies that adjust UAV placement to optimize the network’s Packet Delivery Ratio. Simulation results demonstrate that the proposed optimal placement strategy significantly outperforms baseline approaches for line-based UAV networks.

Graphics processing units (GPUs) are often employed to accelerate the inference of deep neural networks (DNNs) in cyber-physical systems to implement advanced perception and control functionalities. Frameworks for GPU-accelerated DNN inference typically aim at maximizing the processing throughput rather than focusing on providing a predictable timing behavior, which is crucial for time-sensitive cyber-physical systems. This work proposes a framework for GPU-accelerated inference of DNNs on GPU-based embedded platforms in multitasking scenarios, which provides enhanced timing predictability using a design-time optimization procedure of the DNN workload and a specialized method to schedule the GPU acceleration requests of the DNNs at runtime based on fixed-priority limitedpreemptive scheduling. Fine-grained control of the inference is achieved by splitting the DNNs into smaller chunks, which are then scheduled using a specialized real-time scheduling mechanism. Experimental results on commercial embedded platforms report significant improvements in terms of schedulability.

The use of deep learning techniques in railway environments faces significant obstacles, especially for computer vision tasks. Such obstacles are mainly due to the inherent safety concerns required for installing the proper equipment on a train and the substantial effort required to precisely annotate large datasets, especially for segmentation tasks. Public datasets of real-world images are quite scarce and suffer from severe limitations, such as coarse manual annotation or narrow range of scenarios. In addition, real-world datasets often do not contain scenes that represent critical situations. To address such limitations, this paper introduces SynDRA, a synthetic dataset of photo-realistic images generated using a railway simulator built on Unreal Engine 5. SynDRA offers precise pixel-level annotations across diverse scenarios, thereby facilitating more effective testing and training of deep learning models for semantic segmentation tasks in railway settings. The advantages of the proposed dataset are validated through a series of experiments that highlight the potential of Syn-DRA to enhance the performance of deep learning models in scenarios where real-world annotated data is scarce. The dataset is publicly available at the following link: htt ps: //syndra.retis.santannapisa.it

Deep neural networks are becoming crucial in many cyber–physical systems involving complex perceptual tasks. For those embedded systems requiring real-time interactions with dynamic environments, as autonomous robots and drones, it is of paramount importance that such algorithms are efficiently executed onboard on properly designed hardware accelerators to meet the required performance specifications. In particular, some neural network architectures for object detection and tracking, as You Only Look Once (YOLO), include heavy computational stages that need to be executed before and after the model inference. Such stages are typically not incorporated in traditional accelerators and are executed on general-purpose processors, thus introducing a bottleneck in the overall processing pipeline. To overcome such a problem, this paper presents a general-purpose accelerator on a field-programmable gate array (FPGA) able to run pre-processing and post-processing operations typically required by vision tasks. The proposed solution has been tested in combination with a YOLO object detector accelerated on an Advanced Micro Devices (AMD) Xilinx Kria KR260 board mounting an UltraScale+ multiprocessor system-on-chip, achieving a significant improvement in terms of both timing performance and power consumption, and enabling onboard visual processing into drones. The proposed solution is able to boost the traditional object detection process by a factor of 4.4, allowing the execution of the full processing pipeline at 60 frames per second (fps), versus 13.6 fps reachable without the proposed accelerator. As a result, this work enables the use of high-speed cameras for developing more reactive systems that can respond to incoming events with lower latency.

The growing demand for Ethernet-based Industrial Internet of Things (IIoT) is changing the shape of modern industrial systems and emphasizing the need for high-speed, reliable, scalable, and safe communication among industrial devices. Ethernet-based networks provide the basis for seamless device integration, real-time data exchange, and increased operational efficiency, making them the key to Industry 5.0 applications. As industrial automation becomes increasingly complex, the importance of functional safety grows exponentially. The openSAFETY protocol is a fieldbus-independent, scalable, and robust protocol for implementing functional safety. Our contribution is twofold. First, we analyze time synchronization in the openSAFETY to fully understand the interrelated timing parameters and give some practical guidelines to tune the safety application. We have proposed the parameter tuning approach, which is better in terms of performance and ensures continuous, safe operations. Second, we analyze the protocol’s performance via UDP over Ethernet under normal and degraded network conditions. We found the protocol resilient to network impairments under certain levels during the experiments. Under normal working conditions, the cycle time was successfully achieved in the microsecond range, even at full payload capacity. • Importance of functional safety and role of openSAFETY Protocol in industrial automation. • In-depth analysis of the time synchronization mechanism in the openSAFETY protocol. • Deriving the Configuration Parameters for tuning the Safety Application. • Performance analysis of the protocol under normal and degraded network conditions via UDP over Ethernet.

The robustness of neural networks against input perturbations with bounded magnitude represents a serious concern in the deployment of deep learning models in safety-critical systems. Recently, the scientific community has focused on enhancing certifiable robustness guarantees by crafting 's-Lipschit: neural networks that leverage Lipschitz bounded dense and convolutional layers. Different methods have been proposed in the literature to achieve this goal, however, comparing the performance of such methods is not straightforward, since different metrics can be relevant (e.g., training time, memory usage, accuracy, certifiable robustness) for different applications. Therefore, this work provides a thorough comparison between different methods, covering theoretical aspects such as computational complexity and memory requirements, as well as empirical measurements of time per epoch, required memory, accuracy and certifiable robust accuracy. The paper also provides some guidelines and recommendations to support the user in selecting the methods that work best depending on the available resources. We provide code at github.com/berndprach/1LipschitzLayersCompared.

Security threats are becoming an increasingly relevant concern in cyber–physical systems. Cyber attacks on these systems are not only common today but also increasingly sophisticated and constantly evolving. One way to secure the system against such threats is by using intrusion detection systems (IDSs) to detect suspicious or abnormal activities characteristic of potential attacks. State-of-the-art IDSs exploit both signature-based and anomaly-based strategies to detect network threats. However, existing solutions mainly focus on the analysis of statically defined features of the traffic flow, making them potentially less effective against new attacks that cannot be properly captured by analyzing such features. This paper presents an anomaly-based IDS approach that leverages unsupervised neural models to learn the expected network traffic, enabling the detection of unknown novel attacks (as well as previously-known ones). The proposed solution uses an autoencoder to reconstruct the received packets and detect malicious packets based on the reconstruction error. A careful optimization of the model architecture allowed improving detection accuracy while reducing detection time. The proposed solution has been implemented on a real embedded platform, showing that it can support modern high-performance communication interfaces, while significantly outperforming existing approaches in both detection accuracy, inference time, generalization capability, and robustness to poisoning (which is commonly ignored by state-of-the-art IDSs). Finally, a novel mechanism has been developed to explain the detection performed by the proposed IDS through an analysis of the reconstruction error.

Special Issue Part 1 (Issue 3) and Part 2 (Issue 4) of AIEDAM are based on a workshop on Learning and Creativity held at the 2002 conference on Artificial Intelligence in Design, AID '02 (www.cad.strath.ac.uk/AID02_workshop/Workshop_webpage.html; Gero, ...

Adversarial examples represent a serious threat for deep neural networks in several application domains and a huge amount of work has been produced to investigate them and mitigate their effects. Nevertheless, no much work has been devoted to the generation of datasets specifically designed to evaluate the adversarial robustness of neural models. This paper presents CARLA-GeAR, a tool for the automatic generation of photo-realistic synthetic datasets related to driving scenarios that can be used for a systematic evaluation of the adversarial robustness of neural models against physical adversarial patches, as well as for comparing the performance of different adversarial defense/detection methods. The tool is built on the CARLA simulator, using its Python API, and allows the generation of datasets for several vision tasks in the context of autonomous driving. The adversarial patches included in the generated datasets are attached to billboards or the back of a truck and are crafted by using state-of-the-art white-box attack strategies to maximize the prediction error of the model under test. Finally, the paper presents an experimental study to evaluate the performance of some defense methods against such attacks, showing how the datasets generated with CARLA-GeAR might be used in future work as a benchmark for adversarial defense in the real world. All the code and datasets used in this paper are available athttps://carlagear.retis.santannapisa.it.

The existence of real-world adversarial examples (RWAEs) (commonly in the form of patches) poses a serious threat for the use of deep learning models in safety-critical computer vision tasks such as visual perception in autonomous driving. This article presents an extensive evaluation of the robustness of semantic segmentation (SS) models when attacked with different types of adversarial patches, including digital, simulated, and physical ones. A novel loss function is proposed to improve the capabilities of attackers in inducing a misclassification of pixels. Also, a novel attack strategy is presented to improve the expectation over transformation (EOT) method for placing a patch in the scene. Finally, a state-of-the-art method for detecting adversarial patch is first extended to cope with SS models, then improved to obtain real-time performance, and eventually evaluated in real-world scenarios. Experimental results reveal that even though the adversarial effect is visible with both digital and real-world attacks, its impact is often spatially confined to areas of the image around the patch. This opens to further questions about the spatial robustness of real-time SS models.

The use of neural networks in safety-critical systems requires safe and robust models, due to the existence of adversarial attacks. Knowing the minimal adversarial perturbation of any input x, or, equivalently, knowing the distance of x from the classification boundary, allows evaluating the classification robustness, providing certifiable predictions. Unfortunately, state-of-the-art techniques for computing such a distance are computationally expensive and hence not suited for online applications. This work proposes a novel family of classifiers, namely Signed Distance Classifiers (SDCs), that, from a theoretical perspective, directly output the exact distance of x from the classification boundary, rather than a probability score (e.g., SoftMax). SDCs represent a family of robust-by-design classifiers. To practically address the theoretical requirements of an SDC, a novel network architecture named Unitary-Gradient Neural Network is presented. Experimental results show that the proposed architecture approximates a signed distance classifier, hence allowing an online certifiable classification of x at the cost of a single inference.

This work presents Z-Mask, an effective and deterministic strategy to improve the adversarial robustness of convolutional networks against physically-realizable adversarial attacks. The presented defense relies on specific Z-score analysis performed on the internal network features to detect and mask the pixels corresponding to adversarial objects in the input image. To this end, spatially contiguous activations are examined in shallow and deep layers to suggest potential adversarial regions. Such proposals are then aggregated through a multi-thresholding mechanism. The effectiveness of Z-Mask is evaluated with an extensive set of experiments carried out on models for semantic segmentation and object detection. The evaluation is performed with both digital patches added to the input images and printed patches in the real world. The results confirm that Z-Mask outperforms the state-of-the-art methods in terms of detection accuracy and overall performance of the networks under attack. Furthermore, Z-Mask preserves its robustness against defense-aware attacks, making it suitable for safe and secure AI applications.

Although Deep Neural Networks (DNNs) have shown incredible performance in perceptive and control tasks, several trustworthy issues are still open. One of the most discussed topics is the existence of adversarial perturbations, which has opened an interesting research line on provable techniques capable of quantifying the robustness of a given input. In this regard, the euclidean distance of the input from the classification boundary denotes a well-proved robustness assessment as the minimal affordable adversarial perturbation. Unfortunately, computing such a distance is highly complex due the non-convex nature of DNNs. Despite several methods have been proposed to address this issue, to the best of our knowledge, no provable results have been presented to estimate and bound the error committed. This paper addresses this issue by proposing two lightweight strategies to find the minimal adversarial perturbation. Differently from the state-of-the-art, the proposed approach allows formulating an error estimation theory of the approximate distance with respect to the theoretical one. Finally, a substantial set of experiments is reported to evaluate the performance of the algorithms and support the theoretical findings. The obtained results show that the proposed strategies approximate the theoretical distance for samples close to the classification boundary, leading to provable robustness guarantees against any adversarial attacks.

Abstract The heavy use of machine learning algorithms in safety-critical systems poses serious questions related to safety, security, and predictability issues, requiring novel architectural approaches to guarantee such properties. This paper presents an architecture solution that leverages heterogeneous platforms and virtualization technologies to support AI-powered applications consisting of modules with mixed criticalities and safety requirements. The hypervisor exploits the security features of the Xilinx ZCU104 MPSoCs to create two isolated execution environments: a high performance domain running deep learning algorithms under the Linux operating system and a safety-critical domain running control and monitoring functions under the freeRTOS real-time operating system. The proposed approach is validated by a use case consisting of an unmanned aerial vehicle capable of tracking moving targets using a deep neural network accelerated on the FGPA available on the platform.

Modern FPGA System-on-Chips (SoCs) embed large FPGA logics capable of hosting multiple hardware accelerators. Typically, hardware accelerators require direct access to the shared DRAM memory for reaching the high performance demanded by modern applications. In commercial FPGA SoCs, this goal is achieved by interconnecting the hardware accelerators on an interconnect based on AMBA AXI, which is the de-facto industrial standard for on-chip communications. The AXI standard provides great flexibility in the definition of the network topology. Nevertheless, such flexibility generates a significant unpredictability when attempting to bound the hardware accelerators’ response time when executing under contention. This work focus on bounding the worst-case memory access time of hardware accelerators deployed on commercial FPGA SoCs. We propose a modeling and analysis technique to bound the response time of the hardware accelerators and evaluate the schedulability of a system applicable to arbitrary AXI-based bus structures deployed on FPGA SoCs. Our results are validated on real execution traces collected on two popular FPGA SoCs belonging to the Xilinx ZYNQ-7000 and Zynq-Ultrascale+ families and by simulated results.

The railway industry is investigating new ways to improve the safety and the performance of signalling functions (e.g., train localization) and automate other complex train functions, such as signal and sign recognition, obstacle detection, and track discrimination. Such tasks require the artificial perception of the railway environment through the data acquired from different types of sensors, including cameras, LiDARs, wheel encoders, GNSS receivers, and inertial measurement units. However, testing new algorithms and solutions that use such sensory data requires the availability of a large amount of labeled data, acquired in different scenarios and operating conditions, which are difficult to obtain in a real railway setting, due to strict regulations and practical constraints in accessing the trackside infrastructure and equipping a train with the required sensors. To cope with such difficulties, this paper presents a visual simulation framework able to generate realistic railway scenarios in a virtual environment and automatically produce a variety of labeled datasets from different types of emulated sensors, including cameras, LiDARs, and inertial measurement units. Such scenarios and datasets can be used for testing innovative algorithms, as well as for training and testing deep neural networks for a variety of tasks, as image segmentation, object detection, visual odometry, track discrimination, etc. The proposed framework is particularly relevant for the railway domain, considered the lack of similar datasets and the difficulty of reproducing critical situations in a real environment. A set of experimental results are reported to show the effectiveness of the proposed approach.

Over the past few years, convolutional neural networks (CNNs) have proved to reach superhuman performance in visual recognition tasks. However, CNNs can easily be fooled by adversarial examples (AEs), i.e., maliciously crafted images that force the networks to predict an incorrect output while being extremely similar to those for which a correct output is predicted. Regular AEs are not robust to input image transformations, which can then be used to detect whether an AE is presented to the network. Nevertheless, it is still possible to generate AEs that are robust to such transformations. This article extensively explores the detection of AEs via image transformations and proposes a novel methodology, called defense perturbation, to detect robust AEs with the same input transformations the AEs are robust to. Such a defense perturbation is shown to be an effective counter-measure to robust AEs. Furthermore, multinetwork AEs are introduced. This kind of AEs can be used to simultaneously fool multiple networks, which is critical in systems that use network redundancy, such as those based on architectures with majority voting over multiple CNNs. An extensive set of experiments based on state-of-the-art CNNs trained on the Imagenet dataset is finally reported.

The great performance of machine learning algorithms and deep neural networks in several perception and control tasks is pushing the industry to adopt such technologies in safety-critical applications, as autonomous robots and self-driving vehicles. At present, however, several issues need to be solved to make deep learning methods more trustworthy, predictable, safe, and secure against adversarial attacks. Although several methods have been proposed to improve the trustworthiness of deep neural networks, most of them are tailored for specific classes of adversarial examples, hence failing to detect other corner cases or unsafe inputs that heavily deviate from the training samples. This paper presents a lightweight monitoring architecture based on coverage paradigms to enhance the model robustness against different unsafe inputs. In particular, four coverage analysis methods are proposed and tested in the architecture for evaluating multiple detection logic. Experimental results show that the proposed approach is effective in detecting both powerful adversarial examples and out-of-distribution inputs, introducing limited extra-execution time and memory requirements.

In the last decade, enormous and renewed attention to Artificial Intelligence has emerged thanks to Deep Neural Networks (DNNs), which can achieve high performance in performing specific tasks at the cost of a high computational complexity. GPUs are commonly used to accelerate DNNs, but generally determine a very high power consumption and poor time predictability. For this reason, GPUs are becoming less attractive for resource-constrained, real-time systems, while there is a growing demand for specialized hardware accelerators that can better fit the requirements of embedded systems. Following this trend, this paper focuses on hardware acceleration for the DNNs used by Baidu Apollo, an open-source autonomous driving framework. As an experience report of performing R&D with industrial technologies, we discuss challenges faced in shifting from GPU-based to FPGA-based DNN acceleration when per-formed using the DPU core by Xilinx deployed on an Ultrascale+ SoC FPG A platform. Furthermore, it shows pros and cons of today's hardware accelerating tools. Experimental evaluations were conducted to evaluate the performance of FPGA-accelerated DNNs in terms of accuracy, throughput, and power consumption, in comparison with those achieved on embedded GPUs.

Deep learning and convolutional neural networks allow achieving impressive performance in computer vision tasks, such as object detection and semantic segmentation (SS). However, recent studies have shown evident weaknesses of such models against adversarial perturbations. In a real-world scenario instead, like autonomous driving, more attention should be devoted to real-world adversarial examples (RWAEs), which are physical objects (e.g., billboards and printable patches) optimized to be adversarial to the entire perception pipeline. This paper presents an in-depth evaluation of the robustness of popular SS models by testing the effects of both digital and real-world adversarial patches. These patches are crafted with powerful attacks enriched with a novel loss function. Firstly, an investigation on the Cityscapes dataset is conducted by extending the Expectation Over Transformation (EOT) paradigm to cope with SS. Then, a novel attack optimization, called scene-specific attack, is proposed. Such an attack leverages the CARLA driving simulator to improve the transferability of the proposed EOT-based attack to a real 3D environment. Finally, a printed physical billboard containing an adversarial patch was tested in an outdoor driving scenario to assess the feasibility of the studied attacks in the real world. Exhaustive experiments revealed that the proposed attack formulations outperform previous work to craft both digital and real-world adversarial patches for SS. At the same time, the experimental results showed how these attacks are notably less effective in the real world, hence questioning the practical relevance of adversarial attacks to SS models for autonomous/assisted driving.

Modern applications are often characterized by a tight interaction with I/O devices. At the same time, many application domains are also facing a shift toward an integrated approach where multiple applications with mixed levels of safety and security need to co-exist on top of a shared hardware platform, which is typically managed by a hypervisor. This gives rise to the need for a predictable mechanism allowing multiple virtual machines to share I/O devices, while at the same time controlling contention delays when they access global memory. To deal with these shortcomings, this article proposes an I/O virtualization framework providing support for controlling the I/O-related memory contention by leveraging the ARM QoS-400 regulators. Extensive experiments are performed to compare the proposed solution with the Xen hypervisor, showing improvements up to$8\times $when controlling the I/O-related memory contention.

Parallel execution and hardware acceleration involving specialized devices such as GPUs and FPGAs are becoming increasingly relevant in the domain of embedded systems. Communication between jobs dispatched on different cores and hardware accelerators is most often implemented using asynchronous events. Modeling the timing behavior of such systems requires to account for the delays incurred by each task due to the additional time spent waiting for events. This paper presents the event-driven delay-induced (EDD) task model to explicitly deal with complex computing workloads that incur such kinds of delays. The EDD task model generalizes several state-of-the-art models, such as the DAG task model and the segmented self-suspending task model, and is particularly suited to analyze parallel tasks that issue asynchronous hardware acceleration requests. Two analysis techniques for EDD tasks executing on single core platforms are first provided. We then extend those approaches to analyze parallel real-time tasks under partitioned multicore scheduling by means of a model transformation. Experimental results are presented to compare the two analysis techniques for EDD tasks proposed in the paper. Finally, we compare the analysis of partitioned parallel tasks modeled with EDD tasks against federated scheduling.

Nowadays, hypervisors are the standard solution to integrate different domains into a shared hardware platform, while providing safety, security, and predictability. To this end, a hypervisor virtualizes the physical platform and orchestrates the access to each component. When the system needs to comply with certification requirements for safety-critical systems, virtualization latencies need to be analytically bounded for providing off-line guarantees. This paper presents a detailed modeling of three I/O virtualization techniques, providing analytical bounds for each of them under different metrics. Experimental results compare the bounds for a case study and quantify the contribution due to different sources of delay.

This work aims at making Apollo, a popular autonomous driving framework, safer and more secure by designing a multi-domain architecture, where its components are split between a feature-rich domain running Linux and a critical domain running a real-time operating system (RTOS). The two domains are isolated by a hypervisor. We implemented a prototype where the control component has been ported from Linux to the Erika automotive-grade RTOS, and we discuss a number of challenges that have been faced in moving the component to Erika. The proposed solution has been experimentally evaluated by measuring the latencies involving processing paths passing through the control component.

Many real-time software systems, such as those commonly found in the context of multimedia, cloud computing, robotics, and real-time databases, are characterized by a dynamic workload, where applications can join and leave the system at runtime. Global schedulers can transparently support dynamic workload without requiring any off-line task-allocation phase, thus providing advantages to the system designer. Nevertheless, such schedulers exhibit poor worst-case performance when compared to semi-partitioned schedulers, which instead can achieve near-optimal schedulability performance when used in conjunction with smart task splitting and partitioning techniques, and they are also lighter in terms of run-time overhead. This article proposes an approach to efficiently schedule dynamic real-time workloads on multiprocessor systems by means of semi-partitioned scheduling. A linear-time approximation scheme for the C=D splitting algorithm under partitioned EDF scheduling is proposed. Then, a load-balancing algorithm is presented to admit new real-time workloads with a limited number of re-allocations. The article finally reports on a large-scale experimental study showing that (i) the linear-time approximation is characterized by a very limited utilization loss compared with the corresponding exact approach (that has a much higher complexity), and that (ii) the whole approach allows achieving considerable improvements with respect to global and partitioned EDF scheduling.

This article proposes a technique for optimizing the timing performance and the resource consumption of hardware accelerators for deep neural network (DNN) inference on FPGA-based system-on-chips (SoC). When required, the accelerators are decomposed into chunks, each exploiting at best the available FPGA area, and dynamic partial reconfiguration (DPR) is leveraged to schedule such chunks at run-time. To this end, the article presents accurate models of the resource consumption and timing of DNN accelerators provided by the Xilinx FINN framework. The models are then used to formulate an optimization problem that computes the optimal decomposition of DNN accelerators (and their configuration) by minimizing the inference time while ensuring area constraints on the FPGA. Experimental results on Zynq-7000 platforms demonstrate that the proposed technique provides consistent improvements with respect to both stock configurations of the accelerators and other configurations that can be obtained with a static FPGA allocation.

Predictable execution models have been proposed over the years to achieve contention-free execution of real-time tasks by preloading data into dedicated local memories. In this way, memory access delays can be hidden by delegating a DMA engine to perform memory transfers in parallel with processor execution. Nevertheless, state-of-the-art protocols introduce additional blocking due to priority inversion, which may severely penalize latency-sensitive applications and even worsen the system schedulability with respect to the use of classical scheduling schemes. This paper proposes a new protocol that allows hiding memory transfer delays while reducing priority inversion, thus favoring the schedulability of latency-sensitive tasks. The corresponding analysis is formulated as an optimization problem. Experimental results show the advantages of the proposed protocol against state-of-the-art solutions.

FPGA-based system-on-chips (SoC) are powerful computing platforms to implement mixed-criticality systems that require both multiprocessing and hardware acceleration. Virtualization via hypervisor technologies is, de-facto, an effective technique to allow the co-existence of multiple execution domains with different criticality levels in isolation upon the same platform. Implementing such technologies on FPGA-based SoC poses new challenges: one of such is the isolation of hardware accelerators deployed on the FPGA fabric that belong to different domains but share common resources such as a memory bus. This paper proposes AXI HyperConnect, a hypervisor-level hardware component that allows interconnecting hardware accelerators to the same bus while ensuring isolation and predictability features. AXI HyperConnect has been implemented on modern FPGA-SoC by Xilinx and tested with real-world accelerators, including one for Deep Neural Network inference.

FPGA System-on-Chips (SoCs) are heterogeneous platforms that combine general-purpose processors with a field-programmable gate array (FPGA) fabric. The FPGA fabric is composed of a programmable logic in which hardware accelerators can be deployed to accelerate the execution of specific functionality. The main source of unpredictability when bounding the execution times of hardware accelerators pertains the access to the shared memories via the on-chip bus. This work is focused on bounding the worst-case bus contention experienced by the hardware accelerators deployed in the FPGA fabric. To this end, this work considers the AMBA AXI bus, which is the de-facto standard communication interface used in most the commercial off-the-shelf (COTS) FPGA SoCs, and presents an analysis technique to bound the response times of hardware accelerators implemented on such platforms. A fine-grained modeling of the AXI bus and AXI interconnects is first provided. Then, contention delays are studied under hierarchical bus infrastructures with arbitrary depths. Experimental results are finally presented to validate the proposed model with execution traces on two modern FPGA-based SoC produced by Xilinx (Zynq-7000 and Zynq-Ultrascale+ families) and to assess the performance of the proposed analysis.

Advanced eXtensible Interface (AXI) is an open-standard communication bus interface implemented in most commercial off-the-shelf FPGA System-on-Chips (SoC) to exchange data within the chip. Unfortunately, the AXI standard does not mandate any mechanism to detect possible misbehavior of the connected modules. This work shows that this lack of specification has a relevant impact on popular implementations of the AXI bus. In particular, it is shown how it is easily possible to inject arbitrarily-long delays on modern FPGA system-on-chips under the presence of misbehaving bus masters. To safely solve this issue, this paper presents a general timing analysis to bound the execution of periodically-invoked hardware accelerators in nominal conditions. This timing analysis is then used to conFigure a latency-free hardware module named AXI Stall Monitor (ASM), also proposed in this paper, capable of detecting and safely solving possible stalls during AXI bus transactions. The ASM leaves a quantified flexibility to the hardware accelerators when deviating from nominal conditions. The contribution is finally supported by a set of experiments on the Zynq-7000 and Zynq Ultrascale+SoCs by Xilinx.

When adopting multi-core systems for safety-critical applications, certification requirements mandate bounding the delays incurred in accessing shared resources. This is the case of global memories, whose access is often regulated by memory controllers optimized for average-case performance and not designed to be predictable. As a consequence, worst-case bounds on memory access delays often result to be too pessimistic, drastically reducing the advantage of having multiple cores. This paper proposes a fine-grained analysis of the memory contention experienced by parallel tasks running on a multi-core platform. To this end, an optimization problem is formulated to bound the memory interference by leveraging a three-phase execution model and holistically considering multiple memory transactions issued during each phase. Experimental results show the advantage in adopting the proposed approach on both synthetic task sets and benchmarks.

Summary In recent years, the performance of deep neural networks (DNNs) is significantly improved, making them suitable for many application fields, such as autonomous driving, advanced robotics, and industrial control. Despite a lot of research being devoted to improving the accuracy of DNNs, only limited efforts have been spent to enhance their timing predictability, required in several real‐time applications. This paper proposes a software infrastructure based on the Linux operating system to integrate DNNs within a real‐time multicore system. It has been realized by modifying both the internal scheduler of the popular TensorFlow framework and the SCHED_DEADLINE scheduling class of Linux. The proposed infrastructure allows providing timing isolation of DNN inference tasks, hence improving the determinism of the temporal interference generated by TensorFlow. The proposal is finally evaluated with a case study derived from a state‐of‐the‐art benchmark inspired by an autonomous industrial system. Extensive experiments demonstrate the effectiveness of the proposed solution and show a significant reduction of both average and longest‐observed response times of TensorFlow tasks.

Despite several works in the literature targeted predictable execution models for parallel tasks, limited attention has been devoted to study how specific implementation techniques may affect their execution. This paper highlights some issues that can arise when executing parallel tasks with thread pools, which may lead to deadlocks and performance degradation when adopting blocking synchronization mechanisms. A new parallel task model, inspired to a realistic design found in popular software systems, is first presented to study this problem. Then, formal conditions to ensure the absence of deadlocks and schedulability analysis techniques are proposed under both global and partitioned scheduling.

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.

Real-time dynamic workload consists of tasks that can arbitrarily join and leave the system at run-time. To avoid incurring deadline misses, tasks that request to join the system must pass an admission test, which has to cope with potential scheduling transients originated by the residual effect of the tasks that previously left the system. This phenomenon may require some tasks to suffer an admission delay before being accepted for execution. This paper focuses on uniprocessor earliest-deadline first (EDF) scheduling with constrained deadlines and explicitly considers methods for handling scheduling transients in the presence of dynamic real-time workload. A generalized analysis framework is first presented to overcome several limitations of the existing approaches (including the support for overlapping transients), and is then used to derive methods for computing bounds on the admission delays incurred by tasks. Building on such results, an on-line protocol is proposed to handle the admission control of a dynamic workload, which also comes with a variant that can execute in polynomial time to favor its practical application. Furthermore, the paper shows how the presented analysis can be used off-line for analyzing mode-changes among static task sets. Experimental results are finally presented to evaluate the proposed algorithms.

AMBA AXI is a popular bus protocol that is widely adopted as the medium to exchange data in field-programmable gate array system-on-chips (FPGA SoCs). The AXI protocol does not specify how conflicting transactions are arbitrated and hence the design of bus arbiters is left to the vendors that adopt AXI. Typically, a round-robin arbitration is implemented to ensure a fair access to the bus by the master nodes, as for the popular SoCs by Xilinx. This paper addresses a critical issue that can arise when adopting the AXI protocol under round-robin arbitration; specifically, in the presence of bus transactions with heterogeneous burst sizes. First, it is shown that a completely unfair bandwidth distribution can be achieved under some configurations, making possible to arbitrarily decrease the bus bandwidth of a target master node. This issue poses serious performance, safety, and security concerns. Second, a low-latency (one clock cycle) module named AXI burst equalizer (ABE) is proposed to restore fairness. Our investigations and proposals are supported by implementations and tests upon three modern SoCs. Experimental results are reported to confirm the existence of the issue and assess the effectiveness of the ABE with bus traffic generators and hardware accelerators from the Xilinx’s IP library.

Floorplanning is a mandatory step in the design of hardware accelerators for FPGA platforms, especially when adopting dynamic partial reconfiguration (DPR). This paper presents FLORA, an automated floorplanner based on optimization via Mixed-Integer Linear Programming (MILP). The floorplanning problem is solved by means of a novel fine-grained modeling strategy of FPGA resources. Furthermore, differently from other proposals, our approach takes into account several realistic Partial Reconfiguration (PR) floorplanning constraints on FPGAs. FLORA was compared against state-of-the-art floorplanners by means of benchmark suites, showing that it is capable of providing better performance in terms of resource consumption, maximum inter-region, wire-length, and running time required to produce the solutions. Finally, FLORA was utilized to generate placements for a partially-reconfigurable video processing engine that was implemented on a Xilinx Zynq-7020.

This work proposes solutions for bounding the worst-case memory space requirement for parallel tasks running on multicore platforms with scratchpad memories. It introduces a feasibility test that verifies whether memories are large enough to contain the maximum memory backlog that may be generated by the system. Both closed-form bounds and more accurate algorithmic techniques are proposed. It is shown how one can use max-plus algebra and solutions to the max-flow cut problem to efficiently solve the memory feasibility problem. Experimental results are presented to evaluate the efficiency of the proposed feasibility analysis techniques on synthetic workload and state-of-the-art benchmarks.

The study of parallel task models executed with predictable scheduling approaches is a fundamental problem for real-time multiprocessor systems. Nevertheless, to date, limited efforts have been spent in analyzing the combination of partitioned scheduling and non-preemptive execution, which is arguably one of the most predictable schemes that can be envisaged to handle parallel tasks. This paper fills this gap by proposing an analysis for sporadic DAG tasks under partitioned fixed-priority scheduling where the computations corresponding to the nodes of the DAG are non-preemptively executed. The analysis has been achieved by means of segmented self-suspending tasks with nonpreemptable segments, for which a new fine-grained analysis is also proposed. The latter is shown to analytically dominate state-of-the-art approaches. A partitioning algorithm for DAG tasks is finally proposed. By means of experimental results, the proposed analysis has been compared against a previouslyproposed analysis for DAG tasks with non-preemptable nodes managed by global fixed-priority scheduling. The comparison revealed important improvements in terms of schedulability performance.

Engine control systems include computational activities that are triggered at predetermined angular values of the crankshaft, and therefore generate a workload that tends to increase with the engine speed. To cope with overload conditions, a common practice adopted by the automotive industry is to design such angular tasks with a set of modes that switch at given rotation speeds to adapt the computational demand. This paper presents an exact response time analysis for engine control applications consisting of periodic and engine-triggered tasks scheduled by fixed priority. The proposed analysis explicitly takes into account the physical constraints of the considered systems and is based on the derivation of dominant speeds, which are particular engine speeds that are proved to determine the worst-case behavior of engine-triggered tasks from a timing perspective. Experimental results are finally reported to validate the proposed approach and compare it against an existing sufficient test.

Engine control applications include functions that need to be executed at specific rotation angles of the crankshaft. The tasks performing these functions are activated at variable rates and are programmed to be adaptive with respect to the rotation speed of the engine to avoid overloading the CPU. Simplified control implementations are used at high speeds; for example, reducing the number of fuel injections or the complexity of the computations. Such different control implementations define execution modes with different execution times for different ranges of the rotation speed. The selection of the switching speeds for the operating modes of such tasks is an optimization problem, consisting in determining the optimal transition speeds that maximize the engine performance while guaranteeing schedulability. This article presents three methods for tackling such an optimization problem under a set of assumptions about the performance metrics: two heuristics and a branch and bound method that guarantees finding the optimal solution within a given speed granularity. In addition, a simple method to compute a performance upper bound is presented. The approach and the hypothesis are validated using a Simulink model of the engine and the computational tasks, considering the engine efficiency and the production of pollutants (NO 2 ) as metrics of interest. Simulation experiments show that the performance of proposed heuristics is quite close to that of the upper bound and the optimum within a finite granularity.

The adoption of motor-rehabilitative therapies is highly demanded in a society where the average age of the population is constantly increasing. A recent trend to contain costs while providing high quality of healthcare services is to foster the adoption of self-care procedures, performed primarily in patients’ environments rather than in hospitals or healthcare structures, especially in the case of intensive and chronic patients’ rehabilitation. This work presents a platform to enhance limb functional recovery through telerehabilitation sessions. It relies on a sensing system based on inertial sensors and data fusion algorithms, a module to provide bio-feedback tailored to the users, and a module dedicated to the physicians’ practices. The system design had to face several cyber-physical challenges due to the tight interaction between patient and sensors. For instance, integrating the body kinematics into the sensory processing improved the precision of measurements, simplified the calibration procedure, and made it possible to generate bio-feedback signals. The precision of the proposed system is presented through a set of experiments, showing a resolution below one degree in monitoring joint angles. A validation of the proposed solution has been performed through a medical trial on 50 patients affected by osteo-articular diseases. The presented framework has been designed to operate in other application fields, such as neurological rehabilitation (e.g., Parkinson, Stroke, etc.), sports training, and fitness activities.

In automotive systems, engine control applications include computational activities that are triggered by specific rotation angles of the crankshaft, causing their activation rate to be proportional to the engine speed. In order to avoid overloads at high engine speeds, these tasks are implemented to adapt their functionality based on the angular velocity of the engine. This paper proposes a task model for expressing a number of realistic features of such engine control tasks and presents a real-time schedulability analysis for applications consisting of multiple engine control tasks and classical periodic/sporadic tasks scheduled by the earliest deadline first algorithm. Differently from other efforts spent in analyzing engine-control applications, the presented approach is focused on simplicity, providing linear-time and quadratic-time schedulability tests based on utilization bounds. Experimental results are finally presented to assess the performance of the presented analysis techniques.

To improve computing performance in real-time applications, modern embedded platforms comprise hardware accelerators that speed up the task’s most compute-intensive parts. A recent trend in the design of real-time embedded systems is to integrate field-programmable gate arrays (FPGA) that are reconfigured with different accelerators at runtime, to cope with dynamic workloads that are subject to timing constraints. One of the major limitations when dealing with partial FPGA reconfiguration in real-time systems is that the reconfiguration port can only perform one reconfiguration at a time: if a high-priority task issues a reconfiguration request while the reconfiguration port is already occupied by a lower-priority task, the high-priority task has to wait until the current reconfiguration is completed (a phenomenon known as priority inversion ), unless the current reconfiguration is aborted (introducing unbounded delays in low-priority tasks, a phenomenon known as starvation ). This article shows how priority inversion and starvation can be solved by making the reconfiguration process preemptive —that is, allowing it to be interrupted at any time and resumed at a later time without restarting it from scratch. Such a feature is crucial for the design of runtime reconfigurable real-time systems but not yet available in today’s platforms. Furthermore, the trade-off of achieving a guaranteed bound on the reconfiguration delay for low-priority tasks and the maximum delay induced for high-priority tasks when preempting an ongoing reconfiguration has been identified and analyzed. Experimental results on the Xilinx Zynq-7000 platform show that the proposed implementation of preemptive reconfiguration introduces a low runtime overhead, thus effectively solving priority inversion and starvation.

Parallel computation is fundamental to satisfy the performance requirements of advanced safety-critical systems. OpenMP is a good candidate to exploit the performance opportunities of parallel platforms. However, safety-critical systems are often based on static allocation strategies, whereas current OpenMP implementations are based on dynamic schedulers. This paper proposes two OpenMP-compliant static allocation approaches: an optimal but costly approach based on an ILP formulation, and a sub-optimal but tractable approach that computes a worst-case makespan bound close to the optimal one.

Recent work showed that semi-partitioned scheduling can achieve near-optimal schedulability performance, is simpler to implement compared to global scheduling, and less heavier in terms of runtime overhead, thus resulting in an excellent choice for implementing real-world systems. However, semi-partitioned scheduling typically leverages an off-line design to allocate tasks across the available processors, which requires a-priori knowledge of the workload. Conversely, several simple global schedulers, as global earliest-deadline first (G-EDF), can transparently support dynamic workload without requiring a task-allocation phase. Nonetheless, such schedulers exhibit poor worst-case performance. This work proposes a semi-partitioned approach to efficiently schedule dynamic real-time workload on a multiprocessor system. A linear-time approximation for the C=D splitting scheme under partitioned EDF scheduling is first presented to reduce the complexity of online scheduling decisions. Then, a load-balancing algorithm is proposed for admitting new real-time workload in the system with limited workload re-allocation. A large-scale experimental study shows that the linear-time approximation has a very limited utilization loss compared to the exact technique and the proposed approach achieves very high schedulability performance, with a consistent improvement on G-EDF and pure partitioned EDF scheduling.

Although multicore chips are quickly replacing uniprocessor ones, safety-critical embedded systems are still developed using single processor architecture. The reasons mainly concern predictability and certification issues. This paper proposes a scheduling framework for handling Integrated Modular Avionics (IMA) on multicore platforms providing predictability as well as flexibility in managing dynamic load conditions and unexpected temporal misbehaviors of multicore. A new computational model is proposed to allow specifying a higher degree of flexibility and minimum performance requirements. Schedulability analysis is derived for providing off-line guarantees of real-time constraints in worst-case scenarios, and an efficient reclaiming mechanism is proposed to improve the average-case performance. Simulation and experimental results are reported to validate the proposed approach.

Techniques originating from the Internet of Things (IoT) and Cyber-Physical Systems (CPS) areas have extensively been applied to develop intelligent and pervasive systems such as assistive monitoring, feedback in telerehabilitation, energy management, and negotiation. Those application domains particularly include three major characteristics: intelligence, autonomy and real-time behavior. Multi-Agent Systems (MAS) are one of the major technological paradigms that are used to implement such systems. However, they mainly address the first two characteristics, but miss to comply with strict timing constraints. The timing compliance is crucial for safety-critical applications operating in domains such as healthcare and automotive. The main reasons for this lack of real-time satisfiability in MAS originate from current theories, standards, and technological implementations. In particular, internal agent schedulers, communication middlewares, and negotiation protocols have been identified as co-factors inhibiting the real-time compliance. This paper provides an analysis of such MAS components and pave the road for achieving the MAS compliance with strict timing constraints, thus fostering reliability and predictability.

Several task models have been introduced in the literature to describe the intrinsic parallelism of real-time activities, including fork/join, synchronous parallel, DAG-based, etc. Although schedulability tests and resource augmentation bounds have been derived for these task models in the context of multicore systems, they are still too pessimistic to describe the execution flow of parallel tasks characterized by multiple (and nested) conditional statements, where it is hard to decide which execution path to select for modeling the worst-case scenario. To overcome this problem, this paper proposes a task model that integrates control flow information by considering conditional parallel tasks (cp-tasks) represented by DAGs with both precedence and conditional edges. For this task model, a set of meaningful parameters are identified and computed by efficient algorithms and a response-time analysis is presented for different scheduling policies. Experimental results are finally reported to evaluate the efficiency of the proposed schedulability tests and their performance with respect to classic tests based on both conditional and non-conditional existing approaches.

Recent technological advances have led to an increasing gap between memory and processor performance, since memory bandwidth is progressing at a much slower pace than processor bandwidth. Pre-fetching techniques are traditionally used to bridge this gap and achieve high processor utilization while tolerating high memory latencies. Following this trend, new computational models have been proposed to split task execution in two consecutive phases: a memory phase in which the required instructions and data are pre-fetched to local memory (M-phase), and an execution phase in which the task is executed with no memory contention (C-phase). Decoupling memory and execution phases not only simplifies the timing analysis, but also allows a more efficient (and predictable) pipelining of memory and execution phases through proper co-scheduling algorithms. This paper takes a further step towards the design of smart co-scheduling algorithms for sporadic real-time tasks complying with the memory-computation (M/C) model, by proposing a theoretical framework aimed at tightly characterizing the schedulability improvement obtainable with the adopted M/C task model on single-core systems. In particular, a critical instant is identified for M/C tasks scheduled with fixed priority and an exact response time analysis with pseudo-polynomial complexity is provided. Then, we investigate the problem of priority assignment for M/C tasks, showing that a necessary condition to achieve optimality is to allow different priorities for the two phases. Our experiments show that the proposed techniques provide a significant schedulability improvement with respect to classic execution models, placing an important building block towards the design of more efficient partitioned multi-core systems.

Modern distributed embedded systems frequently involve wireless communication nodes where messages have to be delivered within given timing constraints. This goal can be achieved by adopting a suitable real-time communication protocol. In addition, connecting such systems with mobile devices is also desirable for performing configuration, monitoring, and maintenance activities. The Bluetooth low energy (BLE) protocol would be an attractive solution for this purpose, because it is supported by consumer devices, such as tablets and smart phones, for implementing personal area networks with reduced energy consumption. Unfortunately, however, it cannot guarantee a bounded delay for managing real-time traffic. Modern BLE radio transceivers allow partitioning the network bandwidth between the BLE protocol and another user-defined protocol running on top of the raw radio. This paper exploits this feature to provide an analysis and a design methodology to guarantee the feasibility of a real-time custom protocol that shares the radio with the BLE. Experimental results on a Nordic reference platform show the feasibility of the dual-protocol approach and its capability to support a custom real-time protocol on the raw radio with a bounded overhead.

Engine control applications typically include computational activities consisting of periodic tasks, activated by timers, and engine-triggered tasks, activated at specific angular positions of the crankshaft. Such tasks are typically managed by a OSEK-compliant real-time kernel using a fixed-priority scheduler, as specified in the AUTOSAR standard adopted by most automotive industries. Recent theoretical results, however, have highlighted significant limitations of fixed-priority scheduling in managing engine-triggered tasks that could be solved by a dynamic scheduling policy. To address this issue, this paper proposes a new kernel implementation within the ERIKA Enterprise operating system, providing EDF scheduling for both periodic and engine-triggered tasks. The proposed kernel has been conceived to have an API similar to the AUTOSAR/OSEK standard one, limiting the effort needed to use the new kernel with an existing legacy application. The proposed kernel implementation is discussed and evaluated in terms of run-time overhead and footprint. In addition, a simulation framework is presented, showing a powerful environment for studying the execution of tasks under the proposed kernel.

Computing platforms are evolving towards heterogeneous architectures including processors of different types and field programmable gate arrays (FPGAs), used as hardware accelerators for speeding up specific functions. The increasing capacity and performance of modern FPGAs, with their partial reconfiguration capabilities, have made them attractive in several application domains, including space applications.This paper proposes a framework for supporting the development of safety-critical real-time systems that exploit hardware accelerators developed through FPGAs with dynamic partial reconfiguration capabilities.A model is first presented and then used to derive a response-time analysis to verify the schedulability of a real-time task set under given constraints and assumptions. Although the analysis is based on a generic model, the proposed framework has been conceived to account for several real-world constraints present on today's platforms and has been practically validated on the Zynq platform, showing that it can actually be supported by state-of-the-art technologies. Finally, a number of experiments are reported to evaluate the worst-case performance of the proposed approach on synthetic workload.

A significant number of real-time control applications include computational activities where the results have to be delivered at precise instants, rather than within a deadline. The performance of such systems significantly degrades if outputs are generated before or after the desired target time. This work presents a general methodology that can be used to design and analyze target-sensitive applications in which the timing parameters of the computational activities are tightly coupled with the physical characteristics of the system to be controlled. For the sake of clarity, the proposed methodology is illustrated through a sample case study used to show how to derive and verify real-time constraints from the mission requirements. Software implementation issues necessary to map the computational activities into tasks running on a real-time kernel are also discussed to identify the kernel mechanisms necessary to enforce timing constraints and analyze the feasibility of the application. A set of experiments are finally presented with the purpose of validating the proposed methodology. Copyright © 2015 John Wiley & Sons, Ltd.

Sharing resources in hierarchical real-time systems implemented with reservation servers requires the adoption of special budget management protocols that preserve the bandwidth allocated to a specific component. In addition, blocking times must be accurately estimated to guarantee both the global feasibility of all the servers and the local schedulability of applications running on each component. This paper presents two new local schedulability tests to verify the schedulability of real-time applications running on reservation servers under fixed priority and EDF local schedulers. Reservation servers are implemented with the BROE algorithm. A simple extension to the SRP protocol is also proposed to reduce the blocking time of the server when accessing global resources shared among components. The performance of the new schedulability tests are compared with other solutions proposed in the literature, showing the effectiveness of the proposed improvements. Finally, an implementation of the main protocols on a lightweight RTOS is described, highlighting the main practical issues that have been encountered.

This article presents a survey of energy-aware scheduling algorithms proposed for real-time systems. The analysis presents the main results starting from the middle 1990s until today, showing how the proposed solutions evolved to address the evolution of the platform's features and needs. The survey first presents a taxonomy to classify the existing approaches for uniprocessor systems, distinguishing them according to the technology exploited for reducing energy consumption, that is, Dynamic Voltage and Frequency Scaling (DVFS), Dynamic Power Management (DPM), or both. Then, the survey discusses the approaches proposed in the literature to deal with the additional problems related to the evolution of computing platforms toward multicore architectures.

In embedded systems operated by battery and interacting with the environment, a fundamental issue is the enforcement of real-time and energy constraints to guarantee a desired lifetime with a given performance. A lot of research has focused on energy management at the communication level; however, not many authors considered both real-time and energy requirements in wireless communication systems. This article proposes El-SMan, a power-aware framework working in combination with MAC layer communication protocols for maximizing battery lifetime in wireless networks of embedded systems with real-time constraints. Exploiting the flexibility in bandwidth requirements, El-SMan adapts stream parameters to balance performance versus energy consumption, taking both lifetime and message deadlines into account.

The fast evolution of multicore systems, combined with the need of sharing the same platform for independently developed software, demands for new methodologies and algorithms that allow resource partitioning, while guaranteeing the isolation of concurrent applications. Unfortunately, a major problem that can break the isolation property of concurrent partitions is resource sharing. Although a number of resource access protocols exist for hierarchical uniprocessor systems, no protocols are available today for managing hierarchical partitions implemented on top a multiporcessor platform under partitioned scheduling. This paper presents a framework to support component based design on a multiprocessor platform and proposes a novel reservation server mechanism, called M-BROE, to handle shared resources in multiprocessor systems in the presence of resource reservation scheduling mechanisms.

Engine control applications include software tasks that are triggered at predetermined angular values of the crankshaft, thus generating a computational workload that varies with the engine speed. To avoid overloads at high rotation speeds, these tasks are implemented to self adapt and reduce their computational demand by switching mode at given rotation speeds. For this reason, they are referred to as adaptive variable rate (AVR) tasks. Although a few works have been proposed in the literature to model and analyze the schedulability of such a peculiar type of tasks, an exact analysis of engine control applications has been derived only for fixed priority systems, under a set of simplifying assumptions. The major problem of scheduling AVR tasks with fixed priorities, however, is that, due to engine accelerations, the interarrival period of an AVR task is subject to large variations, therefore there will be several speeds at which any fixed priority assignment is far from being optimal, significantly penalizing the schedulability of the system. This paper proposes for the first time an exact feasibility test under the Earliest Deadline First scheduling algorithm for tasks sets including regular periodic tasks and AVR tasks triggered by a common rotation source. In addition, a set of simulation results are reported to evaluate the schedulability gain achieved in this context by EDF over fixed priority scheduling.

Different task models have been proposed to represent the parallel structure of real-time tasks executing on manycore platforms: fork/join, synchronous parallel, DAG-based, etc. Despite different schedulability tests and resource augmentation bounds are available for these task systems, we experience difficulties in applying such results to real application scenarios, where the execution flow of parallel tasks is characterized by multiple (and nested) conditional structures. When a conditional branch drives the number and size of sub-jobs to spawn, it is hard to decide which execution path to select for modeling the worst-case scenario. To circumvent this problem, we integrate control flow information in the task model, considering conditional parallel tasks (cp-tasks) represented by DAGs composed of both precedence and conditional edges. For this task model, we identify meaningful parameters that characterize the schedulability of the system, and derive efficient algorithms to compute them. A response time analysis based on these parameters is then presented for different scheduling policies. A set of simulations shows that the proposed approach allows efficiently checking the schedulability of the addressed systems, and that it significantly tightens the schedulability analysis of non-conditional (e.g., Classic DAG) tasks over existing approaches.

Low energy consumption is one of the primary issues that have to be addressed in body area networks to prevent frequent battery recharges in the nodes. Such networks are being increasingly used to acquire sensory data that need to be processed in real-time. The Bluetooth Low Energy (BLE) protocol is an attractive solution for implementing personal area networks with reduced energy consumption, also because it is supported by consumer devices such as tablets and smart phones; however, it cannot guarantee a bounded delay for managing real-time traffic. This paper overcomes such a limitation by presenting a bandwidth sharing mechanism that allows partitioning the available network bandwidth between the BLE and another user-defined protocol built on top of the raw radio transceiver. Experimental results are also reported to characterize the timing behavior of the dual protocol on a specific platform.

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.

Modularity and hierarchical-based design are crucial features that need to be supported in complex embedded systems characterized by multiple applications with timing requirements.Resource reservation is a powerful scheduling mechanism for achieving such goals and providing temporal isolation among different real-time applications. When different applications share mutually exclusive resources, a precise feasibility analysis can still be performed in isolation, using specific resource access protocols, taking into account only the application features and the reservation parameters. This paper presents a methodology for selecting the parameters of each reservation in order to guarantee the feasibility of the served applications and minimize the required bandwidth.

Engine control applications require the execution of tasks activated in relation to specific system variables, such as the crankshaft rotation angle. To prevent possible overload conditions at high rotation speeds, such tasks are designed to vary their functionality (hence their computational requirements) for different speed ranges. Modeling and analyzing such a type of tasks poses new research challenges in the schedulability analysis that are now being addressed in the real-time literature. This paper advances the state of the art by presenting a method for computing the exact worst-case interference of such adaptive variable-rate tasks under fixed priority scheduling, enabling a tight analysis and design of engine control applications.

Energy-aware scheduling is a challenging problem that has been studied for decades, investigating the trade-off between performance and energy consumption. In early CMOS circuits, Dynamic Voltage and Frequency Scaling (DVFS) techniques allowed drastically reducing the power consumption. Recent technological advancements have decreased the portion of dissipation which is affected by speed scaling, making Dynamic Power Management (DPM) algorithms more effective. However, the adoption of simplistic power models often biased the decision on which technique to adopt, decreasing the effectiveness of the selected implementation. This paper discusses the factors to consider when deciding which technique to implement on a given single-core architecture, highlight the limitations of the current mainstream.

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.

The question whether preemptive algorithms are better than nonpreemptive ones for scheduling a set of real-time tasks has been debated for a long time in the research community. In fact, especially under fixed priority systems, each approach has advantages and disadvantages, and no one dominates the other when both predictability and efficiency have to be taken into account in the system design. Recently, limited preemption models have been proposed as a viable alternative between the two extreme cases of fully preemptive and nonpreemptive scheduling. This paper presents a survey of the existing approaches for reducing preemptions and compares them under different metrics, providing both qualitative and quantitative performance evaluations.

Several real-time applications include tasks in which the output must be produced at precise time instants, rather than “within” a deadline, and the overall system performance significantly degrades when the task is executed too late or too early with respect to the desired time. This paper illustrates one of such applications and takes it as a reference case study to propose a general approach to show how to derive the timing constraints from the application requirements, how to implement the application on top of a realtime kernel, identifying the operating system features necessary to enforce such constraints, and how to analyze the schedulability of the task set. A set of experimental results are also presented to validate the proposed approach.

The design of wireless embedded systems for realtime applications requires a careful management of timing and energy requirements. This paper describes a wireless communication protocol that can guarantee both message deadlines and system lifetime by properly allocating the network bandwidth to each node. The protocol allows multi-hop wireless communication under different network topologies. The proposed approach is validated through both theoretical and experimental results.

The energy consumption in distributed systems depends on several inter-related factors, including task partitioning, process redundancy, fault tolerance, task and message scheduling, and communication bandwidth allocation. Although some of these issues have been considered in the literature in isolation, a systematic approach considering all the constraints is still missing. This paper addresses the problem of allocating a task set and the required communication bandwidth on a distributed embedded system, aiming at reducing energy consumption while guaranteeing timing and redundancy constraints. Two heuristic approaches are proposed and compared against a complete method and simulated annealing. Simulation results show the effectiveness of the proposed approaches.

A central issue for verifying the schedulability of hard real-time systems is the correct evaluation of task execution times. These values are significantly influenced by the preemption overhead, which mainly includes the cache related delays and the context switch times introduced by each preemption. Since such an overhead significantly depends on the particular point in the code where preemption takes place, this paper proposes a method for placing suitable preemption points in each task in order to maximize the chances of finding a schedulable solution. In a previous work, we presented a method for the optimal selection of preemption points under the restrictive assumption of a fixed preemption cost, identical for each preemption point. In this paper, we remove such an assumption, exploring a more realistic and complex scenario where the preemption cost varies throughout the task code. Instead of modeling the problem with an integer programming formulation, with exponential worst-case complexity, we derive an optimal algorithm that has a linear time and space complexity. This somewhat surprising result allows selecting the best preemption points even in complex scenarios with a large number of potential preemption locations. Experimental results are also presented to show the effectiveness of the proposed approach in increasing the system schedulability.

A crucial objective in battery operated embedded systems is to work under the minimal power consumption that provides a desired level of performance. Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Management (DPM) are typical techniques used on processors and devices to reduce the power consumption through speed variations and power switching, respectively. The effectiveness of DVFS and DPM methods needs to be considered in the development of a power management policy for systems that consist of DVFS-enabled or DPM-enabled components. This paper explores how to efficiently reduce the power consumption of real-time applications with constrained resources, like energy, CPU and transmission bandwidth. A combined DVFS-DPM approach with a reduced complexity is proposed to make use of on-line strategies for embedded systems.

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.

Several servers have been proposed to schedule streams of a periodic jobs in the presence of other periodic tasks. Standard schedulability analysis has been extended to consider such servers. However, not much attention has been laid on computing the worst-case delay suffered by a given stream of jobs when scheduled via a server. Such analysis is essential for using servers to schedule hard real-time tasks. We illustrate, with examples, that well established resource models, such as supply bound function and models from Real-Time Calculus, do not tightly characterize servers. In this work, we analyze the server algorithm of the Constant Bandwidth Server and compute a provably tight resource model of the server. The approach used enables us to differentiate between the soft and hard variants of the server. A similar approach can be used to characterize other servers, the final results for which are presented.

Preemptive schedulers have been widely adopted in single processor real-time systems to avoid the blocking associated with the non-preemptive execution of lower priority tasks and achieve a high processor utilization. However, under fixed priority assignments, there are cases in which limiting preemptions can improve schedulability with respect to a fully preemptive solution. This is true even neglecting preemption overhead, as it will be shown in the paper. In previous works, limited-preemption schedulers have been mainly considered to reduce the preemption overhead, and make the estimation of worst-case execution times more predictable. In this work, we instead show how to improve the feasibility of fixed-priority task systems by executing the last portion of each task in a non-preemptive fashion. A proper dimensioning of such a region of code allows increasing the number of task sets that are schedulable with a fixed priority algorithm. Simulation experiments are also presented to validate the effectiveness of the proposed approach.

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.

Dynamic power management has become essential for battery-driven embedded systems. This paper explores how to efficiently and effectively reduce the energy consumption of a device (system) for serving multiple event streams. Considering two different preemptive scheduling, i.e., earliest deadline first and fixed priority, we propose new method to adaptively control the power mode of the device according to historical arrivals of events. Our method can not only tackle arbitrary event arrivals but also provide hard real-time guarantees with respect to both timing and backlog constraints. Simulation results are presented as well to demonstrate the effectiveness of our approach.

Limited preemption scheduling has been introduced as a viable alternative to non-preemptive and fully preemptive scheduling when reduced blocking times need to coexist with an acceptable context switch overhead. To achieve this goal, preemptions are allowed only at selected points of the code of each task, decreasing the preemption overhead and simplifying the estimation of worst-case execution parameters. Unfortunately, the problem of how to place these preemption points is rather complex and has not been solved. In this paper, a method is presented for the optimal placement of preemption points under simplifying conditions, namely, a fixed preemption overhead at each point. We will prove that if our method is not able to produce a feasible schedule, then no other possible preemption point placement (including non-preemptive and fully preemptive scheduling) can find a schedulable solution. The presented method is general enough to be applicable to both EDF and Fixed Priority scheduling, with limited modifications.

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).

A crucial objective in battery operated embedded systems is to work under the minimal power consumption that provides a desired level of performance. Dynamic Voltage Scaling (DVS) and Dynamic. Power Management (DPM) are typical techniques used on processors and devices to reduce the power consumption through speed variations and power switching, respectively. The effectivenes of both DVS and DPM needs to be considered in the development of a power management policy for a system that consists of both DVS-enabled and DPM-enabled components.

Many real-time applications are designed to work in different operating modes each characterized by different functionality and resource demands. With each mode change, resource demands of applications change, and static resource reservations may not be feasible anymore. Dynamic environments where applications may be added and removed online also need to adapt their resource reservations. In such scenarios, resource reconfigurations are needed for changing the resource reservations during runtime and achieve better resource allocations. There are a lot of results in the scientific literature of how to find the optimal amount of resources needed by an application in the different operating modes, or how an application can perform safe mode transitions. However, the problem of resource reconfigurations for systems with reservations has not been addressed. A resource scheduler should be reconfigured online in such a way that it still guarantees a certain amount of resources during the reconfiguration process, otherwise applications may miss deadlines. The paper proposes a framework for scheduling real-time applications through scheduling servers that provide resource reservations, and algorithms for changing the resource reservations online while still guaranteeing the feasibility of the system and the schedulability of applications. The framework analysis is integrated into a well-known modular performance analysis paradigm based on Real-Time Calculus. The results are illustrated with examples and a case study.

In the design of hard real-time systems, the feasibility of the task set is one of the primary concerns. However, in embedded systems with scarce resources, optimizing resource usage is equally important. In particular, the RAM is highly expensive in terms of chip space, and it heavily impacts the cost of the final product.

Schedulability analysis of real-time systems requires the knowledge of the worst-case execution time (WCET) of each computational activity. A precise estimation of such a task parameter is quite difficult to achieve, because execution times depend on many factors, including the task structure, the system architecture details, operating system features and so on. While some of these features are not under our control, selecting a proper scheduling algorithm can reduce the runtime overhead and make the WCETs smaller and more predictable. In particular, since task execution times can be significantly affected by preemptions, a number of scheduling methods have been proposed in the real-time literature to limit preemption during task execution. In this paper, we provide a comprehensive overview of the possible scheduling approaches that can be used to contain preemptions and present a comparative study aimed at evaluating their impact on task execution times.

Next-generation real-time systems will be increasingly based on heterogeneous MPSoC design paradigms, where predictability and performance will be key issues to deal with. Such issues can be tackled both at the hardware level, by embedding technologies such as TDMA busses, and at the OS level, where suitable scheduling techniques can improve performance and reduce energy consumption. Among these, elastic scheduling has been proved to provide satisfactory results by dynamically reducing task periods at run-time to ensure the highest utilization possible of the processors. On the other hand, elastic scheduling lowers the degree of predictability and increases the complexity of the analysis at the system level. This reduces the benefits given by the TDMA bus, which relies on the high level task analysis for a robust and efficient slot allocation. Starting from this consideration, we propose a system where the elastic scheduling and the TDMA bus work synergistically. We introduce a QoS-aware adaptive bus service which takes the best of both techniques, mitigating their drawbacks at the same time. We show how the overhead introduced by coordination action is small, and it is however dominated by the benefits of the overall strategy in terms of performance and predictability guarantees.

In the design of wearable robots, the possibility of dynamically regulating the mechanical output impedance is crucial to achieve an efficient and safe human-robot interaction and to produce useful emergent dynamical behaviors. In this paper we propose a Variable Impedance Differential Actuator (VIDA) for wearable robotics applications. The system comprises two actuators (one being an impedance-controlled rotary Series Elastic Actuator) connected through a Harmonic Drive in a differential configuration used to separately control output position and mechanical impedance. Design choices regarding the overall architecture and the single components are presented and discussed. The mechanical structure also comprises a custom-made torsion spring designed after a CAD/FEM optimization. An electromechanical model of the system has been developed and a control strategy, based on the equilibrium point approach, is simulated to validate the performances of the system against system requirements. The actuation architecture allows to implement a control strategy where an equilibrium position and impedance field are simultaneously and independently regulated. This is possible still adopting very simple control laws: two controls for position and impedance regulation of the two input shafts.

Limited preemption models have been proposed as a viable alternative between the two extreme cases of fully preemptive and non-preemptive scheduling. In particular, allowing preemption to occur only at predefined preemption points reduces context switch costs, simplifies the access to shared resources, and allows more predictable estimations of worst-case execution times. Current results related to such a model, however, exhibit two major deficiencies: (i) The exact response time analysis has a high computational complexity; (ii) The maximum lengths of then on-preemptive regions was not completely investigated in all possible scenarios. In this paper, we address the problem of scheduling a set of real-time tasks having fixed priorities and fixed preemption points. In particular, under specific but not restrictive assumptions we simplified the feasibility analysis and proposed an efficient feasibility test. Finally, an algorithm for computing the maximum length of fixed non-preemptive regions for each task is described, and some simulation experiments are presented to validate the proposed approach.

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.

The question whether preemptive systems are better than non-preemptive systems has been debated for a long time, but only partial answers have been provided in the real-time literature and still some issues remain open. In fact, each approach has advantages and disadvantages, and no one dominates the other when both predictability and efficiency have to be taken into account in the system design. In particular, limiting preemptions allows increasing program locality, making timing analysis more predictable with respect to the fully preemptive case. In this paper, we integrate the features of both preemptive and non-preemptive scheduling by considering that each task can switch to non-preemptive mode, at any time, for a bounded interval. Three methods (with different complexity and performance) are presented to calculate the longest non-preemptive interval that can be executed by each task, under fixed priorities, without degrading the schedulability of the task set, with respect to the fully preemptive case. The methods are also compared by simulations to evaluate their effectiveness in reducing the number of preemptions.

Power dissipation has constrained the performance boosting of modern computer systems in the past decade. Dynamic power management has been widely applied to change the system (or device) state dynamically to reduce the power consumption. This paper explores how to effectively reduce the energy consumption to handle event streams with hard real-time guarantees. We adopt Real-Time Calculus to describe the event arrival and resource service by arrival curves and service curves in the interval domain, respectively. We develop online algorithms to adaptively control the power mode of the device, postponing the processing of arrival events as late as possible. Profited from the worst-case interval-based abstraction, our algorithms can on one hand tackle arbitrary event arrivals (even with burstiness) and on the other hand guarantee hard real-time requirements in terms of both timing and backlog constraints. We also present simulation results to demonstrate the effectiveness of our algorithms.

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.

Token passing is a channel access technique used in several communication networks. Among them, one of the most effective solution for supporting both real-time traffic (synchronous messages) and non real-time traffic (asynchronous messages), is the so-called timed-token protocol. Recently, a new token passing protocol, called budget sharing token protocol (BuST), was proposed to improve the existing timed-token approaches in terms of synchronous bandwidth guarantee, while guaranteeing a minimum throughput for the asynchronous traffic. This paper analyzes the ability of BuST to manage realtime and non real-time traffic in comparison with the classic timed-token protocol and its modified version, under the normalized proportional allocation (NPA) scheme. We will show that BuST achieves higher guaranteed realtime bandwidth than the original timed-token protocol, and improves the service for the non real-time traffic respect to its modified version.

Token passing channel access mechanisms are used in several communication networks. An important class of token passing approaches are the so-called timed token protocols, which are able to manage both real-time traffic and non real-time traffic. Recently, a new token passing protocol, called Budget Sharing Token protocol (BuST), was proposed to improve the existing timed token approaches in terms of real-time bandwidth guarantee. This paper analyzes the ability of BuST to manage real-time and non real-time traffic under three different budget allocation schemes, and compares the performance of BuST with the original timed-token protocol (FDDI) and its modified version (FDDI-M). It is shown that BuST provides an higher guaranteed bandwidth for real-time traffic than FDDI, and improves the service for non real-time traffic with respect to FDDI-M. Moreover, new properties of the analyzed budget allocation schemes are provided for BuST, FDDI and FDDI-M. Finally, a set of simulation results are carried out to assess the performance of the three considered protocols.

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.

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.

Timed-token networks, such as FDDI, support both synchronous real-time traffic and non real-time traffic (asynchronous messages). The medium access scheme of FDDI guarantees up to one half of the total network bandwidth for synchronous communication. Further enhancements, such as FDDI-M, improve the bandwidth dedicated to real-time messages. However, the ability of timed-token protocols to guarantee synchronous message deadlines highly depends on specific Synchronous Budget Allocation (SBA) schemes. This paper introduces BuST, the Budget Sharing Token protocol which improves the management of periodic real-time traffic, while guaranteeing a minimum throughput for non real-time messages, with respect to existing techniques. We evaluate the performance of BuST, in comparison with FDDI and FDDI-M, considering a Synchronous Budget Allocation (SBA) scheme proposed in the literature, using the Worst-Case Achievable Utilization (WCAU) as performance metrics. We demonstrate that the performance achieved by BuST is better or, in a few cases, equal to FDDI and FDDI-M.

Transient overload conditions may cause unpredictable performance degradations in computer controlled systems if not properly handled. To prevent such problems, a common technique adopted in periodic task systems is to reduce the workload by enlarging activation periods. In a digital controller, however, the variation applied on the task period also affects the control law, which needs to be recomputed for the new activation rate. If computing a new control law requires too much time to be performed at runtime, a set of controllers has to be designed offline for different rates and the system has to switch to the proper controller in the presence of an overload condition. In this paper, we present a method for reducing the number of controllers to be designed offline, while still guaranteeing a given control performance. The proposed approach has been integrated with the elastic scheduling theory to promptly react to overload conditions. The effectiveness of the proposed approach has been verified through extensive simulation experiments performed on an inverted pendulum. In addition, the method has been implemented on a real inverted pendulum. Experimental results and implementation issues are reported and discussed

Applying classical dynamic voltage scaling (DVS) techniques to real-time systems running on processors with discrete voltage/frequency modes causes a waste of computational resources. In fact, whenever the ideal speed level computed by the DVS algorithm is not available in the system, to guarantee the feasibility of the task set, the processor speed must be set to the nearest level greater than the optimal one, thus underutilizing the system. Whenever the task set allows a certain degree of flexibility in specifying timing constraints, rate adaptation techniques can be adopted to balance performance (which is a function of task rates) versus energy consumption (which is a function of the processor speed). In this paper, we propose a new method that combines discrete DVS management with elastic scheduling to fully exploit the available computational resources. Depending on the application requirements, the algorithm can be set to improve performance or reduce energy consumption, so enhancing the flexibility of the system. A reclaiming mechanism is also used to take advantage of early completions. To make the proposed approach usable in real-world applications, the task model is enhanced to consider some of the real CPU characteristics, such as discrete voltage/frequency levels, switching overhead, task execution times nonlinear with the frequency, and tasks with different power consumption. Implementation issues and experimental results for the proposed algorithm are also discussed

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 most real-time applications, deadlines are artifices that need to be enforced to meet different performance requirements. For example, in periodic task sets, jitter requirements can be met by assigning suitable relative deadlines and guaranteeing the feasibility of the schedule. This paper presents a method (called minD) for calculating the minimum EDF-feasible deadline of a real-time task. More precisely, given a set of periodic tasks with hard real-time requirements, which is feasible under EDF, the proposed algorithm allows computing the shortest deadline that can be assigned to an arbitrary task in the set, or to a new incoming task (periodic or aperiodic), still preserving the EDF feasibility of the new task set. The algorithm has a pseudo polynomial complexity and handles arbitrary relative deadlines, which can be less than, equal to, or greater than periods

Applying classical dynamic voltage scaling (DVS) techniques to real-time systems running on processors with discrete voltage/frequency modes causes a waste of computational resources. In fact, whenever the ideal speed level computed by the DVS algorithm is not available in the system, to guarantee the feasibility of the task set, the processor speed must be set to the nearest level greater than the optimal one, thus underutilizing the system. Whenever the task set allows a certain degree of flexibility in specifying timing constraints, rate adaptation techniques can be adopted to balance performance (which is a function of task rates) vs. energy consumption (which is a function of the processor speed). In this paper, we propose a new method that combines discrete DVS management with elastic scheduling to fully exploit the available computational resources. Depending on the application requirements, the algorithm can be set to improve performance or reduce energy consumption, so enhancing the flexibility of the system. A reclaiming mechanism is also used to take advantage of early completions

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.

Low-level support of peripheral devices is one of the most demanding activities in a real-time operating system. In fact, the rapid development of new interface boards causes a tremendous effort at the operating system level for writing and testing low-level drivers for supporting the new hardware. The possibility of reusing legacy drivers in real-time systems would offer the great advantage of keeping the rate of changes with a small programming effort. Since typical legacy drivers are written to execute in a non-preemptive fashion, a suitable operating system mechanism is needed to protect real-time application tasks from unpredictable bursty interrupt requests. In this paper, we present a novel approach suitable for scheduling interrupt service routines. Main features of the method include: high priority of the handler, non preemptive execution, bandwidth reservation for the application tasks, and independence of the interrupt service policy from the scheduling policy adopted for the application tasks.

The management of ad-hoc networks raises interesting problems, that are particularly challenging for networks of mobile nodes. Considering the inherent complexity of these systems, the development of distributed applications relying on wireless communication protocols would be greatly simplified by the use of specific tools for supporting testing and step-by-step debugging. In this paper we describe WISE, a flexible interactive simulation environment for the development of wireless ad-hoc networks consisting of mobile units. A graphical interface allows the user to create/delete nodes, change their positions and parameters, and select specific mobility models in order to verify the network behavior in dynamic conditions. The simulator also provides a useful support for the verification of agreement protocols, synchronization algorithms and distributed scheduling, allowing the user to display a step-by-step evolution of the algorithms in a suitable graphical representation

We present a general CPU scheduling methodology for managing overruns in a real-time environment, where tasks may have different criticality, flexible timing constraints, shared resources, and variable execution times. The proposed method enhances, the constant bandwidth server (CBS) by providing two important extensions. First, it includes an efficient bandwidth sharing mechanism that reclaims the unused bandwidth to enhance task responsiveness. It is proven that the reclaiming mechanism does not violate the isolation property of the CBS and can be safely adopted to achieve temporal protection even when resource reservations are not precisely assigned. Second, the proposed method allows the CBS to work in the presence of shared resources. The enhancements achieved by the proposed approach turned out to be very effective with respect to classical CPU reservation schemes. The algorithm complexity is O(ln N), where N is the number of real-time tasks in the system, and its performance has been experimentally evaluated by extensive simulations.

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.

Ethernet was not originally developed to meet the requirements of real-time industrial automation systems and it was commonly considered unsuited for applications at the field level. Hence, several techniques were developed to make this protocol exhibit real-time behavior, some of them requiring specialized hardware, others providing soft-real-time guarantees only, or others achieving hard real-time guarantees with different levels of bandwidth efficiency. More recently, there has been an effort to support quality-of-service (QoS) negotiation and enforcement but there is not yet an Ethernet-based data link protocol capable of providing dynamic QoS management to further exploit the variable requirements of dynamic applications. This paper presents the FTT-Ethernet protocol, which efficiently supports hard-real-time operation in a flexible way, seamlessly over shared or switched Ethernet. The FTT-Ethernet protocol employs an efficient master/multislave transmission control technique and combines online scheduling with online admission control, to guarantee continued real-time operation under dynamic communication requirements, together with data structures and mechanisms that are tailored to support dynamic QoS management. The paper includes a sample application, aiming at the management of video streams, which highlights the protocol's ability to support dynamic QoS management with real-time guarantees.

Wireless communication technology is spreading quickly in almost all the information technology areas as a consequence of a gradual enhancement in quality and security of the communication, together with a decrease in the related costs. This facilitates the development of relatively low-cost teams of autonomous (robotic) mobile units that cooperate to achieve a common goal. Providing real-time communication among the team units is highly desirable for guaranteeing a predictable behavior while operating autonomously in unstructured environments. This paper proposes a MAC protocol for wireless communication that supports dynamic resource reservation for small teams of cooperative robots. The protocol uses a slotted time-triggered medium access transmission control that is collision-free, even in the presence of hidden nodes. The transmissions are scheduled according to the earliest deadline first scheduling policy. An adequate admission control guarantees the timing constraints of the team communication requirements, including when new nodes dynamically join or leave the team. The paper describes the protocol focusing on the consensus procedure that supports coherent changes in the global system. Finally, a set of simulation results are shown that illustrate the effectiveness of the proposed protocol.

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.

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.

In many real-time applications involving human-computer interactions, the quality of service also depends on the way performance is changed during workload variations. When human factors affect performance measurements, smooth rate transitions are always preferred with respect to abrupt parameter changes.In this paper, we propose a new methodology for automatically achieving smooth rate adaptation of a periodic task set during workload variations due to abrupt environmental or systems changes. Load balancing is performed using an elastic task model, according to which tasks utilizations are treated as damped springs with given elastic and damping co-efficients. The model has been implemented on top a real-time kernel and experimental results are reported to show the effectiveness of the proposed approach.

Next generation embedded systems will demand applications with increasing complexity, so a standard uniprocessor microcontroller architecture will likely be unsuited to support. A possible solution to cope with embedded applications with high computational requirements is to adopt multiple-processor-on-a-chip architectures. The paper discusses the problem of multiprocessor scheduling for asymmetric architectures composed of a general purpose CPU and a DSP. The challenging issue addressed in this work is to verify whether the use of a dedicated processor can effectively enhance the performance of an embedded system, still maintaining some kind of real-time guarantee. In particular, we provide a method for increasing the schedulability bound in the considered architecture, allowing a more efficient use of the computational resources.

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.

Recent advances in wireless technology have brought us closer to the vision of pervasive computing where sensors/actuators can be connected through a wireless network. Due to cost constraints and the dynamic nature of sensor networks, it is undesirable to assume the existence of base stations connected by a wired backbone. In this paper, we present a network architecture suitable for sensor networks along with a medium access control protocol based on earliest deadline first.

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.

In many real-time control applications, the task periods are typically fixed and worst-case execution times are used in schedulability analysis. With the advancement of robotics, flexible visual sensing using cameras has become a popular alternative to the use of embedded sensors. Unfortunately, the execution time of visual tracking varies greatly. In such environments, control tasks have a normally short computation time, but also an occasional long computation time; therefore, the use of worst-case execution time is inefficient for controlling performance optimization. Nevertheless, to maintain the control stability, we still need to guarantee the schedulability of the task set, even if the worst case arises. In this paper, we propose an integrated approach to control performance optimization and task scheduling for control applications where the execution time of each task can vary greatly. We present an innovative approach to overrun management that allows us to fully utilize the processor for optimizing the control performance and yet guaranteeing the schedulability of all tasks under worst-case conditions.

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.

This paper presents a dynamic configurable kernel architecture designed for supporting a simple implementation, integration and evaluation of scheduling algorithms. The main goal of the proposed architecture is to provide a platform for fast prototyping scheduling algorithms both for the CPU and for the devices. The kernel is fully modular in terms of scheduling policies, aperiodic servers, and concurrency control protocols, allowing applications to be developed independently from a particular system configuration. Finally, the system is compliant with the POSIX 1003.13 PSE52 specifications to simplify porting of application code developed for other POSIX compliant kernels.

Real-world industrial applications impose complex constraints, such as distribution, end-to-end deadlines, and jitter control on real-time systems. Most scheduling algorithms concentrate on single or limited combinations of constraints and requirements only. Offline scheduling resolves complex constraints, but provides only very limited flexibility. Online scheduling on the other hand, supports flexibility, resource reclaiming, and overload handling, but handling constraints such as distribution or end-to-end deadline can be costly, if not intractable. In the paper, we propose a method to efficiently handle soft real-time tasks in offline scheduled real-time systems using a total bandwidth server. In a first step, the offline scheduler resolves complex constraints, reduces their complexity, and provides for guaranteed available bandwidth. The constructed schedule is translated into independent tasks on single nodes with start-times and dead-line constraints only. These are then executed using earliest deadline first, total bandwidth server scheduling at runtime.

Resource Reservation is an effective technique for allocating CPU time to concurrent real-time applications running on a uniprocessor system. The most important advantage of reservation-based CPU allocation is that it enforces temporal isolation, thus ensuring that the behaviour of each application will not depend on the temporal requirement of the others. In this paper a stochastic analysis of a generic reservation system is presented, enabling application designers to compute the probability of respecting deadlines when the probability distributions of the interarrival and execution times are known.

A remarkable class of soft real time applications exhibits a very dynamical behaviour due to the variations in the treated data. Moreover, such programs have to be able to run on hundreds of different platforms. As a consequence, classical real time scheduling algorithms are not flexible enough since they are based on the exact knowledge of the tasks' timing parameters. Some of the approaches proposed so far in the literature guarantee temporal isolation, but they make a static assignment of resources to each task, which, once again, is based on an a priori knowledge. The authors propose a closed loop method for online adapting of the fraction of assigned resource to the task requirements. The approach is based on adaptive control techniques and has resulted in being effective in a significant set of real life experiments.

In many real time control applications, the task periods are typically fixed and worst case execution times are used in schedulability analysis. With the advancement of robotics, flexible visual sensing using cameras has become a popular alternative to the use of embedded sensors. Unfortunately, the execution time of visual tracking varies greatly. In such environments, control tasks have a normally short computation time but also an occasional long computation time; therefore, the use of worst case execution time is inefficient for controlling performance optimization. Nevertheless, to maintain the control stability, we still need to guarantee the task set, even if the worst case arises. We propose an integrated approach to control performance optimization and task scheduling for control applications where the execution time of each task can vary greatly. We create an innovative approach to elastic control that allows us to fully utilize the processor to optimize the control performance and yet guarantee the schedulability of all tasks under worst case conditions.

Presents a general scheduling methodology for managing overruns in a real-time environment, where tasks may have different criticalities and flexible timing constraints. The proposed method achieves isolation among tasks through a resource reservation mechanism which bounds the effects of task interference but which also performs efficient reclamation of the unused computation times in order to relax the utilization constraints imposed by isolation. The enhancements achieved by the proposed approach were found to be very effective with respect to classical reservation schemes. The performance has been evaluated by implementing the algorithm on a real-time kernel. The runtime overhead introduced by the scheduling mechanism has also been investigated with specific experiments, in order for this to be taken into account in the schedulability analysis. However, this overhead was found to be negligible in most practical cases.

A typical approach for realizing digital controllers is to synthesize the control law in the continuous-time domain and then to implement it as a set of periodic threads complying with tight temporal constraints. The strict respect of all deadlines can often be obtained only by selecting low activation rates which determine a remarkable performance degradation. On the other hand, many control systems are known to tolerate a certain amount of deadline misses. We realized a software tool which allows to numerically evaluate the quality of the control resulting from the scheduling. The tool has been applied to a robotic case study. Considering a meaningful set of trajectories, we have drawn experimental evidence that the use of soft real-time constraints on the threads leads to significant improvements in the system performance. The performance improvement is more evident if scheduling approaches like resource reservation schemes, able to separate the thread importance from its activation rate, are used.

This paper presents a probabilistic approach to guarantee the performance of a real-time system. While traditional real-time system analysis tends to guarantee that each task instance will complete its execution before its absolute deadline (hard guarantee), our approach permits to estimate the probability that it will happen. Such a statistical guarantee is performed based on inter-arrival and execution times probability distributions, rather than their worst case values. The advantage of a probabilistic approach is a more efficient usage of system resources, allowing to give a certain level of deadline guarantee to task sets that the classical schedulability analysis would reject.

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.

We present a novel scheduling approach for servicing soft aperiodic requests in a hard real time environment, where a set of hard periodic tasks is scheduled using the Earliest Deadline First algorithm. The main characteristic of the proposed algorithm is that it achieves full processor utilization and optimal aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Another interesting feature of the proposed algorithm is that it can easily be tuned to balance performance versus complexity for adapting it to different application requirements. Schedulability issues, performance results, and implementation complexity of the algorithm are discussed and compared with other methods, such as Background, the Total Bandwidth Server, and the Slack Stealer. Resource reclaiming and extensions to more general cases are also considered. Extensive simulations show that a substantial improvement can be achieved with a little increase of complexity, ranging from the performance of the Total Bandwidth Server up to the optimal behavior.

In certain real-time applications, ranging from multimedia to telecommunication systems, timing constraints can be more flexible than scheduling theory usually permits. In this paper, we deal with the problem of scheduling hybrid sets of tasks, consisting of firm periodic tasks (i.e. tasks with deadlines which can occasionally skip one instance) and soft aperiodic requests, which have to be served as soon as possible to achieve good responsiveness. We propose and analyze an algorithm, based on a variant of earliest-deadline-first scheduling, which exploits skips to minimize the response time of aperiodic requests. One of the most interesting features of our algorithm is that it can easily be tuned to balance performance vs. complexity, for adapting it to different application requirements. Extensive simulation experiments show the effectiveness of the proposed approach with respect to existing methods. Schedulability bounds are also derived to perform off-line analysis.

This paper focuses on the problem of providing efficient run-time support to multimedia applications in a real-time system, where two types of tasks can coexist simultaneously: multimedia soft real-time tasks and hard real-time tasks. Hard tasks are guaranteed based on worst case execution times and minimum interarrival times, whereas multimedia and soft tasks are served based on mean parameters. The paper describes a server-based mechanism for scheduling soft and multimedia tasks without jeopardizing the a priori guarantee of hard real-time activities. The performance of the proposed method is compared with that of similar service mechanisms through extensive simulation experiments and several multimedia applications have been implemented on the HARTIK kernel.

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.

In this paper we present a new scheduling approach for servicing soft aperiodic requests in a hard real-time environment, where a set of hard periodic tasks is scheduled using the Earliest Deadline First algorithm. The main characteristic of the proposed algorithm is that it achieves full processor utilization and optimal aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Another interesting feature of the algorithm is that it can easily be tuned to change its performance and complexity according to the application requirements. Schedulability issues, performance results, and implementation complexity of the algorithm are discussed and compared with other classical methods, such as Background, the Total Bandwidth Sewer (TBS), and the optimal EDL server. Extensive simulations show that a substantial improvement can be achieved with a little increase of complexity, ranging from the TBS performance up to the optimal behavior.

In certain real-time applications, ranging from multimedia to telecommunication systems, timing constraints can be more flexible than scheduling theory usually permits. For example, in video reception, missing a deadline is acceptable, provided that most deadlines are met. We deal with the problem of scheduling hybrid sets of tasks, consisting of firm periodic tasks (i.e., tasks with deadlines which can occasionally skip one instance) and soft aperiodic requests, which have to be served as soon as possible to minimize their average response time. We propose and analyze an algorithm, based on a variant of earliest deadline first scheduling, which exploits skips to enhance the response time of aperiodic requests. Schedulability bounds are also derived to perform off-line analysis.

In this paper, we describe an integrated environment to assist the development of hard real-time applications. It includes an interactive graphic interface which allows the user to describe the application requirements according to three hierarchical levels: the application level, the component level, and the object level. The development model we propose is based on an iterative process in which the real-time scheduling support is considered since the beginning of the design phases. Our graphic environment integrates several tools to analyse, test, and simulate the real-time application under development. In particular, the tools we have implemented are: a Design Tool, to describe the structure of the application, a Schedulability Analyser Tool (SAT), to verify off-line the feasibility of the schedule of a critical task set, a Scheduling Simulator, to test the average behaviour of the application, and a Maximum Execution Time (MET) estimator to bound the worst case duration of each task.

We present a comparative study among scheduling algorithms which use different priority assignments and different guarantee mechanisms to improve the performance of a real-time system during overload conditions. In order to enhance the quality of service, we assume that tasks are characterized not only by a deadline, but also by an importance value. The performance of the scheduling algorithm is then evaluated by computing the cumulative value gained on a task set, i.e. the sum of the values of those tasks that completed by their deadline. The purpose of this simulation study was twofold. Firstly, we wanted to discover which priority assignment is able to achieve the best performance in overload conditions. Secondly, we were interested in understanding how the pessimistic assumptions made in the guarantee test affect the performance of the scheduling algorithms, and how much a reclaiming mechanism can compensate this degradation. Simulation results show that, without any admission control, value-density scheduling performs best. Simple admission control based on worst case estimates of the load worsen the performance of all value based algorithms. EDF scheduling performs best if admission control is used along with a reclaiming mechanism that takes advantage of early completions. Finally, scheduling by deadline before overload and by value during overload works best in most practical conditions.

When hard periodic and firm aperiodic tasks are jointly scheduled in the same system, the processor workload can vary according to the arrival times of aperiodic requests. In order to guarantee the schedulability of the periodic task set, in overload conditions some aperiodic tasks must be rejected. In this paper we propose a technique that, in overload conditions, adds robustness to the joint scheduling of periodic and aperiodic tasks in systems with dynamic priorities. Our technique is based on an aperiodic server, called total bandwidth server, already proven effective in a previous work. Here the algorithm is first extended to efficiently handle firm aperiodic tasks and then integrated with a robust guarantee mechanism that allows to achieve graceful degradation in case of transient overloads. Extensive simulations show that the proposed new algorithm is effective in all workload conditions.

We present four new on-line algorithms for servicing soft aperiodic requests in real-time systems, where a set of hard periodic tasks is scheduled using the Earliest Deadline First (EDF) algorithm. All the proposed solutions can achieve full processor utilization and enhance aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Operation of the algorithms, performance, schedulability analysis, and implementation complexity are discussed and compared with classical alternative solutions, such as background and polling service. Extensive simulations show that algorithms with contained run-time overhead present nearly optimal responsiveness. A valuable contribution of this work is to provide the real-time system designer with a wide range of practical solutions which allow to balance efficiency against implementation complexity.>

This paper presents a hard real-time kernel, called HARTIK, specifically designed to handle robotics applications with predictable response time. The main relevant features of this kernel include: direct specification of time constraints, such as periods and deadlines; preemptive scheduling; coexistence of hard soft, and non real-time tasks, separation between time constraints and importance; deadline tolerance; dynamic guarantee of critical tasks; and graceful degradation in overload conditions. The functionality of the kernel is then shown by presenting a concrete example of a robot system that has to explore unknown objects by visual and force feedback.>

A sensor-based robot control technique for handling non-contact/transitions in a partially unknown environment is presented. Desired contacts with the environment were handled by integrating proximity and force/torque sensing information to improve efficiency in terms of speed and safety. By detecting in advance the target surface to be reached, the algorithm plans the trajectory to impose a smooth velocity profile during the approach, as well as to maintain the impact forces at the desired level by means of force control. A smooth transition between free and constrained motion control was obtained by means of weight functions depending on the measured distance between the robot end-effector and the target to be reached.>

Describes the architecture and the components of a robot workstation designed to investigate active perception, with particular emphasis on tactile sensing procedures. The workstation is centered around a multifunctional finger-like probe equipped with different types of sensors, and a PUMA 562 manipulator to carry out exploration. The system operates under the control of a distributed architecture in which different sensory information is processed in parallel, whereas exploratory parameters (contact force, direction, velocity) are set in real time. Dedicated exploratory procedures allow to extract specific object features and to sort different objects out of a given set.>