Search

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.

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.

Because most tasks on real-time systems are conducted periodically, its execution pattern is highly predictable. While such a property of real-time systems allows developing the strong schedulability analysis tools providing high analytical capability, it also leads that security attackers could analyze the predictable execution patterns of real-time systems and use them as attack surfaces. Among the few approaches to foil such a timing-inference security attack, TaskShuffler as a schedule randomization protocol received considerable attention owing to its simplicity and applicability. However, the existing TaskShuffler is only applicable to uniprocessor platforms, where the task execution pattern is quite simple to analyze when compared to multiprocessor platforms. In this study, we propose a new schedule randomization protocol for real-time systems on symmetry multiprocessor platforms where all processors are composed of the same architecture, which extends the existing TaskShuffler initially designed for uniprocessor platforms.

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.

A timing constraint and a high level of reliability are the fundamental requirements for designing hard real-time systems. To support both requirements, the N modular redundancy (NMR) technique as a fault-tolerant real-time scheduling has been proposed, which executes identical copies for each task simultaneously on multiprocessor platforms, and a single correct one is voted on, if any. However, this technique can compromise the schedulability of the target system during improving reliability because it produces N identical copies of each job that execute in parallel on multiprocessor platforms, and some tasks may miss their deadlines due to the enlarged computing power required for completing their executions. In this paper, we propose task-level N modular redundancy (TL-NMR), which improves the system reliability of the target system of which tasks are scheduled by any fixed-priority (FP) scheduling without schedulability loss. Based on experimental results, we demonstrate that TL-NMR maintains the schedulability, while significantly improving average system safety compared to the existing NMR.

While recent studies addressed security attacks in real-time embedded systems, most of them assumed prior knowledge of parameters of periodic tasks, which is not realistic under many environments. In this paper, we address how to infer task parameters, from restricted information obtained by simple system monitoring. To this end, we first develop static properties that are independent of inference results and therefore applied only once in the beginning. We further develop dynamic properties each of which can tighten inference results by feeding an update of the inference results obtained by other properties. Our simulation results demonstrate that the proposed inference framework infers task parameters for RM (Rate Monotonic) with reasonable tightness, the ratio of exactly inferred task periods is 95.3% and 65.6%, respectively with low and high task set use. The results also discover that the inference performance varies with the monitoring interval length and the task set use.