Designing and deploying real-time computing pipelines efficiently on modern embedded platforms is increasingly challenging due to the growing complexity of hardware architectures, often featuring multi-core processors, frequency scaling capabilities, heterogeneous cores for enhanced power efficiency, and hardware accelerators. OpenMP is a prominent tool for parallelizing applications on multi-core platforms and is gaining increasing adoption in the domain of real-time systems. However, providing sound performance guarantees on the timing behavior of complex parallel computations organized as graph structures on heterogeneous platforms, while achieving optimal or near-optimal energy efficiency, is all but trivial. This paper tackles this problem by proposing a methodology to deploy and analyze both traditional parallel real-time applications and OpenMP parallel applications, modeled as directed acyclic graphs (DAGs) and coexisting on the same heterogeneous platform. Specifically, the approach targets asymmetric multi-core platforms with frequency scaling capabilities, with the aim of minimizing energy consumption while guaranteeing end-to-end latency constraints via schedulability analysis. The proposed approach features an optimal solver based on a mixed-integer quadratic constrained programming formulation, and a computationally efficient heuristic to extract high-quality solutions with reduced solving time. The concept is experimentally validated using randomly generated sets of DAGs, optimized by the two techniques and deployed using an OpenMP-based DAG synthetic benchmark on Linux running on an embedded board. Results demonstrate that the methodology enables energy-efficient deployment of mixed traditional and OpenMP real-time DAG applications while preserving end-to-end latency guarantees.

Containerisation is becoming a cornerstone of modern distributed systems, thanks to their lightweight virtualisation, high portability, and seamless integration with orchestration tools such as Kubernetes. The usage of containers has also gained traction in real-time cyber-physical systems, such as software-defined vehicles, which are characterised by strict timing requirements to ensure safety and performance. Nevertheless, ensuring real-time execution of co-located containers is challenging because of mutual interference due to the sharing of the same processing hardware. Existing parallel computing frameworks such as Ray and its Kubernetes-enabled variant, KubeRay, excel in distributed computation but lack support for scheduling policies that allow guaranteeing real-time timing constraints and CPU resource isolation between containers, such as the SCHED_DEADLINE policy of Linux. To fill this gap, this paper extends Ray to support real-time containers that leverage SCHED_DEADLINE. To this end, we propose KubeDeadline, a novel, modular Kubernetes extension to support SCHED_DEADLINE. We evaluate our approach through extensive experiments, using synthetic workloads and a case study based on the MobileNet and EfficientNet deep neural networks. Our evaluation shows that KubeDeadline ensures deadline compliance in all synthetic workloads, adds minimal deployment overhead (in the order of milliseconds), and achieves lower worst-case response times, up to 4 times lower, than vanilla Kubernetes under background interference.

Conventional cloud services and infrastructures are mainly designed to maximize utilization of resources and provide best-effort Quality-of-Service levels. However, many emerging use cases in both public and private cloud computing scenarios are time-critical in nature. For example, automated vehicles, smart cities, and automated factories, are all application domains characterized by the need for highly reliable and consistent low-latency services. The incorporation of predictable execution properties in cloud solutions is essential to meet these requirements. This paper provides an overview of the current research landscape in cloud computing, summarizing the key aspects to enable support of time-critical applications. The paper explores various levels of the typical cloud software stack: machine virtualization and containers, resource management and orchestration, fault tolerance, serverless computing, data storage and management, and communications.

This paper tackles the problem of optimal configuration and deployment of fault-tolerant time-critical service chains with arbitrary DAG-alike topologies. We propose RTilience, designed according to a scalable cloud microservice paradigm, and prototyped on top of the well-known Kubernetes cloud orchestrator. It features real-time reservation scheduling of containers to guarantee temporal isolation of time-critical tasks, leading to fine-grained control of compute latencies, while allowing for sharing physical CPUs among containers. A distributed routing library, ReqRoute, is configured with a timeout and primary and secondary routes, enabling autonomous and decentralized handling of failing requests. The routes are configured by a centralized controller that performs admission control, resource management of microservice instances, task placement, and fault detection and recovery, extending the features available in Kubernetes. Admission control is based on a theoretical framework enclosing a worst-case performance model for the experienced end-to-end response-time under various fault handling options, and an optimization framework that computes the optimum resource allocation for admitted services. Extensive experimentation of the proposed solution has been performed with synthetic examples, and an autonomous transport robot use-case, verifying that end-to-end deadlines are effectively respected, even in presence of high fault rates of individual microservice instances, according to the theoretical expectations. RTilience is made available as open-source software, released under a MIT license.

Real-time virtualization is currently a hot topic, and there is much ongoing research on real-time Virtual Machines and hypervisors. However, most of the previous research focused either on reducing the latencies introduced by the virtualization stack (hypervisor, host Operating System, Virtual Machine scheduling, etc...) or analyzing the virtual CPU scheduling algorithms. Only a few works investigated the impact of the guest Operating System architecture on real-time performance or considered multiple performance metrics (latency, schedulability, startup times, resource consumption) at the same time. This paper compares various features of different virtualization technologies and guest Operating Systems, evaluating their suitability for serving real-time applications. The results indicate that solutions based on KVM (and an appropriate microvm) and the OSv unikernel can be considered viable alternatives to more traditional VMs or containers.

This work presents a model for designing and deploying time-critical, cloud-native applications under fault conditions. Our model considers the interactions and interferences among service components, as well as the possible occurrence of faults. Given a set of to-be-deployed applications with precise temporal constraints and a predefined configuration of the service components, we devised an optimizer to verify at design time if the cloud services guarantee compliance with the timing constraints while minimizing the resources needed to achieve fault tolerance.

This paper presents the Fault-Tolerant Real-Time Cloud (FTRTC) project that aims to design cloud computing infrastructures capable of hosting highly reliable and real-time applications. These applications are characterized by strict timing and reliability constraints, as well as critical failure scenarios. For instance, such requirements are commonly found in the context of Industry 4.0. We present a formalization of the problem of designing real-time cloud applications supporting an adjustable level of fault tolerance throughout their distributed execution in a cloud infrastructure. The contributions presented in this paper indicate important research directions when building cloud infrastructures able to supporting ultra-reliable real-time applications.

In this article, the problem of temporal isolation among containerized software components running in shared cloud infrastructures is tackled, proposing an approach based on hierarchical real-time CPU scheduling. This allows for reserving a precise share of the available computing power for each container deployed in a multi-core server, so to provide it with a stable performance, independently from the load of other co-located containers. The proposed technique enables the use of reliable modeling techniques for end-to-end service chains that are effective in controlling the application-level performance. An implementation of the technique within the well-known OpenStack cloud orchestration software is presented, focusing on a use-case framed in the context of network function virtualization. The modified OpenStack is capable of leveraging the special real-time scheduling features made available in the underlying Linux operating system through a patch to the in-kernel process scheduler. The effectiveness of the technique is validated by gathering performance data from two applications running in a real test-bed with the mentioned modifications to OpenStack and the Linux kernel. A performance model is developed that tightly models the application behavior under a variety of conditions. Extensive experimentation shows that the proposed mechanism is successful in guaranteeing isolation of individual containerized activities on the platform.

This paper provides an open implementation and an experimental evaluation of an adaptive partitioning approach for scheduling real-time tasks on symmetric multicore systems. The proposed technique is based on combining partitioned EDF scheduling with an adaptive migration policy that moves tasks across processors only when strictly needed to respect their temporal constraints. The implementation of the technique within the Linux kernel, via modifications to the SCHED_DEADLINE code base, is presented. An extensive experimentation-has been conducted by applying the technique on a real multi-core platform with several randomly generated synthetic task sets. The obtained experimental results highlight that the approach exhibits a promising performance to schedule real-time workloads on a real system, with a greatly reduced number of migrations compared to the original global EDF available in SCHED_DEADLINE.

This work presents a framework for evaluating the performance of various virtual switching solutions, each widely adopted on Linux to provide virtual network connectivity to containers in high-performance scenarios, like in Network Function Virtualization (NFV). We present results from the use of this framework for the quantitative comparison of the performance of software-based and hardware-accelerated virtual switches on a real platform with respect to a number of key metrics, namely network throughput, latency and scalability.

This paper deals with the problem of performance stability of software running in shared virtualized infrastructures. The focus is on the ability to build an abstract performance model of containerized application components, where real-time scheduling at the CPU level, along with traffic shaping at the networking level, are used to limit the temporal interferences among co-located workloads, so as to obtain a predictable distributed computing platform. A model for a simple client-server application running in containers is used as a case-study, where an extensive experimental validation of the model is conducted over a testbed running a modified OpenStack on top of a custom real-time CPU scheduler in the Linux kernel.

This paper tackles the problem of admitting real-time tasks onto a symmetric multi-processor platform, where a partitioned EDF-based scheduler is used. We propose to combine a well-known utilization-based test for the first-fit partitioning strategy, with a simple heuristic based on the number of tasks and exact knowledge of the utilization of the first few biggest tasks. This results in an effective and efficient test improving on the state of the art in terms of admitted tasks, as shown by extensive tests performed on task sets generated using the widely adopted randfixedsum algorithm.

Summary Model‐based development (MBD) holds the promise to capture potential timing problems in embedded software during the early phases of the development, securing the production of bug‐free embedded software. For most MBD approaches, the source code is just an intermediate artifact that can be generated automatically from the models. This assumption clashes with an undeniable fact: a large share of the commercial embedded software exploits existing libraries or is developed using C/C++ natively. A way to reconcile the ambitions of MBD with the use of a programming language is by offering new language constructs and an innovative compilation tool‐chain that prevents model error and timing problems “by construction.” However, the persistent popularity of C/C++ among embedded programmers and the limited availability of tools have severely limited the uptake of alternative programming languages for embedded software. Therefore, we propose an original route. Our language proposal, named Tice, has been shaped as a C++ active library. Tice retains full compatibility with existing C++ code, which can be integrated easily into new Tice‐based projects. The enforcement of Tice syntax and semantics can be made by a standard C++ compiler, forgoing the need for new tools. In this article, we describe Tice's syntax, semantics, and model of computation and communication. We demonstrate Tice's practical applicability on an industrial scale use‐case and give ample evidence for Tice's efficient compilation using off‐the‐shelf C++ compilers. Finally, we show Tice's code generation process.

The recent developments in virtualisation technologies have made feasible the execution of complex and performance critical applications in virtual machines. When such applications are characterised by real-time constraints, the virtual machines must be scheduled predictably over the physical cores. Several works in real-time literature have analysed such a scenario, proposing advance scheduling and design techniques to respect the application constraints. However, most of the previous works focused on scheduling algorithms and theoretical analysis, without considering important implementation details such as the latencies introduced by the virtualisation mechanism. The paper, which can be seen as a complement for such works, investigates the latencies introduced by two of the most widely used hypervisors, Xen and KVM, so that previous theoretical analysis and algorithms can be used in practice.

This paper presents preliminary results from our on-going research for ensuring stable performance of co-located distributed cloud services in a resource-efficient way. It is based on using a real-time CPU scheduling policy to achieve a fine-grain control of the temporal interferences among real-time services running in co-located containers. We present results obtained applying the method to a synthetic application running within LXC containers on Linux, where a modified kernel has been used that includes our real-time scheduling policy.

This paper highlights inefficiencies in modern cloud infrastructures due to a distance between the research on high-level cloud management / orchestration and the research on low-level kernel and hypervisor mechanisms. Our position about this issue is that more research is needed to make these two worlds talk to each other, providing richer abstractions to describe the low-level mechanisms and automatically map higher-level descriptions and abstractions to configuration and performance tuning options available within operating systems and kernels (both host and guest), as well as hypervisors.

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

Summary In recent years, series of important achievements have paved the way for the introduction of probabilistic analysis in the area of soft real‐time systems design. In this article, we present an extensible design tool, called PROSIT, which facilitates the access to this technology for a potentially large number of researchers and industrial practitioners. The tool enables the probabilistic analysis of the temporal performance of a real‐time task under fixed‐priority and resource reservations scheduling algorithms. For resource reservations, the tool also offers an automatic procedure for the synthesis of scheduling parameters that optimize a quality metric related to the probabilistic behavior of the tasks.

This paper presents a methodology to model and check the behavior of a part of the Linux kernel by applying automaton theory and in-kernel tracing from real execution. It is possible to check that the state transitions of the kernel during a real execution match with the allowed ones, according to the formal model. The scope of the paper is limited to the IRQ/NMI subsystem of the Linux kernel.

A large class of modern real-time applications exhibits important variations in the computation time and is resilient to occasional deadline misses. In such cases, probabilistic methods, in which the probability of a deadline miss can be guaranteed and related to the scheduling design choices, can be an important tool for system design. Several techniques for probabilistic guarantees exist for the resource reservation scheduler and are based on the assumption that the process describing the application is independent and identically distributed (i.i.d.). In this paper, we consider a particular class of robotic application for which this assumption is not verified. For such applications, we have verified that the computation time is more faithfully described by a Markov model. We propose techniques based on the theory of hidden Markov models to extract the structure of the model from the observation of a number of execution traces of the application. As a second contribution, we show how to adapt probabilistic guarantees to a Markovian computation time. Our experimental results reveal a very good match between the theoretical findings and the experiments.

Summary During the last decade, there has been a considerable interest in using Linux in real‐time systems, especially for industrial control. The simple and elegant design of Linux guarantees reliability and very good performance, while its open‐source license allows to modify and change the source code according to the user needs. However, Linux has been designed to be a general‐purpose operating system. Therefore, it presents some issues like unpredictable latencies and limited support for real‐time scheduling. In this paper, we present our experience in the design and implementation of the real‐time scheduler that has been recently included in the Linux kernel. The scheduler is based on the Resource Reservation paradigm, which allows to enforce temporal isolation between the running tasks. We describe the genesis of the project, the challenges we have encountered, the implementation details and the API offered to the programmers. Then, we show the experimental results measured on a real hardware. Copyright © 2015 John Wiley & Sons, Ltd.

We show a methodology for the computation of the probability of deadline miss for a periodic real-time task scheduled by a resource reservation algorithm. We propose a modelling technique for the system that reduces the computation of such a probability to that of the steady state probability of an infinite state Discrete Time Markov Chain with a periodic structure. This structure is exploited to develop an efficient numeric solution where different accuracy/computation time trade-offs can be obtained by operating on the granularity of the model. More importantly we offer a closed form conservative bound for the probability of a deadline miss. Our experiments reveal that the bound remains reasonably close to the experimental probability in one real-time application of practical interest. When this bound is used for the optimisation of the overall Quality of Service for a set of tasks sharing the CPU, it produces a good sub-optimal solution in a small amount of time.

Summary This paper describes an approach to perform reproducible performance tests on virtual routers, comparing different virtual routing architectures, different software versions and configurations. The presented approach is based on VRKit, a software tool that allows to build pre‐configured bootable virtual router images with the desired characteristics. Design decisions are described, and some usage examples are presented, showing how the tool can be used for research on virtual routing, facilitating performance comparison of various virtual router implementations. Copyright © 2013 John Wiley & Sons, Ltd.

Peer-to-peer live-streaming (P2P-TV) systems' goal is disseminating real-time video content using peer-to-peer technology. Their performance is driven by the overlay topology, i.e., the virtual topology that peers use to exchange video chunks. Several proposals have been made in the past to optimize it, yet few experimental studies have corroborated results. The aim of this paper is to provide a comprehensive experimental comparison based on PeerStreamer in order to benchmark different strategies for the construction and maintenance of the overlay topology in P2P-TV systems. We present only experimental results in which fully distributed strategies are evaluated in both controlled experiments and the Internet using thousands of peers. Results confirm that the topological properties of the overlay have a deep impact on both user quality of experience and network load. Strategies based solely on random peer selection are greatly outperformed by smart yet simple and actually implementable strategies. The most performing strategy we devise guarantees to deliver almost all chunks to all peers with a playout delay as low as 6 s even when system load approaches 1, and in almost adversarial network scenarios. PeerStreamer is open-source to make results reproducible and allow further research by the community.

Today's rapidly evolving network ecosystem, characterized by increasing traffic volumes, service heterogeneity and mutating cyber-threats, calls for new approaches to packet processing to address key issues such as scalability, flexibility, programmability and fast deployment. To this aim, this paper explores a new direction to packet processing by pushing forward functional programming principles in the definition of a ''software defined networking'' paradigm.

This paper shows how to use an open virtualisation architecture to analyse and improve the forwarding performance of a virtual router. In particular, the forwarding performance of the Linux kernel running inside a KVM virtual machine and the performance of some more advanced architectures based on virtual routers aggregation are analysed, showing how increasing the number of used CPU core can improve performance and how properly setting the CPU affinity of the various virtualisation activities affects virtual router throughput.

This paper presents a new Model of Computation (MoC) for real-time tasks used in control systems. This new model, named continuous stream task model, relaxes some of the constraints imposed by the traditional hard and soft real-time task models. A key advantage of the model is the possibility to easily analyse the probabilistic evolution of the delays. This leads to an easy formalisation of necessary and sufficient conditions for the stochastic stability of the closed loop system producing considerable savings in the amount of CPU bandwidth required to stabilise the system. This fact is confirmed by an extensive set of simulations.

The application of a resource reservation scheduler to soft real -- time systems requires effective means to compute the probability of a deadline miss given a particular choice for the scheduling parameters. This is a challenging research problem, for which only numeric solutions, complex and difficult to manage, are currently available. In this paper, we adopt an analytical approach. By using an approximate and conservative model for the evolution of a periodic task scheduled through a reservation, we construct a closed form lower bound for the probability of a deadline miss. Our experiments reveal that the bound remains reasonably close to the experimental probability for many real -- time applications of interest.

This paper presents an efficient algorithm for providing probabilistic guarantees in soft real-time systems using resource reservations. We use a conservative model for the temporal evolution of a resource reservation, which has a particular structure - a quasi birth death process - enabling an efficient computation of the stationary probability of respecting deadlines. We show the accuracy and the efficiency of the method in a large set of experiments.

P2P-TV systems performance are driven by the overlay topology that peers form. Several proposals have been made in the past to optimize it, yet little experimental studies have corroborated results. The aim of this work is to provide a comprehensive experimental comparison of different strategies for the construction and maintenance of the overlay topology in P2P-TV systems. To this goal, we have implemented different fully-distributed strategies in a P2P-TV application, called Peer-Streamer, that we use to run extensive experimental campaigns in a completely controlled set-up which involves thousands of peers, spanning very different networking scenarios. Results show that the topological properties of the overlay have a deep impact on both user quality of experience and network load. Strategies based solely on random peer selection are greatly outperformed by smart, yet simple strategies that can be implemented with negligible overhead. Even with different and complex scenarios, the neighborhood filtering strategy we devised as most performing guarantees to deliver almost all chunks to all peers with a play-out delay as low as only 6s even with system loads close to 1.0. Results are confirmed by running experiments on PlanetLab. PeerStreamer is open-source to make results reproducible and allow further research by the community.

SUMMARY This paper presents an evaluation of the impact of the so‐called operating system (OS) latencies on the performance of a synchronous network based on global time coordination. The concept of end‐to‐end latency was first defined by extending the concept of latency used to evaluate the performance of real‐time systems and the end‐to‐end latency provided by a general‐purpose OS was measured as a benchmark. Finally, real‐time techniques were used to reduce the worst‐case values of such a latency, showing how a gateway between synchronous and asynchronous networks can be implemented by using commercial‐off‐the‐shelf hardware and a proper software stack (based on a real‐time version of Linux). The use of a real‐time OS is still a nontrivial task, which requires experience and the analysis of the specific application to devise the proper techniques to be applied. This work dissects the problem of OS‐to‐network data transfer (and vice versa) identifying the key sources of latencies and delay jitter, and solving each problem with the application of a proper technique. Copyright © 2011 John Wiley & Sons, Ltd.

Multimedia applications are often executed on standard personal computers. The absence of established standards has hindered the adoption of real-time scheduling solutions in this class of applications. Developers have adopted a wide range of heuristic approaches to achieve an acceptable timing behavior but the result is often unreliable. We propose a mechanism to extend the benefits of real-time scheduling to legacy applications based on the combination of two techniques: (1) a real-time monitor that observes and infers the activation period of the application, and (2) a feedback mechanism that adapts the scheduling parameters to improve its real-time performance.

Peer-to-peer (P2P) and cloud computing, two of the Internet trends of the last decade, hold similar promises: the (virtually) infinite availability of computing and storage resources. But there are important differences: the cloud provides highly-available resources, but at a cost; P2P resources are for free, but their availability is shaky. Several academic and commercial projects have explored the possibility of mixing the two, creating a large number of peer-assisted applications, particularly in the field of content distribution, where the cloud provides a highly-available and persistent service, while P2P resources are exploited for free whenever possible to reduce the economic cost. While executing active servers on elastic computing facilities like Amazon EC2 and pairing them with user-provided peers is definitely one way to go, this paper proposes a novel approach that further reduces the economic cost. Here, a passive storage service like Amazon S3 is exploited not only to distribute content to clients, but also to build and manage the P2P network linking them. An effort is made to guarantee that the read/write load imposed on the storage remains constant, regardless of the number of peers/clients. These two choices allows us to keep the monetary cost of the cloud always under control, in the presence of just one peer or with a million of them. We show the feasibility of our approach by discussing two cases studies for content distribution: the Dilbert's comic strips and the hourly News Update podcast from CNN.

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

We present an approach for adaptive scheduling of soft real-time legacy applications (for which no timing information is exposed to the system). Our strategy is based on the combination of two techniques: 1) a real-time monitor that observes the sequence of events generated by the application to infer its activation period, 2) a feedback mechanism that adapts the scheduling parameters to ensure a timely execution of the application. By a thorough experimental evaluation of an implementation of our approach, we show its performance and its efficiency.

Splitting a P2P video distribution in multiple media flows with different priorities is an interesting approach for developing flexible and adaptive streaming systems, ranging from VoD to TV. Such an approach can both yield satisfactory quality to all end users and be light in network resources usage, because low-priority flows can be discarded a-priori when target peers do not have enough resources to receive them. This paper focuses on chunk-based video distribution in unstructured meshes, adopting a push strategy (the sender takes the scheduling decision) based on buffer map exchange to avoid sending duplicated chunks. A deadline-based scheduling algorithm is proposed, where different flows of chunks are prioritized using different deadline postponing parameters for each flow. Some experimental results show good differentiation properties and streaming performance much better than with strict priority enforcement. Also, PSNR measures on real video streams show improvements compared to both strict priority and single stream distribution.

P2P TV and video streaming are among the most bandwidth-hungry applications running over the Internet. One of the main reasons is that the scheduling of information transfer between peers is extremely aggressive and does not take network characteristics into account. Moreover, schedulers are not designed to be robust and configurable, so that their performance is greatly affected by networking conditions. This work first analyzes the impact of network heterogeneity on the streaming performance and then proposes a novel, robust, configurable, network-aware scheduler that outperforms the other schedulers in all networking scenarios.

P2P TV distribution is going commercial, and the video quality delivered to users becomes of the utmost importance. However, the impact of P2P distribution on the video quality is not completely understood yet, especially in live streaming situations. This work addresses the impact of P2P distribution when the delay of the playout is limited, as it must be in any true live TV service. A methodology for the evaluation (using standard objective video quality metrics) is proposed, showing that different ways of grouping frames in chunks for the distribution can lead to very different quality when the system is overloaded.

P2P-TV systems have become part of the Internet landscape (See for instance http://www.pplive.com, http://www.soapcast.com, http://www.tvants.com, and many others). The architecture of these (normally proprietary) applications is generally receiver-driven, in that receivers actively search for suitable peers to download from, trying to maximize their performance. This results in very aggressive applications that generate huge and non optimized traffic loads. The demo summarized in this short paper shows the impact of various P2P streaming options and the efficiency of the Napa-Wine approach (compared to more traditional approaches) by running real streaming clients in realistic conditions. To make this comparison possible, the software developed in Napa-Wine is highly modular and configurable, allowing the user to test different topology management and chunk trading techniques developed within the Napa-Wine project, as well as to configure it to mimic other chunk/peer selection strategies known from literature.

Some real-time kernels (such as a recent real-time version of Linux) permit to execute interrupt handlers in dedicated threads, to control their interference on real-time applications. However, from the stand-point of real-time analysis, such threads are challenging and cannot be dealt with in the traditional ways. Furthermore, the application of traditional scheduling solutions (such as fixed priorities) proves ineffective in striking a good trade-off between predictability and hardware performance. This paper shows how the problem can be tackled by using the resource reservation abstraction and an appropriate model for schedulability analysis.

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

This paper reports some experiences in providing service guarantees to real-time (RT) applications running in virtual machine (VM), showing how proper scheduling is a necessary condition for a predictable execution. In particular, resource reservation techniques allow to cope with some of the overhead and unpredictabilities experienced when executing multiple VMs on the same host.

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

A remarkable research activity has been carried out in the past few years to support real-time applications with appropriate scheduling solutions. Unfortunately, most of such techniques can be used only if real-time applications use a specialized API, and if some important information (such as the worst-case execution-time) are knownapriori. In this paper, we present a novel technique, the legacy feedback scheduler (LFS), for a class of legacy applications that need the support of a real-time scheduler but are not written using a specialized API and have unknown or varying execution requirements. The approach is based on the combination of a resource reservation scheduler and a feedback-based adaptation mechanism for identifying the correct scheduling parameters.

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

A remarkable research activity has been carried out in the past few years to support real-time applications by means of appropriate scheduling solutions. For scarcely known or highly dynamic applications, feedback scheduling has emerged as an effective technique to tune the scheduling parameters, based on a run-time monitoring of the timing performance of the application. This technique requires a specialised API for the application and is therefore unfit for legacy applications, for which the source code is not accessible. In this paper, we present an alternative technique, called legacy feedback scheduling (LFS), for feedback based adaptation of the scheduling parameters. LFS does not make any assumption on the programming model of the application and is applicable to legacy applications. Throughout the paper, we carry out a comparison between a well settled technique (called adaptive reservations), which leverages a particular structure for the application, and LFS. The conclusion is that the greater generality and flexibility of the LFS has to be paid in terms of timing performance. However, LFS successfully identifies the ldquoaveragerdquo scheduling parameters needed to sustain a given execution rate.

In this paper, we consider the problem of providing QoS guarantees to the execution of applications using the X11 window system. In particular, we offer a system level analysis of the issues encountered when using X11 to serve realtime applications. By using a tracer developed for the purpose we analyse in depth the internal behaviour of the system. The result of the analysis puts on display the adverse effect played by a non real-time scheduler on the performance of time-sensitive applications. Based on this analysis, we propose an alternative solution based on the CBS scheduler and prove its effectiveness by an extensive set of experiments on real hardware.

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

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

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.

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

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

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

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.

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.

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

The resource-sharing problem in priority-driven realtime systems has been studied at length, with the result that some effective and practical solutions are available for both fixed-priority and dynamic-priority systems. In recent years, real-time operating systems have begun to support the resource reservation paradigm, providing a "temporal isolation" abstraction. However the problem of sharing logical resources across reserved applications has not been extensively studied. In this paper we consider both the theoretical and practical implications of such resource-sharing in reservation-based systems. Moreover we provide some experimental results from the implementation of our proposed schemes in Linux/RK, a "resource kernel" that supports reservations.

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.

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