Containerisation is becoming a cornerstone of modern distributed systems, thanks to their lightweight virtualisation, high portability, and seamless integration with orchestration tools such as Kubernetes. The usage of containers has also gained traction in real-time cyber-physical systems, such as software-defined vehicles, which are characterised by strict timing requirements to ensure safety and performance. Nevertheless, ensuring real-time execution of co-located containers is challenging because of mutual interference due to the sharing of the same processing hardware. Existing parallel computing frameworks such as Ray and its Kubernetes-enabled variant, KubeRay, excel in distributed computation but lack support for scheduling policies that allow guaranteeing real-time timing constraints and CPU resource isolation between containers, such as the SCHED_DEADLINE policy of Linux. To fill this gap, this paper extends Ray to support real-time containers that leverage SCHED_DEADLINE. To this end, we propose KubeDeadline, a novel, modular Kubernetes extension to support SCHED_DEADLINE. We evaluate our approach through extensive experiments, using synthetic workloads and a case study based on the MobileNet and EfficientNet deep neural networks. Our evaluation shows that KubeDeadline ensures deadline compliance in all synthetic workloads, adds minimal deployment overhead (in the order of milliseconds), and achieves lower worst-case response times, up to 4 times lower, than vanilla Kubernetes under background interference.

This paper presents a unified formal framework, called ReTA, that allows users to definescheduling problemsusing a user-friendly domain-specific language (DSL) and automatically obtain response times of jobs in return. ReTA supports user-defined online scheduling policies (beyond work-conserving or priority-based scheduling) for heterogeneous computing resource types with multiple instances per type (e.g., multiple CPU cores, GPUs, DSPs, and FPGAs on one single chip), thus supporting global, partitioned, and clustered scheduling. In the current version of ReTA, we focus on non-preemptive periodic tasks as these are susceptible to scheduling anomalies and hence harder to analyze. ReTA performs response-time analysis by constructing atimed labeled transition system(TLTS) from the domain model as a basis for performing a reachability analysis enriched with efficient state-space reduction techniques. Our empirical evaluations show that ReTA identifies up to50 times more schedulable task setsthan fixed-point iteration-based analyses. With a runtime on the order of a few minutes, ReTA produces highly accurate resultstwo-orders of magnitude fasterthan an exact Timed Automata-based analysis in UPPAAL (e.g., for systems with 16 cores and 32 tasks).

Centralised servers provide on-demand resources to process offloaded workloads from computing nodes. While server-based computing has been successful for applications with soft timing constraints, it falls short for safety-critical real-time systems with hard timing requirements. To bridge this gap, we develop a job-level admission test to satisfy the requirements for real-time applications deployed on a server by extending the “(M, K)-firm weakly hard” model to server systems, ensuring timely processing of server requests. We introduce an admission policy to regulate the workload and prevent deadline misses while attempting to admit more requests than the minimum required by the initial (M, K) constraints. The admission policy is designed to allow an optimal resource allocation to applications deployed on the server.11This work is an extension of our work-in-progress paper at RTAS'24 [1].

Ensuring deadlines of hard real-time applications in server-based deployments is a challenging problem, particularly if the workload arrives following an arbitrary arrival curve. This work extends the “(M, /K)-firm weakly hard” model to server-based systems, ensuring timely processing of real-time requests to the server. We introduce an admission policy to regulate the remote server workload and prevent deadline misses while attempting to admit more requests than the minimum required, when possible. We guarantee the weakly hard constraints through optimal resource allocation and server confiauration.

Real-time systems are commonly used in safety-critical applications which require tasks to be completed before their deadlines, even in the presence of faults. Thus, fault tolerance becomes essential to ensure a certain level of reliability in safety-critical real-time systems [1]. To achieve fault tolerance in computer systems, redundancy can be implemented either in space (spatial redundancy) or time (time redundancy) [2]. Unlike spatial redundancy which involves increasing hardware resources, time redundancy focuses on re-execution or multiple executions of software on the same hardware resources [3] and therefore is better suited for embedded systems with limited cost and size constraints that are subject to transient faults more often than permanent faults [2], [4].

While multicore real-time systems are extensively employed in the industry, research gaps still exist in developing a scalable analysis to find tight bounds on the worst-case response time (WCRT) of tasks scheduled by global preemptive scheduling policies. Additionally, the presence of release jitter poses a challenge where examining the earliest and latest release times may not derive WCRT. The existing analyses either provide very conservative bounds or face challenges in scaling to systems with numerous cores and tasks. This work provides preliminary foundations to derive tight WCRT bounds for tasks scheduled by global preemptive job-level fixed-priority scheduling policies (e.g., EDF and FP) on homogeneous multicore platforms by performing a reachability analysis using time-label-transition systems. Our solution uses 2 orders of magnitude less memory than UPPAAL and identifies on average 12% (up to 39%) more schedulable task sets than sufficient schedulability analyses (e.g., for systems with 4 cores and 10 tasks).

Schedulability analyses check whether all tasks in a task set will meet their timing requirements. They thus provide a boolean answer. Some analyses may also compute bounds on the worst-case response-time (WCRT) of tasks. However, only knowing WCRT is often not enough to understand which tasks are involved in deadline-miss scenarios and under what conditions those scenarios may happen. Therefore, it is hard to infer what must be fixed to make unschedulable task sets schedulable. This issue is exacerbated when tasks are non-preemptive since they are subject to timing anomalies that are non-trivial to analyze. The schedule-abstraction technique is a relatively scalable reachability-based response-time analysis that explores the space of possible schedules to detect potential deadline misses. There-fore, it can tell which jobs (of which tasks) are involved in a deadline-miss scenario. However, the schedule abstraction framework is not yet able to provide concrete release and execution times (and therefore concrete schedules) for those jobs. The reason is that, to reduce memory consumption, the schedule abstraction framework deliberately forgets information about the job execution ordering that led to a state. It also merges states to defer state-space explosion during the state-space exploration. In this work, we propose a technique to derive concrete schedules resulting in deadline misses by augmenting the exploration phase of the schedule-abstraction technique to carry minimal extra information that allows resolving ambiguities while tracing back jobs involved in deadline-miss scenarios using our own partial-order planning algorithm.

Abstract Response-time analysis (RTA) has been a means to evaluate the temporal correctness of real-time systems since the 1970 s. While early analyses were successful in capturing the exact upper bound on the worst-case response-time (WCRT) of systems with relatively simple computing platforms and task activation models, nowadays we see that most existing RTAs either become pessimistic or do not scale well as systems become more complex (e.g., parallel tasks running on a multicore platform). To make a trade-off between accuracy and scalability, recently, a new reachability-based RTA, called schedule-abstraction graph (SAG), has been proposed. The analysis is at least three orders of magnitude faster than other exact RTAs based on UPPAAL. However, it still has a fundamental limitation in scalability as it suffers from state-space explosion when there are large uncertainties in the timing parameters of the input jobs (e.g., large release jitters or execution-time variations). This could impede its applicability to large industrial use cases, or to be integrated with automated tools that explore alternative design choices. In this paper, we improve the scalability of the SAG analysis by introducing partial-order reduction rules that avoid combinatorial exploration of all possible scheduling decisions. We include systems with dependent and independent task execution models (i.e., with and without precedence constraint). Our empirical evaluations show that the proposed solution is able to reduce the runtime by five orders of magnitude and the number of explored states by 98% in comparison to the original SAG analysis. These achievements come only at a negligible cost of an over-estimation of 0.1% on the actual WCRT. We applied our solution on an automotive case study showing that it is able to scale to realistic systems made of hundreds of tasks for which the original analysis fails to finish.

The temporal correctness of safety-critical systems is typically guaranteed via a response-time analysis (RTA). However, as systems become complex (e.g., parallel tasks running on a multicore platform), most existing RTAs either become pessimistic or do not scale well. To make a trade-off between accuracy and scalability, recently, a new reachability-based RTA, called schedule-abstraction graph (SAG), has been proposed. The analysis is at least three orders of magnitude faster than other exact RTAs based on UPPAAL.One fundamental limitation of the SAG analysis is that it suffers from state-space explosion when there are large uncertainties in the timing parameters of the input jobs, which may impede its applicability to some industrial use cases. In this paper, we improve the scalability of the SAG analysis by introducing partial-order reduction (POR) rules that avoid combinatorial exploration of all possible scheduling decisions. An empirical evaluation shows that our solution is able to reduce the runtime by five orders of magnitude and the number of explored states by 98%, at a negligible cost of an over-estimation of 0.1% on the tasks’ worst-case response-time (WCRT). We applied our solution on an automotive case study showing that it is able to scale to realistic systems made of hundreds of tasks for which the original analysis fails to finish.

Abstract This paper presents results and observations from a survey of 120 industry practitioners in the field of real-time embedded systems. The survey provides insights into the characteristics of the systems being developed today and identifies important trends for the future. It extends the results from the survey data to the broader population that it is representative of, and discusses significant differences between application domains. The survey aims to inform both academics and practitioners, helping to avoid divergence between industry practice and academic research. The value of this research is highlighted by a study showing that the aggregate findings of the survey are not common knowledge in the real-time systems community.

Abstract With the growth in complexity of real-time embedded systems, there is an increasing need for tools and techniques to understand and compare the observed runtime behavior of a system with the expected one. Since many real-time applications require periodic interactions with the environment, one of the fundamental problems in guaranteeing their temporal correctness is to be able to infer the periodicity of certain events in the system. The practicability of a period inference tool, however, depends on both its accuracy and robustness (also its resilience) against noise in the output trace of the system, e.g., when the system trace is impacted by the presence of aperiodic tasks, release jitters, and runtime variations in the execution time of the tasks. This work (i) presents the first period inference framework that uses regression-based machine-learning (RBML) methods, and (ii) thoroughly investigates the accuracy and robustness of different families of RBML methods in the presence of uncertainties in the system parameters. We show, on both synthetically generated traces and traces from actual systems, that our solutions can reduce the error of period estimation by two to three orders of magnitudes w.r.t. the state of the art.

The secure functioning of automotive systems is vital to the safety of their passengers and other roadway users. One of the critical functions for safety is the controller area network (CAN), which interconnects the safety-critical electronic control units (ECUs) in the majority of ground vehicles. Unfortunately CAN is known to be vulnerable to several attacks. One such attack is the bus-off attack, which can be used to cause a victim ECU to disconnect itself from the CAN bus and, subsequently, for an attacker to masquerade as that ECU. A limitation of the bus-off attack is that it requires the attacker to achieve tight synchronization between the transmission of the victim and the attacker’s injected message. In this paper, we introduce a schedule-based attack framework for the CAN bus-off attack that uses the real-time schedule of the CAN bus to predict more attack opportunities than previously known. We describe a ranking method for an attacker to select and optimize its attack injections with respect to criteria such as attack success rate, bus perturbation, or attack latency. The results show that vulnerabilities of the CAN bus can be enhanced by schedulebased attacks.

The temporal correctness of safety-critical systems is typically guaranteed via a response-time analysis (RTA). However, as the systems become complex (e.g., parallel tasks running on a multicore platform), most existing RTAs either become pessimistic or do not scale with respect to e.g., the number of tasks or period values. To make a trade-off between accuracy and scalability, recently, a new reachability-based RTA called schedule-abstraction graph (SAG) has been introduced by Nasri et al. It explores the space of possible decisions that a scheduling policy can take while dispatching a set of tasks or jobs on processing resources. The analysis is at least three orders of magnitude faster than other exact RTAs and is able to identify many more schedulable task sets than the existing fixed-point iteration-based analyses. One fundamental limitation of the SAG analysis is that in its reachability graph, each edge can only account for a single scheduling decision. Therefore, the graph grows exponentially when there are large uncertainties in the release time or execution time of the jobs. In this paper, we improve the scalability of the SAG analysis by introducing partial-order reduction (POR) rules that allow combining multiple scheduling decisions on one edge and hence avoiding combinatorial exploration of all possible scheduling decisions. An empirical evaluation shows that our solution is able to reduce the runtime by five orders of magnitude and the number of explored states by 98%.

This paper presents results and observations from a survey of 120 industry practitioners in the field of real-time embedded systems. The survey provides insights into the characteristics of the systems being developed today and identifies important trends for the future. The survey aims to inform both academics and practitioners, helping to avoid divergence between industry practice and fundamental academic research.

Motivated by the lack of response-time analyses for non-preemptive global scheduling that consider shared resources, this paper provides such an analysis for global job-level fixed-priority (JLFP) scheduling policies and FIFO-ordered spin locks. The proposed analysis computes response-time bounds for a set of resource-sharing jobs subject to release jitter and execution-time uncertainties by implicitly exploring all possible execution scenarios using state-abstraction and state-pruning techniques. A large-scale empirical evaluation of the proposed analysis shows it to be substantially less pessimistic than simple execution-time inflation methods, thanks to the explicit modeling of contention for shared resources and scenario-aware blocking analysis.

With the growth in complexity of real-time embedded systems, there is an increasing need for tools and techniques to understand and compare the observed runtime behavior of a system with the expected one. Since many real-time applications require periodic interactions with the environment, one of the fundamental problems in guaranteeing their temporal correctness is to be able to infer the periodicity of certain events in the system. The practicability of a period inference tool, however, depends on both its accuracy and robustness (also its resilience) against noise in the output trace of the system, e.g., when the system trace is impacted by the presence of aperiodic tasks, release jitters, and runtime variations in the execution time of the tasks. This work (i) presents the first period inference framework that uses regression-based machine-learning (RBML) methods, and (ii) thoroughly investigates the accuracy and robustness of different families of RBML methods in the presence of uncertainties in the system parameters. We show, on both synthetically generated traces and traces from actual systems, that our solutions can reduce the error of period estimation by two to three orders of magnitudes w.r.t. state of the art.

Exact schedulability analysis of limited-preemptive (or non-preemptive) real-time workloads with variable execution costs and release jitter is a notoriously difficult challenge due to the scheduling anomalies inherent in non-preemptive execution. Furthermore, the presence of self-suspending tasks is well-understood to add tremendous complications to an already difficult problem. By mapping the schedulability problem to the reachability problem in timed automata (TA), this paper provides the first exact schedulability test for this challenging model. Specifically, using TA extensions available in UPPAAL, this paper presents an exact schedulability test for sets of periodic and sporadic self-suspending tasks with fixed preemption points that are scheduled upon a multiprocessor under a global fixed-priority scheduling policy. To the best of our knowledge, this is the first exact schedulability test for non- and limited-preemptive self-suspending tasks (for both uniprocessor and multiprocessor systems), and thus also the first exact schedulability test for the special case of global non-preemptive fixed-priority scheduling (for either periodic or sporadic tasks). Additionally, the paper highlights some subtle pitfalls and limitations in existing TA-based schedulability tests for non-preemptive workloads.

Estimating metrics such as the Mean Time To Failure (MTTF) or its inverse, the Failures-In-Time (FIT), is a central problem in reliability estimation of safety-critical systems. To this end, prior work in the real-time and embedded systems community has focused on bounding the probability of failures in a single iteration of the control loop, resulting in, for example, the worst-case probability of a message transmission error due to electromagnetic interference, or an upper bound on the probability of a skipped or an incorrect actuation. However, periodic systems, which can be found at the core of most safety-critical real-time systems, are routinely designed to be robust to a single fault or to occasional failures (case in point, control applications are usually robust to a few skipped or misbehaving control loop iterations). Thus, obtaining long-run reliability metrics like MTTF and FIT from single iteration estimates by calculating the time to first fault can be quite pessimistic. Instead, overall system failures for such systems are better characterized using multi-state models such as weakly-hard constraints. In this paper, we describe and empirically evaluate three orthogonal approaches, PMC, Mart, and SAp, for the sound estimation of system’s MTTF, starting from a periodic stochastic model characterizing the failure in a single iteration of a periodic system, and using weakly-hard constraints as a measure of system robustness. PMC and Mart are exact analyses based on Markov chain analysis and martingale theory, respectively, whereas SAp is a sound approximation based on numerical analysis. We evaluate these techniques empirically in terms of their accuracy and numerical precision, their expressiveness for different definitions of weakly-hard constraints, and their space and time complexities, which affect their scalability and applicability in different regions of the space of weakly-hard constraints.

Most recurrent real-time applications can be modeled as a set of sequential code segments (or blocks) that must be (repeatedly) executed in a specific order. This paper provides a schedulability analysis for such systems modeled as a set of parallel DAG tasks executed under any limited-preemptive global job-level fixed priority scheduling policy. More precisely, we derive response-time bounds for a set of jobs subject to precedence constraints, release jitter, and execution-time uncertainty, which enables support for a wide variety of parallel, limited-preemptive execution models (e.g., periodic DAG tasks, transactional tasks, generalized multi-frame tasks, etc.). Our analysis explores the space of all possible schedules using a powerful new state abstraction and state-pruning technique. An empirical evaluation shows the analysis to identify between 10 to 90 percentage points more schedulable task sets than the state-of-the-art schedulability test for limited-preemptive sporadic DAG tasks. It scales to systems of up to 64 cores with 20 DAG tasks. Moreover, while our analysis is almost as accurate as the state-of-the-art exact schedulability test based on model checking (for sequential non-preemptive tasks), it is three orders of magnitude faster and hence capable of analyzing task sets with more than 60 tasks on 8 cores in a few seconds.

Schedule randomization is one of the recently introduced security defenses against schedule-based attacks, i.e., attacks whose success depends on a particular ordering between the execution window of an attacker and a victim task within the system. It falls into the category of information hiding (as opposed to deterministic isolation-based defenses) and is designed to reduce the attacker's ability to infer the future schedule. This paper aims to investigate the limitations and vulnerabilities of schedule randomization-based defenses in real-time systems. We first provide definitions, categorization, and examples of schedule-based attacks, and then discuss the challenges of employing schedule randomization in real-time systems. Further, we provide a preliminary security test to determine whether a certain timing relation between the attacker and victim tasks will never happen in systems scheduled by a fixed-priority scheduling algorithm. Finally, we compare fixed-priority scheduling against schedule-randomization techniques in terms of the success rate of various schedule-based attacks for both synthetic and real-world applications. Our results show that, in many cases, schedule randomization either has no security benefits or can even increase the success rate of the attacker depending on the priority relation between the attacker and victim tasks.

Complex real-time systems are traditionally developed in several disjoint steps: (i) decomposition of applications into sets of recurrent tasks, (ii) worst-case execution time estimation, and (iii) schedulability analysis. Each step is already in itself complex and error-prone, and the composition of all three poses a nontrivial integration problem. In particular, it is challenging to obtain an end-to-end analysis of timing properties of the whole system due to practical differences between the interfaces of tools for extracting task models, execution time analysis, and schedulability tests. To address this problem, we propose a seamless and pragmatic end-to-end compilation and timing analysis toolchain, where source programs are written in a real-time extension of C, called Timed C. The toolchain automatically translates timing primitives into executable code, measures execution times, and verifies temporal correctness using an extended schedulability test for non-preemptive generalized multiframe task sets. Novel aspects of our approach are: (i) both soft and firm tasks can be expressed at the programming language level and stated timing requirements are automatically verified by the schedulability test, and (ii) the schedulability test outputs per-job response-time information that enables a new approach to sensitivity analysis. Specifically, we perform a weakly hard sensitivity analysis that determines the worst-case execution time margins for the strongest still-satisfied (M,K) constraint, where M = m1+...+ mNdenotes the number of deadline misses across the entire task set, and K = {k1,..., kN} is the set of windows of interest of the different tasks. The toolchain is implemented as a source-to-source compiler, freely available as open source, and conveniently distributed as a Docker container.

In time-sensitive, safety-critical systems that must be fail-operational, active replication is commonly used to mitigate transient faults that arise due to electromagnetic interference (EMI). However, designing an effective and well-performing active replication scheme is challenging since replication conflicts with the size, weight, power, and cost constraints of embedded applications. To enable a systematic and rigorous exploration of the resulting tradeoffs, we present an analysis to quantify the resiliency of fail-operational networked control systems against EMI-induced memory corruption, host crashes, and retransmission delays. Since control systems are typically robust to a few failed iterations, e.g., one missed actuation does not crash an inverted pendulum, traditional solutions based on hard real-time assumptions are often too pessimistic. Our analysis reduces this pessimism by modeling a control system's inherent robustness as an (m,k)-firm specification. A case study with an active suspension workload indicates that the analytical bounds closely predict the failure rate estimates obtained through simulation, thereby enabling a meaningful design-space exploration, and also demonstrates the utility of the analysis in identifying non-trivial and non-obvious reliability tradeoffs.

An effective way to increase the timing predictability of multicore platforms is to use non-preemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores.

The OS scheduler's memory and runtime overheads form crucial design constraints for embedded systems implemented on low-cost hardware platforms. Table-driven scheduling can provide a high level of schedulability; however, it also consumes significant amounts of memory. By contrast, effective non-preemptive scheduling policies, such as the non-work-conserving Critical-Window EDF (CW-EDF), have low memory usage, but substantial runtime overheads. This paper aims to achieve efficient and effective non-preemptive scheduling by using a First-In-First-Out (FIFO) scheduling policy combined with a novel offset tuning technique. This technique enables the FIFO policy to reproduce a given feasible schedule, such as that followed by CW-EDF, resulting in a high level of schedulability, combined with comparatively low runtime overheads. Further, by using a small number of offsets per task, memory overheads are also tightly constrained. The proposed solution is evaluated in terms of runtime overhead, memory consumption, and schedulability ratio, using a prototype implementation on an Arduino board. This shows that FIFO with offset tuning can match the schedulability ratio of CW-EDF, while typically exhibiting lower scheduling overheads and memory consumption than the state-of-the-art Offline Equivalence technique, which is based on Non-Preemptive Fixed Priority (NP-FP) scheduling.

Harmonic periods have wide applicability in industrial real-time systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic and the task set is required to be feasible. We study two variants of this problem. In the first one, the objective is to maximize the system utilization, while in the second one, the goal is to minimize the total weighted sum of the periods. First, we assume that an interval is determined a priori for each task from which its period can be selected. We show that both variants of the problem are (at least) weakly NP-hard. This is shown by reducing the NP-complete number partitioning problem to the mentioned harmonic period assignment problems. Afterwards, we consider a variant of the second problem in which the periods are not restricted to a special interval. We present two approximation algorithms with polynomial-time complexity for this problem and show that the maximum relative error of these algorithms is bounded by a factor of 1.125. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.

Graphics Processing Units (GPU) are becoming the key hardware accelerators in the emerging image processing applications such as self-driving cars and mobile augmented reality systems. As GPUs execute launched workloads non-preemptively, their usage in safety-critical systems with hard real-time constraints is impeded. The existing solutions for scheduling real-time tasks on a single GPU focus on soft real-time systems. In this paper, we consider real-time systems with a single dedicated GPU handling sporadic tasks with hard deadlines and propose a scheduling approach based on time division multiplexing called the GPU-TDMh - a lightweight middleware framework located between the application and the GPU driver layers. We evaluate the proposed approach on a matrix multiplication benchmark on a heterogeneous platform. The experiments demonstrate the effectiveness of our method as well as superiority over the non-preemptive online scheduling policies.

We consider the problem of scheduling a set of nonpreemptive periodic tasks in an embedded system with a limited amount of memory. On the one hand, due to the memory limitations, a table-based scheduling approach might not be applicable, and on the other hand, the existing online non-preemptive scheduling algorithms are either not efficient in terms of the schedulability ratio, or suffer from considerable runtime overhead. To arrive at a compromise, this paper proposes an online policy that is equivalent to a given offline table to combine some of the advantages of both online and offline scheduling: we first consider a low-overhead online scheduling algorithm as a baseline, and then identify any irregular situations where a given offline table differs from the schedule generated by the online algorithm. We store any such irregularities in tables for use by the online scheduling algorithm, which then can recreate the table at runtime. To generate suitable tables, we provide an offline scheduling algorithm for nonpreemptive tasks, and a table-transformation algorithm to reduce the number of irregularities that must be stored. In an evaluation using an Arduino board and synthetic task sets, we have observed the technique to result in a substantial reduction of scheduling overhead compared toCW-EDF, the online scheduler that achieves the highest schedulability ratio, while having to store on average only a few dozen to a few hundreds of bytes of the static schedule.

This paper provides an exact and sustainable schedulability test for a set of non-preemptive jobs scheduled with a fixed-job-priority (FJP) policy upon a uniprocessor. Both classic work-conserving and recent non-work-conserving schedulers are supported. Jobs may exhibit both release jitter and execution time variation. Both best- and worst-case response time bounds are derived. No prior response-time analysis (RTA) for this general setting is both exact and sustainable, nor does any prior RTA support non-work-conserving schedulers. The proposed analysis works by building a schedule graph that precisely abstracts all possible execution scenarios. Key to deferring the state-space explosion problem is a novel path-merging technique that collapses similar scenarios without giving up analysis precision. In an empirical evaluation with randomly generated workloads based on an automotive benchmark, the method is shown to scale to 30+ periodic tasks with thousands of jobs (per hyperperiod).

In many real-time systems, preemption is either impossible or prohibitively expensive. The problem of scheduling non-preemptive periodic tasks with known release offsets is known to be NP-Hard. In this paper, we investigate the existing non-preemptive scheduling algorithms in both categories of work-conserving and non-work-conserving algorithms, where in the former, the processing resource is not allowed to be idle as long as there is an unfinished job in the system. While describing the advantages and weaknesses of the existing scheduling solutions we show that using online non-work-conserving algorithms it is possible to schedule more task sets. In our work, we discuss the challenges to design the idle-time insertion policy (IIP) which can be combined with the existing scheduling policies such as the earliest deadline first (EDF), rate monotonic (RM), etc. Further we present a tighter necessary condition for schedulability of non-preemptive tasks. We also provide an IIP for EDF based on looking into a number of jobs in future. Through the experiments we show that the our IIP for EDF significantly increases the schedulability of non-preemptive tasks, particularly in periodic task sets. While our schedulability ratio is more than 80%, the state of the art work-conserving algorithms are about 15%.

This paper considers the problem of reducing the number of preemptions in a system with periodic tasks and preemption overhead. The proposed solution is based on the key observation that for periodic task sets, the task with the smallest period plays an important role in determining the maximum interval of time during which a lower priority task can be executed without being preempted. We use this property to build a new limited preemptive scheduling algorithm, named RS-LP, based on fixed-priority scheduling. In RS-LP, the length of each task's non-preemptive region is varying during the system execution so as to keep the preemptions aligned with the releases of the highest priority task. This simple mechanism allows us to reduce the overall number of preemptions. The proposed algorithm, decides whether or not to preempt the currently executing task based on the maximum blocking tolerance of the higher priority tasks. In any case, the preemptions are authorized only at release instants of the task with the smallest period, thereby limiting the maximum number of preemptions to the number of releases of the highest priority task. Moreover, in this paper, we provide two different preemption overhead aware schedulability tests for periodic and loose-harmonic task sets (i.e., where each period is an integer multiple of the smallest period), together with a lower bound on the maximum number of preemptions. To conclude, extensive experiments comparing RS-LP with the state of the art limited preemptive scheduling algorithms are finally presented.

During the design phase of many real-time systems, designers often have a range of acceptable period values for which some levels of safety or quality of service are guaranteed. The choice of period values influences system schedulability and computational complexity of schedulability analysis, especially for the rate monotonic (RM) scheduling algorithm. It has been shown that RM guarantees 100% utilization if the periods are harmonic, i.e., Each period is an integer multiple of shorter periods. In this paper, we address harmonic period assignment problem where each task has a given period range. We extend the results of our previous work and present an O(n^2log(n)) algorithm (where n is the number of tasks) to verify necessary and sufficient conditions for the existence of a harmonic period assignment in cases where the previous solution has pseudo-polynomial computational complexity. We provide utilization bounds of the potential assignments as well as a heuristic algorithm to construct low utilization harmonic task sets. The efficiency of our period assignment algorithms has been evaluated in terms of acceptance ratio, task set utilization, data structure size, and the number of operations required for harmonic period assignment.

The periodic task model has been widely used in real-time systems due to the periodic behavior of many applications or periodic observation patterns of environmental events as in control applications. While the tasks of some applications have inherent values for periods, many can be defined via ranges of acceptable values. The designer choice of period values has consequences w.r.t. To utilization of the task set and the resulting hyper period. Harmonic task sets are favored, e.g., for their polynomial-time worst case response time analysis or their small hyper periods, which is of major concern e.g., for hyper visors used in virtualization or time triggered systems. In this paper we present a model to describe harmonic relations between ranges of period values, rather than single numbers only. We derive sufficient conditions for the existence of a linear-time solution, as well as a graph representation for the relations between period ranges. We provide utilization bounds of each resulting harmonic range, giving the designer flexibility to select a harmonic task set with high or low utilization. The tightness of the bounds as well as efficiency of our period assignment algorithms have been evaluated by synthetic experiments via system utilization and feasibly constructed harmonic task sets.

Timeliness and accuracy are two major concerns in many real-time embedded systems working in dynamic environments. It has been emphasized in the literature that in various real-time applications such as control systems and Kalman filters, delay is one main source of inaccuracy in the system. In this paper, we present a solution based on scheduling algorithms for the problem of inaccuracy in such systems. To this aim, first an accuracy model is introduced for systems which their accuracy is influenced by sampling and I/O delays. Then an algorithm called adjacency trade is presented to improve system accuracy while maintaining its timeliness. This algorithm follows an iterative approach and can be applied to each priority-based scheduling algorithm with no intervention in respecting the deadlines. Finally, through various simulation experiments, the effectiveness of this algorithm is examined against some algorithms in the literature.