Abstract With widespread adoption across industries, Industrial Internet of Things (IIoT) environments have become prime targets for cyberattacks. Moreover, the complexity and scale of these attacks can involve highly sophisticated, artificial intelligence (AI)–enabled, and even autonomous capabilities, occurring at machine speeds and making conventional defensive mechanisms insufficient. Therefore, defensive systems must possess considerable autonomy to detect and mitigate such attacks effectively and promptly. This work presents an IIoT cyber defense system (NS-IoT) that integrates the sensitivity of Deep Reinforcement Learning (DRL) with the agility of multi-agent systems, providing an autonomous defense solution for distributed denial of service (DDoS) attacks. The NS-IoT system consists of two modules: detection and defense. For the detection module, a Deep Q-Network (DQN)-based agent (DQN-IoT) was developed to detect DDoS attacks. This agent employs DRL techniques to treat attack classification like a guessing game, leverages feedback to improve decision-making within the Markov Decision Process (MDP), and combines rewards for enhanced performance. In this study, DDoS attacks were detected using the proposed DQN-IoT model, achieving 98.43% and 98.05% accuracy on the CIC-IoT-2022 and CIC-IoT-2023 datasets, respectively. While these results highlight the model’s effectiveness, real-time response speed is crucial in real-time events. Therefore, the proposed NS-IoT system addresses this need with its autonomous multi-agent structure, which minimizes human intervention.

With ever-increasing attacks against learning-enabled components (LECs) in safety-critical systems, it has become more challenging to ensure robust operations. By focusing on anterior and posterior attacks on LECs, where malicious tasks need to run before and after a victim task, respectively, to launch attacks, we study in this work the victim-aware fixed-priority scheduling in single processor systems. Specifically, by exploiting the preference-oriented fixed-priority (POFP) scheduler, we devise a Victim-Aware Priority Assignment (VAPA) scheme to assign different priorities for victim tasks that are subject to anterior and posterior attacks, respectively. VAPA aims at reducing both anterior and posterior attacking occasions in the resultant schedule and thus enhancing the robust operations of the victim tasks. Online adaptation is also considered by exploiting idle time slots to further remove such attacking occasions whenever possible. The main ideas of the victim-aware scheduling are illustrated via a concrete example and future work is discussed.

Dynamic Modulation Scaling (DMS) is a well-known mechanism that can effectively exploit the tradeoff between communication time and energy consumption. In recent years a number of studies have suggested that DMS techniques can reduce energy consumption while maintaining performance objectives in low-power wireless transmission technologies such as those defined in IEEE 802.15.4. These studies tend to rely on theoretical or simulation DMS models to predict network performance metrics. However, there is little, if any, work that is based upon empirically verified network performance outcomes using DMS. This paper fills that gap. Our contribution is four-fold; first, using GNU~Radio and SDR hardware we show how to emulate DMS in low power wireless systems. Second, we measure the impact of varying Signal-to-Noise levels on throughput and delivery rates for different DMS control strategies. Third, using DMS we quantify the impact of distance and finally, we measure the impact of different elevations between sender and receiver on network performance. Our results provide an empirical basis for future work in this area.

For a set of real-time tasks that have mixed preference of being executed at early or late times before their deadlines, we have recently studied both earliest-deadline based and fixed-priority preference-oriented (PO) scheduling algorithms for uniprocessor systems. In this work, focusing on multiprocessor real-time systems, we study the foundational guidelines to design partition-based PO scheduling algorithms for tasks with mixed preference requirements. In particular, through a concrete example, we illustrate that the harmonicity of tasks' periods should be incorporated when making scheduling decisions in addition to their execution preferences to obtain favorable schedules that better fulfill tasks' preference requirements. Based on such guidelines, we design a period-aware preference-oriented (PAPO) partitioned scheduling algorithm and discuss several variations by considering harmonicity as well as utilization of tasks.

Internet of Things (IoT) has become a hot research topic recently. IoT networks are expected to integrate billions of small devices to the Internet enabling countless applications ranging from automation of cities to home based healthcare solutions for elderly and vulnerable population. Such wide range of application pose unique challenges such as the need for high reliability, ultra low power and low delay communications. In addition to these challenges, such Internet enabled small devices will have to be equipped with the necessary security suits to cope with security challenges posed by the Internet. Furthermore, these solutions have to address such unique challenges via a micro controller generally with a limited processing power and memory consuming as little energy as possible. This paper presents an extension to the secure bootstrapping mechanism of the newly introduced IETF 6TiSCH protocol where the authentication keys are distributed within the trusted nodes of the IoT network to enable an efficient authentication and bootstrapping process. Using a distributed approach, we aim to reduce the communication overhead of the standard IETF 6TiSCH authentication mechanism and improve energy efficiency of the network by keeping authentication tokens at the edge of the IoT network.

In mixed-criticality (MC) systems, multiple activities with various certification requirements (thus with different criticality levels) can co-exist on shared hardware platforms, where multicore processors have emerged as the de facto computing engines. In this paper, by using the partitioned earliest-deadline-first with virtual deadlines (EDF-VDs) scheduler for a set of periodic MC tasks running on multicore systems, we derive a criticality-aware utilization bound for efficient feasibility tests and then identify its characteristics. Our analysis shows that the bound increases with increasing number of cores and decreasing system criticality level. We show that, since the utilizations of MC tasks at different criticality levels can vary considerably, the utilization contribution of a task on different cores may have large variations and thus can significantly affect the system schedulability under the EDF-VD scheduler. Based on these observations, we propose a novel and efficient criticality-aware task partitioning algorithm (CA-TPA) to compensate for the inherent pessimism of the utilization bound. In order to improve the system schedulability, the task priorities are determined according to their utilization contributions to the system in CA-TPA. Moreover, by analyzing the utilization variations of tasks at different levels, we develop several heuristics to minimize the utilization increment and balance the workload on cores. The simulation results show that the CA-TPA scheme is very effective in achieving higher schedulability ratio and yielding balanced workloads. The actual implementation in Linux operating system further demonstrates the applicability of CA-TPA with lower run-time overhead, compared to the existing partitioning schemes.

Internet of things (IoT) is being developed for a wide range of applications from home automation and personal fitness to smart cities. With the extensive growth in adaptation of IoT devices comes the uncoordinated and substandard designs aimed at promptly making products available to the end consumer. This substandard approach restricts the growth of IoT in the near future and necessitates that studies understand requirements for an efficient design. A particular area where IoT applications have grown significantly is surveillance and monitoring. Applications of IoT in this domain are relying on distributed sensors, each equipped with a battery, capable of collecting images, processing images, and communicating the raw or processed data to the nearest node until it reaches the base station for decision making. In such an IoT network where processing can be distributed over the network, the important research question is how much of data each node should process and how much it should communicate for a given objective. This work answers this question and provides a deeper understanding of energy and delay tradeoffs in an IoT network with three different target metrics.

Standby-sparing systems where one processor is used as primary while another one is deployed as spare have been used to provide high reliability to real-time embedded systems. To reduce the energy consumption, the primary uses DVFS while the spare employs DPM to postpone the backup tasks. In this paper, we re-visit the problem for heterogeneous multicore systems that include both high-performance and low-power cores. We identify and address the two main dimensions of the problem, namely, what type of core to use as the primary or backup, and how to make frequency assignments on the primary to maximize energy savings.

In this article, we consider clustered wireless sensor networks where the nodes harvest energy from the environment. We target performance-sensitive applications that have to collectively send their information to a cluster head by a predefined deadline. The nodes are equipped with Dynamic Modulation Scaling (DMS)-capable wireless radios. DMS provides a tuning knob, allowing us to trade off communication latency with energy consumption. We consider two optimization objectives, maximizing total energy reserves and maximizing the minimum energy level across all nodes. For both objectives, we show that optimal solutions can be obtained by solving Mixed Integer Linear Programming problems. We also develop several fast heuristics that are shown to provide approximate solutions experimentally.

On emerging multicore systems, task replication is a powerful way to achieve high reliability targets. In this paper, we consider the problem of achieving a given reliability target for a set of periodic real-time tasks running on a multicore system with minimum energy consumption. Our framework explicitly takes into account the coverage factor of the fault detection techniques and the negative impact of Dynamic Voltage Scaling (DVS) on the rate of transient faults leading to soft errors. We characterize the subtle interplay between the processing frequency, replication level, reliability, fault coverage, and energy consumption on DVS-enabled multicore systems. We first develop static solutions and then propose dynamic adaptation schemes in order to reduce the concurrent execution of the replicas of a given task and to take advantage of early completions. Our simulation results indicate that through our algorithms, a very broad spectrum of reliability targets can be achieved with minimum energy consumption thanks to the judicious task replication and frequency assignment.

The scheduling for mixed-criticality (MC) systems, where multiple activities have different certification requirements and thus different criticality on a shared hardware platform, has recently become an important research focus. In this work, considering that multicore processors have emerged as the de-facto platform for modern embedded systems, we propose a novel and efficient criticality-aware task partitioning algorithm (CA-TPA) for a set of periodic MC tasks running on multicore systems. We employ the state-of-the art EDF-VD scheduler on each core. Our work is based on the observation that the utilizations of MC tasks at different criticality levels can have quite large variations, hence when a task is allocated, its utilization contribution on different processors may vary by large margins and this can significantly affect the schedulability of tasks. During partitioning, CA-TPA sorts the tasks according to their utilization contributions on individual processors. Several heuristics are investigated to balance the workload on processors with the objective of improving the schedulability of tasks under CA-TPA. The simulation results show that our proposed CA-TPA scheme is effective, giving much higher schedulability ratios when compared to the classical partitioning schemes.

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

Most real-time scheduling algorithms prioritize tasks solely based on their timing parameters and cannot effectively handle them when they have different execution preferences. In this paper, for a set of periodic tasks, where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP), we investigate preference-oriented fixed-priority scheduling algorithms. Specifically, following the idea in dual-priority scheduling, we derive promotion times for ALAP tasks (only). Then, we devise a dual-queue based fixed-priority scheduling algorithm that retains ALAP tasks in the waiting queue until their promotion times to delay their executions while putting ASAP tasks into the ready queue immediately once they arrive for early execution. We also investigate online techniques to further expedite (delay) the executions of ASAP (ALAP) tasks, respectively. Our evaluation results show that the dual-queue technique with ALAP tasks' promotion times can effectively address the execution preferences of both ASAP and ALAP tasks, which can be further improved at runtime with wrapper-task based slack management. Our technique is shown to yield clear advantages over a simple technique that periodically inserts idle intervals to the schedule before ALAP tasks are executed.

In this paper, we consider the feasibility problem of a set of real-time jobs which may be subject to a fault burst during execution. A fault burst represents a time interval during which multiple jobs may incur faults; hence multiple recoveries may be needed. We show that determining the feasibility of a real-time system, which may be subject to a fault burst that may last at most Δ time units, is an NP-Hard problem even when the exact position of the fault burst is known a priori. However, in a practical system, the fault burst may occur at any arbitrary and unpredictable time. We develop feasibility analysis by assuming multiple recovery strategy where, in addition to the job at the end of which the fault is detected, all preempted tasks are also re-executed. We formally characterize the overhead that a scheduler incurs due to a fault burst and present a generic recovery strategy, called Δ-idling, that is shown to minimize the worst-case overhead for any priority-driven scheduling algorithm. Next, we analyze periodic task systems. We show that the preemptive EDF policy, when coupled with Δ-idling, provides the highest possible utilization bound ½ (1 - Δ over Pmin), where Pminis the smallest task period. We also present an empirical evaluation of the EDF policy with Δ-idling over synthetically generated task sets, and show that it offers a clear improvement over the naive EDF policy that triggers the recovery tasks as soon as an error is detected.

The Standby-Sparing (SS) technique has been previously explored to improve energy efficiency while providing fault tolerance in dual-processor real-time systems. In this paper, by considering both transient and permanent faults, we develop energy-efficient fault tolerance techniques for real-time systems deploying an arbitrary number of identical processors. First, we study the Paired-SS technique, where processors are organized as groups of two (i.e., pairs) and SS is applied within each pair of processors directly after partitioning tasks to the pairs. Then, we propose a Generalized-SS technique that partitions processors into two groups containing primary and secondary processors, respectively. The main and backup copies of tasks are executed on the primary and secondary processors under the partitioned-EDF and partitioned-EDL scheduling policies, respectively. The objective is to reduce the overlapped executions of the main and backup copies in order to improve energy savings. Our experimental evaluations show that, for a given system with fixed number of processors, typically there exists a configuration of primary and secondary processors under the Generalized-SS technique that can lead to better energy savings when compared to the Paired-SS technique.

As Cyber-Physical-Systems (CPSs) evolve they will be increasingly relied on to support time-critical and performance-intensive monitoring and control activities. Further, many CPSs that utilize Wireless Sensor Networking (WSN) technologies will require the use of energy harvesting methods to extend their lifetimes. For this application class, there are currently few algorithmic techniques that combine performance sensitive processing and communication with efficient management techniques for energy harvesting. Our paper addresses this problem. We first propose a general purpose, multihop WSN architecture capable of supporting time-critical CPS systems using energy harvesting. We then present a set of Harvesting Aware Speed Selection (HASS) algorithms. Our technique maximizes the minimum energy reserve for all the nodes in the network, thus ensuring highly resilient performance under emergency or fault-driven situations. We present an optimal centralized solution, along with an efficient, distributed solution. We propose a CPS-specific experimental methodology, enabling us to evaluate our approach. Our experiments show that our algorithms yield significantly higher energy reserves than baseline methods.

While Dynamic Voltage Scaling (DVS) remains as a popular energy management technique for modern computing systems, recent research has identified significant and negative impacts of voltage scaling on system reliability. To preserve system reliability under DVS settings, a number of reliability-aware power management (RA-PM) schemes have been recently studied. However, the existing RA-PM schemes normally schedule a separate recovery for each task whose execution is scaled down and are rather conservative. To overcome such conservativeness, we study in this article novel RA-PM schemes based on the shared recovery (SHR) technique. Specifically, we consider a set of frame-based real-time tasks with individual deadlines and a common period where the precedence constraints are represented by a directed acyclic graph (DAG). We first show that the earliest deadline first (EDF) algorithm can always yield a schedule where all timing and precedence constraints are met by considering the effective deadlines of tasks derived from as late as possible (ALAP) policy, provided that the task set is feasible. Then, we propose a shared recovery based frequency assignment technique (namely SHR-DAG) and prove its optimality to minimize energy consumption while preserving the system reliability. To exploit additional slack that arises from early completion of tasks, we also study a dynamic extension for SHR-DAG to improve energy efficiency and system reliability at runtime. The results from our extensive simulations show that, compared to the existing RA-PM schemes, SHR-DAG can achieve up to 35% energy savings, which is very close to the maximum achievable energy savings. More interestingly, our extensive evaluation also indicates that the new schemes offer non-trivial improvements on system reliability over the existing RA-PM schemes as well.

The negative impact of the popular energy management technique Dynamic Voltage and Frequency Scaling (DVFS) on the reliability of real-time embedded systems, in terms of increased transient fault rates, has been recently identified. As a result, recent research literature includes a number of solutions within the so-called Reliability-Aware Power Management (RA-PM) framework, where the aim is to preserve the system's original reliability. In this research effort, we propose a more general framework where the aim is to achieve arbitrary reliability levels that may vary for each periodic task. A critical component of our solution is the use of dynamically allocated recoveries: we show that providing a relatively modest recovery allowance to a given periodic task helps to achieve surprisingly high reliability levels as long as these allowances can be reclaimed on-demand during the hyper period. We propose a pseudo-polynomial time feasibility test, as well as static and dynamic algorithms to determine the recovery allowance and frequency assignments to minimize energy consumption while satisfying timing and reliability constraints. Our experimental evaluation points to the significant gain potential of the new framework in terms of both energy and reliability figures.

Voltage/Frequency Scaling (VFS) and Device Power Management (DPM) are two popular techniques commonly employed to save energy in real-time embedded systems. VFS policies aim at reducing the CPU energy, while DPM-based solutions involve putting the system components (e.g., memory or I/O devices) to low-power/sleep states at runtime, when sufficiently long idle intervals can be predicted. Despite numerous research papers that tackled the energy minimization problem using VFS or DPM separately, the interactions of these two popular techniques are not yet well understood. In this paper, we undertake an exact analysis of the problem for a real-time embedded application running on a VFS-enabled CPU and using multiple devices. Specifically, by adopting a generalized system-level energy model, we characterize the variations in different components of the system energy as a function of the CPU processing frequency. Then, we propose a provably optimal and efficient algorithm to determine the optimal CPU frequency as well as device state transition decisions to minimize the system-level energy. We also extend our solution to deal with workload variability. The experimental evaluations confirm that substantial energy savings can be obtained through our solution that combines VFS and DPM optimally under the given task and energy models.

DVFS remains an important energy management technique for embedded systems. However, its negative impact on transient fault rates has been recently shown. In this paper, we propose the Generalized Shared Recovery (GSHR) technique to optimally use the DVFS technique in order to achieve a given reliability goal for real-time embedded applications. Our technique determines the optimal number of recoveries to deploy as well as task-level processing frequencies to minimize the energy consumption while achieving the reliability goal and meeting the timing constraints. The recoveries may be shared among tasks, improving the prospects of DVFS compared to existing reliability-aware power management frameworks. The experimental evaluation points to the close-to-optimal energy savings of our proposed technique.

In this paper, we investigate energy-aware real-time scheduling algorithms with speed change constraints. A processor is equipped with variable clock frequency (speedy) feature and is used to schedule a set of given jobs with deadlines. Each speed change involves time/energy overhead and recent studies show that it also impacts negatively the processor's lifetime reliability. Motivated by this, we study theoretical energy-aware scheduling problems with consideration of number and cost of speed changes. We associate a cost with each speed change to reflect its negative impact on the processor's lifetime reliability. We design speed schedules to satisfy all jobs' deadlines and optimize the energy consumption and the total cost incurred due to speed changes. Four related problems based on this framework are considered. We develop algorithms that perform arbitrarily close to the optimal and we also analyze their time complexities.

In this paper, we present an energy-aware standby-sparing technique for periodic real-time applications. A standby-sparing system consists of a primary processor where the application tasks are executed using Dynamic Voltage Scaling (DVS) to save energy, and a spare processor where the backup tasks are executed at maximum voltage/frequency, should there be a need. In our framework, we employ Earliest-Deadline-First (EDF) and Earliest-Deadline-Late (EDL) scheduling policies on the primary and spare CPUs, respectively. The use of EDL on the spare CPU allows delaying the backup tasks on the spare CPU as much as possible, enabling energy savings. We develop static and dynamic algorithms based on these principles, and evaluate their performance experimentally. Our simulation results show significant energy savings compared to existing reliability-aware power management (RAPM) techniques for most execution scenarios.

There is currently tremendous interest in deploying energy harvesting wireless sensor networks. Engineering such systems requires striking a careful balance between sensing performance and energy management. Our work addresses this problem through the design and analysis of a harvesting aware utility-based sensing rate allocation algorithm. Based on a network utility formulation, we show that our algorithm is optimal in terms of assigning rates to individual nodes to maximize overall utility, while ensuring energy-neutral operation. To our knowledge, our work is the first optimal solution that maximizes network utility through rate assignments for tree-structured energy harvesting sensor networks. Our algorithm is fast and efficient with running time O(N3), where N is the number of nodes. We evaluate the performance, scalability, and overhead of our algorithm for various utility functions and network sizes, underlining its significant advantages.

Mixed-criticality real-time systems, where tasks may be associated with different criticality and assurance levels, have attracted much attention in the recent past. In this paper, we consider partitioning-based multiprocessor scheduling of mixed- criticality real-time task sets. Guaranteeing feasibility in this setting is shown to be NP-Hard. With a focus on fixed-priority preemptive scheduling on each processor, we identify the two main aspects of the problem, namely the task allocation and priority assignment dimensions. For the task allocation dimension, we propose and compare bin-packing-inspired heuristics, based on offline task ordering according to utilization and criticality. For the priority assignment dimension, we compare the well- known Rate Monotonic priority assignment policy with Audsley's priority assignment algorithm. Through simulations, we also assess and discuss the relative importance of these two primary dimensions on the overall mixed-criticality feasibility problem for multiprocessor platforms.

Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM) techniques form the basis of numerous energy management schemes proposed for real-time embedded systems. DVS targets reducing the dynamic CPU energy consumption, while DPM attempts to reduce theenergy consumption of idle devices by putting them to low-power states over sufficiently long intervals. It is imperative that the system-wide energy management schemes efficiently integrate DVS and DPM while exploiting the subtle trade-off dimensions. In this paper, we develop and propose a unified framework for periodic real-time tasks where DVS and DPM are judiciously combined. The framework, called DFR-EDF, assumes a general system-level energy model and includes both static and dynamic(online) components. The static part is based on the extension of the recently proposed Device Forbidden Regions (DFRs) approach to Earliest-Deadline-First (EDF) scheduling. The online component integrates the predictive DPM techniques and offers a generalized slack reclaiming mechanism that can be used by DVS and DPM simultaneously. Our experimental evaluation indicates significant gains of DFR-EDF at the system-level compared to the state-of-the-art solutions. Finally, this research effort makes another contribution by formally showing that optimally solving the DPM problem in periodic real-time execution settings is NP-Hard in the strong sense, even in the absence of DVS.

Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, by adopting optimal global schedulers within each cluster, first we investigate the worstcase utilization bound for cluster scheduling. Specifically, for a system with m homogeneous clusters where each cluster has k processors, we show that the worstcase achievable system utilization is (⌊k/α⌋·m+1)/(⌊k/α⌋+1) · k, where a is the maximum utilization for the periodic tasks considered. By focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware partitioning heuristic aiming at reducing the scheduling overhead. Simulation results show that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters (e.g., k = 2). Moreover, the proposed period-aware partitioning heuristic markedly reduces the scheduling overhead of cluster scheduling with Bfair.

Recently, the negative effect of the popular power management technique Dynamic Voltage and Frequency Scaling (DVFS) on the system reliability has been identified. As a result, various reliability-aware power management (RAPM) schemes have been studied for uniprocessor real-time systems. In this paper, we investigate global scheduling-based RAPM (G-RAPM) schemes for a set of frame-based real-time tasks running on a homogeneous multiprocessor system. An important dimension of the problem is how to select the appropriate subset of tasks for energy and reliability management (i.e., schedule a recovery for each selected task and scale down their executions). We show that making this decision optimally (i.e., the static G-RAPM problem) is NP-hard. Then we propose two efficient G-RAPM heuristics, which rely on local and global task selections, respectively. Moreover, to reclaim dynamic slack generated at runtime, we extend the slack-sharing based global dynamic power management scheme to the reliability-aware settings. The proposed schemes are evaluated through extensive simulations. The results show that our static G-RAPM heuristics can preserve system reliability while achieving significant energy savings (within 3% of an upper bound for most cases). Moreover, G-RAPM with global task selection provides better opportunities for dynamic slack reclamation and up to 15% more energy savings can be obtained at runtime compared to that of local task selection.

The dynamic voltage and frequency scaling (DVFS) technique is the basis of numerous state-of-the-art energy management schemes proposed for real-time embedded systems. However, recent research has illustrated the alarmingly negative impact of DVFS on task and system reliability. In this paper, we consider the problem of assigning processing frequencies to a set of real-time tasks in order to maximize the overall reliability, under given time and energy constraints. First, under the frame-based task model, we formulate the problem as a nonlinear optimization problem and show how to obtain the static optimal solution. Then, we propose online (dynamic) algorithms that detect early completions and adjust the task frequencies at runtime, to improve overall reliability. Furthermore, we extend these solutions to the periodic task model, with both static and dynamic solutions. All our solutions ensure that all timing constraints are met while the cumulative energy consumption of tasks does not exceed the given energy budget. Our simulation results indicate that our algorithms perform comparably to a clairvoyant optimal scheduler that knows the exact workload in advance.

In this paper, we undertake the competitive analysis of the online real-time scheduling problems under a given hard energy constraint. Specifically, we derive worst-case performance bounds that apply to any online algorithm, when compared to an optimal algorithm that has the knowledge of the input sequence in advance. First, by focusing on uniform value-density settings, we prove that no online algorithm can achieve a competitive factor greater than 1 - emax/E, where emaxis the upper bound on the size of any job and E is the available energy budget. Then we propose a variant of EDF algorithm, EC-EDF, that is able to achieve this upper bound. We show that a priori information about the largest job size in the actual input sequence makes possible the design of a semi-online algorithm EC-EDF* which achieves a constant competitive factor of 0.5. This turns out to be the best achievable competitive factor in these settings. We also extend our analysis to other settings, including those with non-uniform value densities and dynamic voltage scaling capability.

While Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM) techniques are widely used in real-time embedded applications, their complex interaction is not fully understood. In this research effort, we consider the problem of minimizing the expected energy consumption on settings where the workload is known only probabilistically. By adopting a system-level power model, we formally show how the optimal processing frequency can be computed efficiently for a real-time embedded application that can use multiple devices during its execution, while still meeting the timing constraints. Our evaluations indicate that the new technique provides clear (up to 35%) energy gains over the existing solutions that are proposed for deterministic workloads. Moreover, in a non-negligible part of the parameter spectrum, the algorithm's performance is shown to be close to that of a clairvoyant algorithm that can minimize the energy consumption with the advance knowledge about the exact workload.

While Dynamic Voltage Scaling (DVS) remains as a popular energy management technique for real-time embedded applications, recent research has identified significant and negative impact of voltage scaling on system reliability. For this reason, a number of reliability-aware power management (RA-PM) schemes were recently proposed to preserve the system reliability when DVS is used. In this paper, we propose a new approach, called the shared recovery (SHR) technique, to minimize the system-level energy consumption while still preserving the system’s original reliability. The main idea of the SHR technique is to avoid the offline allocation of separate recovery tasks to the scaled tasks by assigning a global/shared recovery block that can be used by any task at run-time. Our simulation results show that, compared to the existing RA-PM schemes, our scheme can achieve up to 35 % energy savings. Further, this performance is shown to be comparable to the maximum energy savings thatcanbeachievedbyanyalgorithm. Interestingly,ourextensive evaluation indicates that SHR offers also non-trivial gains over the previous algorithms on the reliability side. Further, a dynamic extension is proposed to improve energy and reliability management at run-time by reducing the size of the recovery block and re-using the slack that arises from early completions.

Dynamic voltage and frequency scaling (DVFS) has been widely used to manage energy in real-time embedded systems. However, it was recently shown that DVFS has direct and adverse effects on system reliability. In this work, we investigate static and dynamic reliability-aware energy management schemes to minimize energy consumption for periodic real-time systems while preserving system reliability. Focusing on earliest deadline first (EDF) scheduling, we first show that the static version of the problem is NP-hard and propose two task-level utilization-based heuristics. Then, we develop a job-level online scheme by building on the idea of wrapper-tasks, to monitor and manage dynamic slack efficiently in reliability-aware settings. The feasibility of the dynamic scheme is formally proved. Finally, we present two integrated approaches to reclaim both static and dynamic slack at runtime. To preserve system reliability, the proposed schemes incorporate recovery tasks/jobs into the schedule as needed, while still using the remaining slack for energy savings. The proposed schemes are evaluated through extensive simulations. The results confirm that all the proposed schemes can preserve the system reliability, while the ordinary (but reliability-ignorant) energy management schemes result in drastically decreased system reliability. For the static heuristics, the energy savings are close to what can be achieved by an optimal solution by a margin of 5 percent. By effectively exploiting the runtime slack, the dynamic schemes can achieve additional energy savings while preserving system reliability.

Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM) are two popular techniques commonly employed to save energy in real-time embedded systems. DVS policies aim at reducing the CPU energy, while DPM-based solutions involve putting the system components (e.g. memory or I/O devices) to low-power/sleep states at run-time, when sufficiently long idle intervals can be predicted. Despite numerous research papers that tackled the energy minimization problem using DVS or DPM separately, the interactions of these two popular techniques are not yet well understood. In this paper, we undertake an exact analysis of the problem for a real-time embedded application running on a DVS-enabled CPU and using potentially multiple devices. Specifically, by adopting a generalized system-level energy model and taking into account the non-trivial time/energy overheads involved in device transitions, we characterize the variations in different components of the system energy as a function of the CPU processing speed. Then, we propose a provably optimal algorithm to determine the optimal CPU speed as well as device state transition decisions to minimize the system-level energy. Our algorithm runs in O(m log m) time, where m is the number of devices used by the application. The evaluations with realistic system parameters indicate that our solution, which combines DVS and DPM optimally, can lead to substantial energy savings when compared to previous solutions.

The dynamic voltage scaling (DVS) technique is the basis of numerous state-of-the-art energy management schemes proposed for real-time embedded systems. However, recent research has illustrated the alarmingly negative impact of DVS on task and system reliability. In this paper, we consider the problem of processing frequency assignment to a set of real-time tasks in order to maximize the overall reliability, under given time and energy constraints. First, we formulate the problem as a non-linear optimization problem and show how to obtain the static optimal solution. Then, we propose on-line (dynamic) algorithms that detect early completions and adjust the task frequencies at run-time, to improve overall reliability. Our simulation results indicate that our algorithms perform comparably to a clairvoyant optimal scheduler that knows the exact workload in advance.

Dynamic power management (DPM) techniques are crucial in minimizing the overall energy consumption in real-time embedded systems. The timing constraints of real-time applications and non-trivial time/energy transition overheads introduce significant challenges, as the device sleep intervals should be longer than a minimum threshold (called the break-even time) to ensure energy-efficiency. In this paper, we present a novel approach to the real-time DPM problem by explicitly enforcing long device sleep intervals for different devices, called device forbidden regions. We focus on the application of our technique to task systems with rate-monotonic priorities, and develop our algorithm DFR-RMS. Our solution includes a static component where the duration and frequency of forbidden regions are determined through the extended time-demand analysis to preserve the temporal correctness of all the tasks, while enhancing the energy savings. Then, we present a sophisticated on-line component which interacts with existing prediction-based DPM schemes to realize the full potential of device forbidden regions. Further, our scheme can be used with or without dynamic voltage scaling (DVS). Our experimental evaluation hints that significant energy gains can be obtained, when compared to the existing prediction-based techniques. Another contribution of this research effort is to show that the general problem of generating feasible schedules for preemptive periodic real-time tasks where all device sleep intervals are longer than the device break-even times is NP-hard in the strong sense.

Reliability-aware power management (RAPM) schemes, which consider the negative effects of voltage scaling on system reliability, were recently studied to save energy while preserving system reliability. The existing RAPM schemes for periodic tasks may be, however, inherently unfair in that they can manage only some tasks at the expense of the other remaining tasks. In this work, we propose the flexible reliability-aware power management framework, which allows the management of all the tasks in the system, according to their assurance requirements. Optimally solving this problem is shown to be NP-hard in the strong sense and upper bounds on energy savings are derived. Then, by extending the processor demand analysis, a pseudo-polynomial-time static scheme is proposed for the "deeply red" recovery patterns. On-line schemes that manage dynamic slack for better energy savings and reliability enhancement are also discussed. The schemes are evaluated extensively through simulations. The results show that, compared to the previous RAPM schemes, the new flexible RAPM schemes can guarantee the assurance requirements for all the tasks, but at the cost of slightly decreased energy savings. However, when combined with dynamic reclaiming, the new schemes become as competitive as the previous ones on the energy dimension, while improving overall reliability.

Reliability-aware power management (RAPM) schemes have been recently studied to save energy while preserving system reliability. The existing RAPM schemes, however, provision for worst-case execution scenarios and are rather conservative. In this paper, by exploiting the probabilistic execution time information of real-time tasks, we develop an optimistic RAPM scheme. Instead of scheduling a full recovery for tasks whose executions are scaled down, the new scheme puts aside just enough slack to guarantee the required reliability leave while leaving more slack for energy management to achieve better energy savings. The problem is shown to be NP-hard and a novel heuristic algorithm is proposed and evaluated. The simulation results show that the optimistic RAPM scheme performs very well. It achieves energy savings comparable to that of the ordinary (but reliability-ignorant) power management scheme, while maintaining the system reliability as successfully as the conservative RAPM schemes.

Considering the impact of the popular energy management technique Dynamic Voltage and Frequency Scaling (DVFS) on system reliability, the Reliability-Aware Power Management (RA-PM) problem has been recently explored to save energy while maintaining system reliability. In this work, focusing on Rate Monotonic Scheduling (RMS) policy, we study static RA-PM schemes for periodic realtime tasks. After showing the intractability of the problem, we focus on two widely-known feasibility tests for RMS (namely, the Liu-Layland bound and Time Demand Analysis) and propose a number of heuristics based on the priority-monotonic speed assignment. The heuristics are evaluated through extensive simulations.

The prominent energy management technique, dynamic voltage and frequency scaling (DVFS), was recently shown to have direct and adverse effects on system reliability. In this work, we investigate static and dynamic reliability-aware energy management schemes for a set of periodic real-time tasks to minimize energy consumption while preserving system reliability. Focusing on EDF scheduling, we first show that the static problem is NP-hard and propose two task-level utilization-based heuristics. Then, we develop a job-level dynamic (on-line) scheme by building on the idea of wrappertasks, to monitor and manage dynamic slack efficiently in reliability-aware settings. Our schemes incorporate recovery tasks/jobs into the schedule as needed for reliability preservation, while still using the remaining slack for energy savings. Simulation results show that all the proposed schemes can achieve significant energy savings while preserving the system reliability. Moreover, the energy savings of the static heuristics are close to those of the static optimal solution by a margin of 5%

In this paper, we consider the problem of checking the feasibility of a set of n real-time tasks while provisioning for timely recovery from (at most) k transient faults. We extend the well-known processor demand approach to take into account the extra overhead that may be induced by potential recovery operations under earliest-deadline-first scheduling. We develop a necessary and sufficient test using a dynamic programming technique. An improvement upon the previous solutions is to address and efficiently solve the case where the recovery blocks associated with a given task do not necessarily have the same execution time. We also provide an online version of the algorithm that does not require a priori knowledge of release times. The online algorithm runs in O(m ldr k2) time, where m is the number of ready tasks. We extend the framework to periodic execution settings: We derive a sufficient condition that can be checked efficiently for the feasibility of periodic tasks in the presence of faults. Finally, we analyze the case where the recovery blocks are to be executed nonpreemptively and we formally show that the problem becomes intractable under that assumption.

With the continued scaling of CMOS technologies and reduced design margins, the reliability concerns induced by transient faults have become prominent. Moreover, the popular energy management technique dynamic voltage and frequency scaling (DVFS) has been shown to have direct and negative effects on reliability. In this work, for a set of real-time tasks, we focus on the slack allocation problem to minimize their energy consumption while preserving the overall system reliability. Building on our previous findings for a single real-time application where a recovery task was used to preserve reliability, we identify the problem of reliability-aware energy management for multiple tasks as NP-hard and propose two polynomial-time heuristic schemes. We also investigate the effects of on-chip/off-chip workload decomposition on energy management, by considering a generalized power model. Simulation results show that ordinary energy management schemes could lead to drastically decreased system reliability, while the proposed reliability-aware heuristic schemes are able to preserve the system reliability and obtain significant energy savings at the same time.

In this paper, we consider the system-wide energy management problem for a set of periodic real-time tasks running on a DVS-enabled processor. Our solution uses a generalized power model, in which frequency-dependent and frequency-independent power components are explicitly considered. Further, variations in power dissipations and on-chip/off-chip access patterns of different tasks are encoded in the problem formulation. Using this generalized power model, we show that it is possible to obtain analytically the task-level energy-efficient speed below which DVS starts to affect overall energy consumption negatively. Then, we formulate the system-wide energy management problem as a non-linear optimization problem and provide a polynomial-time solution. We also provide a dynamic slack reclaiming extension which considers the effects of slow-down on the system-wide energy consumption. Our experimental evaluation shows that the optimal solution provides significant (up to 50%) gains over the previous solutions that focused on dynamic CPU power at the expense of ignoring other power components

We consider the problem of energy minimization for periodic preemptive hard real-time tasks that are scheduled on an identical multiprocessor platform with dynamic voltage scaling capability. We adopt partitioned scheduling and assume that the tasks are assigned rate-monotonic priorities. We show that the problem is NP-hard in the strong sense on m /spl ges/ 2 processors even when the feasibility is guaranteed a priori. Because of the intractability of the problem, we propose an integrated approach that consists of three different components: RMS admission control test, the partitioning heuristic and the speed assignment algorithm. We discuss possible options for each component by considering state-of-the-art solutions. Then, we experimentally investigate the impact of heuristics on feasibility, energy and feasibility/energy performance dimensions. In offline settings where tasks can be ordered according to the utilization values, we show that worst-fit dominates other well-known heuristics. For online settings, we propose an algorithm that is based on reserving a subset of processors for light tasks to guarantee a consistent performance.

In this paper, we explore performance optimization problems for real-time systems that have to rely on a fixed energy budget during an operation/mission. We adopt the weakly-hard realtime scheduling paradigm to ensure a predictable performance for all the tasks: Our aim is to minimize the number of dynamic failures (in terms of (m, k)-firm deadline constraints) while remaining within the energy budget. We prove that this problem is NP-hard in the strong sense even for an ideal DVS architecture with continuous speed spectrum. We propose techniques to statically compute the speed of the CPU in order to meet the (m, k)-firm deadline constraints. We present on-line speed adjustment algorithms to exploit the slack time of skipped and completed jobs. Through extensive simulations, we show how the performance can be significantly improved by selectively dispatching jobs by considering their energy costs as well as their contribution to the system performance

We explore the performance tradeoffs for real-time systems with dynamic voltage scaling (DVS) capability, when the workload includes aperiodic jobs as well as periodic tasks. As opposed to the assumptions of early works on real-tune DVS or nonpower-aware scheduling of hybrid task sets, the settings require the consideration of two often-conflicting objectives: Improving the responsiveness of aperiodic jobs and reducing the energy consumption. We propose the composite metric, energy * average response time, as a performance measure in energy-aware scheduling of hybrid task sets. Then we develop our framework that integrates dynamic reclaiming algorithm (DRA) and total bandwidth server (TBS) mechanism in variable-speed settings. In addition to the static algorithm, we propose basic reclaiming scheme (BRS) and mutual reclaiming scheme (MRS) that enable the reuse of the system slack arising from early task completions. We also present our bandwidth sharing scheme (BSS) that aggressively exploits the bandwidth reserved for TBS to further slow down the periodic tasks. We provide an experimental evaluation of our algorithms under different workloads and speed settings, and show that BSS can provide significant performance improvements when the actual variability in the workload is high.

In this paper, we consider the problem of checking the feasibility of a set of n aperiodic real-time tasks while provisioning for timely recovery from (at most) k transient faults. We extend the well-known processor demand approach to take into account the extra overhead that may be induced by potential recovery operations under earliest deadline first scheduling. We develop a necessary and sufficient test using dynamic programming technique. An improvement upon the previous solutions is to address and efficiently solve the case where the recovery blocks associated with faults of a given task do not have necessarily the same execution time. Further, we provide an on-line version of our algorithm that does not require a priori knowledge of release times. The on-line algorithm runs in O(m/spl middot/k/sup 2/) time where m is the number of ready tasks. We also show how to quickly adjust the recovery-related parameters of the algorithm for the remaining part of the execution when a fault is detected.

We address power-aware scheduling of periodic tasks to reduce CPU energy consumption in hard real-time systems through dynamic voltage scaling. Our intertask voltage scheduling solution includes three components: 1) a static (offline) solution to compute the optimal speed, assuming worst-case workload for each arrival, 2) an online speed reduction mechanism to reclaim energy by adapting to the actual workload, and 3) an online, adaptive and speculative speed adjustment mechanism to anticipate early completions of future executions by using the average-case workload information. All these solutions still guarantee that all deadlines are met. Our simulation results show that our reclaiming algorithm alone outperforms other recently proposed intertask voltage scheduling schemes. Our speculative techniques are shown to provide additional gains, approaching the theoretical lower-bound by a margin of 10 percent.

The need for supporting dynamic real-time environments where changes in workloads occur frequently requires a scheduling framework that: (1) explicitly addresses overload conditions, (2) allows the system to achieve graceful degradation while guaranteeing the deadlines of the most critical tasks in the system, and (3) supports an efficient runtime selection mechanism capable of determining the load to be shed from the system to handle the overload. In this paper, we propose a novel scheduling framework for a real-time environment that experiences dynamic workload changes. This framework is capable of adjusting the system workload in incremental steps under overloaded conditions such that the most critical tasks in the system are always scheduled and the total value of the system is maximized. Each task has an assigned criticality value and consists of two parts, a mandatory part and an optional part. A timely answer is available after the mandatory part completes execution and its value may be improved by executing the entire optional part. The process of selecting tasks (mandatory or optional parts) to discard while maximizing the value of the system requires the exploration of a potentially large number of combinations. Since an optimal solution is too time-consuming to be computed online, an approximate algorithm is executed incrementally whenever the processor would otherwise be idle, progressively refining the quality of the solution. This scheme allows the scheduler to handle overloads with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the most critical tasks in the system. Simulation results show that few stages of the algorithm need to be executed for achieving a performance with near-optimal results.

In this paper, we provide an efficient solution for periodic real-time tasks with (potentially) different power consumption characteristics. We show that a task T/sub i/ can run at a constant speed S/sub i/ at every instance without hurting optimality. We sketch an O(n/sup 2/ log n) algorithm to compute the optimal S/sub i/ values. We also prove that the EDF (Earliest Deadline First) scheduling policy can be used to obtain a feasible schedule with these optimal speed values.

In this paper we address power-aware scheduling of periodic hard real-time tasks using dynamic voltage scaling. Our solution includes three parts: (a) a static (off-line) solution to compute the optimal speed, assuming worst-case workload for each arrival, (b) an on-line speed reduction mechanism to reclaim energy by adapting to the actual workload, and (c) an online, adaptive and speculative speed adjustment mechanism to anticipate early completions of future executions by using the average-case workload information. All these solutions still guarantee that all deadlines are met. Our simulation results show that the reclaiming algorithm saves a striking 50% of the energy, over the static algorithm. Further our speculative techniques allow for an additional approximately 20% savings over the reclaiming algorithm. In this study, we also establish that solving an instance of the static power-aware scheduling problem is equivalent to solving an instance of the reward-based scheduling problem [1, 4] with concave reward functions.

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part. The mandatory part must complete before the task's deadline, while a nondecreasing reward function is associated with the execution of the optional part, which can be interrupted at any time. Imprecise computation and Increased-Reward-with-Increased-Service models fall within the scope of this-framework. In this paper, we address the reward-based scheduling problem for periodic tasks. An optimal schedule is one where mandatory-parts complete in a timely manner and the weighted average reward is maximized. For linear and concave reward functions, which are most common, we 1) show the existence of an optimal schedule where the optional service time of a task is constant at every instance and 2) show how to efficiently compute this service time. We also prove the optimality of Rate Monotonic Scheduling (with harmonic periods), Earliest Deadline First, and Least Laxity First policies for the case of uniprocessors when used with the optimal service times we computed. Moreover, we extend our result by showing that any policy which can fully utilize all the processors is also optimal for the multiprocessor periodic reward-based scheduling. To show-that our optimal solution is pushing the limits of reward-based scheduling, we further prove that, when the reward functions are convex, the problem becomes NP-Hard. Our static optimal solution, besides providing considerable reward improvements over the previous suboptimal strategies, also has a major practical benefit. Run-time overhead is eliminated and existing scheduling disciplines may be used without modification with the computed optimal service times.

The imprecise computation (IC) model is a general scheduling framework that is capable of expressing the precision vs. timeliness tradeoff involved in many current real-time applications. In that model, each task comprises mandatory and optional parts. While allowing greater scheduling flexibility, the mandatory parts in the IC model still have hard deadlines, and hence they must be completed before the task's deadline, even in the presence of faults. In this paper, we address fault-tolerant (FT) scheduling issues for IC tasks. First, we propose two recovery schemes, namely immediate recovery and delayed recovery. These schemes can be readily applied to provide fault tolerance to the mandatory parts by scheduling the optional parts appropriately for recovery operations. After deriving the necessary and sufficient conditions for both schemes, we consider the FT-optimality problem, i.e. generating a schedule which is FT and whose reward is maximum among all possible FT schedules. For immediate recovery, we present and prove the correctness of an efficient FT-optimal scheduling algorithm. For delayed recovery, we show that the FT-optimality problem is NP-hard, and thus is intractable.

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part, with which a nondecreasing reward function is associated. Imprecise Computation and Increased-Reward-with-Increased-Service models fall within the scope of this framework. In this paper we address the reward-based scheduling problem for periodic tasks. For linear and concave reward functions we show: (a) the existence of an optimal schedule where the optional service time of a task is constant at every instance and (b) how to efficiently compute this service time. We also prove that RMS-h (RMS with harmonic periods), EDF and LLF policies are optimal when used with the optimal service times we computed, and that the problem becomes NP-Hard, when the reward functions are convex. Further, our solution eliminates run-time overhead, and makes possible the use of existing scheduling disciplines.