State-of-the-art (SOTA) gradient-based adversarial attacks on spiking neural networks (SNNs), which largely rely on extending FGSM and PGD frameworks, face a critical limitation: substantial attack latency from multi-timestep processing, rendering them infeasible for practical real-time applications. This inefficiency stems from their design as direct extensions of ANN paradigms, which fail to exploit key SNN properties. In this paper, we propose the timestep compressed attack (TCA), a novel framework that significantly reduces attack latency. TCA introduces two components founded on key insights into SNN behavior. First, timestep-level backpropagation (TLBP) is based on our finding that global temporal information in backpropagation to generate perturbations is not critical for an attack’s success, enabling per-timestep evaluation for early stopping. Second, adversarial membrane potential reuse (A-MPR) is motivated by the observation that initial timesteps are inefficiently spent accumulating membrane potential, a warm-up phase that can be pre-calculated and reused. Our experiments on VGG-11 and ResNet-17 with the CIFAR-10/100 and CIFAR10-DVS datasets show that TCA significantly reduces the required attack latency by up to 56.6% and 57.1% compared to SOTA methods in white-box and black-box settings, respectively, while maintaining a comparable attack success rate.

Intermittent systems powered by harvested energy face significant challenges due to limited memory and fluctuating energy availability. These challenges are further amplified in real-time applications such as environmental monitoring, where multiple DNN (Deep Neural Network) tasks must satisfy strict timing guarantees and maintain high inference accuracy. Existing solutions based on lightweight static or dynamic DNNs suffer from the lack of energy adaptability and/or excessive memory overhead, making them unsuitable for real-time intermittent systems. To address these limitations, we propose LEAF, a novel layer-wise energy-adaptive framework for real-time intermittent systems executing multiple DNN tasks. LEAF consists of three key components: (i) a runtime-reconfigurable DNN model and training methodology that supports multiple latency–accuracy trade-offs without incurring additional memory overhead; (ii) an energy-aware time budget abstraction that integrates intermittent inference behavior into existing timing guarantee frameworks; and (iii) a runtime scheduling mechanism that jointly leverages the model and abstraction to ensure both timing guarantees and high inference accuracy. Experimental results demonstrate that LEAF ensures the timely, energy-aware execution of multiple DNN tasks with higher accuracy compared to existing solutions, validating its effectiveness for real-time intermittent systems.

Dynamic Voltage and Frequency Scaling (DVFS) is a key technology for enhancing power efficiency in computing devices. However, conventional DVFS methods struggle with the unique demands of mobile devices. Recent reinforcement learning (RL)-based approaches address this by tailoring to mobile-specific thermal and workload characteristics. Yet, these solutions make frequency adjustments that ignore device-specific configurations calibrated by vendors, neglect the impact of ambient and non-processor components—such as battery, display, and integrated circuits—that significantly affect processor thermal management, and rely on fixed environment-dependent parameters, limiting adaptability across different environments. To address these limitations, we propose EarDVFS, an environment-adaptable RL-based solution that employs proactive throttling to combine the strengths of traditional and RL-based methods, considers the temperatures of ambient and non-processor components for better thermal management, and features an environment-robust RL parameter design. Extensive experiments across varying ambient temperatures, devices, and workloads demonstrate that EarDVFS consistently enhances power efficiency by an average of 21.6% and up to 49.6% compared to default DVFS while maintaining performance. Furthermore, we conduct comprehensive ablation studies on the action, state, and reward elements of our RL model, confirming that each element significantly contributes to EarDVFS’s adaptability and effectiveness across diverse thermal environments.

Modern multi-object tracking (MOT) predominantly relies on the tracking-by-detection paradigm to construct object trajectories. Traditional MOT attacks primarily degrade detection quality in specific frames only, lacking efficiency, while state-of-the-art (SOTA) approaches induce persistent identity (ID) switches by manipulating object positions during the association phase, even after the attack ends. In this paper, we reveal that these SOTA attacks can be easily counteracted by adjusting distance-related parameters in the association phase, exposing their lack of robustness. To overcome these limitations, we propose BankTweak, a novel adversarial attack targeting feature-based MOT systems to induce persistent ID switches (efficiency) without modifying object positions (robustness). BankTweak exploits a critical vulnerability in the Hungarian matching algorithm of MOT systems by strategically injecting altered features into feature banks during the association phase. Extensive experiments on MOT17 and MOT20 datasets, combining various detectors, feature extractors, and trackers, demonstrate that BankTweak significantly outperforms SOTA attacks up to 11.8 times, exposing fundamental vulnerabilities in the tracking-by-detection framework.

Edge devices for robotics in hazardous environments, such as rescue drones, navigate complex terrains while transmitting images to remote servers for anomaly detection, including wildfires. However, these devices operate under strict resource constraints, prioritizing operational-critical tasks (e.g., autonomous navigation) while handling image-processing workloads with minimal overhead. Offloading computation to a remote server can alleviate this burden, but unstable network conditions can degrade accuracy and timeliness. To address these challenges, this paper presents a novel offloading framework that balances computational efficiency and accuracy in image-processing tasks. Specifically, it ensures (R1) a minimum accuracy level for individual image-processing tasks associated with different camera sensors and (R2) maximizes the overall image-processing accuracy across all sensors. Our approach builds on an edge-server collaborative image reconstruction architecture, where images are divided into patches and selectively reconstructed. To achieve R1 and R2, we introduce: (i) a hierarchical scheduler that effectively prioritizes patch transmissions under resource constraints and (ii) a feedback mechanism that adapts to network instability, ensuring reliable offloading and inference. Experimental results demonstrate that our framework maintains high accuracy and timely processing, even under network failures.

With the increasing popularity of electric vehicles (EVs), drivers want their vehicle batteries to be charged in a few minutes; at present, this is feasible only if battery service stations replace the EV battery pack with a fully charged battery pack. In this paper, we formulate the scheduling problem for battery swap stations, aiming to provide the drivers timing guarantees for different types of EVs, each with its own sporadic/periodic arrival pattern and deadline constraint. To solve this problem, we analyze its unique characteristics from a real-time scheduling perspective, with the main challenge being the circular timing dependency between two distinct scheduling processes: the swapping operation and the charging operation. We first derive a sufficient condition that decouples the dependency and then develop scheduling policies and timing guarantee techniques, designed for not only being specialized for the problem but also accommodating the sufficient condition in a time-predictable and resource-efficient manner. While the problem formulation and solution hold significance as the first attempt to establish real-time scheduling principles for battery swap stations, we also address how to accommodate real-world EV arrivals at a swapping station that do not necessarily follow a sporadic/periodic pattern. Finally, we evaluate the effectiveness of the proposed principles not only in addressing the formulated problem but also in accommodating real-world EV arrival patterns via simulation and a case study.

The development of parallel computing architectures has created a growing need for scheduling real-time gang tasks, in which a specified number of threads per task must be executed simultaneously under timing constraints. However, existing approaches struggle to handle a fundamental challenge the heterogeneity in the number of threads across gang tasks. To address the challenge, this paper proposes a novel scheduling framework, called Recursive Partitioned Scheduling (RPS), in which each partition can be recursively divided into subpartitions whose assigned processor sets are disjoint and collectively equal to that of the parent, forming a tree-like hierarchical structure. RPS provides a flexible interface that allows each task to be assigned to an appropriate level in the hierarchy based on the number of threads it requires. To fully exploit RPS, we adopt fixed-priority scheduling and address two key issues. First, we develop a tight schedulability analysis, which not only utilizes the well-known exact schedulability analysis results for uniprocessor scheduling but also leverages the relationship between intra-and inter-partition interference. Second, based on the insights from the analysis, we design an effective partition generation and task assignment algorithm specialized for RPS, and further enhance it through task priority reassignment. Simulation results demonstrate that our approach significantly outperforms existing approaches in terms of schedulability.

Consensus algorithms are widely adopted in clustered systems to distribute data efficiently, with Raft being a prominent failover algorithm due to its effectiveness and fault tolerance. However, Raft and other consensus algorithms do not provide timing guarantees, limiting their application to time-critical systems such as industrial control systems, drone swarms, and autonomous vehicle networks, where it is critical to distribute state machines in time and prevent multiple timing misses of data. In this paper, we propose CARTEL (Consensus Adapting Real-Time and Efficient Logging), a novel consensus algorithm that integrates time-predictability into the Raft framework. To achieve this aim, we examine Raft's mechanisms and identify the characteristics that impact the timing of data propagation within a distributed system. Based on these insights, we design CARTEL by developing two mechanisms that address the primary limitations of Raft: (i) CARTEL voting to solve the uncertainty of leader election timing, and (ii) CARTEL node buffer to limit the number of indeterminately deferred data during leader failure. Moreover, we propose how to utilize the mechanisms of CARTEL to ensure time-predictability in leader elections and mitigate the indeterminate nature of data logging during leader transitions, without harming the integrity of Raft. We validate the effectiveness of CARTEL through real-world implementation. The experiments confirm that CARTEL not only reduces the uncertainty of system recovery inherent in the election process (by 65.7% compared to Raft) but also enhances the integrity of the distributed system by guaranteeing timely data logging.

Detection Transformers (DETR) are increasingly adopted in autonomous vehicle (AV) perception systems due to their superior accuracy over convolutional networks. However, concurrently executing multiple DETR tasks presents significant challenges in meeting firm real-time deadlines (R1) and high accuracy requirements (R2), particularly for safety-critical objects, while navigating the inherent latency-accuracy trade-off under resource constraints. Existing real-time DNN scheduling approaches often treat models generically, failing to leverage Transformer-specific properties for efficient resource allocation. To address these challenges, we propose CF-DETR, an integrated system featuring a novel coarse-to-fine Transformer architecture and a dedicated real-time scheduling framework NPFP**. CF-DETR employs three key strategies (A1: coarse-to-fine inference, A2: selective fine inference, A3: multi-level batch inference) that exploit Transformer properties to dynamically adjust patch granularity and attention scope based on object criticality, aiming to satisfy R2. The NPFP** scheduling framework (A4) orchestrates these adaptive mechanisms A1-A3. It partitions each DETR task into a safety-critical coarse subtask for guaranteed critical object detection within its deadline (ensuring R1), and an optional fine subtask for enhanced overall accuracy (R2), while managing individual and batched execution. Our extensive evaluations on server, GPU-enabled embedded platforms, and actual AV platforms demonstrate that CF-DETR, under an NPFP** policy, successfully meets strict timing guarantees for critical operations and achieves significantly higher accuracy compared to existing baselines across diverse AV workloads.

While most existing battery cell balancing approaches were posttreatment (i.e., handling diverse voltage levels originating from different battery cell status), a pretreatment approach, called reconfiguration-assisted charging (RAC), was developed, which dynamically attaches a proper number of resistor arrays to each group of battery cells with similar status, preventing battery cell imbalance; note that this pretreatment approach can be used orthogonally with existing posttreatment approaches such as active/passive balancing. Relaxing its impractical assumptions of RAC (e.g., all necessary resistor arrays are deployed in the target system), this article proposesRAC$^+$, which realizes its practical and efficient use for the pretreatment concept of RAC. The experiment results demonstrate thatRAC$^+$achieves the same balancing performance asRACwhile reducing the number of required resistors by 69% compared toRAC. The extensive experiment results also show thatRAC$^+$is not only robust to various charging environments, but also proven to be effective in terms of minimizing power loss.

Even with advances in single-cell batteries, mobile users still experience low battery anxiety. By analyzing 19,855 hours of user behavior, we proposeMixMax, a heterogeneous battery system consisting of three complementary battery types tailored to minimizing low battery time. While the heterogeneous battery system offers an opportunity to simultaneously improve capacity and charging speed, one must face non-trivial challenges to design charge/discharge policies during runtime and determine the ratio of enclosed batteries. They are highly dependent on each other, which entails almost infinite candidates for the choice.MixMaxsimplifies this by reformulating the problem as an optimization problem, breaking it down into manageable sub-problems. However,MixMaxstill faces the challenge of catering to all users due to their diverse battery usage patterns. To address this, we introduce a customizedMixMaxthat groups users based on their usage patterns and provides tailored battery solutions. In evaluatingMixMax, we fabricate coin-cell batteries, develop a precise battery emulator using the fabricated batteries, and prototypeMixMaxon a real-world smartphone. Our evaluation shows thatMixMaxreduces low battery time by up to 24.6% without compromising capacity, volume, weight, or user behavior, and its customized version can further reduce it by up to 46.2%.

As the application scope of DNNs executed on microcontroller units (MCUs) extends to time-critical systems, it becomes important to ensure timing guarantees for increasing demand of DNN inferences. To this end, this paper proposes RT-MDM, the first RealTime scheduling framework for Multiple DNN tasks executed on an MCU using external memory. Identifying execution-order dependencies among segmented DNN models and memory requirements for parallel execution subject to the dependencies, we propose (i) a segment-group-based memory management policy that achieves isolated memory usage within a segment group and sharded memory usage across different segment groups, and (ii) an intra-task scheduler specialized for the proposed policy. Implementing RT-MDM on an actual system and optimizing its parameters for DNN segmentation and segment-group mapping, we demonstrate the effectiveness of RT-MDM in accommodating more DNN tasks while providing their timing guarantees.

The increasing complexity and memory demands of Deep Neural Networks (DNNs) for real-time systems pose new significant challenges, one of which is the GPU memory capacity bottleneck, where the limited physical memory inside GPUs impedes the deployment of sophisticated DNN models. This paper presents, to the best of our knowledge, the first study of addressing the GPU memory bottleneck issues, while simultaneously ensuring the timely inference of multiple DNN tasks. We propose RT-Swap, a real-time memory management framework, that enables transparent and efficient swap scheduling of memory objects, employing the relatively larger CPU memory to extend the available GPU memory capacity, without compromising timing guarantees. We have implemented RT-Swap on top of representative machine-learning frameworks, demonstrating its effectiveness in making significantly more DNN task sets schedulable at least 72% over existing approaches even when the task sets demand up to 96.2% more memory than the GPU's physical capacity.

A mixed-criticality (MC) system is a computational platform shared by tasks with two or more safety-critical levels. An important research topic related to MC systems is designing scheduling algorithms that can satisfy the computation requirements of tasks with different criticality levels. Numerous studies have focused on this topic, but only a few have considered parallel tasks. To address the research gap, we propose a dual-criticality scheduling algorithm based on federated scheduling for parallel tasks with Directed Acyclic Graph (DAG) structures. We particularly focus on the task set in which each task has a deadline longer than its release period. To the best of our knowledge, our work is the first that does not assume the constrained-or implicit-deadline in the MC DAG task model. In addition to simulation experiments, we demonstrate that our algorithm has a capacity augmentation bound of 4, providing a quantitative worst-case performance guarantee for our algorithm.

Vision-centric Bird’s Eye View (BEV) perception has become popular for enhancing the situational awareness of autonomous vehicles (AVs). It uses multiple cameras to create a 360° view, capturing essential details for the vehicle’s navigation and decision-making. However, reducing the end-to-end (e2e) BEV perception latency without sacrificing accuracy is challenging due to the lack of co-optimization of message communication and object detection. Prior work either compresses the dense detection model to reduce computation which can hurt accuracy and assume images are well synchronized, or focuses on worstcase communication delay without considering the characteristics of object detection. To meet this challenge, we propose RT-BEV, the first frame-work designed to co-optimize message communication and object detection to improve real-time e2e BEV perception without sacrificing accuracy. The main insight of RT-BEV lies in generating traffic environment- and context-aware Regions of Interest (ROIs) for AV safety, combined with ROI-aware message communication. RT-BEV features an ROI-aware Camera Synchronizer that adaptively determines message groups and allowable delays based on ROIs’ coverage. We also develop a ROIs Generator to model context-aware ROIs and a Feature Split & Merge component to handle variable-sized ROIs effectively. Furthermore, a Time Predictor forecasts timelines for processing ROIs, and a Coordinator jointly optimizes latency and accuracy for the entire e2e pipeline. We have implemented RT-BEV in a ROS-based BEV perception pipeline and evaluated it with the nuScenes dataset. RT-BEV is shown to significantly enhances real-time BEV perception, reducing average e2e latency by $1.5 \times$, maintaining high mean Average Precision (mAP), doubling the number of processed frames, and improving the frame efficiency score (FES) by $2.9 \times$ compared to the existing approaches. Moreover, RT-BEV is shown to reduce the worst-case e2e latency by $19.3 \times$.

Abstract This paper considers the real-time scheduling of a parallel task with reclaiming computing resources, which can be utilized for soft real-time tasks or switching to low-energy mode to save energy. Existing works allocate a rectangular piece of computing resources based on the worst-case characterizations of the task to guarantee the deadline, which inherently incurs severe resource wasting due to coarse-grained resource allocation. To address this resource-wasting problem, this paper proposes the ladder-like resource allocation (i.e., a series of rectangular pieces of computing resources). To characterize the ladder-like resource allocation, we present two concepts called resource distribution and allocation vector, which serve as the interfaces between hard and soft real-time tasks. For the former, we derive schedulability tests under the given two interfaces; for the latter, we discuss the methods of determining the two interfaces to reclaim computing resources. This paper is the first work to fully explore the concept of ladder-like resource allocation and its potential consequences on computing resources, soft real-time tasks, and energy. Experiments demonstrate that the proposed approach can effectively reclaim more computing resources than existing approaches while maintaining hard real-time guarantees.

Targeting a multiobject tracking (MOT) system with multiple MOT tasks, this article develops Batch-MOT, the first system design that achieves both (G1) timing guarantee and (G2) accuracy maximization, by utilizing batch execution that allows multiple deep neural network (DNN) executions to perform simultaneously in a single DNN inference resulting in significantly decreased execution time without accuracy loss. To this end, we propose an adaptable scheduling framework that allows run-time execution behaviors deviated from our base scheduling algorithm (i.e., nonpreemptive fixed-priority scheduling) without compromising G1. Based on the adaptable framework, we then develop 1) a run-time batching mechanism that finds and executes a batch set of MOT tasks and 2) a run-time idling mechanism that waits for the future releases of MOT tasks for batch execution. Both run-time mechanisms can achieve G1 and G2 without incurring high run-time overhead, as they systematically exploit the run-time execution behaviors allowed by the adaptive framework. Our evaluation conducted with a real-world data set demonstrates the effectiveness of Batch-MOT in improving tracking accuracy while providing a timing guarantee compared to the state-of-the-art real-time MOT system for multiple MOT tasks.

Despite the physical advance of an existing single-cell battery system, mobile users are still suffering from low battery anxiety. With a careful analysis of users' battery usage behavior collected for 19,855 hours, we propose a heterogeneous battery system, MixMax, consisting of three complementary battery types tailored to minimizing the low battery time. While composing a heterogeneous battery system opens up a chance to simultaneously improve the capacity and the charging speed, one must face non-trivial challenges to determine the ratio of enclosed batteries and charge/discharge policies during the run-time. They are highly dependent on each other, which entails almost infinite candidates for the choice. MixMax gracefully unwinds the dependencies as it formulates the decision-making problem into an optimization problem and decomposes it into multiple sub-problems instead. To evaluate MixMax, we fabricate coin-cell batteries and experiment with them to model an accurate battery emulator which sophisticatedly reproduces the dynamics of battery systems. Our experimental results demonstrate that MixMax can reduce the low battery time by up to 24.6% without compromising capacity, volume, weight, and more importantly, users' battery usage behavior. In addition, we prototype MixMax on a smartphone, presenting the practicality of MixMax on mobile systems.

Although blockchain technology is being increasingly utilized across various fields, the challenge of providing timing guarantees for transactions remains unmet, which is an obstacle in implementing blockchain solutions for time-sensitive applications such as high-frequency trading and real-time payments. In this paper, we propose the first solution to achieve a timing guarantee on blockchain. To this end, we raise and address two issues for timely transactions on a blockchain: (a) architectural support, and (b) real-time scheduling principles specialized for blockchain. For (a), we modify an existing blockchain network, offering an interface to preferentially select the transactions with the earliest deadlines. We then extend the blockchain network to provide the flexibility of the number of generated blocks at a single block time. Under such architectural supports, we achieve (b) with three steps. First, to resolve a discrepancy between a periodic request of a transaction-generating node and the corresponding arrival on a block-generating node, we translate the former into the latter, which eases the modeling of the transaction load imposed on the blockchain network. Second, we derive a schedulability condition of the modeled transaction load, which guarantees no missed deadline for all transactions under a work-conserving deadline-based scheduling policy. Last, we develop a lazy scheduling policy and its condition, which reduces the number of generated blocks without compromising the degree of timing guarantees for the work-conserving policy. By implementing RT-blockchain on top of an existing open-source blockchain project, we demonstrate the effectiveness of the proposed scheduling principles with architectural supports in not only ensuring timely transactions but also reducing the number of generating blocks.

As real-time object detection systems, such as autonomous cars, need to process input images acquired from multiple cameras, they face significant challenges in delivering accurate and timely inferences often based on machine learning (ML). To meet these challenges, we want to provide different levels of object detection accuracy and timeliness to different portions within each input image with different criticality levels. Specifically, we develop DNN-SAM, a dynamic Split-And-Merge Deep Neural Network (DNN) execution and scheduling framework, that enables seamless split-and-merge DNN execution for unmodified DNN models. Instead of processing an entire input image once in a full DNN model, DNN-SAM first splits a DNN inference task into two smaller sub-tasks-a mandatory sub-task dedicated for a safety-critical (cropped) portion of each image and an optional sub-task for processing a down-scaled image–then executes them independently, and finally merges their results into a complete inference. To achieve DNN-SAM’s timely and accurate detection of objects in each image, we also develop two scheduling algorithms that prioritize sub-tasks according to their criticality levels and adaptively adjust the scale of the input image to meet the timing constraints while minimizing the response time of mandatory sub-tasks or maximizing the accuracy of optional sub-tasks. We have implemented and evaluated DNN-SAM on a representative ML framework. Our evaluation shows DNN-SAM to improve detection accuracy in the safety-critical region by $2.0-3.7\times$ and lower average inference latency by $4.8-9.7\times$ over existing approaches without violating any timing constraints.

Different from existing MOT (Multi-Object Tracking) techniques that usually aim at improving tracking accuracy and average FPS, real-time systems such as autonomous vehicles necessitate new requirements of MOT under limited computing resources: (R1) guarantee of timely execution and (R2) high tracking accuracy. In this paper, we propose RT-MOT, a novel system design for multiple MOT tasks, which addresses R1 and R2. Focusing on multiple choices of a workload pair of detection and association, which are two main components of the tracking-by-detection approach for MOT, we tailor a measure of object confidence for RT-MOT and develop how to estimate the measure for the next frame of each MOT task. By utilizing the estimation, we make it possible to predict tracking accuracy variation according to different workload pairs to be applied to the next frame of an MOT task. Next, we develop a novel confidence-aware real-time scheduling framework, which offers an offline timing guarantee for a set of MOT tasks based on non-preemptive fixed-priority scheduling with the smallest workload pair. At run-time, the framework checks the feasibility of a priority-inversion associated with a larger workload pair, which does not compromise the timing guarantee of every task, and then chooses a feasible scenario that yields the largest tracking accuracy improvement based on the proposed prediction. Our experiment results demonstrate that RT-MOT significantly improves overall tracking accuracy by up to 1.5 ×, compared to existing popular tracking-by-detection approaches, while guaranteeing timely execution of all MOT tasks.

Due to its efficient and predictable utilization of modern computing units, recent studies have paid attention to gang scheduling in which all threads of a real-time task should be concurrently executed on different processors. However, the studies have been biased to preemptive gang scheduling, although non-preemptive gang scheduling (NPG) is practical for inherently non-preemptive tasks and tasks that incur large preemption overhead. In this paper, focusing on a new type of priority-inversion incurred by NPG, we design a generalized NPG framework, called NPG*, under which each task has an option to allow or disallow the situation that incurs the priority-inversion specialized for NPG. To demonstrate the effectiveness of NPG* in terms of timing guarantees, we target NPG*-FP by employing fixed-priority scheduling (FP) as a prioritization policy, and develop the first NPG*-FP schedulability test and its improved version under a given assignment of the allowance/disallowance option to each task. We then develop the optimal allowance/disallowance assignment algorithm, which finds an assignment (if exists) that makes a target task set schedulable by the proposed schedulability tests. Via simulations, we demonstrate that the assignment algorithm associated with the schedulability tests for NPG*-FP can find a number of additional schedulable task sets, each of which has not been covered by the traditional NPG framework.

This paper aims at developing a tight schedulability analysis for real-time global gang scheduling, in which threads of each task subject to timing requirements are assigned to multiple processors in parallel (i.e., following the rigid gang task model). Focusing on the RTA (Response Time Analysis) framework known to exhibit high schedulability performance for other task models, we address two following issues: i) how to generalize the existing RTA framework to gang scheduling and utilize existing RTA components of other task models for the generalized framework, and ii) how to incorporate important characteristics of gang scheduling into the RTA framework in a systematic way to minimize the framework's pessimism in judging schedulability. By addressing the issues, our RTA framework enables to derive tight schedulability analysis for EDF, FP and potentially more scheduling algorithms for real-time global gang scheduling. Also, our simulation results demonstrate that the proposed RTA framework outperforms/complements existing studies for real-time global/non-global gang scheduling, in terms of schedulability performance.

Mixed-criticality (MC) scheduling becomes popular in real-time systems as it supports different criticality levels in a resource-efficient manner. Although it has been well established (i) how to guarantee MC schedulability offline, existing studies have paid less attention to achieve (ii) how to minimize deadline misses of low-criticality tasks at runtime; in addition, it has not matured yet how to address (ii) without compromising (i). In this paper, we propose MC-FLEX, which employs a task-level mode transition mechanism (as opposed to system-level one). MC-FLEX not only determines time instants at which each high-criticality task enters and exits the critical mode in a task level, but also selects time instants and target low-criticality task(s) to be dropped and resumed for each task-level mode change of individual high-criticality tasks, yielding the achievement of both (i) and (ii). Via simulation results, we demonstrate that the proposed framework reduces the job deadline miss ratio of low-criticality tasks at runtime (by over 54.8% compared to the existing work), without compromising offline MC schedulability.

As multiple software components with different safety-criticality levels are integrated on a shared computing platform, a real-time embedded system becomes a mixed-criticality (MC) system, which should provide timing guarantees at all different levels of assurance to software components with different criticality levels. In the real-time systems community, the concept of an MC system is regarded as a promising, emerging solution to solve an inherent challenge of real-time systems: pessimistic reservation of computing resources, which yields a low resource-utilization for the sake of guaranteeing timing requirements. Since a timing guarantee should be provided before a real-time system starts to operate, its feasibility has been extensively studied for single-criticality systems; however, the same cannot be said for MC systems. In this article, we develop necessary feasibility tests for MC real-time embedded systems, which is the first study that yields non-trivial results for MC necessary feasibility on both uniprocessor and multiprocessor platforms. To this end, we investigate characteristics of MC necessary feasibility conditions, and identify new challenges posed by the characteristics. By addressing those challenges, we develop two collective necessary feasibility tests and their simplified versions, which are able to exploit a tradeoff between capability in finding infeasible task sets and time-complexity. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets for both uniprocessor and multiprocessor platforms, which have been proven neither feasible nor infeasible by any existing studies.

As machine learning (ML) has been proven effective in solving various problems, researchers in the real-time systems (RT) community have recently paid increasing attention to ML. While most of them focused on timing issues for ML applications (i.e., RT for ML), only a little has been done on the use of ML for solving fundamental RT problems. In this paper, we aim at utilizing ML to solve a fundamental RT problem of priority assignment for global fixed-priority preemptive (gFP) scheduling on a multiprocessor platform. This problem is known to be challenging in the case of a large number (n) of tasks in a task set because exhaustive testing of all priority assignments (as many as n!) is intractable and existing heuristics cannot find a schedulable priority assignment, even if exists, for a number of task sets. We systematically incorporate RT domain knowledge into ML and develop an ML framework tailored to the problem, called PAL. First, raising and addressing technical issues including neural architecture selection and training sample regulation, we enable PAL to infer a schedulable priority assignment of a set of n tasks, by training PAL with same-size (i.e., with n tasks) samples each of whose schedulable priority assignment has already been identified. Second, considering the exhaustive testing of all priority assignments of each task set with large n makes it intractable to provide training samples to PAL, we derive inductive properties that can generate training samples with large n from those with small n, through empirical observation of PAL and mathematical analysis of the target gFP schedulability test. Finally, utilizing the inductive properties and additional techniques, we propose how to systematically implement PAL whose training sample generation process not only yields unbiased samples but also is tractable even for large n. Our experimental results demonstrate PAL covers a number of additional task sets, each of which has never been proven schedulable by any existing approaches for gFP.

Deep neural networks (DNNs) have shown remarkable success in various machine-learning (ML) tasks useful for many safety-critical, real-time embedded systems. The foremost design goal for enabling DNN execution on real-time embedded systems is to provide worst-case timing guarantees with limited computing resources. Yet, the state-of-the-art ML frameworks hardly leverage heterogeneous computing resources (i.e., CPU, GPU) to improve the schedulability of real-time DNN tasks due to several factors, which include a coarse-grained resource allocation model (one-resource-per-task), the asymmetric nature of DNN execution on CPU and GPU, and lack of schedulability-aware CPU/GPU allocation scheme. This paper presents, to the best of our knowledge, the first study of addressing the above three major barriers and examining their cooperative effect on schedulability improvement. In this paper, we propose LaLaRAND, a real-time layer-level DNN scheduling framework, that enables flexible CPU/GPU scheduling of individual DNN layers by tightly coupling CPU-friendly quantization with fine-grained CPU/GPU allocation schemes (one-resource-per-layer) while mitigating accuracy loss without compromising timing guarantees. We have implemented and evaluated LaLaRAND on top of the state-of-the-art ML framework to demonstrate its effectiveness in making more DNN task sets schedulable by 56% and 80% over an existing approach and a baseline (vanilla PyTorch), respectively, with only up to -0.4% of performance (inference accuracy) difference.

Although essential for Inherently non-preemptive tasks and favorable to tasks with large preemption/migration overheads, non-preemptive scheduling has not been thoroughly studied compared to preemptive scheduling. In particular, existing studies for non-preemptive scheduling could not effectively exploit being non-work-conserving (i.e., idling processor(s) intentionally), failing to achieve its full schedulability capability. In this paper, we propose the first non-preemptive scheduling framework that covers work-conserving-infeasible task sets (each of which is proven unschedulable by every work-conserving non-preemptive scheduling), without knowledge of future release patterns of tasks (i.e., without clairvoyance). To this end, we first discover the following principle: without clairvoyance, it is impossible to generate a feasible schedule for work-conserving-infeasible task sets on a uniprocessor platform. To make it possible on a multi-processor platform, we design the NWC(N)-NP-* framework that systematically idles up to N processors so as to enable N designated tasks (that yield work-conserving-infeasibility) to be schedulable without clairvoyance, and derive important properties of the framework. We then target the framework associated with fixed- priority scheduling (as a prioritization policy), and develop its schedulability test by utilizing the framework's properties. Our simulation results demonstrate that the proposed framework successfully covers a number of work-conserving-infeasible task sets, none of which can be deemed schedulable by any previous approach.

Modern electric systems, such as electric vehicles, mobile robots, nano satellites, and drones, require to support various power-demand operations for user applications and system maintenance. This, in turn, calls for advanced power management that jointly considers power demand by the operations and power supply from various sources, such as batteries, solar panels, and supercapacitors. In this article, we develop a power scheduling framework for a reliable energy storage system with multiple power-supply sources and multiple power-demand operations. Specifically, we develop offline power-supply guarantee analysis and online power management. The former provides an offline power-supply guarantee such that every power-demand operation completes its execution in time while the sum of power required by individual operations does not exceed the total power supplied by the entire energy storage system at any time; to this end, we develop a plain power-supply analysis as well as its improved version using real-time scheduling techniques. On the other hand, the latter efficiently utilizes the surplus power available at runtime for improving system performance; we propose two approaches, depending on whether future scheduling information of power-demanding tasks is available or not. For evaluation, we perform simulations to evaluate both the plain and improved analyses for offline power guarantee under various synthetic power-demand operations. In addition, we have built a simulation model and demonstrated that the proposed framework with the offline analysis and online management not only guarantees the required power-supply, but also enhances system performance by up to 56.49 percent.

The development of complex cyber-physical systems necessitates real-time networking with timing guarantees even in the presence of a link fault. Targeting firm real-time flows with the maximum allowable number of continuous deadline misses, this paper introduces FR-SDN, a fault-resilient SDN (Software-Defined Networking) framework that satisfies the timing requirements of firm real-time flows. To this end, we first investigate individual steps for path restoration: fault recognition, path recalculation, and path reassignment. We then design novel system architecture that reduces the delay of the fault recognition and path reassignment steps to potentially assign more time budget to the path recalculation step. Based on the calculation of tight upper-bounds on the delays in individual steps under the proposed system design, we derive a necessary feasibility condition that guarantees the timing requirements of firm real-time flows, and we calculate a time budget for the path recalculation step. Finally, we develop a multi-constrained path finding algorithm that can dynamically adjust the scope of flows to reroute according to the time budget. To the best of our knowledge, FR-SDN is the first study on adaptive path restoration for real-time flows, taking into account path restoration delay and fault tolerance constraints in case of link fault. We have implemented and evaluated FR-SDN on top of Open vSwitch to demonstrate its effectiveness, achieving an order of magnitude reduction in path restoration delay. In addition, we have deployed FR-SDN into a 1/10 scale autonomous vehicle and have shown, via an in-depth case study of adaptive cruise control, that FR-SDN is able to meet all fault tolerance requirements so that it can behave similarly as if there were no link failure.

While feasibility of timing guarantees has been extensively studied for single-criticality (SC) task systems, the same cannot be said true for mixed-criticality (MC) task systems. In particular, there exist only a few studies that address necessary feasibility conditions for MC task systems, and all of them have derived trivial results from existing SC studies that rely on simple demand-supply comparison. In this paper, we develop necessary feasibility tests for MC task systems on a uniprocessor platform, which is the first study that yields non-trivial results for MC necessary feasibility. To this end, we investigate characteristics of MC necessary feasibility conditions. Due to the existence of the mode change and consequences thereof, the characteristics pose new challenges that cannot be resolved by existing techniques for SC task systems, including how to calculate demand when the mode change occurs, how to determine the target sub-intervals for demand-supply comparison, how to derive an infeasibility condition from demand-supply comparisons with different possible mode change instants, how to select a scenario to specify the mode change instant without the target scheduling algorithm, and how to find infeasible task sets with reasonable time-complexity. By addressing those challenges, we develop a new necessary feasibility test and its simplified version. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets which have been proven neither feasible nor infeasible by any existing studies.

Battery aging is one of the critical issues in battery-powered electric systems. However, this issue has not received much attention in the real-time systems community. In this paper, we present the first attempt to translate the problem of minimizing battery aging subject to timing requirements into a real-time scheduling problem, addressing the following issues. (i) Can scheduling make a systematic impact on battery aging? If so, which scheduling principles are favorable to minimizing battery aging? (ii) If there exists any, how can we build upon the scheduling principle to guarantee real-time requirements? For (i), we first illuminate the connection between task scheduling and battery aging minimization and then derive a principle for task scheduling from abstracting the complicated dynamics of battery aging, which is to minimize the variance of total power consumption over time. In addition, we implement a battery aging simulator and use it to verify the effectiveness of the proposed principle in minimizing battery aging and its impact on quantitative improvement. For (ii), we propose a scheduling framework that separates control for timing guarantees from that for battery aging minimization. Such a separation allows reducing the complexity significantly such that we can employ existing scheduling algorithm and schedulability analysis for real-time guarantee and tailor the proposed scheduling principle to decelerate battery aging without taking real-time guarantees into accounts. Our simulation results show that the proposed framework can extend the battery lifespan by up to 144.4%.

These days, the term of Internet of Things (IoT) becomes popular to interact and cooperate with individual smart objects, and one of the most critical challenges for IoT is to achieve efficient resource sharing as well as ensure safety-stringent timing constraints. To design such reliable real-time IoT, this paper focuses on the concept of mixed-criticality (MC) introduced to address the low processor utilization on traditional real-time systems. Although different worst-case execution time estimates depending on criticality are proven effective on processor scheduling, the MC concept is not yet mature on distributed systems (such as IoT), especially with end-to-end deadline guarantee. To the best of our knowledge, this paper presents the first attempt to apply the MC concept into interference (or jitter), which is a complicated source of pessimism when analyzing the schedulability of distributed systems. Our goal is to guarantee the end-to-end deadlines of high-criticality flows and minimize the deadline miss ratio of low-criticality flows in distributed systems. To achieve this goal, we introduce a jitter-based MC (JMC) scheduling framework, which supports node-level mode changes in distributed systems. We present an optimal feasibility condition (subject to given schedulability analysis) and two policies to determine jitter-threshold values to achieve the goal in different conditions. Via simulation results for randomly generated workloads, JMC outperforms an existing criticality-monotonic scheme in terms of achieving higher schedulability and fewer deadline misses.

Despite recent advances, there still remain many problems to design reliable cyber-physical systems. One of the typical problems is to achieve a seemingly conflicting goal, which is to support timely delivery of real-time flows while improving resource efficiency. Recently, the concept of mixed-criticality (MC) has been widely accepted as useful in addressing the goal for real-time resource management. However, it has not been yet studied well for real-time communication. In this paper, we present the first approach to support MC flow scheduling on switched Ethernet networks leveraging an emerging network architecture, software-defined networking (SDN). Though SDN provides flexible and programmatic ways to control packet forwarding and scheduling, it yet raises several challenges to enable real-time MC flow scheduling on SDN, including: 1) how to handle (i.e., drop or re-prioritize) out-of-mode packets in the middle of the network when the criticality mode changes and 2) how the mode change affects end-to-end transmission delays. Addressing such challenges, we develop MC-SDN that supports real-time MC flow scheduling by extending SDN-enabled switches and OpenFlow protocols. It manages and schedules MC packets in different ways depending on the system criticality mode. To this end, we carefully design the mode change protocol that provides analytic mode change delay bound, and then resolve implementation issues for system architecture. For evaluation, we implement a prototype of MC-SDN on top of Open vSwitch, and integrate it into a real world network testbed as well as a 1/10 autonomous vehicle. Our extensive evaluations with the network testbed and vehicle deployment show that MC-SDN supports MC flow scheduling with minimal delays on forwarding rule updates and it brings a significant improvement in safety in a real-world application scenario.

Safety-critical cyber-physical systems like autonomous cars require not only different levels of assurance, but also close interactions with dynamically-changing physical environments. While the former has been studied extensively by exploiting the notion of mixed-criticality (MC) systems, the latter has not, especially in conjunction with MC systems. To fill this important gap, we conduct an in-depth case study, demonstrating the importance of capturing current physical states, and introduce the problem of achieving efficient utilization of computing resources under varying physical states in MC systems. To solve this problem, we first develop a physical-state-aware MC task model, which is a generalization of the existing basic MC task model. We then propose new slack concepts tailored to the new task model, which enable efficient utilization of computing resources for MC systems. Finally, we develop a physical-state-aware dynamic slack management framework and demonstrate how to utilize the new MC task model and slack concepts towards efficient system utilization. We show, via a case study and in-depth evaluation, that the proposed framework makes 20x less low-criticality jobs dropped over a popular MC scheduling algorithm without compromising the MC-schedulability requirements.

A cyber-physical system (CPS) usually contains multiple control loops, each responsible for controlling different physical subprocesses, that run simultaneously upon a shared platform. The foremost design goal for CPSes is to guarantee system stability and control quality with limited cyber resources. We show, via an in-depth case study, that two inter-related design parameters - sampling period and consecutive control update misses - play a key role in determining stability and control performance. However, most CPS designs, such as control-schedule co-design and fault-tolerant scheduling, focus on either sampling period or control update misses alone, but not both. To remedy this problem, we propose a new CPS task model that captures both system stability and control performance in terms of sampling period and maximum allowable number of consecutive control update misses. To demonstrate the utility and power of this model, we develop two new scheduling mechanisms, offline parameter assignment and online state-aware scheduling. The former determines the sampling period and the maximum allowable number of consecutive job deadline misses for each task while preserving system stability. The latter then generates a schedule by exploiting the state of each physical subprocess to manage job deadline misses so as to improve the overall system performance without compromising system stability. Our in-depth evaluation results demonstrate that the proposed task model and the corresponding scheduling algorithm not only enable the efficient use of computing resource, but also significantly improve control performance without compromising system stability.

In this paper, we present the first approach to support mixed-criticality (MC) flow scheduling on switched Ethernet networks leveraging an emerging network architecture, Software-Defined Networking (SDN). Though SDN provides flexible and programmatic ways to control packet forwarding and scheduling, it yet raises several challenges to enable real-time MC flow scheduling on SDN, including i) how to handle (i.e., drop or reprioritize) out-of-mode packets in the middle of the network when the criticality mode changes, and ii) how the mode change affects end-to-end transmission delays. Addressing such challenges, we develop MC-SDN that supports real-time MC flow scheduling by extending SDN-enabled switches and OpenFlow protocols. It manages and schedules MC packets in different ways depending on the system criticality mode. To this end, we carefully design the mode change protocol that provides analytic mode change delay bound, and then resolve implementation issues for system architecture. For evaluation, we implement a prototype of MC-SDN on top of Open vSwitch, and integrate it into a real world network testbed as well as a 1/10 autonomous vehicle. Our extensive evaluations with the network testbed and vehicle deployment show that MC-SDN supports MC flow scheduling with minimal delays on forwarding rule updates and it brings a significant improvement in safety in a real-world application scenario.

Real-time scheduling for Mixed-Criticality (MC) systems has received a growing attention as real-time embedded systems accommodate various tasks with different levels of criticality. While many studies have addressed how to guarantee timing requirements for MC systems with uniprocessor and multiprocessors, most of them have focused on supporting preemptive tasks. On the other hand, there have been few studies to address non-preemptive scheduling especially for MC multiprocessor platforms, in which the jobs under execution cannot be preempted by other jobs. In this paper, we develop schedulability tests for non-preemptive scheduling, which is the first attempt for MC multiprocessor systems. To this end, we first generalize an existing NP-EDF (Non-Preemptive Earliest Deadline First) schedulability test developed for single-criticality multiprocessor systems, towards for MC multiprocessor systems. For the generalization, we introduce new timing guarantee techniques for the system transition between two different criticalities, which is one of the key features in MC systems. We next extend the proposed NP-EDF schedulability test towards NP-EDFVD (NP-EDF with Virtual Deadlines) that is specialized for MC systems, and pose a virtual deadline assignment problem. We develop an optimal virtual deadline assignment policy using a control knob of the system-level deadline-reduction parameter and then a suboptimal one for the task-level parameter. Our simulation results demonstrate that the NP-EDFVD schedulability test with the proposed virtual deadline assignment policies finds a number of additional schedulable task sets, which are not schedulable by the NP-EDF schedulability test.

In the real-time systems community, many studies have addressed how to efficiently utilize a multiprocessor platform so as to accommodate as many periodic/sporadic real-time tasks as possible without violating any timing constraints. The scheduling theory has sufficiently matured for a set of implicit-deadline tasks (the relative deadline equal to the period), yielding a class of optimal scheduling algorithms. However, the same does not hold for a set of constrained-deadline tasks (the relative deadline no larger than the period) in that those task sets have been fully covered by neither existing implicit-deadline optimal scheduling algorithms nor heuristic scheduling algorithms., In this paper, we propose a scheduling framework that not only takes advantage of both existing implicit-deadline optimal and heuristic algorithms, but also surpasses both in finding schedulable constrained-deadline task sets. The proposed framework logically divides a given task set into the higher- and lower-priority classes and schedules the classes using an implicit-deadline optimal algorithm and a heuristic algorithm, respectively. Then, while the proposed framework guarantees schedulability of tasks in the higher-priority class by the target implicit-deadline optimal algorithm, we need to address the following technical issues for enabling tasks in the lower-priority class to efficiently reclaim remaining processor capacity while guaranteeing their schedulability: (i) division of a given task set into the two classes, (ii) selection/development of scheduling algorithms for the two classes, and (iii) development of a schedulability test for the framework with given (i) and (ii). We present a general case showing how to address (i)-(iii), and then a specific case addressing how to further improve schedulability by utilizing characteristics of the specific case. Our simulation results demonstrate that the proposed framework outperforms all existing scheduling algorithms in covering schedulable task sets; in particular, if we focus on task sets with the system density larger than the number of processors, the framework finds up to 446.3% additional schedulable task sets, compared to task sets covered by at least one of existing scheduling algorithms.

A time instant is said to be a critical instant for a task, if the task's arrival at the instant makes the duration between the task's arrival and completion the longest. Critical instants for a task, once revealed, make it possible to check the task's schedulability by investigating situations associated with the critical instants. This potentially results in efficient and tight schedulability tests, which is important in real-time systems. For example, existing studies have discovered critical instants under preemptive fixed-priority scheduling (P-FP), which limit interference from carry-in jobs, yielding the state-of-the-art schedulability tests on both uniprocessor and multiprocessor platforms. However, studies on schedulability tests associated with critical instants have not matured yet for non-preemptive scheduling, especially on a multiprocessor platform. In this paper, we find necessary conditions for critical instants for non-preemptive global fixed-priority scheduling (NP-FP) on a multiprocessor platform, and develop a new schedulability test that takes advantage of the finding for reducing carry-in jobs' interference. Evaluation results show that the proposed schedulability test finds up to 14.3 percent additional task sets schedulable by NP-FP, which are not deemed schedulable by the state-of-theart NP-FP schedulability test.

With the widespread adoption of multi-core architectures, it is becoming more important to develop software in ways that takes advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced for targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to parallel task models, including DAG models, on multi-core platforms, without knowing an optimal schedule. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in global EDF schedulability analysis for parallel tasks. In particular, we identify that our proposed schedulability tests are adaptive to different degrees of thread-level parallelism and scalable to the number of processors, resulting in substantial improvement of schedulability for parallel tasks on multi-core platforms.

The real-time systems community has widely studied real-time scheduling, focusing on how to guarantee schedulability (i.e., timely execution) of a set of real-time tasks. However, there still exist a number of task sets that are actually schedulable by a target scheduling algorithm, but proven schedulable by none of existing schedulability tests, especially on a multiprocessor. In this paper, we propose a new paradigm for real-time scheduling, called time-reversibility, which views real-time scheduling under a change in the sign of time, and present how to utilize the paradigm for schedulability improvement. To this end, we first define the notion of a time-reversed scheduling algorithm and a time-reversible schedulability test; for example, the time-reversed scheduling algorithm against Earliest Deadline First (EDF) is Latest Release-time First (LRF). Then, we develop time-reversibility theories for schedulability improvement, which utilizes the definitions so as to compose schedulability. Finally, we generalize the definitions and theories to job-level dynamic-priority scheduling in which the priority of a job may vary with time, such as Earliest Deadline first until Zero Laxity (EDZL). Specifically, we accommodate time-varying job parameters to the time-reversibility definitions, and adapt the time-reversibility theories for the additional necessary deadline-miss conditions specialized for a class of job-level dynamic-priority scheduling algorithms. As case studies, we demonstrate that the time-reversibility theories help to find up to 13.6 percent additional EDFand EDZL-schedulable task sets.

Since modern electric systems require to support various power-demand operations for user applications and system maintenance, they need advanced power management that jointly considers power demand by the operations and power supply from various sources, such as batteries, solar panels, and supercapacitors. In this paper, we develop a power scheduling framework for a reliable energy storage system with multiple power-supply sources and multiple power-demand operations. First, we provide an offline power-supply guarantee such that every power-demand operation completes its execution in time while the sum of power required by individual operations does not exceed the total power supplied by the entire energy storage system at any time. We find similarities between this and a real-time scheduling problem, and make a power-supply guarantee using real-time scheduling techniques. Second, we propose online power management that efficiently utilizes the surplus power (available at run-time) for system performance improvement. Our experimental results on a prototype demonstrate that the proposed framework not only guarantees the required power supply, but also enhances system performance by up to 33.1%.

Motivated by the cutting-edge two-type heterogeneous multicore chips, such as ARM's big.LITTLE, that offer a practical support for migration, this paper studies the global (or fully-migrative) approach to two-type heterogeneous multicore scheduling. Our goal is to design an optimal fully-migrative scheduling framework. To achieve this goal in an efficient and simple manner, we break the scheduling problem into two subproblems: workload assignment and schedule generation. We propose a per-cluster workload assignment algorithm, called Hetero-Split, that determines the fractions of workload of each task to be assigned to both clusters without losing feasibility with the complexity of O(n log n), where n is the number of tasks. Furthermore, it provides a couple of important properties (e.g., a dual property) that help to generate an optimal schedule efficiently. We also derive scheduling guidelines to design optimal schedulers for two-type heterogeneous multicore platforms, called Hetero-Fair. By tightly coupling the solutions of Hetero-Split and Hetero-Fair, we develop the first optimal two-type heterogeneous multicore scheduling algorithm, called Hetero-Wrap, that has the same complexity (O(n)) as in the identical multicore case. Finally, concerning a practical point of view, we derive the first bounds on the numbers of intra-and inter-cluster migrations under two-type heterogeneous multicore scheduling, respectively.

Modern electric vehicles are equipped with an advanced battery management system, responsible for providing the necessary power efficiently from batteries to electric motors while maintaining the batteries within an operational condition. Because discharge-rate and temperature of batteries affect their health and efficiency significantly, batteries are managed to mitigate their discharge and thermal stresses. In this paper, we develop a real-time, efficient integrated management system for discharge-rate and temperature of batteries. To achieve this objective, we first construct a prognosis system predicting the likely states of batteries' capacity and capability. Based on prognostic estimates of the impact of temperature and discharge-rate on the performance, we solve an optimization problem to search for efficient discharging and cooling scheduling. Our experimentation and simulation demonstrate that the proposed management enhances system performance up to 85.3%.

With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms often comes with several different schedulability tests, especially when it is difficult to find exact schedulability tests for the algorithm. Such tests usually find different task sets deemed schedulable even under the same scheduling algorithm. While these different tests have been compared with each other in terms of schedulability performance, little has been done on how to combine such different tests to improve the overall schedulability of a given scheduling algorithm beyond a simple union of their individual schedulability. Motivated by this, we propose a composition theory for schedulability tests with two new methods. The first method composes task-level timing guarantees derived from different schedulability tests, and the second one derives system-level schedulability results from a single schedulability test. The unified composition theory with these two methods then utilizes existing schedulability tests effectively so as to cover additional schedulable task sets. The proposed composition theory is shown to be applicable to most existing preemptive/non-preemptive scheduling algorithms. We also present three case-studies, demonstrating how and by how much the theory can improve schedulability by composing existing schedulability tests. Our evaluation results also show that the composition theory makes it possible to cover up to 181.7 percent additional schedulable task sets for preemptive fpEDF, preemptive EDF and non-preemptive EDF scheduling algorithms beyond their existing tests.

Electric vehicles (EVs) are equipped with a large number of expensive battery cells, necessitating an effective battery management system (BMS) which protects the battery cells from harsh conditions while providing the required power efficiently. The discharge/charge rate affects battery health significantly, and existing BMSes employ simple discharge/charge rate scheduling so as to prevent weak cells from excessive discharge/charge. In this paper, we design and evaluate the real-time management of battery discharge/charge rate to extend battery life for EVs based on the physical dynamics and operation history of batteries. We first explore a modern energy storage system for EVs to capture physical dynamics and their impact on the battery discharge/charge rate, for example, a regenerative braking system for reusing the dissipated energy leads to current surges into the batteries, which shortens battery life. Based on understanding of the effects of discharge/charge rate in an energy storage system, we devise control knobs for manipulating the rate. Then, we design an adaptive discharge/charge rate management algorithm that determines the control knobs with a reconfigurable energy storage architecture. Our in-depth evaluation results demonstrate that the proposed discharge/charge rate management improves battery life up to 37.7% at little additional cost over the existing energy storage systems.

For timing guarantees of a set of real-time tasks under a target scheduling algorithm, a number of schedulability tests have been studied. However, there still exist many task sets that are potentially schedulable by a target scheduling algorithm, but proven schedulable by none of existing schedulability tests, especially on a multiprocessor platform. In this paper, we propose a new notion of time-reversibility of schedulability tests, which yields tighter schedulability guarantees by viewing real-time scheduling under a change in the sign of time. To this end, we first define the notion of a time-reversed scheduling algorithm against a target scheduling algorithm, for example, the time-reversed scheduling algorithm against EDF (Earliest Deadline First) is LCFS (Last-Come, First-Served), and the converse also holds. Then, a schedulability test for a scheduling algorithm is said to be time-reversible with respect to schedulability, if all task sets deemed schedulable by the test are also schedulable by its time-reversed scheduling algorithm. To exploit the notion of time-reversibility for tighter schedulability guarantees, we not only prove time-reversibility of an existing schedulability test, but also develop a new time-reversible schedulability test, both of which cover additional schedulable task sets. Next, we generalize the time-reversibility theory towards partial execution. Utilizing the notion, we can assure the schedulability of a task under a target scheduling algorithm in a divide-and-conquer manner: (i) the first some units of execution guaranteed by a schedulability test for the scheduling algorithm, and (ii) the remaining execution guaranteed by a time-reversible (with respect to partial execution) schedulability test for its time-reversed scheduling algorithm. Such a divide-and-conquer approach has not been directly applied to existing schedulability tests in that they cannot address (ii) effectively. As a case study, this paper develops RTA (Response-Time Analysis) for LCFS, proves its time-reversibility, and applies the divide-and-conquer approach to the test along with an existing EDF schedulability test. Our simulation results show that the time-reversibility theory helps to find up to 13.1% additional EDF-schedulable task sets on a multiprocessor platform.

The earliest-deadline-first (EDF) policy has been widely studied for the scheduling of real-time jobs for its effectiveness and simplicity. However, since each preemption incurs an additional delay to the execution of jobs, the effectiveness of EDF is affected greatly by the underlying preemption policy that determines if and when a higher-priority job is allowed to preempt a currently executing lower-priority job. To address this problem, we propose a new and better (in meeting job deadlines) preemption policy of EDF, given a non-zero preemption delay. Specifically, we propose a controlled preemption (CP) policy that controls the condition of preempting jobs, whereas existing approaches focus on that of preempted jobs. We define cp-EDF in which the CP policy is applied to EDF, and analyze its schedulability. This schedulability analysis is then utilized to develop an algorithm that assigns the optimal control parameters of cp-EDF. Our in-depth evaluation has demonstrated that cp-EDF with the optimal parameter assignment improves EDF schedulability over existing preemption policies by up to 7.4%.

A time slot is defined as contention-free if the number of jobs with remaining executions in the slot is no larger than the number of processors, or contending , otherwise. Then an important property holds that in any contention-free slot, all jobs with remaining executions are guaranteed to be scheduled as long as the scheduler is work-conserving. This article aims at improving schedulability by utilizing the contention-free slots. To achieve this, this article presents a policy (called CF policy) that moves some job executions from contending slots to contention-free ones. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from jobs is reduced when their executions are postponed to contention-free slots. Simulation results demonstrate that the CF policy, incorporated into existing algorithms, significantly improves schedulability of those existing algorithms.

While tasks may be preemptive or non-preemptive (due to their transactional operations), deadline guarantees in multi-core systems have been made only for those task sets in each of which all tasks are preemptive or non-preemptive, not a mixture thereof,i.e., fully preemptive or fully non-preemptive. In this paper, we first develop a schedulability analysis framework that guarantees the timing requirements of a given task set in which a task can be either preemptive or non-preemptive in multi-core systems. We then apply this framework to the prioritization polices of EDF (earliest deadline first) and FP (fixed priority), yielding schedulability tests of mpn-EDF (Mixed Preemptive/Non-preemptive EDF) and mpn-FP, which are generalizations of corresponding fully-preemptive and non-preemptive algorithms, i.e., fp-EDF and np-EDF, and fp-FP and np-FP. In addition to their timing guarantees for any task set that consists of a mixture of preemptive and non-preemptive tasks, the tests outperform the existing schedulability tests of np-EDF andnp-FP (i.e., special cases of mpn-EDF and mpn-FP). Using these tests, we also improve schedulability by developing an algorithm that optimally disallows preemption of a preemptive task under a certain assumption. We demonstrate via simulation that the algorithm finds up to 47.6 percent additional task sets that are schedulable with mpn-FP (likewise mpn-EDF), but not with fp-FP and np-FP (likewisefp-EDF and np-EDF).

The potential of multi-core chips for high performance and reliability at low cost has made them ideal computing platforms for embedded real-time systems. As a result, power management of a multi-core chip has become an important issue in the design of embedded real-time systems. Most existing approaches have been designed to regulate the behavior of average power consumption, such as minimizing the total energy consumption or the chip temperature. However, little attention has been paid to the worst-case behavior of instantaneous power consumption on a chip, called chip-level peak power consumption, an important design parameter that determines the cost and/or size of chip design/packaging and the underlying power supply. We address this problem by reducing the chip-level peak power consumption at design time without violating any real-time constraints. We achieve this by carefully scheduling real-time tasks, without relying on any additional hardware implementation for power management, such as dynamic voltage and frequency scaling. Specifically, we propose a new scheduling algorithm FPΘthat restricts the concurrent execution of tasks assigned on different cores, and perform its schedulability analysis. Using this analysis, we develop a method that finds a set of concurrent executable tasks, such that the design-time chip-level peak power consumption is minimized and all timing requirements are met. We demonstrate via simulation that the proposed method not only keeps the design-time chip-level peak power consumption as low as the theoretical lower bound for trivial cases, but also reduces the peak power consumption for non-trivial cases by up to 12.9 percent compared to the case of no restriction on concurrent task execution.

The trend towards multi-core/many-core architectures is well underway. It is therefore becoming very important to develop software in ways that take advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to synchronous parallel task models on multi-core platforms. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in EDF schedulability analysis for synchronous parallel tasks.

Satellites are indispensable for broadcast, weather forecast, navigation, and many other applications, but their design entails a number of stringent requirements, such as limited space and weight, impossible/costly online repairs, severe radiation, and a wide range of temperature they have to withstand. These requirements can only be met by an effective, robust co-design of physical and computing (control) parts of each satellite, making them prototypical cyber-physical systems (CPSes). Of the various CPS issues related to satellites, this paper focuses on offline design and online management of satellite power systems. Specifically, we analyze and model unique characteristics of power supply and demand of a satellite, which are dictated by the periodicity of power generation from solar panels and the nonlinear behavior of rechargeable battery cells. Based on the understanding of these characteristics, we first propose how to find the best configuration (e.g., the number, the arrangement, and the type) of solar panels and battery cells at design time, such that all tasks can be executed without power shortage throughout the satellite's mission lifetime. Second, we propose how to manage power online so as to execute the highest QoS versions of tasks (thus yielding the most power-effective performance) without compromising the power-sufficiency guarantee under a given configuration. As a case study, we study cubic-shaped nanosatellites, which have been launched multiple times since 2004. We borrow their architecture, configuration and parameters, and demonstrate the effectiveness of our design and management of satellite power systems.

To enable real-time systems to adapt to dynamically changing environments, update functionalities and/or accommodate those tasks migrated from other failed sub-systems, there have been a number of studies on making timing guarantees while accounting for change of parameters and addition/deletion of tasks. While most of them have dealt with "transition" protocols that delay next task releases or discard the unfinished tasks released before the transition, such protocols are not suitable for many control systems in which missing/delaying control updates (by completing periodic tasks) even during a transition or mode-change may cause system instability or incur a significant incremental operational cost. In this paper, we focus on a transition protocol that does not miss/delay control updates during a system transition, and develop a new schedulability analysis for the transition in a real-time multi-core system, which provides sufficient timing guarantees without requiring any online information, such as the release and execution patterns of tasks and the start time of a transition. To achieve this, we extend an existing popular schedulability analysis framework for nontransitional tasks, and identify the scenarios that maximize the duration of a task's interference to another task in the case of a transition. Since the analysis works for any arbitrary transition order of tasks, we can improve the schedulability performance by enforcing a specific order. We formulate the problem of assigning an optimal transition order, and develop a solution by deriving some properties of optimality. Our evaluation results demonstrate that the proposed solution finds more schedulable task sets, which are not covered by naive approaches.

In real-time systems, correctness depends not only on functionality but also on timeliness. A great number of scheduling theories have been developed for verification of the temporal correctness of jobs (software) in such systems. Among them, the Earliest Deadline first until Zero-Laxity (EDZL) scheduling algorithm has received growing attention thanks to its effectiveness in multicore real-time scheduling. However, the true potential of EDZL has not yet been fully exploited in its schedulability analysis as the state-of-the-art EDZL analysis techniques involve considerable pessimism. In this paper, we propose a new EDZL multicore schedulability test. We first introduce an interesting observation that suggests an insight toward pessimism reduction in the schedulability analysis of EDZL. We then incorporate it into a well-known existing Earliest Deadline First (EDF) schedulability test, resulting in a new EDZL schedulability test. We demonstrate that the proposed EDZL test not only has lower time complexity than existing EDZL schedulability tests, but also significantly improves the schedulability of EDZL by up to 36.6 percent compared to the best existing EDZL schedulability tests.

We present a novel, linear programming (LP)-based scheduling algorithm that exploits heterogeneous multicore architectures such as CPUs and GPUs to accelerate a wide variety of proximity queries. To represent complicated performance relationships between heterogeneous architectures and different computations of proximity queries, we propose a simple, yet accurate model that measures the expected running time of these computations. Based on this model, we formulate an optimization problem that minimizes the largest time spent on computing resources, and propose a novel, iterative LP-based scheduling algorithm. Since our method is general, we are able to apply our method into various proximity queries used in five different applications that have different characteristics. Our method achieves an order of magnitude performance improvement by using four different GPUs and two hexa-core CPUs over using a hexa-core CPU only. Unlike prior scheduling methods, our method continually improves the performance, as we add more computing resources. Also, our method achieves much higher performance improvement compared with prior methods as heterogeneity of computing resources is increased. Moreover, for one of tested applications, our method achieves even higher performance than a prior parallel method optimized manually for the application. We also show that our method provides results that are close (e.g., 75 percent) to the performance provided by a conservative upper bound of the ideal throughput. These results demonstrate the efficiency and robustness of our algorithm that have not been achieved by prior methods. In addition, we integrate one of our contributions with a work stealing method. Our version of the work stealing method achieves 18 percent performance improvement on average over the original work stealing method. This result shows wide applicability of our approach.

In global real-time multiprocessor scheduling, a recent analysis technique for Task-level Fixed-Priority (TFP) scheduling has been shown to outperform many of the analyses for Job-level Fixed-Priority (JFP) scheduling on average. Since JFP is a generalization of TFP scheduling, and the TFP analysis technique itself has been adapted from an earlier JFP analysis, this result is counter-intuitive and in our opinion highlights the lack of good JFP scheduling techniques. Towards generalizing the superior TFP analysis to JFP scheduling, we propose the Smallest Pseudo-Deadline First (SPDF) JFP scheduling algorithm. SPDF uses a simple task-level parameter called pseudo-deadline to prioritize jobs, and hence can behave as a TFP or JFP scheduler depending on the values of the pseudodeadlines. This natural transition from TFP to JFP scheduling has enabled us to incorporate the superior TFP analysis technique in an SPDF schedulability test. We also present a pseudo-deadline assignment algorithm for SPDF scheduling that extends the well-known Optimal Priority Assignment (OPA) algorithm for TFP scheduling. We show that our algorithm is optimal for the derived schedulability test, and also present a heuristic to overcome the computational complexity issue of the optimal algorithm. Our simulation results show that the SPDF algorithm with the new analysis significantly outperforms state-of-the-art TFP and JFP analysis.

Interest in real-time multiprocessor scheduling has been rekindled as multi-core chips are increasingly used for embedded real-time systems. While tasks may be preemptive or non-preemptive (due to their transactional operations), deadline guarantees are usually made only for those task sets in each of which all tasks are preemptive or non-preemptive, not a mixture thereof, i.e., all or nothing. In this paper, we develop a schedulability analysis framework that guarantees the timing requirements of a given task set in which a task can be either preemptive or non-preemptive. As an example, we apply this framework to the prioritization policy of EDF (Earliest Deadline First), yielding schedulability tests of mpn-EDF (Mixed Preemptive/Non-preemptive EDF), which is a generalization of both fp-EDF (fully-preemptive EDF) and np-EDF (non-preemptive EDF). In addition to their deadline guarantees for any task set that is composed of a mixture of preemptive and non-preemptive tasks, the tests outperform the existing schedulability tests of np-EDF (a special case of mpn-EDF) by up to 109.1%. Using these tests, we also improve schedulability by disallowing preemptions of some preemptive tasks. For this, we develop an algorithm that optimally disallows preemption of a preemptive task under a certain assumption, and demonstrate via simulation that the algorithm discovers up to 30.9% additional task sets that are schedulable with the proposed scheduling scheme, but not with fp-EDF or np-EDF.

It is widely assumed that scheduling real-time tasks becomes more difficult as their deadlines get shorter. With deadlines shorter, however, tasks potentially compete less with each other for processors, and this could produce more contention-free slots at which the number of competing tasks is smaller than or equal to the number of available processors. This paper presents a policy (called CF policy) that utilizes such contention-free slots effectively. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from tasks is reduced when their executions are postponed to contention-free slots. Finally, using the properties of the CF policy, we derive a counter-intuitive claim that shortening of task deadlines can help improve schedulability of task systems. We present heuristics that effectively reduce task deadlines for better scheduability without performing any exhaustive search.

The current industry trend is towards using Commercially available Off-The-Shelf (COTS) based multicores for developing real time embedded systems, as opposed to the usage of custom-made hardware. In typical implementation of such COTS-based multicores, multiple cores access the main memory via a shared bus. This often leads to contention on this shared channel, which results in an increase of the response time of the tasks. Analyzing this increased response time, considering the contention on the shared bus, is challenging on COTS-based systems mainly because bus arbitration protocols are often undocumented and the exact instants at which the shared bus is accessed by tasks are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. This paper makes three contributions towards analyzing tasks scheduled on COTS-based multicores. Firstly, we describe a method to model the memory access patterns of a task. Secondly, we apply this model to analyze the worst case response time for a set of tasks. Although the required parameters to obtain the request profile can be obtained by static analysis, we provide an alternative method to experimentally obtain them by using performance monitoring counters (PMCs). We also compare our work against an existing approach and show that our approach outperforms it by providing tighter upper-bound on the number of bus requests generated by a task.

In distributed soft real-time systems, maximizing the aggregate quality-of-service (QoS) is a typical system-wide goal, and addressing the problem through distributed optimization is challenging. Subtasks are subject to unpredictable failures in many practical environments, and this makes the problem much harder. In this paper, we present a robust optimization framework for maximizing the aggregate QoS in the presence of random failures. We introduce the notion of K-failure to bound the effect of random failures on schedulability. Using this notion we define the concept of K-robustness that quantifies the degree of robustness on QoS guarantee in a probabilistic sense. The parameter K helps to tradeoff achievable QoS versus robustness. The proposed robust framework produces optimal solutions through distributed computations on the basis of Lagrangian duality, and we present some implementation techniques. Our simulation results show that the proposed framework can probabilistically guarantee sub-optimal QoS which remains feasible even in the presence of random failures.

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.

In a mobile ad hoc network (MANET), it has been addressed that packet losses due to collision are often misinterpreted as routing failures, and cause unnecessary overhead for routing maintenance. There have been several attempts to avoid the unnecessary overhead through reducing collision losses. They are effective in a static topology where most losses are due to collision. In a dynamic topology, however, packets are lost due to actual routing failures (induced by mobility) as well as due to collision, and efforts for reducing collision are not enough. In this paper, we propose a new scheme for adjusting the limit of RTS retransmissions. In the proposed scheme, we treat packet losses differently as follows: (a) upon collisions, we increase the limit to reduce collision losses; and (b) upon routing failures, we decrease the limit to avoid unnecessary retransmissions. Through extensive simulations, it is shown that the proposed scheme effectively improves throughput in various scenarios and outperforms other comparable schemes.

Regarding to address allocation, a mobile ad hoc network (MANET) may suffer from the lack of address and network partition/merging due to mobility of nodes. In this paper, we propose a new address allocation protocol for dealing with those problems. The proposed protocol is developed based on disjoint address set distribution with binary splitting for scalability, and provides special treatments for resolving the lack of addresses. We also present an effective technique for handling network partition and merging. Through simulation, we show that the proposed protocol is effective to allocate addresses in a MANET with reasonable latency and communication overhead.