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.

This paper proposes a cascaded backstepping control method with an augmented observer for the lateral control of an autonomous vehicle. The proposed cascaded backstepping control structure consists of an inner-loop electric power steering (EPS) system and an outer-loop lane-keeping system (LKS). The outer-loop controller for LKS calculates and provides the desired steering angle to the inner-loop EPS system for maintaining the vehicle at the center of the lane. Subsequently, the inner-loop controller for the EPS system generates steering torque to track the desired steering angle from the outer loop. The proposed method can guarantee the stability of the vehicle considering both inner-loop and outer-loop dynamics. In addition, an augmented observer affords robustness against unknown model parameters and external disturbances. The stability of the closed loop of the overall system, including the lateral dynamics and the EPS system, is proven using the input-to-state stable property. Controller design with consideration of the overall system can improve the lateral control performance.

In a traditional real-time system, the major requirement is to finish every real-time task within its predefined time. However, as a modern real-time system is connected to external networks and its subsystems are developed by different vendors, it becomes an important requirement to address the problem of information leakage on resources shared by different real-time tasks. This triggers studies that incorporate security mechanisms into the real-time scheduling. While it is one of the most well-known approaches to add the flush task (FT) mechanism and analyze its effect on timing guarantees, the existing FT approaches have been limited to a real-time system that employs at most one resource shared by real-time tasks executed on a uniprocessor platform. In this paper, we propose a flush task incorporated priority-inheritance protocol (FT-PIP) for global fixed-priority multiprocessor scheduling and develop its schedulability analysis, which is the first attempt that not only (a) supports timing guarantees but also (b) satisfies security constraints for (c) a multiprocessor platform with multiple shared resources. Via simulations, we demonstrate that FT-PIP and its schedulability analysis are effective in achieving both (a) and (b) for (c).

Component-based design has received considerable attention owing to its advantages in terms of security and safety when developing modern embedded systems. To effectively allocate computing resources to components in these systems, real-time component-based scheduling theory has been studied from various perspectives. The main advantage of component-based scheduling theory is that it guarantees the schedulability of an independent component and composability of multiple components. However, the existing component scheduling theory cannot be directly applied to real hardware platform due to an impractical assumption that resource allocation must be conducted across the continuum of real numbers, whereas actual operating systems (or virtualization systems) allocate resources in units of scheduling time quantum. In this study, we proposed a new efficient resource allocation and supply mechanism for quantumized hardware platforms while using real-number-based component interface. In simulation results with randomly-generated workloads, our approach reduced the overhead of existing approaches by up to 97.1% in an individual component. In composition of multiple components, our approach has up to 0.41 better acceptance ratio than existing approaches.

Non-preemptive scheduling is essential to tasks that inherently disallow any preemption and useful for tasks that exhibit extremely large preemption/migration overhead; however, studies of non-preemptive scheduling have not matured for real-time tasks subject to timing constraints. In this letter, we propose an improved schedulability test for non-preemptive fixed-priority scheduling (NP-FP), which offers timing guarantees for a set of real-time tasks executed on a multiprocessor platform. To this end, we first carefully investigate the NP-FP properties, and present an observation why the existing technique is pessimistic in calculating interference from higher-priority tasks. We then develop a new technique that tightly upper bounds the amount of the interference, and show how to incorporate the technique into the existing schedulability test. Via simulations, we demonstrate that our proposed test improves schedulability performance of NP-FP up to 18%, compared with the state-of-the-art existing tests.

Recently, traditional real-time systems that played a dedicated role in a limited environment have been evolving to interact with dynamically varying environments. In modern real-time systems, characteristics of real-time tasks such as computational demand and resource allocation can vary over time according to different circumstances, which is referred to as mode transition . In this paper, we focus on the problem of timing guarantees of a set of multi-mode tasks associated with mode transitions and develop an offline schedulability analysis, which does not require any online information; this is an important problem in the real-time systems area. The proposed schedulability analysis not only generalizes an existing framework designed for single-mode tasks, but also significantly improves the state-of-the-art framework designed for multi-mode tasks. Building on the proposed analysis, we also address the problem of enforcing the order of tasks within each mode transition and propose a task-level transition order assignment algorithm, yielding further improvement in schedulability performance. Through simulations, our proposed framework is shown to improve schedulability up to 777.3% over an existing schedulability analysis for multi-mode tasks, depending on the experiment setting under our evaluation environment.

Real-time scheduling is the primary research for designing real-time systems whose correctness is determined by not only logical correctness but also timely execution. Real-time scheduling involves two fundamental issues: scheduling algorithm design and schedulability analysis development, which aim at developing a prioritization policy for real-time tasks and offering their timing guarantees at design time, respectively. Among the numerous scheduling algorithms and schedulability analysis for a multiprocessor platform, the contention-free (CF) policy and response-time analysis (RTA) have received considerable attention owing to their wide applicability and high analytical performance, respectively. Notwithstanding their effectiveness, it has been conjectured that it is not feasible to exploit the two techniques together. In this study, we propose a new schedulability analysis for the CF policy, referred to as pseudo-response time analysis (PRTA), which exploits a new notion of pseudo-response time effectively capturing the time instant at which the schedulability of a task is guaranteed under the CF policy. To demonstrate the effectiveness of PRTA, we apply PRTA to the existing earliest deadline first and rate monotonic scheduling algorithms employing the CF policy, and show that up to 46.4% and 18.3% schedulability performance improvement can be achieved, respectively, compared to those applying the existing schedulability analysis.

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.

Zero-laxity (ZL) and contention-free (CF) policies have received considerable attention owing to their simplicity and applicability to real-time systems equipped with symmetry multiprocessors. Recently, the ZL policy for mixed-criticality (MC) systems has been proposed and studied, but the applicability to and performance of the CF policy for MC systems have not been investigated yet. In this paper, we propose the CF policy (as a scheduling policy) for MC symmetry multiprocessor systems, referred to as the MC systems tailored CF policy (MC-CF), and a schedulability analysis in support thereof. We define the notion of contention-free slots for two different criticalities (of MC systems) of tasks, propose a technique to limit the amount to be utilized for each task by defining an upper bound, and subsequently explain the way in which the contention-free slots are systematically utilized to improve the schedulability of MC symmetry multiprocessor systems. Following this, we develop a deadline analysis (DA) for MC-CF. Using our experimental results under various environmental settings, we demonstrate that MC-CF can significantly improve the schedulability of fixed-priority scheduling.

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.

The contention-free policy has received attention in real-time multiprocessor scheduling owing to its wide applicability and significant improvement in offline schedulability guarantees. Utilizing the notion of contention-free slots in which the number of active jobs is smaller than or equal to the number of processors, the policy improves the schedulability by offloading executions in contending time slots to contention-free ones. In this paper, we propose the multi-level contention-free policy by exploiting a new, generalized notion of multi-level contention-free slots. In a case study, we present how the multi-level contention-free policy is applied to EDF (Earliest Deadline First) scheduling and develop a schedulability test for EDF that adopts the new policy. Our evaluation results demonstrate that the multi-level contention-free policy significantly improves the schedulability by up to 4188% and 127%, compared to vanilla EDF and EDF adopting the existing contention-free policy, respectively.

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.

Hard real-time systems are employed in military, aeronautics, and astronautics fields where deployed systems are susceptible to software faults that can result in functional errors. Thus, there is a need to use fault-tolerant (FT) real-time scheduling. Among the various fault-tolerant real-time scheduling techniques, re-execution has been applied widely to existing real-time systems owing to its simplicity and applicability. However, re-execution requires multiple executions of every task, and some tasks miss their deadlines owing to the prolonged execution time, therefore, it has been found to be suitable for only soft real-time systems. In this paper, we propose an FT policy that can be incorporated into most (if not all) existing real-time scheduling algorithms on multiprocessor systems, which improves the reliability of the target system without a tradeoff against schedulability. As a case study, we apply the FT policy to existing fixed-priority scheduling and earliest deadline zero-laxity scheduling, and we demonstrate that it enhances reliability without schedulability loss.

General-Purpose computing on a Graphics Processing Unit (GPGPU) involves leveraging commodity GPUs as massively parallel processing units. GPGPU is an emerging computing paradigm for high-performance and data-intensive computations such as cryptographic operations. Although GPGPU is an attractive solution for accelerating modern cryptographic operations, the security challenges that stem from utilizing commodity GPUs remain an unresolved problem. In this paper, we present an On-demand Bootstrapping Mechanism for Isolated cryptographic operations (OBMI). OBMI transforms commodity GPUs into a securely isolated processing core for various cryptographic operations while maintaining cost-effective computations. By leveraging System Management Mode (SMM), a privileged execution mode provided by x86 architectures, OBMI implements a program and a secret key into the GPU such that they are securely isolated during the acceleration of cryptographic operations, even in the presence of compromised kernels. Our approach does not require an additional hardware-abstraction layer such as a hypervisor or micro-kernel, and it does not entail modifying the GPU driver. An evaluation of the proposed OBMI demonstrated that even adversaries with kernel privileges cannot gain access to the secret key, and it also showed that the proposed mechanism incurs negligible performance degradation for both the CPU and GPU.

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.

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.

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.

This paper presents an adaptive time-delayed control based on the sliding-mode (ATDC-SM). The proposed ATDC-SM provides a new adaptive law imposing time-varying boundedness that is developed to adjust the control gains appropriately while suppressing the negative impact generated by the robot manipulators. Moreover, the control gains are constructed as a continuous function with a fast adaptation rate and hence can remedy chattering and fluctuation inherent in the existing adaptive time-delayed control. These synergistic effects provide a fast convergence rate while producing stable control gains. Besides, the proposed ATDC-SM uses one-sample delayed estimation to cancel out complex nonlinear dynamics and unknown disturbances. Thus, it produces a simple structure but effective approach due to this estimation. From these benefits, the proposed ATDC-SM provides precise tracking performance without undesired side effects. It is shown that the tracking errors are uniformly ultimately bounded through a Lyapunov function. The effectiveness of the proposed ATDC-SM is illustrated through simulation with a one-link robot manipulator, which is compared to that of the existing control approaches.