In dynamic environments, safety-critical autonomous systems must adapt to environmental changes without violating safety requirements. Model verification at runtime supports adaptation through the periodic analysis of continually updated models. A major limitation of the technique is the high overhead associated with the regular analyses of large state-space models. Our article introduces an adaptive approximation strategy that tackles this limitation by delaying unnecessary model updates, significantly reducing the overheads of these analyses. The strategy is applicable to Markov decision processes (MDPs) and is partitioned into components that can be analyzed independently and approximately. Each component is assigned a priority that depends on its impact on the accuracy of verification, and only the highest-priority components affected by changes are scheduled for updating/approximating. A complete update and verification of the entire model is triggered infrequently when the accuracy drops below a predefined threshold. We provide theoretical guarantees and proofs which ensure that our strategy can be applied without impacting the overall safety of the verified autonomous system. The experimental results from a case study in which we applied the strategy to a rescue robot team show that it is fully robust against safety-critical errors and can achieve a decision accuracy of over 97%.

Multitask real-time embedded systems are often restricted by tight energy budgets, whilst they usually have environmental interactions through software-controlled energy-hungry peripheral modules like LTE, WiFi, and GSM. The way that the driver calls are used within the embedded software to do such a control introduces program energy-hotspots (EHs) from the peripheral module perspective, namely the code pieces wasting the system energy. By the energy waste, we mean that the energy consumption is reducible via some program code modifications without threatening the system schedulability and logical correctness. This paper examines the program EHs of fixed-priority real-time tasks where two types of energy inefficiency can occur: Intra-task type, causing energy waste even if a task runs individually, and inter-task type, happening due to the interaction between different system tasks, namely preemption scenarios even if there is no intra-task EH. The main cause of such EHs is the unnecessary time intervals between the driver calls, causing extra energy consumption by peripheral modules. We propose some static analysis methods to automatically detect and eliminate both types of intra-and inter-task EHs regarding their mutual relevance, according to the extreme (worst-case and best-case) execution times of certain task code parts. Our manipulations on the tasks to eliminate the EHs include some program code modifications with the awareness of system schedulability and logical correctness, and changing some scheduling decisions, namely limiting the preemption points. After applying our proposed method to the test tasks, our simulation results show an energy reduction of up to 19 percent.

Automotive cyber-physical systems consist of multiple control subsystems working under resource limitations, and the trend is to run the corresponding control tasks on a shared platform. The resource requirements of the tasks are usually variable at runtime due to the uncertainties in the environment, necessitating some kinds of adaptation to deal with the resource limitations. Such adaptations may positively or negatively affect the control performance of several subsystems. Since there might be some thresholds on the control performances as quality constraints, this matter should be considered carefully to avoid any quality attribute constraint violation. This article proposes a scalable control performance constraint verification method for such a system that works based on a feedback scheduler. The scalability is the result of a control-aware pruning method. In case of a constraint violation, the designer may change the system configuration and perform re-verification. Our evaluations show that the proposed method scales well while preserving the verification soundness.

Embedded nodes in future cyber-physical systems are mostly self-powered, scavenging their required energy from the environment. The environmental sources of energy are usually variable, so that some prediction methods are employed to proactively adapt to the variable harvesting energy. However, prediction errors may surprise the system with some unpredicted changes, needing appropriate reactions. We consider an energy-harvesting real-time system with periodic tasks of multiple performance levels. An energy-resilient scheduler is proposed for the system to react to the unpredicted changes such that the system is survivable, recovers from such a change in a timely manner, and appropriately controls its performance degradation. After the recovery, however, the energy-resilient scheduler preserves the system survivability and maximizes its performance in a prediction time horizon, while it will be ready for another surprise. We provide some theoretical properties and a feasibility test which are used in the design of the energy-resilient scheduler. Our simulations show that the proposed resilient scheduler outperforms well-known performance maximization methods, effectively approximates the optimal solution, and reacts appropriately against surprises of high severity.

Today’s deeply embedded systems, with real-time interactions to the environment, are largely battery-operated, and peripheral modules like LTE, WiFi, and GPS are among the most energy-hungry components of them. These components are often under the direct control of an embedded software. Some pieces of the software program are called energy hotspots if they can be transformed towards better system energy consumption while leaving it logically- and temporally-correct. This paper focuses on three such energy hotspots from the peripheral module perspective. The root causes of the hotspots in the software program are misplaced driver calls: Early acquiring or late releasing of the module causes it to waste energy in the active state, having unnecessary distance between the use operations causes extra tail energy overhead, and unaccounted releasing and re-acquiring of the module causes more energy consumption in comparison to leaving the module unreleased. We provide static analysis methods for the detection and elimination of such energy hotspots automatically with regard to some relations between temporal requirements of the real-time embedded software, the time and energy specifications of the module, and the extreme (worst-case/best-case) execution times of specific pieces of the software program. Our simulation results show about 4.7 to 20 percent of energy reductions after elimination of the energy hotspots of the test programs using our proposed method.

Appropriate battery selection is a major design decision regarding the fast growth of battery-operated devices like space rovers, wireless sensor network nodes, rescue robots, and so on. Many such systems are mission critical, where estimation of the battery depletion time has an important role in the design efficiency with regard to the mission time. Accurate characterization of the system power usage pattern is essential for such an estimation. The following complexities exist: (1) The system behavior changes during interaction with the physical world, (2) the power consumption varies as the runtime progresses, (3) the total delivered battery charge has non-linear dependency on the power variability, and (4) design-time exhaustive study about runtime execution paths is almost impossible. This article presents an analytical method to first characterize the power variability of a given embedded program modeled by a directed acyclic graph, concerning the first and the second complexities. To include the third complexity, however, the concept of Worst-case Power Consumption Trace (WPCT) is proposed toward the worst-case scenario in terms of charge depletion for a given battery. A polynomial algorithm is also presented to construct WPCT and use it to estimate a tight lower bound for the system energy depletion time, i.e., its failure time, avoiding an exhaustive study. Comparisons between the analytical and simulation results reveal less than 3.4% of error in the bound estimations for the considered setups.

CMOS miniaturization and timing faults due to factors, such as aging, emphasize that embedded processor reliability is a major concern. Among the various aging mechanisms, negative bias temperature instability (NBTI) is encountered as the dominant factor. Techniques against NBTI are mostly based on aggressive Vdd scaling, decelerating aging at the expense of performance degradation. Traditionally, designers use conservative guard-bands to combat timing faults, leading to loss of efficiency. Some other reactive approaches use sensors, requiring hardware modification and large area and debug overheads. According to the literature, two opportunities exist to compensate for the performance loss: instruction timing slacks imposed by static timing analysis (STA) and application computational error resiliency. This article proposes an efficient estimation model for the instruction-level timing slack probability distribution function (PDF) and gives a dynamic approach for statistical timing analysis, which is used for dynamic frequency management to improve performance of both error-resilient and errorsensitive applications. To this aim, we introduce a metric called architecture timing-fault vulnerability factor, considering NBTI and Vdd effects. Simulation results show that the proposed timing slack PDF estimation model has an accuracy of about 94%, which can be used to increase throughput of error-resilient applications up to 3.2 times compared with when the traditional STA is used.

In recent years, the increase in cyber threats has raised many concerns about security and privacy in the digital world. However, new attack methods are often limited to a few core techniques. Here, in order to detect new threat patterns, the authors use an attack graph structure to model unprecedented network traffic. This graph for the unknown attack is matched to a pre‐known threat database, which contains attack graphs related to each known threat. The main challenge is to associate unknown traffics to a family of known threats. For this, the authors utilise random walks and pattern theorem. The authors utilise the pattern theorem and apply it to a set of proposed algorithms for detecting new generations of malicious traffics. Under the assumption of having a proper threat database, the authors argue that for each unknown threat, which belongs to a family of threats, it is possible to find at least one matching pattern with high matching rate and sensitivity.

Lifetime reliability management of miniaturized CMOS devices continuously gets more importance with the shrinking of technology size. Neither of existing design-time solutions (like guard-banding) and runtime methods (like reactive monitoring) does efficiently address this issue; rather, proactive approaches, which use runtime aging prediction, are getting more promising to provide resiliency. Among various reliability threatening mechanisms in recent technologies, negative bias temperature instability is the dominant factor; it depends on multiple time-varying operational parameters, including temperature, supply voltage, and stress. This paper proposes an efficient instruction-level stress estimation model; accordingly, it introduces a runtime aging prediction approach for embedded processors, taking simultaneous impacts of the temperature, supply voltage, and stress variations. We propose instruction degradation factor and architecture degradation factor metrics, respectively, for fine-grained stress estimation and recurring runtime aging prediction. We also provide a simulation environment for model validation. Simulation results of several benchmarks show that the proposed stress estimation model has an accuracy of about 92%, indicating that the method is accurate enough, yet simple for runtime usage.

Summary Based on a pay‐as‐you‐go model, cloud computing provides the possibility of hosting pervasive applications from both academic and business domains. However, data centers hosting cloud applications consume huge amounts of electrical energy, contributing to high operational costs and large carbon footprints to the environment. Energy‐aware resource provisioning is an effective solution to diminish the energy consumption of cloud data centers. Recently, a growing trend has emerged, where cloud technology is used to run periodic real‐time applications such as multimedia, telecommunication, video gaming, and industrial applications. In order for a real‐time application to be able to use cloud services, cloud providers have to be able to provide timing guarantees. In this paper, we introduce an energy‐aware resource provisioning mechanism for cloud data centers, which are capable of serving real‐time periodic tasks following the Software as a Service model. The proposed method is compared against an energy‐aware version of the RT‐OpenStack. RT‐OpenStack is a recently proposed approach to provide a time‐predictable version of OpenStack. The experimental results manifest that our proposed resource provisioning method outperforms energy‐aware version of the RT‐OpenStack by 16.01%, 25.45%, and 25.45% in terms of energy consumption, number of used servers, and average utilization of used servers, respectively. Moreover, from the scalability perspective, the preference of the proposed method for large‐scale data centers is more considerable.

Large scale distributed systems employ thousands of resources which inevitably suffer from the unavailability issue. Serious side effects like unexpected delay or failure in the application execution are probable in case of such an issue. The imposed outcome might then be catastrophic consequences for real time applications or penalties for the service providers. Better prediction of the resource unavailability helps diminishing the undesired outcomes. This paper proposes a resource availability prediction algorithm for the mentioned goal. The resource availability variation is modeled as a stochastic process. By analyzing the availability information of NDU resources and both physical and virtual machines of the PlantLab, we found that the transition probabilities among the availability levels are non-stationary. To cope with this characteristic, we introduce Availability Transition Patterns (ATPs); the ATPs are dynamically constructed and the transitions between them are modeled by a Markov chain. The future ATP is then predicted based on the constructed Markov chain, according to which the resource availability-level is predicted. Experimental results confirm the efficiency of the proposed prediction algorithm.

This paper deals with thermal management of a multicore processor executing multiple stochastic real-time job streams. The main objective is to reduce the chip-wide temperature gradient to decelerate processor aging, and the subordinate goal is to decrease the hotspot temperature. A pair of active and passive cores is dedicated to each stream, which the active one services the corresponding real-time jobs. In order to reduce the chip-wide temperature gradient between cores, the active and passive cores of an individual stream are replaced at appropriate times through job migration. The thermal management of this system is a specific stochastic control problem. Regarding the inter-effects of core temperatures and the stochastic nature of the system, systematic achievement of the objective needs an appropriate method. The control theory of Markov jump linear system (MJLS) has been used to design the desired thermal controller and analytically study its stability. The efficacy of the proposed approach in terms of the thermal management objectives is investigated through simulation experiments.

The periodic task model has been widely used in real-time systems due to the periodic behavior of many applications or periodic observation patterns of environmental events as in control applications. While the tasks of some applications have inherent values for periods, many can be defined via ranges of acceptable values. The designer choice of period values has consequences w.r.t. To utilization of the task set and the resulting hyper period. Harmonic task sets are favored, e.g., for their polynomial-time worst case response time analysis or their small hyper periods, which is of major concern e.g., for hyper visors used in virtualization or time triggered systems. In this paper we present a model to describe harmonic relations between ranges of period values, rather than single numbers only. We derive sufficient conditions for the existence of a linear-time solution, as well as a graph representation for the relations between period ranges. We provide utilization bounds of each resulting harmonic range, giving the designer flexibility to select a harmonic task set with high or low utilization. The tightness of the bounds as well as efficiency of our period assignment algorithms have been evaluated by synthetic experiments via system utilization and feasibly constructed harmonic task sets.

We consider a firm real-time system with a single processor working in two power modes depending on whether it is idle or executing a job. The system is equipped with dynamic thermal management through a cooling subsystem which can switch between two cooling modes. Real-time jobs which arrive to the system have stochastic properties and are prone to soft errors. A successful job is one that enters the system and completes its execution with no timing or soft error. Appropriateness of the system is evaluated based on its performance, temperature behavior, reliability, and energy consumption. It is noteworthy that these criteria have mutual interactions to each other: the stochastic nature of the system affects the success ratio of jobs beside the system dynamic power, the leakage as well as dynamic power impacts the processor temperature, this temperature affects the leakage power, the cooling subsystem power, and the soft error rate, which the latter in turn impacts the system reliability and the success ratio of jobs. This paper proposes an analytical evaluation method with a Markovian view to the system which considers these reciprocal effects. A number of simulation experiments are carried out to validate the accuracy of the proposed method.

Energy management is an important issue in today's real-time systems due to the high costs of energy supplying. Using renewable, like wave, wind, and solar energy sources seem promising methods to address this issue. However, because of the existing contrast between the critical nature of hard real-time systems and the unpredictable nature of renewable energies, some supplementary energy source like electricity grid or battery is needed. In this paper, we consider hard real-time systems with two renewable and nonrenewable energy sources. In order to reduce the costs, we present two dynamic voltage scaling controllers to minimize the energy attained from the latter source. In order to handle variations of the environmental energy and workload, the model predictive control approach is employed. One nonlinear approach beside one fast linear piecewise affine explicit controller are proposed. The efficacies of the proposed approaches have been investigated through extensive simulations. Comparisons to an ideal clairvoyant controller as a baseline show that, in the studied scenarios, the proposed controllers guarantee at least 78% of the baseline performance.

Timeliness and accuracy are two major concerns in many real-time embedded systems working in dynamic environments. It has been emphasized in the literature that in various real-time applications such as control systems and Kalman filters, delay is one main source of inaccuracy in the system. In this paper, we present a solution based on scheduling algorithms for the problem of inaccuracy in such systems. To this aim, first an accuracy model is introduced for systems which their accuracy is influenced by sampling and I/O delays. Then an algorithm called adjacency trade is presented to improve system accuracy while maintaining its timeliness. This algorithm follows an iterative approach and can be applied to each priority-based scheduling algorithm with no intervention in respecting the deadlines. Finally, through various simulation experiments, the effectiveness of this algorithm is examined against some algorithms in the literature.

We consider a single-processor firm real-time (FRT) system with exponential interarrival and execution times for jobs with relative deadlines following a general distribution. The scheduling policy of the system is first-come first-served (FCFS) and the capacity of the system is arbitrary. This system is subject to an arbitrary-shaped time/utility function (TUF), which determines the accrued utility of each job according to its completion time. It is considered that the system power consumption at different working states is predetermined for each processor speed. We have proposed an exact analytical method for the calculation of specific performance and power-related measures of the system. The resulting analytical formulations for the performance measures are functions of the processor speed and system capacity. These measures are optimized through appropriate selections of the speed using derivatives and the capacity employing numerical search methods. Some experimental results are presented for different unimodal TUFs in systems with deterministic and exponential relative deadlines. For the latter distribution, the results are compared against similar results obtained through simulation for the nonpreemptive earliest-deadline-first (NP-EDF) scheduling policy. The comparisons show that FCFS is superior to NP-EDF for some measures and TUFs.

This paper considers object-based distributed real-time systems within which objects provide system services to the real-time tasks. Each task is subject to a time/utility function (TUF) which determines the accrued utility of the task according to its completion time. One major problem in such systems is to place the objects onto the computing nodes so as to maximize the total accrued utility. Thus, we propose a utility accrual object distribution (UAOD) algorithm which consists of two phases. In the first phase, through object placement and replication beside some types of deadline decomposition and adaptation, the computing nodes are reserved for the most beneficial tasks. As the second phase, UAOD follows a load-balancing algorithm for the placement of the remaining objects on the nodes to service the less beneficial tasks. Simulation results reveal that the total accrued utility is improved with the UAOD algorithm comparing to the traditional object placement methods.

One of the main properties of today's distributed and parallel systems, such as mobile ad-hoc networks and grids, is their heterogeneity in the available resources. Further, many applications of such systems are subject to Time/Utility Function (TUF) time constraints for jobs, unavoidable variability in job characteristics and arrivals, and statistical assurance requirements on timeliness behaviors. In this paper, we propose an exact analytical solution for performance evaluation of dynamic policies used for routing of TUF-constrained Firm Real-Time (FRT) jobs among parallel single-processor queues with arbitrary processing rates and capacities. The analytical method can be used for the evaluation of the compliance of some important statistical assurance requirements. Furthermore, we present a utility-aware dynamic routing policy to improve the expected accrued utility of the parallel system. The policy called Maximum Expected Utility (MEU) behaves based on the information gathered from the analytical solution. MEU is compared with some well-known Dynamic Routing (DR) policies for different TUF shapes and both cases of homogeneous and heterogeneous processors of a two-queue system. The comparisons show the efficiency of MEU for the former case and its good behavior in most situations for the latter case.

Wireless sensor networks are characterized by dense deployment of energy constrained nodes. Owing to the deployment of large number of sensor nodes in uncontrolled hostile or harsh environments and unmonitored operation, it is common that a node becomes inactive due to a node failure or exhaustion of the respective energy resource. Such node failures result in the reduction of the cluster quality of service (Qos). This problem becomes more complex when the services in the wireless sensor network (WSN) are real-time. To avoid the degradation of QoS, it is necessary that the failures be recovered using a proper method. In this paper, we present a dynamic energy efficient real-time job allocation algorithm called ERTJA for handling such node failures in a cluster. ERTJA relies on the other cluster nodes to handle the node failure. It tries to minimize the energy consumption of the cluster by minimal activation of the sleeping nodes, while guaranteeing the QoS of the cluster application. Further, when the number of sleeping nodes is limited, the proposed algorithm uses the idle times of the existing nodes to have a graceful QoS degradation of the cluster QoS upon the node failure. Simulation results show significant performance improvements of ERTJA in terms of energy consumption comparing to the N-EDF-Plus algorithm. According to the results, ERTJA can save up to 27.2% of the cluster energy consumption with respect to N-EDF-Plus.

Most of the previous studies on real-time systems focus on the satisfaction of completion-time constraints of jobs. A lot of them consider pure deadline, where the real-time jobs should be completed before their respective deadline. Some others consider time/utility functions for their jobs, which specifies the benefit that a job can accrue according to its exact completion time. However, we propose a different type of timing constraints for real-time jobs called Instant Value Function (IVF). According to IVF, the exact instant where a job is executed affects the value that the job can accrue. Therefore, the IVF specifies that which instants are the most appropriate ones to execute the job. This type of timing constraints can express the behavior of specific applications in a more precise manner. Furthermore, we have presented a scheduling algorithm that tries to maximize the accrued value of real-time systems with IVF-constrained jobs. The experimental results show that the proposed method considerably outperforms EDF.

This paper introduces an analytical method for approximating the performance of a soft real-time system modeled by a single-server queue. The service discipline in the queue is earliest-deadline-first (EDF), which is an optimal scheduling policy. Real-time jobs with exponentially distributed deadlines arrive according to a Poisson process. All jobs have deadlines until the end of service and are served non-preemptively. Occurrences of transient faults in the server are also taken into account. The important performance measure to calculate is the loss probability due to deadline misses and/or transient faults. The system is approximated by a Markovian model in the long run. A key parameter, namely, the loss rate when there are n jobs in the system is used in the model, which is estimated by partitioning the system into two virtual subsystems. The resulting model can then be solved analytically using standard Markovian solution techniques. Comparing numerical and simulation results, we find that the existing errors are relatively small.

This paper introduces an analytical method for approximating the fraction of jobs that miss their deadlines in a real-time system when earliest-deadline-first scheduling policy (EDF) is used. In the system, jobs either all have deadlines until the beginning of service or deadlines until the end of service. In the former case, EDF is known to be optimal and, in the latter case, it is optimal if preemption is allowed. In both cases, the system is modeled by an M/M/1/EDF+M queue, i.e., a single server queue with Poisson arrival, and service times and customer impatience, which are exponentially distributed. The optimality property of EDF is used for the estimation of a key parameter, /spl gamma//sub n/, which is the loss rate when there are n customers in the system. The estimation is possible by finding an upper bound and a lower bound for /spl gamma//sub n/ and linearly combining these two bounds. The resulting Markov chains are then easy to solve numerically. Comparing numerical and simulation results, we find that the existing errors are relatively small.