Abstract A hard real-time system cannot miss any deadline. A weakly-hard real-time system, on the contrary, is designed to tolerate a specific number of deadline misses. For instance, the $$\texttt {{\textbf {AnyMiss}}}\,(2, 300)$$ AnyMiss ( 2 , 300 ) weakly-hard constraint stipulates that in every window of 300 consecutive jobs, at most 2 deadlines are missed. The weakly-hard model is the state-of-the-art for industrial dependability-by-design of control systems that tolerate deterministic failures. Weakly-hard constraints correspond to regular languages. The size of the minimal finite state machine that recognizes whether a string satisfies the constraint (about 45 k states for $$\texttt {{\textbf {AnyMiss}}}\,(2, 300)$$ AnyMiss ( 2 , 300 ) ) is a notorious impediment for the verification of control system properties. This paper discusses an over-approximation of the language that allows us to provide sound safety guarantees for control systems under deadline misses that would be out of reach using the minimal finite state machine. We present a compressed language acceptor and prove that it simulates the original finite state machine. We study language cardinality properties, and report on empirical results that show how the new acceptor can be embedded in the control design workflow, leading to verifying safety for systems for which the state-of-the-art tools do not provide answers.

Deadline misses are more common in real-world systems than one may expect. The weakly-hard task model has become a standard abstraction to describe and analyze how often these misses occur, and has been especially used in control applications. Most existing control approaches check whether a controller manages to stabilize the system it controls when its implementation occasionally misses deadlines. However, they usually do not incorporate deadline-overrun knowledge during the controller synthesis process. In this paper, we present a framework that explicitly integrates weakly-hard constraints into the control design. Our method supports various overrun handling strategies and guarantees stability and performance under weakly-hard constraints. We validate the synthesized controllers on a Furuta pendulum, a representative control benchmark. The results show that constraint-aware controllers significantly outperform traditional designs, demonstrating the benefits of proactive and informed synthesis for overrun-aware real-time control.

This is the Replicated Computational Results (RCR) Report for the article “ Testing Abstractions for Cyber-Physical Control Systems .” The article empirically studies how substituting different components in Cyber-Physical Systems (CPSs) testing with simulators impacts the fault-exposition. This RCR report describes the artefacts used in the article, how to use the testing setups used in the article and how to reproduce the empirical results of the article.

This paper presents an in-depth analysis of the stability and performance of control systems experiencing sensor timing misalignments, a common challenge in practical applications such as autonomous vehicles and aerospace systems. We model multichannel sensor delays as independent random variables, capturing the variability of real-world systems where different sensors exhibit distinct and non-constant processing times or communication delays. This allows us to formulate the systems subject to delays as Markov Jump Linear Systems, enabling a rigorous examination of stability and performance under such misalignments. To validate the proposed methodology, we conduct experimental studies with two applications: an adaptive cruise controller and an inverted pendulum. In the analysis, we show that the impact of delays in different channels on a control system is typically not symmetric. Very often there is a sensor channel that is more critical for the controller and delays in that specific channel are hardly tolerated, while other channels can be delayed without compromising the stability and performance of the system.

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

This is the Replicated Computational Results (RCR) Report for the article ‘ Stress Testing Control Loops in Cyber-Physical Systems ’. The article proposes a novel approach for testing Cyber-Physical Systems (CPS) based on the integration of the guarantees that can be provided with the control theoretical models into the software testing practices. This RCR report describes how to reproduce the empirical results of the article. We make available the different scripts needed to fully replicate the results obtained in our article.

The Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS) provides a forum for researchers that propose software engineering methods, techniques, processes, and tools to support the construction of safe, performant, and cost-effective self-adaptive and autonomous systems that provide self-* properties such as self-configuration, self-healing, selfoptimization, and self-protection.The objective of SEAMS is to bring together researchers and practitioners from academia, industry, and government to investigate, discuss, examine, and advance the fundamental principles, state of the art, and the solutions addressing critical challenges of engineering self-adaptive and self-managing systems.SEAMS 2022 was co-located with the 44th International Conference on Software Engineering, in Pittsburgh, USA, in May 2022.The symposium took place toward the end of the COVID-19 pandemic and marked the first chance for an in-person meeting after 2 years of purely digital contacts.Due to uncertainty and a global reluctance to travel, we held the main technical program remotely, while a smaller group met in Pittsburgh and discussed better ways to transfer our community research into practice.We received 49 high-quality submissions belonging to several paper types: Twenty-five submissions were full research papers (eight of them were accepted, with an acceptance rate of 31%, in line with the acceptance rate of prior SEAMS editions).We selected six papers and invited their authors to extend the paper contribution for this special issue.The papers were chosen based on reviewer scores, potential for impact, and stimulating discussions during the conference.The papers for this special issue fall into two broad categories: (1) papers that advance the research of self-adaptation into new domains, such as UAVs teaming with humans, software-defined networks, and edge computing and (2) those that advance the software engineering of self-adaptive systems in the upcoming areas of learning model drift, testing, and proactive prediction of

Control systems are ubiquitous and often at the core of Cyber-Physical Systems, like cars and aeroplanes. They are implemented as embedded software that interacts in closed loop with the physical world through sensors and actuators. As a consequence, the software cannot just be tested in isolation. To close the loop in a testing environment and root causing failure generated by different parts of the system, executable models are used to abstract specific components. Different testing setups can be implemented by abstracting different elements: The most common ones are model-in-the-loop, software-in-the-loop, hardware-in-the-loop, and real-physics-in-the-loop. In this article, we discuss the properties of these setups and the types of faults they can expose. We develop a comprehensive case study using the Crazyflie, a drone whose software and hardware are open source. We implement all the most common testing setups and ensure the consistent injection of faults in each of them. We inject faults in the control system and we compare with the nominal performance of the non-faulty software. Our results show the specific capabilities of the different setups in exposing faults. Contrary to intuition and previous literature, we show that the setups do not belong to a strict hierarchy, and they are best designed to maximize the differences across them rather than to be as close as possible to reality.

Cyber-physical Systems (CPSs) are often safety-critical and deployed in uncertain environments. Identifying scenarios where CPSs do not comply with requirements is fundamental but difficult due to the multidisciplinary nature of CPSs. We investigate the testing of control-based CPSs, where control and software engineers develop the software collaboratively. Control engineers make design assumptions during system development to leverage control theory and obtain guarantees on CPS behaviour. In the implemented system, however, such assumptions are not always satisfied, and their falsification can lead the loss of guarantees. We define stress testing of control-based CPSs as generating tests to falsify such design assumptions. We highlight different types of assumptions, focusing on the use of linearised physics models. To generate stress tests falsifying such assumptions, we leverage control theory to qualitatively characterise the input space of a control-based CPS. We propose a novel test parametrisation for control-based CPSs and use it with the input space characterisation to develop a stress testing approach. We evaluate our approach on three case study systems, including a drone, a continuous-current motor (in five configurations), and an aircraft. Our results show the effectiveness of the proposed testing approach in falsifying the design assumptions and highlighting the causes of assumption violations.

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

Control theory allows one to design controllers that are robust to external disturbances, model simplification, and modelling inaccuracy. Researchers have investigated whether the robustness carries on to the controller’s digital implementation, mostly looking at how the controller reacts to either communication or computational problems. Communication problems are typically modelled using random variables (i.e., estimating the probability that a fault will occur during a transmission), while computational problems are modelled using deterministic guarantees on the number of deadlines that the control task has to meet. These fault models allow the engineer to both design robust controllers and assess the controllers’ behaviour in the presence of isolated faults. Despite being very relevant for the real-world implementations of control system, the question of what happens when these faults occur simultaneously does not yet have a proper answer. In this paper, we answer this question in the stochastic setting, using the theory of Markov Jump Linear Systems to provide stability contracts with almost sure guarantees of convergence. For linear time-invariant Markov jump linear systems, mean square stability implies almost sure convergence – a property that is central to our investigation. Our research primarily emphasises the validation of this property for closed-loop systems that are subject to packet losses and computational overruns, potentially occurring simultaneously. We apply our method to two case studies from the recent literature and show their robustness to a comprehensive set of faults. We employ closed-loop system simulations to empirically derive performance metrics that elucidate the quality of the controller implementation, such as the system settling time and the integral absolute error.

Weakly-hard models have been used to analyse real-time systems subject to patterns of deadline hits and misses. However, the tools that are available in the literature have a set of shortcomings. The analysis they offer is limited to a single weaklyhard constraint and to patterns that specify the number of misses, rather than the number of hits. Furthermore, the scalability of the tools is limited, effectively making it hard to address systems where deadline misses are really sporadic events. In this paper we present WeaklyHard.jl, a scalable tool to analyse a set of weakly hard constraints belonging to all the four types of weakly hard models. To achieve scalability, we exploit novel dominance relations between weakly-hard constraints, based on deadline hits. We provide experimental evidence of the tool’s scalability, compared to the state-of-the-art for a single constraint, a thorough investigation of hit-based weakly-hard constraints, and a sensitivity analysis to constraint set parameters.

Modern embedded software includes complex functionalities and routines, often implemented by splitting the code across different tasks. Such tasks communicate their partial computations to their successors, forming a task chain. Traditionally, this architecture relies on the assumption of hard deadlines and timely communication. However, in actual implementations, tasks may miss their deadlines, thus affecting the propagation of their data. This article analyzes a task chain in which tasks can fail to complete their jobs according to the weakly-hard task model. We explore how missing deadlines affect chains in terms of classic latency metrics and valid data paths. Our analysis, based on mixed integer linear programming, extracts the worst-case deadline miss pattern for any given performance metric.

This paper discusses methods to test the performance of the adaptation layer in a self-adaptive system. The problem is notoriously hard, due to the high degree of uncertainty and variability inherent in an adaptive software application. In particular, providing any type of formal guarantee for this problem is extremely difficult. In this paper we propose the use of a rigorous probabilistic approach to overcome the mentioned difficulties and provide probabilistic guarantees on the software performance. We describe the set up needed for the application of a probabilistic approach. We then discuss the traditional tools from statistics that could be applied to analyse the results, highlighting their limitations and motivating why they are unsuitable for the given problem. We propose the use of a novel tool –the Scenario Theory– to overcome said limitations. We conclude the paper with a thorough empirical evaluation of the proposed approach, using three adaptive software applications: the Tele-Assistance Service, the Self-Adaptive Video Encoder, and the Traffic Reconfiguration via Adaptive Participatory Planning. With the first, we empirically expose the trade-off between data collection and confidence in the testing campaign. With the second, we demonstrate how to compare different adaptation strategies. With the third, we discuss the role of the randomisation in the selection of test inputs. In the evaluation, we apply the scenario theory and also classical statistical tools: Monte Carlo and Extreme Value Theory. We provide a complete evaluation and a thorough comparison of the confidence and guarantees that can be given with all the approaches.

Most off-the-shelf embedded control systems lack proper mechanisms to handle computational overload conditions. Therefore, delays may accumulate and produce overruns, potentially harming the stability and performance of the controlled system. In this paper, we explore a controller implementation in which overrun events are tolerated and tackled with a proper countermeasure, which can be easily plugged into existing controller implementations and in particular commercial off-the-shelf control systems. When an overrun occurs, the control period of the next job is reinitialized and its control parameters are adjusted to counteract the additional delay of the previous job. The main strength of this approach resides in a straightforward applicability and in a high flexibility in deployment. It does neither require a stochastic model of the timing evolution of the system, nor rely on prediction of future delays. We provide an exact tool to determine the system stability, which requires only the knowledge of the worst case response time. The final controlled system exhibits a good trade-off between simplicity and performance, both during nominal and overload conditions.

Control systems are by design robust to various disturbances, ranging from noise to unmodelled dynamics. Recent work on the weakly hard model - applied to controllers - has shown that control tasks can also be inherently robust to deadline misses. However, existing exact analyses are limited to the stability of the closed-loop system. In this paper we show that stability is important but cannot be the only factor to determine whether the behaviour of a system is acceptable also under deadline misses. We focus on systems that experience bursts of deadline misses and on their recovery to normal operation. We apply the resulting comprehensive analysis (that includes both stability and performance) to a Furuta pendulum, comparing simulated data and data obtained with the real plant. We further evaluate our analysis using a benchmark set composed of 133 systems, which is considered representative of industrial control plants. Our results show the handling of the control signal is an extremely important factor in the performance degradation that the controller experiences - a clear indication that only a stability test does not give enough indication about the robustness to deadline misses.

This paper deals with the real-time implementation of feedback controllers. In particular, it provides an analysis of the stability property of closed-loop systems that include a controller that can sporadically miss deadlines. In this context, the weakly hard m-K computational model has been widely adopted and researchers used it to design and verify controllers that are robust to deadline misses. Rather than using the m-K model, we focus on another weakly-hard model, the number of consecutive deadline misses, showing a neat mathematical connection between real-time systems and control theory. We formalise this connection using the joint spectral radius and we discuss how to prove stability guarantees on the combination of a controller (that is unaware of deadline misses) and its system-level implementation. We apply the proposed verification procedure to a synthetic example and to an industrial case study.

This paper discusses the problem of testing the performance of the adaptation layer in a self-adaptive system. The problem is notoriously hard, due to the high degree of uncertainty and variability inherent in an adaptive software application. In particular, providing any type of formal guarantee for this problem is extremely difficult. In this paper we propose the use of a rigorous probabilistic approach to overcome the mentioned difficulties and provide probabilistic guarantees on the software performance. We describe the set up needed for the application of a probabilistic approach. We then discuss the traditional tools from statistics that could be applied to analyse the results, highlighting their limitations and motivating why they are unsuitable for the given problem. We propose the use of a novel tool – the scenario theory – to overcome said limitations. We conclude the paper with a thorough empirical evaluation of the proposed approach, using two adaptive software applications: the Tele-Assistance Service and the Self-Adaptive Video Encoder. With the first, we empirically expose the trade-off between data collection and confidence in the testing campaign. With the second, we demonstrate how to compare different adaptation strategies.

The interest for studying server systems subject to cloned requests has recently increased. In this paper we present a model that allows us to equivalently represent a system of servers with cloned requests, as a single server. The model is very general, and we show that no assumptions on either inter-arrival or service time distributions are required, allowing for, e.g., both heterogeneity and dependencies. Further, we show that the model holds for any queuing discipline. However, we focus our attention on Processor Sharing, as the discipline has not been studied before in this context. The key requirement that enables us to use the single server G/G/1 model is that the request clones have to receive synchronized service. We show examples of server systems fulfilling this requirement. We also use our G/G/1 model to co-design traditional load-balancing algorithms together with cloning strategies, providing well-performing and provably stable designs. Finally, we also relax the synchronized service requirement and study the effects of non-perfect synchronization. We derive bounds for how common imperfections that occur in practice, such as arrival and cancellation delays, affect the accuracy of our model. We empirically demonstrate that the bounds are tight for small imperfections, and that our co-design method for the popular Join-Shortest-Queue (JSQ) policy can be used even under relaxed synchronization assumptions with small loss in accuracy.

The real-time implementation of periodic controllers requires solving a co-design problem, in which the choice of the controller sampling period is a crucial element. Classic design techniques limit the period exploration to safe values, that guarantee the correct execution of the controller alongside the remaining real-time load, i.e., ensuring that the controller worst-case response time does not exceed its deadline. This paper presents DMAC: the first formally-grounded controller design strategy that explores shorter periods, thus explicitly taking into account the possibility of missing deadlines. The design leverages information about the probability that specific sub-sequences of deadline misses are experienced. The result is a fixed controller that on average works as the ideal clairvoyant time-varying controller that knows future deadline hits and misses. We obtain a safe estimate of the hit and miss events using the scenario theory, that allows us to provide probabilistic guarantees. The paper analyzes controllers implemented using the Logical Execution Time paradigm and three different strategies to handle deadline miss events: killing the job, letting the job continue but skipping the next activation, and letting the job continue using a limited queue of jobs. Experimental results show that our design proposal - i.e., exploring the space where deadlines can be missed and handled with different strategies - greatly outperforms classical control design techniques.

Self-adaptation provides a principled way to deal with software systems’ uncertainty during operation. Examples of such uncertainties are disturbances in the environment, variations in sensor readings, and changes in user requirements. As more systems with strict goals require self-adaptation, the need for formal guarantees in self-adaptive systems is becoming a high-priority concern. Designing self-adaptive software using principles from control theory has been identified as one of the approaches to provide guarantees. In general, self-adaptation covers a wide range of approaches to maintain system requirements under uncertainty, ranging from dynamic adaptation of system parameters to runtime architectural reconfiguration. Existing control-theoretic approaches have mainly focused on handling requirements in the form of setpoint values or as quantities to be optimized. Furthermore, existing research primarily focuses on handling uncertainty in the execution environment. This article presents SimCA*, which provides two contributions to the state-of-the-art in control-theoretic adaptation: (i) it supports requirements that keep a value above and below a required threshold, in addition to setpoint and optimization requirements; and (ii) it deals with uncertainty in system parameters, component interactions, system requirements, in addition to uncertainty in the environment. SimCA* provides guarantees for the three types of requirements of the system that is subject to different types of uncertainties. We evaluate SimCA* for two systems with strict requirements from different domains: an Unmanned Underwater Vehicle system used for oceanic surveillance and an Internet of Things application for monitoring a geographical area. The test results confirm that SimCA* can satisfy the three types of requirements in the presence of different types of uncertainty.

This paper describes a method to compute frame size estimates to be used in quasi Worst-Case Transmission Times (qWCTT) for cameras that transmit frames over IP-based communication networks. The precise determination of qWCTT allows us to model the network access scheduling problem as a multiframe problem and to re-use theoretical results for network scheduling. The paper presents a set of experiments, conducted in an industrial testbed, that validate the qWCTT estimation. We believe that a more precise estimation will lead to savings for network infrastructure and to better network utilization.

Modern software applications are subject to uncertain operating conditions, such as dynamics in the availability of services and variations of system goals. Consequently, runtime changes cannot be ignored, but often cannot be predicted at design time. Control theory has been identified as a principled way of addressing runtime changes and it has been applied successfully to modify the structure and behavior of software applications. Most of the times, however, the adaptation targeted the resources that the software has available for execution (CPU, storage, etc.) more than the software application itself. This paper investigates the research efforts that have been conducted to make software adaptable by modifying the software rather than the resource allocated to its execution. This paper aims to identify: the focus of research on control-theoretical software adaptation; how software is modeled and what control mechanisms are used to adapt software; what software qualities and controller guarantees are considered. To that end, we performed a systematic literature review in which we extracted data from 42 primary studies selected from 1,512 papers that resulted from an automatic search. The results of our investigation show that even though the behavior of software is considered non-linear, research efforts use linear models to represent it, with some success. Also, the control strategies that are most often considered are classic control, mostly in the form of Proportional and Integral controllers, and Model Predictive Control. The paper also discusses sensing and actuating strategies that are prominent for software adaptation and the (often neglected) proof of formal properties. Finally, we distill open challenges for control-theoretical software adaptation.

Applications hosted in the cloud have become indispensable in several contexts, with their performance often being key to business operation and their running costs needing to be minimized. To minimize running costs, most modern virtualization technologies such as Linux Containers, Xen, and KVM offer powerful resource control primitives for individual provisioning - that enable adding or removing of fraction of cores and/or megabytes of memory for as short as few seconds. Despite the technology being ready, there is a lack of proper techniques for fine-grained resource allocation, because there is an inherent challenge in determining the correct composition of resources an application needs, with varying workload, to ensure deterministic performance. This paper presents a control-based approach for the management of multiple resources, accounting for the resource consumption, together with the application performance, enabling fine-grained vertical elasticity. The control strategy ensures that the application meets the target performance indicators, consuming as less resources as possible. We carried out an extensive set of experiments using different applications - interactive with response-time requirements, as well as noninteractive with throughput desires - by varying the workload mixes of each application over time. The results demonstrate that our solution precisely provides guaranteed performance while at the same time avoiding both resource over-and underprovisioning.

Modern computing systems are often formed by multiple components that interact with each other through the use of shared resources (e.g., CPU, network bandwidth, storage). In this paper, we consider a representative scenario of one such system in the context of an Internet of Things application. The system consists of a network of self-adaptive cameras that share a communication channel, transmitting streams of frames to a central node. The cameras can modify a quality parameter to adapt the amount of information encoded and to affect their bandwidth requirements and usage. A critical design choice for such a system is scheduling channel access, i.e., how to determine the amount of channel capacity that should be used by each of the cameras at any point in time. Two main issues have to be considered for the choice of a bandwidth allocation scheme: (i) camera adaptation and network access scheduling may interfere with one another, (ii) bandwidth distribution should be triggered only when necessary, to limit additional overhead. This paper proposes the first formally verified event-triggered adaptation scheme for bandwidth allocation, designed to minimize additional overhead in the network. Desired properties of the system are verified using model checking. The paper also describes experimental results obtained with an implementation of the scheme.

Modern software should satisfy multiple goals simultaneously: it should provide predictable performance, be robust to failures, handle peak loads and deal seamlessly with unexpected conditions and changes in the execution environment. For this to happen, software designs should account for the possibility of runtime changes and provide formal guarantees of the software's behavior. Control theory is one of the possible design drivers for runtime adaptation, but adopting control theoretic principles often requires additional, specialized knowledge. To overcome this limitation, automated methodologies have been proposed to extract the necessary information from experimental data and design a control system for runtime adaptation. These proposals, however, only process one goal at a time, creating a chain of controllers. In this paper, we propose and evaluate the first automated strategy that takes into account multiple goals without separating them into multiple control strategies. Avoiding the separation allows us to tackle a larger class of problems and provide stronger guarantees. We test our methodology's generality with three case studies that demonstrate its broad applicability in meeting performance, reliability, quality, security, and energy goals despite environmental or requirements changes.

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

The pervasiveness and growing complexity of software systems are challenging software engineering to design systems that can adapt their behavior to withstand unpredictable, uncertain, and continuously changing execution environments. Control theoretical adaptation mechanisms have received growing interest from the software engineering community in the last few years for their mathematical grounding, allowing formal guarantees on the behavior of the controlled systems. However, most of these mechanisms are tailored to specific applications and can hardly be generalized into broadly applicable software design and development processes. This article discusses a reference control design process, from goal identification to the verification and validation of the controlled system. A taxonomy of the main control strategies is introduced, analyzing their applicability to software adaptation for both functional and nonfunctional goals. A brief extract on how to deal with uncertainty complements the discussion. Finally, the article highlights a set of open challenges, both for the software engineering and the control theory research communities.

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

Embedded real-time systems must meet timing constraints while minimizing energy consumption. To this end, many energy optimizations are introduced for specific platforms or specific applications. These solutions are not portable, however, and when the application or the platform change, these solutions must be redesigned. Portable techniques are hard to develop due to the varying tradeoffs experienced with different application/platform configurations. This paper addresses the problem of finding and exploiting general tradeoffs, using control theory and mathematical optimization to achieve energy minimization under soft real-time application constraints. The paper presents POET, an open-source C library and runtime system that takes a specification of the platform resources and optimizes the application execution. We test POET's ability to portably deliver predictable timing and energy reduction on two embedded systems with different tradeoff spaces - the first with a mobile Intel Haswell processor, and the second with an ARM big.LITTLE System on Chip. POET achieves the desired latency goals with small error while consuming, on average, only 1.3% more energy than the dynamic optimal oracle on the Haswell and 2.9% more on the ARM. We believe this open-source, library-based approach to resource management will simplify the process of writing portable, energy-efficient code for embedded systems.

Clock synchronization is a necessary component in modern distributed systems, especially Wireless Sensor Networks (WSNs). Despite the great effort and the numerous improvements, the existing synchronization schemes do not yet address the cancellation of propagation delays. Up to a few years ago, this was not perceived as a problem, because the time-stamping precision was a more limiting factor for the accuracy achievable with a synchronization scheme. However, the recent introduction of efficient flooding schemes based on constructive interference has greatly improved the achievable accuracy, to the point where propagation delays can effectively become the main source of error. In this paper, we propose a method to estimate and compensate for the network propagation delays. Our proposal does not require to maintain a spanning tree of the network, and exploits constructive interference even to transmit packets whose content are slightly different. To show the validity of the approach, we implemented the propagation delay estimator on top of the FLOPSYNC-2 synchronization scheme. Experimental results prove the feasibility of measuring propagation delays using off-the-shelf microcontrollers and radio transceivers, and show how the proposed solution allows to achieve sub-microsecond clock synchronization even for networks where propagation delays are significant.

While software is becoming more complex everyday, the requirements on its behavior are not getting any easier to satisfy. An application should offer a certain quality of service, adapt to the current environmental conditions and withstand runtime variations that were simply unpredictable during the design phase. To tackle this complexity, control theory has been proposed as a technique for managing software's dynamic behavior, obviating the need for human intervention. Control-theoretical solutions, however, are either tailored for the specific application or do not handle the complexity of multiple interacting components and multiple goals. In this paper, we develop an automated control synthesis methodology that takes, as input, the configurable software components (or knobs) and the goals to be achieved. Our approach automatically constructs a control system that manages the specified knobs and guarantees the goals are met. These claims are backed up by experimental studies on three different software applications, where we show how the proposed automated approach handles the complexity of multiple knobs and objectives.

Self-adaptation enables software to execute successfully in dynamic, unpredictable, and uncertain environments.

Self-adaptation is a first class concern for cloud applications, which should be able to withstand diverse runtime changes. Variations are simultaneously happening both at the cloud infrastructure level - for example hardware failures - and at the user workload level - flash crowds. However, robustly withstanding extreme variability, requires costly hardware over-provisioning.

Time synchronisation is crucial for distributed systems, and particularly for Wireless Sensor Networks (WSNs), where each node is executing concurrent operations to achieve a real-time objective. However, synchronisation is quite difficult to achieve in WSNs, due to the unpredictable deployment conditions and to physical effects like thermal stress, that cause drifts in the local node clocks. As a result, state-of-the-art synchronisation schemes do not guarantee monotonicity of the nodes clock, or are relying on external hardware assistance. In this paper we present FLOPSYNC-2, a scheme to synchronise the clocks of multiple nodes in a WSN, requiring no additional hardware, and based on the application of control-theoretical principles. The scheme guarantees low overhead, low power consumption and synchronisation with clock monotonicity. We propose an implementation of FLOPSYNC-2 on top of the microcontroller operating system Miosix, and prove the validity of our claims with several-days-long experiments on an eight-hop network. The experimental results show that the average clock difference among nodes is limited to a hundred of ns, with a sub-microsecond standard deviation. By introducing a suitable power model, we also prove that synchronisation is achieved with a sub-μA consumption overhead.

We focus on improving resilience of cloud services (e.g., e-commerce website), when correlated or cascading failures lead to computing capacity shortage. We study how to extend the classical cloud service architecture composed of a load-balancer and replicas with a recently proposed self-adaptive paradigm called brownout. Such services are able to reduce their capacity requirements by degrading user experience (e.g., disabling recommendations). Combining resilience with the brownout paradigm is to date an open practical problem. The issue is to ensure that replica self-adaptivity would not confuse the load-balancing algorithm, overloading replicas that are already struggling with capacity shortage. For example, load-balancing strategies based on response times are not able to decide which replicas should be selected, since the response times are already controlled by the brownout paradigm. In this paper we propose two novel brownout-aware load-balancing algorithms. To test their practical applicability, we extended the popular lighttpd web server and load-balancer, thus obtaining a production-ready implementation. Experimental evaluation shows that the approach enables cloud services to remain responsive despite cascading failures. Moreover, when compared to Shortest Queue First (SQF), believed to be near-optimal in the non-adaptive case, our algorithms improve user experience by 5%, with high statistical significance, while preserving response time predictability.

This article presents a new approach to the design of task scheduling algorithms, where system-theoretical methodologies are used throughout. The proposal implies a significant perspective shift with respect to mainstream design practices, but yields large payoffs in terms of simplicity, flexibility, solution uniformity for different problems, and possibility to formally assess the results also in the presence of unpredictable run-time situations. A complete implementation example is illustrated, together with various comparative tests, and a methodological treatise of the matter.

Nowadays, the same piece of code should run on different architectures, providing performance guarantees in a variety of environments and situations. To this end, designers often integrate existing systems with ad-hoc adaptive strategies able to tune specific parameters that impact performance or energy—for example, frequency scaling. However, these strategies interfere with one another and unpredictable performance degradation may occur due to the interaction between different entities. In this article, we propose a software approach to reconfiguration when different strategies, called loops , are encapsulated in the system and are available to be activated. Our solution to loop coordination is based on machine learning and it selects a policy for the activation of loops inside of a system without prior knowledge. We implemented our solution on top of GNU/Linux and evaluated it with a significant subset of the PARSEC benchmark suite.

Constraining the temperature of computing systems has become a dominant aspect in the design of integrated circuits. The supply voltage decrease has lost its pace even though the feature size is shrinking constantly. This results in an increased number of transistors per unit of area and hence a growing power density. Researchers started investigating dynamic thermal management techniques to address the tradeoff between performance and temperature. Hardware dynamic thermal management can guarantee safety but, at the same time, can negatively affect established service-level agreements. On the other hand, software solutions rely on hardware for safety but does not indiscriminately trade-off performance for temperature. We propose ThermOS, an extension for commodity operating systems that harnesses formal feedback control and idle cycle injection to decrease thermal emergencies while showing better efficiency than commodity and cutting edge techniques.

Motivation While the pay-as-you-go model of Infrastructure-as-a-Service (IaaS) clouds is more flexible than an in-house IT infrastructure, it still has a resource-based interface towards users, who can rent virtual computing resources over relatively long time scales. There is a fundamental mismatch between this resource-based interface and what users really care about: performance.

Managing the resources of a virtualized data-center is a key issue in cloud computing [1]. Existing research mostly assumes that applications are either allocated the required resources or fail [2--15]. Combined with the fact that most cloud applications have dynamic resource requirements [16], this imposes a fundamental limitation to cloud computing: To guarantee on-demand resource allocations, the data-center needs large spare capacity, leading to inefficient resource utilization.

Traditionally, hypervisors, operating systems, and runtime systems have been providing an abstraction layer over the bare-metal hardware. Traditional abstractions, however, do not consider for non-functional requirements such as system-level constraints or users' objectives. As these requirements are gaining increasing importance, researchers are looking into making user-specified and system-level objectives first-class citizens in the computer systems' realm.

Mobile devices, due to their wide distribution and to their increasing smartness and availability of computational power, can become the interaction point between users and their surrounding environments. However, current mobile devices OSes lack of the ability to anticipate and overcome internal and external changes. Integrating mechanisms of self-awareness and self-adaptability in nowadays smartphones is an attractive perspective to match with these requirements. Moreover, adaptive behaviors can enhance the management by the mobile device itself, of the available resources at its best, e.g., the battery life. This paper envisions various situations in which a self-aware mobile device can interact with the surrounding environment and support the user in performing everyday actions. A prototype of such an adaptive device, called morphone.os and based on the Android OS, has been designed and implemented to verify the reaction of the device in different situations providing convincing and promising preliminary results.

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

A number of techniques have been proposed to provide runtime performance guarantees while minimizing power consumption. One drawback of existing approaches is that they work only on a fixed set of components (or actuators) that must be specified at design time. If new components become available, these management systems must be redesigned and reimplemented. In this paper, we propose PTRADE, a novel performance management framework that is general with respect to the components it manages. PTRADE can be deployed to work on a new system with different components without redesign and reimplementation. PTRADE's generality is demonstrated through the management of performance goals for a variety of benchmarks on two different Linux/x86 systems and a simulated 128-core system, each with different components governing power and performance tradeoffs. Our experimental results show that PTRADE provides generality while meeting performance goals with low error and close to optimal power consumption.

Addressing the challenges of extreme scale computing requires holistic design of new programming models and systems that support those models. This paper discusses the Angstrom processor, which is designed to support a new Self-aware Computing (SEEC) model. In SEEC, applications explicitly state goals, while other systems components provide actions that the SEEC runtime system can use to meet those goals. Angstrom supports this model by exposing sensors and adaptations that traditionally would be managed independently by hardware. This exposure allows SEEC to coordinate hardware actions with actions specified by other parts of the system, and allows the SEEC runtime system to meet application goals while reducing costs (e.g., power consumption).

Autonomic computing systems are capable of adapting their behavior and resources thousands of times a second to automatically decide the best way to accomplish a given goal despite changing environmental conditions and demands. Different decision mechanisms are considered in the literature, but in the vast majority of the cases a single technique is applied to a given instance of the problem. This article proposes a comparison of some state of the art approaches for decision making, applied to a self-optimizing autonomic system that allocates resources to a software application. A variety of decision mechanisms, from heuristics to control-theory and machine learning, are investigated. The results obtained with these solutions are compared by means of case studies using standard benchmarks. Our results indicate that the most suitable decision mechanism can vary depending on the specific test case but adaptive and model predictive control systems tend to produce good performance and may work best in a priori unknown situations.

This paper investigates a novel approach to derive self-adaptive software by automatically modifying the model of the application using a control-theoretical approach. Self adaptation is achieved at the model level to assure that the model-which lives alongside the application at run-time- continues to satisfy its reliability requirements, despite changes in the environment that might lead to a violation. We assume that the model is given in terms of a Discrete Time Markov Chain (DTMC). DTMCs can express reliability concerns by modeling possible failures through transitions to failure states. Reliability requirements may be expressed as reachability properties that constrain the probability to reach certain states, denoted as failure states. We assume that DTMCs describe possible variant behaviors of the adaptive system through transitions exiting a given state that represent alternative choices, made according to certain probabilities. Viewed from a control-theory standpoint, these probabilities correspond to the input variables of a controlled system-i.e., in the control theory lexicon, "control variables". Adopting the same lexicon, such variables are continuously modified at run-time by a feedback controller so as to ensure continuous satisfaction of the requirements despite disturbances, i.e., changes in the environment. Changes at the model level may then be automatically transferred to changes in the running implementation. The approach is methodologically described by providing a translation scheme from DTMCs to discrete-time dynamic systems, the formalism in which the controllers are derived. An initial empirical assessment is described for a case study. Conjectures for extensions to other models and other requirements.

Self-Aware Adaptive computing systems are capable of adapting their behavior and resources thousands of times based on changing environmental conditions and demands. This allows them to automatically find the best way to accomplish a given goal with the resources at hand. This capability would benefit the full range of computer systems, from embedded devices to servers to supercomputers. Although such a system may seem rather far fetched, we believe that basic semiconductor technology, computer architecture and software systems have advanced to the point that the time is ripe to realize such a system. In this paper we present an implementation of an FPGA-based Self-Aware Adaptive computing system which blends techniques developed in different research fields, i.e, monitoring, decision making, and self-adaptation. The result is a system built on top of a set of enabling technology that proves the effectiveness of using Self-Aware Adaptive computing systems. We used the Application Heartbeats to assess performance goals and to inspect application progress and the Implementation Switch Service to switch between different implementations of the same algorithm (both in software and in hardware) at runtime. Preliminary results show the effectiveness and the usability of the proposed approach.