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.

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.

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.