The classic Earliest Deadline First (EDF) algorithm is widely studied and used due to its simplicity and strong theoretical performance, but has not been rigorously analyzed for systems where jobs may execute critical sections protected by shared locks. Analyzing such systems is often challenging due to unpredictable delays caused by contention. In this paper, we propose a straightforward generalization of EDF, called EDF-Block. In this generalization, the critical sections are executed non-preemptively, but scheduling and lock acquisition priorities are based on EDF. We establish lower bounds on the speed augmentation required for any non-clairvoyant scheduler (EDF-Block is an example of non-clairvoyant schedulers) and for EDF-Block, showing that EDF-Block requires at least 4.11× speed augmentation for jobs and 4× for tasks. We then provide an upper bound analysis, demonstrating that EDF-Block requires speedup of at most 6 to schedule all feasible job and task sets.

Deep learning–based classifiers are widely used for perception in autonomous Cyber-Physical Systems (CPS’s). However, such classifiers rarely offer guarantees of perfect accuracy while being optimized for efficiency. To support safety-critical perception, ensembles of multiple different classifiers working in concert are typically used. Since CPS’s interact with the physical world continuously, it is not unreasonable to expect dependencies among successive inputs in a stream of sensor data. Prior work introduced a classification technique that leverages these inter-input dependencies to reduce the average time to successful classification using classifier ensembles. In this paper, we propose generalizations to this classification technique, both in the improved generation of classifier cascades and the modeling of temporal dependencies. We demonstrate, through theoretical analysis and numerical evaluation, that our approach achieves further reductions in average classification latency compared to the prior methods.

An IDK classifier is a learning-enabled software component that attempts to categorize each input provided to it into one of a fixed set of base classes, returning IDK (“I Don't Know”) if it is unable to do so to a required level of confidence. We consider the use of IDK classifiers in applications where it is natural to consider the base classes as comprising the leaves of a class hierarchy. Classification into higher levels of such a hierarchy may be easier than classification into base classes. Given a collection of different IDK classifiers that have been trained to classify at different levels of a class hierarchy, we derive algorithms for determining the order in which to use these classifiers so as to minimize the expected duration to successful classification (whilst guaranteeing to meet a hard deadline).

Timely observation of transient astrophysical phenomena (TAP) is of crucial importance for our understanding of the universe and the laws of physics, as recognized by the National Academies in the Astro2020 decadal survey. Ultimately, the goal is to observe TAPs as early as possible using optical telescopes. This is non-trivial due to the probabilistic nature of the search problem, where multiple potential sky locations for a TAP, each with an associated probability, must be scheduled for observation before successful localization. The problem lies at the intersection of several research disciplines, including realtime systems, cyber-physical systems, astrophysics, and operations research, motivating the need for a unified modeling framework. To this end, we introduce the first formal stochastic, response-time-aware model for search planning toward detection and localization of TAPs. We consider the problem of maximizing expected utility of early localization and show that it is reducible to the Orienteering Problem. Building on this formulation, we develop the real-time-capable Greedy-Christofides Pathfinding (GCP) algorithm. An evaluation on 37 probability maps from LIGO demonstrates that GCP consistently achieves high solution quality and computational efficiency across diverse search scenarios. GCP achieves$\leq 0.5 \%$deviation from the ILP-computed optimal solution on tractable problem instances while running within a second, on average, for larger inputs.

Abstract We present the first (to our knowledge) Deep-Learning based framework for real-time schedulability-analysis that guarantees to never incorrectly mis-classify an unschedulable system as being schedulable, and is hence suitable for use in safety-critical scenarios. We relate applicability of this framework to well-understood concepts in computational complexity theory: membership in the complexity class NP. We apply the framework upon the widely-studied schedulability analysis problems of determining whether a given constrained-deadline sporadic task system is schedulable on a preemptive uniprocessor under both Deadline-Monotonic and EDF scheduling. As a proof-of-concept, we implement our framework for Deadline-Monotonic scheduling, and demonstrate that it has a predictive accuracy exceeding $$70\%$$ 70 % for systems of as many as 20 tasks without making any unsafe predictions . Furthermore, the implementation has very small ( $$<1$$ < 1 ms on two widely-used embedded platforms; $$<4~\upmu$$ < 4 μ s on an embedded FPGA) and highly predictable running times.

Abstract In scheduling real-time tasks, we face the challenge of meeting hard deadlines while optimizing for some other objective, such as minimizing energy consumption. Formulating the optimization as a Multi-Armed Bandit (MAB) problem allows us to use MAB strategies to balance the exploitation of good choices based on observed data with the exploration of potentially better options. In this paper, we integrate hard real-time constraints with MAB strategies for resource management of a Stochastic Parallel Synchronous Task. On a platform with $$M$$ M cores available for the task, $$m\le M$$ m ≤ M cores are initially assigned. Prior work has shown how to compute a virtual deadline such that assigning all $$M$$ M cores to the task if it has not completed by this virtual deadline guarantees that the deadline will be met. An MAB strategy is used to select the value of $$m$$ m . A Dynamic Power Management (DPM) energy model considering CPU sockets and sleep states is described. Experimental evaluation shows that MAB strategies learn consistently suitable $$m$$ m , and perform well compared to binary exponential search and greedy methods.

Security is increasingly a primary concern in the design of safety-critical embedded systems, yet balancing it with timing constraints is challenging due to limited computing resources. The Multi-Phase Secure (MPS) Sporadic Task Model, proposed in an ISORC-2023 paper, addressed this by balancing overhead from security mechanisms (e.g., trusted-execution environments) with real-time scheduling constraints. However, this model assumed a somewhat pessimistic view of the overhead involved in switching between security mechanisms, often overestimating the necessity of these switches. This paper refines the MPS Sporadic Task Model to more accurately assess when switching security mechanisms is unnecessary, thereby avoiding undue overhead. Our refined model demonstrates a substantial improvement in the schedulability ratio when the utilization of the system approaches one (approximately 15% improvement) for randomly-generated security-aware task systems.

An IDK classifier is a computational element that classifies an input provided to it into one of a set of predefined categories provided that it can achieve the necessary confidence level to do so; otherwise, it outputs “I Don't Know” (IDK). The concept of IDK classifier cascades has emerged as a strategy for striking a balance between the requirements of rapid response and precise classification in machine perception. Effective algorithms for constructing IDK classifier cascades have recently been developed. Here we extend these prior approaches by incorporating fault-tolerance: enabling classification that is concurrently rapid and accurate even in the event of some of the IDK classifiers exhibiting faulty behavior.

Multi-core platforms are becoming increasingly prevalent in cyber-physical systems such as automobiles and robots. However, contention for shared resources makes it chal-lenging to guarantee timing predictability. Existing studies have primarily focused on characterizing the extent to which such interference can induce delays (usually from an adversarial perspective). Unfortunately, less is understood on the physical impacts of these timing delays in different cyber-physical plat-forms. In this paper, we fill this gap by providing an empirical examination of the end-to-end effects of performance interference on real-world applications. We analyze the root causes of harmful interference and summarize potential implementation pitfalls. To automate this process, we introduce TimeTrap, a tool that analyzes performance interference in autonomous systems through the lens of control outcome. To understand the extent to which timing interference may cause control deviations, TimeTrap has to strategically leverage different magnitudes of resource contention to trigger targeted deadline miss patterns. Through this exercise, we found that a naive approach that maximizes task latency via performance interference may fail to trigger worst-case outcomes (i.e. physical damages) due to built-in fail-safe mechanisms. As a result, delays have to be induced in a stealthy manner to avoid triggering fail-safes. To achieve this, TimeTrap first employs a system that actively injects fine-grained delays into the target software, adjusting the duration based on measured feedback. Second, TimeTrap leverages predictability in CPS execution patterns and resource usage to automatically tune its aggressor workloads, matching these patterns to achieve targeted interference and execution delays in a victim. We evaluate TimeTrap on two physical-world platforms and six platforms in a hardware-in-the-Ioop simulation environment, including robotic arms, UGVs, UAVs, self-driving cars, and humanoid robots. These studies demonstrate that an interference-based attack surface exists in different stages of the CPS pipeline, from perception to planning and control.

Elastic scheduling is a framework to reduce task utilizations (often by increasing periods) in response to system overload. This paper extends elastic scheduling to uniprocessor scheduling of implicit-deadline task sets for which periods must remain harmonic. We argue that for tasks with periods constrained to continuous intervals, the problem of selecting harmonic periods from those intervals is unlikely to have a polynomial time solution. However, we outline an approach that is pseudo-polynomial in the range of acceptable periods. We then show that the problem of elastic scheduling is NP-hard with harmonic constraints. Nonetheless, if a total order is imposed on task periods (a natural restriction in many applications with execution pipelines that synchronize input data sources), the problem can be reduced offline to a lookup table, enabling polynomial-time online adaptation if available CPU bandwidth changes. We implement the proposed algorithm in two real-world applications: the Fast Integrated Mobility Spectrometer (FIMS) and ORB-SLAM3. We demonstrate that elastic scheduling allows FIMS to adjust its execution to avoid missing deadlines on a SWaP-constrained computational platform, and that it improves ORB-SLAM3's localization results by as much as lO.4x when available CPU bandwidth changes dynamically during runtime.

Real-time and embedded systems are predominantly written in C, a language that is notoriously not memory safe. This has led to widespread memory-corruption vulnerabilities in real-time embedded cyber-physical systems (CPS). This is concerning, as such devices are becoming increasingly networked with the Internet of Things (IoT) and other communication technologies (e.g., 5G), rendering them vulnerable to remote attacks. Attackers have demonstrated how memory-corruption vulnerabilities can be used to hijack program control flow to implement arbitrary attacker-controlled logic. One class of defenses that has been developed to prevent such attacks is called control-flow integrity (CFI), which applies checks at control-flow transitions to ensure the target is valid. Unfortunately, attackers have shown how to divert control flow to seemingly valid targets in an invalid and malicious sequence. This paper presents InsectACIDE, the first holistic CFI for embedded and real-time systems that does not require binary instrumentation and that is context sensitive, i.e., it checks that the sequence of control-flow transitions taken is valid, not just individual transitions, thereby detecting such attacks. InsectACIDE is implemented on an embedded Cortex-M processor using the TrustZone trusted execution environment, and holistic context-sensitive CFI is enforced for both applications and the kernel. InsectACIDE uses hardware debugging features on the Cortex-M processor and therefore does not require any kernel or application binary modification. Experimental results show that InsectACIDE incurs significantly less runtime overhead compared to the state-of-the-art holistic CFI solution. Real-time schedulability analysis is presented, along with a schedulability evaluation, to demonstrate the tradeoff between stronger protection and real-time schedulability.

An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning IDK (“I Don’t Know”) if it is unable to do so with the required level of confidence. Several different IDK classifiers may be available for the same classification problem, each offering a different trade-off between execution duration and the likelihood of successful classification. Algorithms have been obtained for determining the order in which such classifiers should be called such that the expected duration to successfully classify an input is minimized-such an ordering of classifiers is called an IDK cascade. Cascade-synthesis algorithms make the assumption that each input to be classified is drawn from the same underlying distribution. We derive runtime algorithms that seek to further reduce the expected response time of IDK cascades upon input sequences for which successive inputs are ‘similar’ in the following sense: if a particular classifier successfully classifies some input it is likely to also be able to classify the next input. We evaluate the effectiveness of our algorithms in the context of the algorithms using predictions framework by showing that it significantly reduces expected response time when the desired similarity between successive inputs exists, while suffering only a minor increase in expected response time in the absence of such similarity. We describe how our algorithm is able to learn during runtime whether similarities exist (and if so, to what degree) amongst its inputs.

Safety- and mission-critical cyber-physical systems (CPSs) require temporal correctness to ensure safe physical behavior. This manifests as strict timing requirements, which cannot be missed at runtime. Counter-intuitively, this implies that real-time tasks can be delayed so long as they remain guaranteed to meet their deadlines. This paper explores how extra time in a schedule can be analytically recapitalized for the purpose of applying stronger security protection within individual tasks at compile time. This is achieved through the development of a partial context-sensitive pointer-integrity framework (ParCSPI). In this framework, more fine-grained policies can be enforced, with greater runtime overheads, where so doing does not violate real-time constraints. A whole-system optimization framework based upon a mixed-integer linear programming approach to fixed-priority response-time analysis is used to identify precisely which contexts can be checked within the available system-wide time while maximizing system-wide security. ParCSPI leverages Arm pointer authentication (PA) to encode context-based equivalence classes into the modifiers of the pointer signature and is implemented using a customized program analyzer and LLVM compiler passes. An evaluation of ParCSPI is presented that includes per-task and system-wide overhead and security tradeoffs, as well as a demonstration on a real-world CPS. Empirical results are presented showing that ParCSPI achieves up to 62% pointer-integrity protection with only 10% worst-case execution time (WCET) overhead, and can find optimal security trade-offs in complex real-time task sets as well as approximate them in reasonable time.

Safety-critical embedded systems such as autonomous vehicles typically have only very limited computational capabilities on board that must be carefully managed to provide required enhanced functionalities. As these systems become more complex and inter-connected, some parts may need to be secured to prevent unauthorized access, or isolated to ensure correctness. We propose the multi-phase secure (MPS) task model as a natural extension of the widely used sporadic task model for modeling both the timing and the security (and isolation) requirements for such systems, and develop corresponding scheduling algorithms and associated schedulability tests.

Elastic scheduling provides a model for systems in which individual task utilizations can adapt to guarantee schedulability despite limited resources. Each task is characterized by a range of acceptable utilizations and an “elastic constant” representing its flexibility to reduce or “compress” its utilization from the desired maximum. Utilization compression is realized by either extending task periods or reducing workloads. This paper extends the model to address period compression for fixed-priority constrained-deadline task systems scheduled on a uniprocessor. We propose two approximate algorithms and one optimal algorithm for determining compression under the model. We then compare the execution times and accuracies of all three, demonstrating that even for large task sets, online compression can be performed feasibly on low-powered embedded systems.

In the world of real-time systems (RTS), security has often been overlooked in the design process. However, with the emergence of the Internet of Things and Cyber-Physical Systems, RTS are now frequently used in interconnected applications where data is shared regularly. Unfortunately, this increased connectivity has also led to a larger attack surface. As a result, it is crucial to redesign RTS to not only meet real-time requirements but also to be resilient to threats. To address this issue, we propose a new real-time security co-design task model, and an accompanying scheduling framework, where schedulability can be used to indicate whether both real-time and security requirements are met. Our algorithm is designed to be flexible, allowing different security mechanisms to be used along with real-time tasks. Specifically, we augment the frame-based task model by introducing an n-dimensional security matrix, which serves as a powerful tool to enable our approach. This matrix clearly indicates which defense mechanisms are available for each task in the system by storing the worst-case execution times of tasks. Then, we transform the problem of maximizing security, subject to schedulability, into a variant of the knapsack problem. To make this approach more practical, we implement a fully polynomial time approximation scheme (FPTAS) that reduces the time complexity of solving the knapsack problem from a pseudo-polynomial to a fully polynomial. We also experiment with a greedy-heuristic approach and compare the results of both algorithms. By using an FPTAS, we were able to significantly improve the efficiency of calculating the maximum security and produce near-optimal results against the optimal solution. Our experiments showed that an FPTAS can process a batch of 10,000 task sets 1.5 times faster than the traditional dynamic programming approach.

Algorithms that have been developed for solving computationally intractable schedulability analysis problems may be classified into two broad categories: exact algorithms that run in exponential time, and polynomial-time algorithms that provide approximate solutions. If exact algorithms are sought, it has traditionally been required that these algorithms have pseudo-polynomial running time. More recently, schedulability analysis algorithms that have polynomial running time but are allowed to make calls to an ILP solver have increasingly been considered tractable. When approximation algorithms are acceptable, an objective has been to obtain Fully Polynomial-Time Approximation Schemes, which are ‘tunable’ algorithms that provide a smooth transition between polynomial time and exponential time by letting the user of the algorithm set an appropriate value for a parameter. In this paper we take a fresh view on the connections between the various perspectives on what is considered to be tractable schedulability analysis. We seek to determine when the different forms of tractable analyses are applicable to a particular problem and what problem features rules them out, and demonstrate our findings upon concrete scheduling problems. We also suggest that ‘pseudo-polynomial time’ is perhaps a rather broad category, and propose a finer-grained classification of the class of pseudo-polynomial time algorithms.

The Butterfly Attack, introduced in an RTSS 2019 paper, was billed as a new kind of timing attack against control loops in cyber-physical systems. We conduct a close inspection of the Butterfly Attack in order to identify the root vulnerability that it exploits, and show that an appropriate application of real-time scheduling theory provides an effective countermeasure. We propose improved defenses against this and similar attacks by drawing upon techniques from real-time scheduling theory, control theory, and systems implementation, that are both provably secure and are able to make efficient use of computing resources.

Abstract This paper introduces and evaluates a general construct for trading off accuracy and overall execution duration in classification-based machine perception problems—namely, the generalized IDK classifier cascade . The aim is to select the optimal sequence of classifiers required to minimize the expected (i.e. average) execution duration needed to achieve successful classification, subject to a constraint on quality, and optionally a latency constraint on the worst-case execution duration. An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning “I Don’t Know” (IDK) if it is unable to do so with the required level of confidence. An ensemble of several different IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness (i.e. the probability of successful classification) and timeliness (i.e. execution duration). A model for representing such characteristics is defined, and a method is proposed for determining the values of the model parameters for a given ensemble of IDK classifiers. Optimal algorithms are developed for sequentially ordering IDK classifiers into an IDK cascade, such that the expected duration to successfully classify an input is minimized, optionally subject to a latency constraint on the worst-case overall execution duration of the IDK cascade. The entire methodology is applied to two real-world case studies. In contrast to prior work, the methodology developed in this paper caters for arbitrary dependences between the probabilities of successful classification for different IDK classifiers. Effective practical solutions are developed considering both single and multiple processors.

Abstract A classifier is a software component, often based on Deep Learning, that categorizes each input provided to it into one of a fixed set of classes. An IDK classifier may additionally output “I Don’t Know” (IDK) for certain inputs. Multiple distinct IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness, i.e. the probability of successful classification, and efficiency, i.e. execution time. Optimal offline algorithms are proposed for sequentially ordering IDK classifiers such that the expected duration to successfully classify an input is minimized, optionally subject to a hard deadline on the maximum time permitted for classification. Solutions are provided considering independent and dependent relationships between pairs of classifiers, as well as a mix of the two.

Abstract Reconciling the constraint of guaranteeing to always meet deadlines with the optimization objective of reducing waste of computing capacity lies at the heart of a large body of research on real-time systems. Most approaches to doing so require the application designer to specify a deeper characterization of the workload (and perhaps extensive profiling of its run-time behavior), which then enables shaping the resource assignment to the application. In practice, such approaches are weak as they load the designer with the heavy duty of a detailed workload characterization. We seek approaches for reducing the waste of computing resources for recurrent real-time workloads in the absence of such additional characterization, by monitoring the minimal information that needs to be observable about the run-time behavior of a real-time system: its response time. We propose two resource control strategies to assign resources: one based on binary-exponential search and the other, on principles of control. Both approaches are compared against the clairvoyant scenario in which the average/typical behavior is known. Via an extensive simulation, we show that both techniques are useful approaches to reducing resource computation while meeting hard deadlines.

An IDK classifier is a computing component that categorizes inputs into one of a number of classes, if it is able to do so with the required level of confidence, otherwise it returns “I Don’t Know” (IDK). IDK classifier cascades have been proposed as a way of balancing the needs for fast response and high accuracy in classification-based machine perception. Efficient algorithms for the synthesis of IDK classifier cascades have been derived; however, the responsiveness of these cascades is highly dependent on the accuracy of predictions regarding the run-time behavior of the classifiers from which they are built. Accurate predictions of such run-time behavior is difficult to obtain for many of the classifiers used for perception. By applying the algorithms using predictions framework, we propose efficient algorithms for the synthesis of IDK classifier cascades that are robust to inaccurate predictions in the following sense: the IDK classifier cascades synthesized by our algorithms have short expected execution durations when the predictions are accurate, and these expected durations increase only within specified bounds when the predictions are inaccurate.

The often very limited computational capacity available upon resource-constrained safety-critical embedded systems (such as unmanned aerial vehicles) must be carefully managed in order that they may provide the enhanced functionalities expected of them. Such systems are increasingly becoming a target of hacker attacks; hence there is an increased recognition of the need for real-time resource-allocation techniques that are resistant to such attacks. To meet this need we (i) propose a natural security-cognizant extension of the sporadic task model that is currently widely used in real-time computing; and (ii) develop a scheduling algorithm and associated schedulability test for this task model that guarantees correctness of both timing and security properties.

The algorithmic technique of fixed-parameter analysis of computationally intractable problems seeks to obtain a deeper understanding of the underlying causes of the intractability, with a view to identifying conditions under which the problem becomes tractable. We apply fixed-parameter analysis to the fixed-priority and EDF scheduling of recurrent (periodic and sporadic) task systems upon preemptive uniprocessor platforms.

A recent paper declares a ‘physical error’ to have occurred in an autonomous mobile CPS if it fails to pinpoint its location to within an acceptable degree of accuracy, and proposes an innovative approach for dealing with such physical errors without compromising safety properties. We further generalize the proposed approach to enhance its applicability to a wider range of conditions than is currently possible. We also show that some schedulability analysis that was derived in this recent paper for this approach is too optimistic, and present a fix to get rid of unwarranted optimism.

In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Some recent research has focused upon a semi-clairvoyant model for mixed-criticality systems in which it is assumed that each job reveals upon arrival which of its WCET parameters it will respect. We study the problem of scheduling such semi-clairvoyant systems to ensure graceful degradation of service to less critical jobs in the event that the systems exhibit high-criticality behavior. We propose multiple different interpretations of graceful degradation in such systems, and derive efficient scheduling algorithms that are capable of ensuring graceful degradation under these different interpretations.

Feasibility analysis for Conditional DAG tasks (C-DAGs) upon multiprocessor platforms is shown to be complete for the complexity class pspace. It is shown that as a consequence integer linear programming solvers (ILP solvers) are likely to prove inadequate for such analysis. A demarcation is identified between the feasibility-analysis problems on C-DAGs that are efficiently solvable using ILP solvers and those that are not, by characterizing a restricted class of C-DAGs for which feasibility analysis is shown to be efficiently solvable using ILP solvers.

An IDK classifier is a software component that categorizes each input provided to it into one of a fixed set of “classes,” or outputs an “I don't know” (IDK) to indicate that it is unable to classify this input. An IDK-cascade is a linear arrangement of different IDK classifiers for the same classification problem, which are executed in sequence on a given input until one outputs an actual class (rather than IDK). Given a multistage computation that must be completed within a specified hard end-to-end deadline and a choice of classifiers, one deterministic and one an IDK-cascade, for each stage, the problem of determining which IDK-cascades to schedule in order to minimize the expected end-to-end response time while guaranteeing to meet the specified deadline is considered. Different variants of this problem are defined, and optimal algorithms for solving them are derived.

The partitioned scheduling of periodic and sporadic task systems upon multiprocessor platforms (both identical and heterogeneous) is considered. The computational complexity of a large number of such partitioned schedulability problems is examined. New lower and upper bounds on complexity are presented for several problems. Some problems are pigeonholed into their precise complexity classes in this way. A list of problems for which exact classification remains open is compiled.

Autonomous systems are increasingly using components that incorporate machine learning and other AI-based techniques in order to achieve improved performance. We address the problem of assuring correctness in safety-critical systems that use such components. We investigate an approach which formulates the problem as one in which performance is an objective function to be optimized while safety is a hard constraint that must be satisfied. We then apply heuristics and algorithmic techniques from optimization theory in order to solve the resulting constrained optimization problem.

Autonomous systems increasingly use components that incorporate machine learning and other AI-based techniques in order to achieve improved performance. The problem of assuring correctness in safety-critical systems that use such components is considered. A model is proposed in which components are characterized according to both their worst-case and their typical behaviors; it is argued that while safety must be assured under all circumstances, it is reasonable to be concerned with providing a high degree of performance for typical behaviors only. The problem of assuring safety while providing such improved performance is formulated as an optimization problem in which performance under typical circumstances is the objective function to be optimized while safety is a hard constraint that must be satisfied. Algorithmic techniques are applied to derive an optimal solution to this optimization problem. This optimal solution is compared with an alternative approach that optimizes for performance under worst-case conditions, as well as some common-sense heuristics, via simulation experiments on synthetically-generated workloads.

Model-based design methodologies based on the synchrony assumption are widely used in many safety-critical application domains. The synchrony assumption asserts that actions (such as the execution of code) occur instantaneously; however, physical platforms obviously do not possess this property. This paper considers a scheduling problem that arises when one seeks to implement programs that are written under the synchrony assumption upon actual multiprocessor platforms, and shows that existing results from scheduling theory can be adapted to solve this scheduling problem.Synchronous programming, Multiprocessor scheduling, Deadlines, Makespan minimization, Processor speedup factor.

Challenging scheduling problems arise in the implementation of cyber-physical systems upon heterogeneous platforms with (serial) data offloading and (parallel) computation. In this paper, we adapt techniques from scheduling theory to model, analyze, and derive scheduling algorithms for real-time workloads on such platforms. We characterize the performance of the proposed algorithms, both analytically via the approximation ratio metric and experimentally through simulation experiments upon synthetic workloads that are justified via a case study on a CPU-GPU platform. The evaluation exposes some divergence between the analytical characterization and experimental one; recommendations that seek to balance such divergent characterizations are made regarding the choice of algorithmic approaches.

This work studies the hard-real-time routing problem in graphs: one needs to travel from a given vertex to another within a hard deadline. For each edge in the network, the worst-case delay that may be encountered across that edge is bounded. As far as this given bound is trustworthy at a very high level of assurance, it must be guaranteed that one will meet the specified deadline. The actual delays across edges are uncertain and the goal is to minimize the total expected delay while meeting the deadline. We propose a comprehensive solution to this problem. Specifically, if the precise a priori estimates of the delay probability distributions are available, we develop an optimal table-driven algorithm that identifies the route with the minimum expected delay. If those estimates are not precise (i.e., unknown or dynamic), we develop an efficient Q-Learning approach that leverages the table-driven algorithm to track the true distributions rapidly, while ensuring to meet the specified hard deadline. The proposed solution suggests a promising direction towards incorporating probabilistic information and learning-based approaches into safety-critical systems without compromising safety guarantees, when it is not feasible to establish the trustworthiness of the probabilistic information at the high assurance levels required for verification purposes.

Algorithms used for the pre-runtime analysis of safety-critical systems have traditionally been required to have running times no worse than pseudo-polynomial in the size of their inputs. Some recent work, however, has been motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers and a concurrent widespread and inexpensive availability of increasing computing capabilities, to consider the use of ILP solvers as acceptably efficient for the purposes of such analysis. In this paper, the concept of ILP-tractability is proposed as a formal characterization of the class of scheduling problems that can be solved efficiently under this newer interpretation of efficiency. Techniques are presented for showing a problem to be ILP-tractable, as well as for showing a problem to be ILP-intractable - i.e., it cannot be solved efficiently using ILP solvers.

In this article, we present an industry perspective on key drivers for autonomous navigation, with a particular focus on resiliency and behavior assurance. We provide a brief survey of current deployed mobile autonomous systems and their capabilities (with a primary focus on the air domain but including other domains-underwater, ground, space, and surface-as well). We discuss techniques that are currently used for achieving resiliency and assurance in autonomous navigation, pointing out some of the shortcomings of these techniques. We describe techniques under development in the industry that aims to overcome these shortcomings by combining emerging approaches to resilient behavior with assured autonomous behavior constructs to yield reliable and mission-effective systems necessary to operate successfully in dynamic and adversarial environments. We briefly discuss ongoing efforts to develop multidomain standards that are designed to be applicable across these disparate vehicle domains.

Abstract In this work we consider a measurement-based model for parallel real-time tasks represented by the work and span parameters of directed acyclic graphs, with different bounds for nominal and overload scenarios. We address the corresponding real-time scheduling problem and propose an optimal scheduling strategy with a derived tight bound on the maximum response time of a task.

Mixed-criticality scheduling theory (MCSh) was developed to allow for more resource-efficient implementation of systems comprising different components that need to have their correctness validated at different levels of assurance. As originally defined, MCSh deals exclusively with pre-runtime verification of such systems; hence many mixed-criticality scheduling algorithms that have been developed tend to exhibit rather poor survivability characteristics during run-time. (E.g., MCSh allows for less-important (“Lo-criticality”) workloads to be completely discarded in the event that run-time behavior is not compliant with the assumptions under which the correctness of the LO-criticality workload should be verified.) Here we seek to extend MCSh to incorporate survivability considerations, by proposing quantitative metrics for the robustness and resilience of mixed-criticality scheduling algorithms. Such metrics allow us to make quantitative assertions regarding the survivability characteristics of mixed-criticality scheduling algorithms, and to compare different algorithms from the perspective of their survivability. We propose that MCSh seek to develop scheduling algorithms that possess superior survivability characteristics, thereby obtaining algorithms with better survivability properties than current ones (which, since they have been developed within a survivability-agnostic framework, tend to focus exclusively on pre-runtime verification and ignore survivability issues entirely).

We consider a recently-proposed problem on networks in which each individual link is characterized by two delay parameters: a (usually very conservative) guaranteed upper bound on the worst-case delay, and an estimate of the delay that is typically encountered, across the link. Given a source node, a destination node, and an upper bound on the end-to-end delay that can be tolerated, the objective is to determine routes that typically experience a small delay, while guaranteeing to respect the specified end-to-end upper bound under all circumstances. We show that the prior algorithm that has been proposed for this problem has super-polynomial running time, and derive polynomial time algorithms for solving the problem.

In the Vestal model of mixed-criticality systems, jobs are characterized by multiple different estimates of their actual, but unknown, worst-case execution time (WCET) parameters. Prior work on mixed-criticality scheduling theory assumes that the execution duration of a job is only revealed by actually executing the job through to completion. We consider a different *semi-clairvoyant* model here, in which it is assumed that upon arrival a job reveals which of its WCET parameters it will respect. We identify circumstances under which this is a reasonable model, and design and evaluate scheduling algorithms appropriate for this model. We show that such semi-clairvoyance yields a significant quantifiable benefit over non-clairvoyance, in terms of both the complexity of schedulability analysis and the speedup needed to ensure schedulability.

Under the federated paradigm of multiprocessor scheduling, a set of processors is reserved for the exclusive use of each real-time task. If tasks are characterized very conservatively (as is typical in safety-critical systems), it is likely that most invocations of the task will have computational demand far below the worst-case characterization, and could have been scheduled correctly upon far fewer processors than were assigned to it assuming the worst-case characterization of its run-time behavior. Provided we could safely determine during run-time when all the processors are going to be needed, for the rest of the time the unneeded processors could be idled in low-energy "sleep" mode, or used for executing non-real time work in the background. In this paper we propose a model for representing parallelizable real-time tasks in a manner that permits us to do so. Our model does not require us to have fine-grained knowledge of the internal structure of the code represented by the task; rather, it characterizes each task by a few parameters that are obtained by repeatedly executing the code under different conditions and measuring the run-times.

In seeking to develop mixed-criticality scheduling algorithms, one encounters challenges arising from two sources. First, mixed-criticality scheduling is an inherently an on-line problem in that scheduling decisions must be made without access to all the information that is needed to make such decisions optimally - such information is only revealed over time. Second, many fundamental mixed-criticality schedulability analysis problems are computationally intractable - NP-hard in the strong sense - but we desire to solve these problems using algorithms with polynomial or pseudo-polynomial running time. While these two aspects of intractability are traditionally studied separately in the theoretical computer science literature, they have been considered in an integrated fashion in mixed-criticality scheduling theory. In this work we seek to separate out the effects of being inherently on-line, and being computationally intractable, on the overall intractability of mixed-criticality scheduling problems. Speedup factor is widely used as quantitative metric of the effectiveness of mixed-criticality scheduling algorithms; there has recently been a bit of a debate regarding the appropriateness of doing so. We provide here some additional perspective on this matter: we seek to better understand its appropriateness as well as its limitations in this regard by examining separately how the on-line nature of some mixed-criticality problems, and their computational complexity, contribute to the speedup factors of two widely-studied mixed-criticality scheduling algorithms.

A system is said to be resilient if slight deviations from expected behavior during run-time does not lead to catastrophic degradation of performance: minor deviations should result in no more than minor performance degradation. In mixed-criticality systems, such degradation should additionally be criticality-cognizant. The applicability of control theory is explored for the design of resilient run-time scheduling algorithms for mixed-criticality systems. Recent results in control theory have shown how appropriately designed controllers can provide guaranteed service to hard-real-time servers; this prior work is extended to allow for such guarantees to be made concurrently to multiple criticality-cognizant servers. The applicability of this approach is explored via several experimental simulations in a dual-criticality setting. These experiments demonstrate that our control-based run-time schedulers can be synthesized in such a manner that bounded deviations from expected behavior result in the high-criticality server suffering no performance degradation and the lower-criticality one, bounded performance degradation.

We consider networks in which each individual link is characterized by two delay parameters: a (usually very conservative) guaranteed upper bound on the worst-case delay, and an estimate of the delay that is typically encountered, across the link. Given a source and destination node on such a network and an upper bound on the end-to-end delay that can be tolerated, the objective is to determine routes they typically experience a small delay, while guaranteeing to respect the specified end-to-end upper bound under all circumstances. We formalize the problem of determining such routes as a shortest-paths problem on graphs, and derive algorithms for solving this problem optimally.

Certification authorities require correctness and survivability. In the temporal domain this requires a convincing argument that all deadlines will be met under error free conditions, and that when certain defined errors occur the behaviour of the system is still predictable and safe. This means that occasional execution-time overruns should be tolerated and where more severe errors occur levels of graceful degradation should be supported. With mixed-criticality systems, fault tolerance must be criticality aware, i.e. some tasks should degrade less than others. In this paper a quantitative notion of robustness is defined, and it is shown how fixed priority-based task scheduling can be structured to maximise the likelihood of a system remaining fail operational or fail robust (the latter implying that an occasional job may be skipped if all other deadlines are met). Analysis is developed for fail operational and fail robust behaviour, optimal priority ordering is addressed and an experimental evaluation is described. Overall, the approach presented allows robustness to be balanced against schedulability. A designer would thus be able to explore the design space so defined.

Schedulability analysis techniques that are well understood within the real-time scheduling community are applied to the analysis of recurrent real-time workloads that are modeled using the synchronous data-flow graph (SDFG) model. An enhancement to the standard SDFG model is proposed, that permits the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A technique is derived for transforming such an enhanced SDFG to a collection of traditional 3-parameter sporadic tasks, thereby allowing for the analysis of systems of SDFG tasks using the methods and algorithms that have previously been developed within the real-time scheduling community for the analysis of systems of such sporadic tasks. The applicability of this approach is illustrated by applying prior results from real-time scheduling theory to construct an exact preemptive uniprocessor schedulability test for collections of recurrent processes that are each represented using the enhanced SDFG model.

Sustainability is a formalization of the requirement for scheduling algorithms and schedulability tests that a system deemed to be correctly schedulable should remain so if its run-time behavior is better than anticipated. The notion of sustainability is extended to mixed-criticality systems, and sustainability properties are determined for a variety of widely-studied uniprocessor and multi-processor mixed-criticality scheduling algorithms.

The global scheduling of systems that can be modeled as collections of multiple independent recurrent real-time tasks, each represented as a synchronous dataflow graph (SDFG), upon an identical multiprocessor platform is considered. An EDF-based scheduling algorithm is proved optimal under the speedup factor metric, and a speedup-optimal sufficient schedulability test is derived.

The AMC-IA mixed-criticality scheduling analysis was proposed as an improvement to the AMC-MAX adaptive mixed-criticality scheduling analysis. However, we have identified several necessary corrections to the AMC-IA analysis. In this article, we motivate and describe those corrections, and discuss and illustrate why the corrected AMC-IA analysis cannot be shown to outperform AMC-MAX.

The problem of partitioning systems of independent constrained-deadline sporadic tasks upon heterogeneous multiprocessor platforms is considered. Several different integer linear program (ILP) formulations of this problem, offering different tradeoffs between effectiveness (as quantified by speedup bound) and running time efficiency, are presented.

Many reactive systems must be designed and analyzed prior to deployment in the presence of considerable epistemic uncertainty: the precise nature of the external environment the system will encounter, as well as the run-time behavior of the platform upon which it is implemented, cannot be predicted with complete certainty prior to deployment. The widely-studied Vestal model for mixed-criticality workloads addresses uncertainties in estimating the worst-case execution time (WCET) of real-time code. Different estimations, at different levels of assurance, are made about these WCET values, it is required that all functionalities execute correctly if the less conservative assumptions hold, while only the more critical functionalities are required to execute correctly in the (presumably less likely) event that the less conservative assumptions fail to hold but the more conservative assumptions do. A generalization of the Vestal model is considered here, in which a degraded (but non-zero) level of service is required for the less critical functionalities even in the event of only the more conservative assumptions holding. An algorithm is derived for scheduling dual-criticality implicit-deadline sporadic task systems specified in this more general model upon preemptive uniprocessor platforms, and proved to be speedup-optimal.

In mixed-criticality systems functionalities of different criticalities, that need to have their correctness validated to different levels of assurance, co-exist upon a shared platform. Multiple specifications at differing levels of assurance may be provided for such systems; the specifications that are trusted at very high levels of assurance tend to be more conservative than those at lower levels of assurance. Prior research on the scheduling of such mixed-criticality systems has primarily focused upon the case where multiple estimates of the worst-case execution time (WCET) of pieces of code are provided; in this paper, a model is considered in which multiple estimates are instead provided for the rate at which event-triggered processes are executed. An algorithm is derived for scheduling such systems upon a preemptive uniprocessor; the effectiveness of this algorithm is demonstrated quantitatively via the speedup factor metric.

In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs classified as being more critical are required to execute correctly. The scheduling of collections of such mixed-criticality jobs upon identical multiprocessor platforms in order to minimize the makespan is considered here.

In their widely-cited survey on mixed-criticality systems, Burns and Davis describe a very general model for representing mixed-criticality sporadic tasks. In this general model multiple estimates, at differing levels of assurance, are specified for each of the three parameters -- worst-case execution time (WCET), relative deadline, and period -- characterizing a 3-parameter sporadic task. The preemptive uniprocessor scheduling of systems of such tasks is considered. A scheduling algorithm is presented, proved correct, and quantitatively characterized via the speedup factor metric for dual-criticality systems of such tasks. To our knowledge, this is the first work to conduct any form of analysis of task systems that are represented using this general model.

Under the federated approach to multiprocessor scheduling, each individual task is either restricted to execute upon a single processor (as in partitioned scheduling), or has exclusive access to all the processors upon which it may execute. The federated scheduling of a mixed-criticality collection of independent recurrent tasks is studied here. A model is proposed for mixed-criticality recurrent tasks that extends the (previously-proposed) implicit-deadline sporadic DAG tasks model to account for mixed criticalities. A federated scheduling algorithm for systems of such tasks is presented and proved correct, and a quantitative evaluation of its efficacy derived via the widely-used speedup factor metric.

This paper explores preemption-costs cognizant schedulability and sustainability issues in the uniprocessor EDF scheduling of sporadic task systems.

In this paper, we study a set of real-time scheduling problems whose objectives can be expressed as piecewise linear utility functions. This model has very wide applications in scheduling-related problems, such as mixed criticality, response time minimization, and tardiness analysis. Approximation schemes and matrix vectorization techniques are applied to transform scheduling problems into linear constraint optimization with a piecewise linear and concave objective; thus, a neural network-based optimization method can be adopted to solve such scheduling problems efficiently. This neural network model has a parallel structure, and can also be implemented on circuits, on which the converging time can be significantly limited to meet real-time requirements. Examples are provided to illustrate how to solve the optimization problem and to form a schedule. An approximation ratio bound of 0.5 is further provided. Experimental studies on a large number of randomly generated sets suggest that our algorithm is optimal when the set is nonoverloaded, and outperforms existing typical scheduling strategies when there is overload. Moreover, the number of steps for finding an approximate solution remains at the same level when the size of the problem (number of jobs within a set) increases.

The sporadic DAG task model exposes parallelism that may exist within individual tasks to the run-time scheduling mechanism, and is therefore considered a particularly suitable model for representing recurrent real-time tasks that are to be implemented upon multiprocessor platforms. This paper proposes and evaluates an extension to the model to allow for the concurrent modeling of conditional execution of pieces of an individual task, along with the modeling of intra-task parallelism. The Global Earliest Deadline First (GEDF) scheduling of systems represented in this generalized model is studied, and a GEDF-schedulability test is derived. With regards to GEDF scheduling it is shown that there is no penalty, in terms of worse speedup factor, in generalizing the sporadic DAG tasks model in this manner.

Historically safety-critical real-time systems have been implemented using a cyclic executive (CE). Here a series of frames (minor cycles) are executed in sequence. Once the series is complete the sequence is repeated. The duration of the full sequence is often known as the major cycle. Within each frame, units of computation (jobs) are executed, again in sequence. Although there are a number of drawbacks to the use of CEs they have the advantage of being fully deterministic and efficiently implemented. For multi-core platforms, running a set of frames on each core is an obvious extension to the single core approach. Here there is advantage in coordinating the execution of the cores so that frames are released at the same time across all cores. For mixed criticality systems, the requirement for separation would imply that, at any time, code of the same criticality must execute on all cores. In this paper we consider how this requirement can be met and the performance, in terms of schedulability, it delivers. We consider partitioned and globally allocated work. For partitioned systems an allocation scheme is developed. For globally scheduled schemes we develop a polynomial-time sufficient schedulability test that determines whether a given mixed-criticality system is schedulable, and constructs a schedule if it is.

A federated approach to the multiprocessor scheduling of systems of independent recurrent tasks is considered, in which each task is either restricted to execute preemptively upon a single processor, or may execute upon multiple processors but gets exclusive access to all these processors. Efficient polynomial-time algorithms are derived here for the federated schedulability analysis and run-time scheduling of recurrent task systems that are represented by the conditional sporadic DAG tasks model. The performance of these algorithms is characterized via a speedup factor metric, which quanti es the combined cost of both restricting oneself to the federated scheduling paradigm, and of requiring the scheduling algorithms to run in polynomial time.

An integrated approach, embracing both control and scheduling theories, is proposed to implement multiple control loops upon shared network and computational resources, where the network may additionally introduce packet losses. Each control system is first analyzed from a control-theoretic perspective in order to determine the asymptotic rate at which control signals must be computed to maintain stability and optimal performance despite network losses. Since required completion rates for control tasks are asymptotic, and network packet drops uncertain, the problem of scheduling multiple such control tasks upon shared computational resources does not map to known problems in real-time scheduling. It is therefore formalized here as a new form of periodic task scheduling problem -- one in which each task has an associated asymptotic completion rate requirement. Sufficient schedulability conditions are derived, and a dynamic scheduling algorithm designed, for solving such scheduling problems. This integrated methodology thus provides an effective way to incorporate network loss in the design of cyber-physical systems over integrated architectures. The use of this methodology is illustrated, and its efficacy demonstrated, upon an example system of five inverted pendulums.

Recurrent (periodic and sporadic) task systems have traditionally been scheduled upon multiprocessor platforms using either the partitioned or the global approach. Under the recently-proposed federated approach, each task is either restricted to execute upon a single processor (as in partitioned scheduling), or may execute upon multiple processors but is the only task to execute upon each of these processors. Earlier studies concerning the federated scheduling of task systems represented using the sporadic DAG model were restricted to implicit-deadline and constrained-deadline sporadic task systems, the research reported here extends this study to the consideration of task systems represented using the more general arbitrary-deadline sporadic DAG model.

The fluid scheduling model allows for schedules in which an individual task may be assigned a fraction of a processor at each time instant. These assignments are subject to the constraints that no fraction exceeds one and the sum of all the assigned fractions do not exceed the sum of the computing capacities of all the processors at any instant. An algorithm, MC-Fluid, has recently been proposed for scheduling systems of mixed-criticality implicit-deadline sporadic tasks under the fluid scheduling model. MC-Fluid has been shown to have a speedup bound no worse than (1 + √5)/2 or ≈ 1.618 for scheduling dual-criticality systems. We derive here a simplified variant of MC-Fluid called MCF, that has run-time linear in the number of tasks. We prove that this simplified variant has a speedup bound no worse than 4/3 for dual-criticality systems, and show that this implies that MC-Fluid, too, has a speedup bound no worse than 4/3. We know from prior results in uniprocessor mixed-criticality scheduling that no algorithm may have a speedup bound smaller than 4/3, allowing us to conclude that MCF and MC-Fluid are in fact speedup-optimal for dual-criticality scheduling.

Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixed-criticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm.

An increasing trend in embedded computing is the moving towards mixed-criticality (MC) systems, in which functionalities of different importance degrees (criticalities) are implemented upon a common platform. Most previous work on MC scheduling focuses on the aspect that different timing analysis tools may result in multiple WCET estimations for each "job" (piece of code). Recently, a different MC model has been proposed, targeting systems with varying execution speeds. It is assumed that the precise speed of the processor upon which the system is implemented varies in an a priori unknown manner during runtime, and estimates must be made as to how low the actual speed may fall. Prior work has dealt with uniprocessor platforms of this kind, the research reported in this paper seeks to generalize this prior work to be applicable to multicore platforms. In our method, a linear program (LP) is constructed based on necessary and sufficient scheduling conditions, and according to its solution, jobs are executed in a processor-sharing based method. Optimality of the algorithm is proved, and an example is constructed to show the necessity of processor sharing.

Bonifaci et al have recently introduced some novel analytical techniques in order to derive a speed-up bound for the multiprocessor global EDF scheduling of systems of recurrent tasks that are represented using the sporadic DAG task model, and have applied these techniques to obtain a pseudo-polynomial time sufficient schedulability test. In this paper, these techniques are further generalized to yield an improved pseudo-polynomial time sufficient schedulability test for global EDF scheduling of systems of sporadic DAG tasks. It is shown that this new test strictly dominates the one by Bonifaci et al, in addition, schedulability experiments demonstrate that the improvement can be quite substantial for certain kinds of task systems.

The feasibility of preemptive and non-preemptive scheduling has been well investigated on uniprocessor and multiprocessor platforms under both Fixed Priority Scheduling (FPS) and Earliest Deadline First (EDF) paradigms. While feasibility of limited preemptive scheduling under FPS has been addressed on both uniprocssor and multiprocessor platforms, under EDF it has been investigated only on uniprocessors, and a similar analysis for multiprocessor platforms is still missing. In this paper, we introduce global Limited Preemptive Earliest Deadline First (g-LP-EDF) scheduling, and propose the associated feasibility analysis to complete the above described feasibility analysis spectrum. Specifically, we derive a sufficient condition that guarantees g-LP-EDF feasibility of sporadic real-time tasks which directly provides a global Non-Preemptive Earliest Deadline First (g-NP-EDF) feasibility test. We then study the interplay between g-LP-EDF feasibility and processor speed, in order to quantify the sub-optimality of g-NP-EDF in terms of the minimum speed-up required to guarantee g-NP-EDF feasibility of all feasible task sets. The results presented in this paper complement our previous results on uniprocessors, and provide a unified result on the sub-optimality of non-preemptive EDF on both uniprocessor and multiprocessor platforms.

A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalites"). The problem of executing a MC workload, modeled as a collection of independent implicit-deadline sporadic tasks executing upon a preemptive uniprocessor, is considered. Suitable scheduling strategies are devised for scheduling such systems despite uncertainty and unpredictability in both the amount of execution needed by the tasks, and the effective speed of the processor. These scheduling strategies allow for simultaneously making efficient use of platform resources and ensuring the correctness of the more critical workload components at greater levels of assurance.

In modern embedded platforms, safety-critical functionalities that must be certified correct to very high levels of assurance may co-exist with less critical software that are not subject to certification requirements. One seeks to satisfy two, sometimes contradictory, goals upon such mixed-criticality platforms: (i) certify the safety-critical functionalities under very conservative assumptions, and (ii) achieve high resource utilization during run-time, when actual behavior does not live up to the pessimistic assumptions under which certification was made. This paper describes efforts at designing fixed-priority scheduling algorithms that balance these two requirements, when scheduling recurrent tasks that are triggered by external events of unknown exact frequency.

In many current multiprocessor real-time operating systems, programmers have the ability to set affinity masks that pin a process to a specified subset of the processors in the system. Given a real-time task system consisting of a collection of implicit-deadline sporadic tasks with an affinity mask specified for each task that is to be implemented upon an identical multiprocessor platform, this paper addresses the question of determining whether the task system can be implemented upon the platform to always meet all deadlines, while respecting the affinity mask restrictions. An algorithm is derived that answers this question efficiently in run-time that is polynomial in the representation of the task system.

A varying-speed processor is characterized by two execution speeds: a normal speed and a degraded speed. Under normal circumstances it will execute at its normal speed, conditions during run-time may cause it to execute more slowly (but no slower than at its degraded speed). The problem of executing an integrated workload, consisting of some more important components and some less important ones, upon such a varying-speed processor is considered. It is desired that all components execute correctly under normal circumstances, whereas the more important components should execute correctly (although the less important components need not) if the processor runs at any speed no slower than its specified degraded speed.

Most prior theoretical research on real-time partitioning algorithms for multiprocessor platforms has focused on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's processing power. However, computing capacity is often not the only limiting resource: on many multiprocessor platforms each individual computing unit may have limited amounts of multiple additional types of resources (such as local memory) in addition to having limited processing power. We present algorithms for partitioning a collection of sporadic tasks, each characterized by a WCET, a relative deadline, and a period, upon a multiprocessor platform in a manner that is cognizant of such additional constraints as well as the processing capacity constraints.

Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification, the rest of the functionality is non safety critical and does not need to be certified, or is certified to a lower level of assurance. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is described for the scheduling of such mixed-criticality task systems. Analyses of EDF-VD significantly superior to previously-known ones are presented, based on metrics such as processor speedup factor (EDF-VD is proved to be optimal with respect to this metric) and utilization bounds.

The scheduling of mixed-criticality implicit-deadline sporadic task systems on identical multiprocessor platforms is considered, when inter-processor migration is permitted. A scheduling algorithm is derived and proved correct, and its properties investigated. Theoretical analysis (in the form of both a speedup factor and sufficient schedulability conditions) as well as extensive simulation experiments serve to demonstrate its effectiveness.

On many multiprocessor platforms each individual processor may have limited amounts of several different kinds of resources such as computing capacity, local memory, and network bandwidth. In order to partition tasks effectively upon such platforms the partitioning algorithm should be cognizant of all the resource constraints. We present and evaluate an algorithm for partitioning a collection of implicit-deadline sporadic tasks upon a multiprocessor platform in a manner that is cognizant of multiple such resource constraints.

A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed a cyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. The task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. The scheduling problem is to determine whether such a recurrent task can be scheduled to always meet all deadlines upon a specified number of processors that are dedicated for the use of this task. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. EDF is shown to be a good approximate scheduling algorithm. Polynomial and pseudo-polynomial schedulability tests, of differing effectiveness, are presented for determining whether a given task can be scheduled by EDF to always meet all deadlines on a specified number of processors.

Many safety-critical embedded systems are subject to certification requirements; some systems may be required to meet multiple sets of certification requirements, from different certification authorities. Certification requirements in such "mixed-criticality” systems give rise to interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In this paper, we study a formal model for representing such mixed-criticality workloads. We demonstrate first the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements, even for systems subject to merely two sets of certification requirements. Then we quantify, via the metric of processor speedup factor, the effectiveness of two techniques, reservation-based scheduling and priority-based scheduling, that are widely used in scheduling such mixed-criticality systems, showing that the latter of the two is superior to the former. We also show that the speedup factors we obtain are tight for these two techniques.

We consider several real-time scheduling problems on heterogeneous multiprocessor platforms, in which the different processors share a common memory pool. These include (i)~scheduling a collection of implicit-deadline sporadic tasks with the objective of meeting all deadlines, and (ii)~scheduling a collection of independent jobs with the objective of minimizing the make span of the schedule. Both these problems are intractable (NP-hard). For each, we derive polynomial-time algorithms for solving them approximately, and show that these algorithms have bounded deviation from optimal behavior. We also consider the problem of determining how much common memory a platform needs in order to be able to accommodate a specified real-time workload.

The partitioned preemptive EDF scheduling of implicit-deadline sporadic task systems on an identical multiprocessor platform is considered. Lookup tables, at any selected degree of accuracy, are pre-computed for the multiprocessor platform. By using these lookup tables, task partitioning can be performed in time polynomial in the representation of the task system being partitioned. Although the partitioning will not in general be optimal, the degree of deviation from optimality is bounded according to the degree of accuracy selected during the pre-computation of the lookup tables.

We extend the current state of the art in real-time divisible load theory (RT-DLT), by considering the problems of scheduling a real-time divisible job on computing clusters in which different processing nodes have different computing capabilities, as well as different costs associated with executing on them. We seek to minimize the cost of executing a job while also meeting its deadline.

The partitioned scheduling of sporadic task systems on identical multiprocessors is considered. This is known to be intractable (NP-hard in the strong sense). A polynomial-time approximation scheme (PTAS) is proposed for sporadic task systems satisfying the additional constraint that for each of the three parameters -- worst-case execution time, relative deadline, and period -- that characterize sporadic tasks, the ratio of the largest value to the smallest value is bounded from above by a constant.

Many safety-critical embedded systems are subject to certification requirements. However, only a subset of the functionality of the system may be safety-critical and hence subject to certification, the rest of the functionality is non safety-critical and does not need to be certified, or is certified to a lower level. The resulting mixed criticality system offers challenges both for static schedulability analysis and run-time monitoring. This paper considers a novel implementation scheme for fixed priority uniprocessor scheduling of mixed criticality systems. The scheme requires that jobs have their execution times monitored (as is usually the case in high integrity systems). An optimal priority assignment scheme is derived and sufficient response-time analysis is provided. The new scheme formally dominates those previously published. Evaluations illustrate the benefits of the scheme.

In many modern embedded platforms, safety-critical functionalities that must be certified correct to very high levels of assurance co-exist with less critical software that are not subject to certification requirements. Recent research in real-time scheduling theory has yielded some promising techniques for meeting the dual goals of (i) being able to certify the safety-critical functionalities under very conservative assumptions, and (ii) ensuring high utilization of platform resources under less pessimistic assumptions. This research has centered on an event-triggered/ priority-driven approach to scheduling. However current practice in many safety-critical domains, including (the safety-critical components of) automotive and avionics systems and factory automation, favors a time-triggered approach. In such time-triggered systems, non-interference of safety-critical components by non-critical ones is ensured by strict isolation between components of different criticalities, although such isolation facilitates the certification of the safety-critical functionalities, it can cause very low resource utilization. The research reported in this document is, to our knowledge, the first to study time-triggered scheduling from the perspective of both ensuring certifiability of high-criticality functionalities, and obtaining high resource utilization as in (i) and (ii) above. We present algorithms for time-triggered scheduling of mixed-criticality systems that offers resource utilization guarantees similar to those of event-triggered scheduling. Since the time-triggered approach currently seems to find greater acceptability with certification authorities, it is hoped that this research will hasten the adoption of these results in building embedded systems that are subject to mandatory certification.

The Earliest Deadline First scheduling algorithm (EDF) is known to not be optimal under global scheduling on multiprocessor platforms. Results have been obtained that bound the maximum tardiness- the amount of time by which deadlines may be missed- of any feasible system of implicit-deadline sporadic tasks scheduled using global EDF. However, it is known that these bounds are not tight. In this paper, we derive an algorithm for obtaining tardiness bounds that are superior to previously known bounds. In contrast to prior algorithms, which compute a single tardiness bound for all the tasks in the system, our algorithm derives a separate tardiness bound for each task. Particularly upon task systems in which the parameters of the tasks are very dissimilar, our bounds are significantly better than prior bounds. Our algorithm also yields a simple sufficient test for the tardiness verification problem: given a task system with maximum acceptable tardiness bounds per task, is the system guaranteed to be scheduled by global EDF such that these tardiness constraints are not violated?

Many safety-critical embedded systems are subject to certification requirements. However, only a subset of the functionality of the system may be safety-critical and hence subject to certification; the rest of the functionality is non safety-critical and does not need to be certified. Certification requirements in such mixed-criticality systems give rise to some interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In prior work, we have proposed a priority-based algorithm for scheduling such mixed-criticality systems on preemptive uniprocessor platforms. In this paper, we derive a sufficient schedulability condition for efficiently determining whether a given mixed-criticality system can be successfully scheduled by this algorithm. We show that this algorithm (and the associated schedulability test) is strictly superior to prior algorithms that have been used for scheduling mixed-criticality systems needing certification.

The most important character of real-time systems is that they have stringent timing deadlines that must be guaranteed. A hard real-time system is required to complete its operations before all its timing deadlines. For a given task set, it is useful in an engineering context to know what changes to period can be made to a task that will deliver a schedulable system. In this paper, we develop the sensitivity analysis of task period for EDF scheduled systems on a uniprocessor. We prove that a minimum task period can be determined by a single pass of the QPA algorithm, an improved scheme is presented by using different initial values of the period. The approaches developed for sensitivity analysis of task period are therefore as efficient as QPA, and are easily incorporated into a system design support tool.

The global EDF scheduling of sporadic task systems upon uniform multiprocessor platforms is studied. A new sufficient schedulability test is presented and proved correct. Some interesting issues are discussed, that arise regarding the choice of an appropriate metric for evaluating the test quantitatively. Metrics based on processor speedup factor are proposed, and the test is quantitatively evaluated in terms of these metrics.

Many safety-critical embedded systems are subject to certification requirements; some systems may be required to meet multiple sets of certification requirements, from different certification authorities. Certification requirements in such "mixed-criticality" systems give rise to some interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In this paper, we propose a formal model for representing such mixed-criticality workloads. We demonstrate the intractability of determining whether a system specified in this model can be scheduled to meet all its certification requirements. For dual-criticality systems - systems subject to two sets of certification requirements - we quantify, via the metric of processor speedup factor, the effectiveness of 2 techniques (reservation-based scheduling and priority-based scheduling) that are widely used in scheduling such mixed-criticality systems.

Formal models used for representing recurrent real-time processes are typically characterized by a period parameter, representing the minimum amount of time that may elapse between successive invocations of the process. However a recently proposed model called the non-cyclic GMF model deviates from this trend: there is no single period parameter characterizing the recurrent behavior of the task. In this paper we consider schedulability analysis of real-time systems comprised of collections of such tasks, that are to be scheduled using earliest-deadline first (EDF) scheduling on a single preemptive processor. We provide evidence that indicates that schedulability analysis for such systems is more difficult than for systems in which each recurrent task is characterized by a single period parameter, and derive a pseudo-polynomial time schedulability analysis algorithm for bounded-utilization systems of such tasks.

The correctness of a real-time system depends on not only the system's output but also on the time at which results are produced. A hard real-time system is required to complete its operations before all its timing deadlines. For a given task set it is useful to know what is the minimum speed of the processor that will deliver a schedulable system. It is also beneficial in an engineering context to know what changes to computation time can be made to a task that will result in a system that is borderline schedulable. In this paper, we address the sensitivity analysis (parameter calculations) for task execution times and speed of the processor for EDF-scheduled systems on a uniprocessor. We prove that an optimal (minimum or maximum) task parameter can be determined by a single pass of the QPA algorithm. This algorithm provides efficient and exact sensitivity analysis for arbitrary deadline real-time systems. The approaches developed for task parameter computations are therefore as efficient as QPA, and are easily incorporated into a system design support tool.

Formal models used for representing recurrent real-time processes have traditionally been characterized with a period parameter that specifies the minimum amount of time that may elapse between successive invocations of the process. However a recently proposed model called the non-cyclic GMF model has the distinctive feature that there need be no single period parameter characterizing the recurrent behavior of the task. This paper studies the implications of removing the restriction of requiring a unique period parameter to other previously-proposed models for representing recurrent processes. It is shown that removing this restriction represents a significant generalization to these prior models. Despite the added generality, however, feasibility analysis on preemptive uniprocessors remains tractable.

Many safety-critical embedded systems are subject to certification requirements. However, only a subset of the functionality of the system may be safety-critical and hence subject to certification, the rest of the functionality is non safety-critical and does not need to be certified. Certification requirements in such "mixed-criticality" systems give rise to some interesting scheduling problems, that cannot be satisfactorily addressed using techniques from conventional scheduling theory. In prior work, we have studied the scheduling and analysis of mixed criticality systems that are specified as finite collections of jobs executing on a single shared preemptive processor. In this paper, we consider mixed criticality systems that are comprised of finite collections of recurrent tasks, specified using a mixed-criticality generalization of the widely-used sporadic tasks model. We design a priority-based algorithm for scheduling such systems, derive an algorithm for computing priorities, and obtain a sufficient schedulability condition for efficiently determining whether a given mixed-criticality system can be successfully scheduled by this algorithm.

The optimality of the Earliest Deadline First scheduler for uniprocessor systems is one of the main reasons behind the popularity of this algorithm among real-time systems. The ability of fully utilizing the computational power of a processing unit however requires the possibility of preempting a task before its completion. When preemptions are disabled, the schedulability overhead could be significant, leading to deadline misses even at system utilizations close to zero. On the other hand, each preemption causes an increase in the runtime overhead due to the operations executed during a context switch and the negative cache effects resulting from interleaving tasks' executions. These factors have been often neglected in previous theoretical works, ignoring the cost of preemption in real applications. A hybrid limited-preemption real-time scheduling algorithm is derived here, that aims to have low runtime overhead while scheduling all systems that can be scheduled by fully preemptive algorithms. This hybrid algorithm permits preemption where necessary for maintaining feasibility, but attempts to avoid unnecessary preemptions during runtime. The positive effects of this approach are not limited to a reduced runtime overhead, but will be extended as well to a simplified handling of shared resources.

A scheduling policy or a schedulability test is defined to be sustainable with respect to a particular workload model if any task system represented in that model that is determined to be schedulable remains so if it behaves "better" than mandated by its specifications. We investigate the sustainability properties of global scheduling algorithms when applied to systems represented using the sporadic task model. We show that Fixed-Priority (FP) scheduling of sporadic task sets is sustainable under a variety of scheduling parameter relaxations, including decreased execution requirements, later arrivals, and deadline relaxations. It follows that all sufficient tests of global FP schedulability are sustainable for sporadic task systems. We show that the Earliest Deadline First (EDF) and Earliest-Deadline with Zero Laxity scheduling policies are sustainable with respect to decreased execution requirements and later arrivals. We also introduce a notion of self-sustainability, and show that many widely-used EDF schedulability tests are not self-sustainable but one is.

Recent results have demonstrated the existence of a sufficient global EDF schedulability test for sporadic task systems that makes the following guarantee: any task system that is not determined to be schedulable on an m-processor platform by this test is guaranteed to actually not be so on a platform in which each processor is m/(2m - 1) times as fast. A new global EDF schedulability test is proposed here that builds on this result. This new test is shown to be less pessimistic and more widely applicable than the earlier result was, while retaining the strong theoretical properties - in particular, the speedup bound - of the earlier result.

A new abstraction — the Parallel Supply Function (PSF) — is proposed for representing the computing capabilities offered by virtual platforms implemented atop identical multiprocessors. It is shown that this abstraction is strictly more powerful than previously-proposed ones, from the perspective of more accurately representing the inherent parallelism of the provided computing capabilities. Sufficient tests are derived for determining whether a given real-time task system, represented as a collection of sporadic tasks, is guaranteed to always meet all deadlines when scheduled upon a specified virtual platform using the global EDF scheduling algorithm.

Since worst case response times must be determined repeatedly during the interactive design of real-time application systems, repeated exact computation of such response times would slow down the design process considerably. In this research, we identify three desirable properties of estimates of the exact response times: continuity with respect to system parameters, efficient computability, and approximability. We derive a technique possessing these properties for estimating the worst-case response time of sporadic task systems that are scheduled using fixed priorities upon a preemptive uniprocessor.

We study the problem of executing a collection of independently designed and validated task systems upon a common platform composed of a preemptive processor and additional shared resources. We present an abstract formulation of the problem and identify the major issues that must be addressed in order to solve this problem. We present and prove the correctness of algorithms that address these issues, and thereby obtain a design for an open real-time environment.

Recent results on the global multiprocessor EDF scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each taskpsilas relative deadline parameter is constrained to be no larger than its period. This paper introduces new analysis techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in this manner.

In a paper that was presented at the recently-concluded real-time systems symposium, Vestal proposed a new real-time task model that is able to represent the fact that the worst-case execution time (WCET) of a single task may be determined to different levels of accuracy with different degrees of confidence. In systems with multiple criticality requirements -different tasks need to be assured of meeting their deadlines with different levels of confidence - such multiple specifications of WCET may be exploited to obtain better processor utilization.This paper conducts a thorough study of the feasibility and schedulability questions for such multi-criticality real-time task systems when implemented upon preemptive uniprocessor platforms.

A hybrid scheduling algorithm is proposed, which integrates features of the fixed priority (FP) and earliest deadline first (EDF) scheduling policies. It is shown that this hybrid scheduling algorithm is a generalization of both FP and EDF, and tends to retain most of the desirable properties and features of both individual policies. Two exact (i.e., necessary and sufficient) tests are derived for sporadic task systems scheduled by the hybrid scheduling algorithm.

A hybrid scheduling algorithm is proposed, which integrates features of the fixed priority (FP) and earliest deadline first (EDF) scheduling policies. It is shown that this hybrid scheduling algorithm is a generalization of both FP and EDF, and tends to retain most of the desirable properties and features of both individual policies. An exact (i.e., necessary and sufficient) test is derived for the preemptive uniprocessor scheduling of resource- sharing sporadic task systems using this hybrid scheduling algorithm, with access to shared resources arbitrated using the stack resource policy (SRP).

Recent research in real-time divisible load theory (RT-DLT) has addressed the problem of distributing arbitrarily parallelizable real-time workloads among processors which become available at different instants in the future. Given a real-time job and the times as which the processors become available, we devise exact efficient algorithms to solve two important problems: (i) determine the smallest number of processors needed to complete this job by its deadline; and (ii) given a specific number of processors, determine the earliest completion time for the job on these processors.

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor platforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach - while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation- based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary- deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.

The global EDF scheduling of sporadic task systems upon uniform multiprocessor platforms is studied. A sufficient schedulability test is presented and proved correct. It is shown that this test generalizes the previously-known exact uniprocessor, and sufficient identical multiprocessor, EDF- schedulability tests.

Feasibility analysis determines (prior to system execution-time) whether a specified collection of hard-real-time jobs executed on a processing platform can meet all deadlines. In this paper, we derive near-optimal sufficient tests for determining whether a given collection of jobs can feasibly meet all deadlines upon a specified multiprocessor platform assuming job migration is permitted. These tests are general enough to be applied even when the collection of jobs is incompletely specified. We discuss the applicability of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks. We also show that our feasibility conditions may be used to obtain global-EDF schedulability conditions.

The duration of time for which each application locks each shared resource is critically important in composing multiple independently-developed applications upon a shared "open" platform. In a companion paper, we formally defined and studied the concept of resource hold time (RHT) - the largest length of time that may elapse between the instant that an application system locks a resource and the instant that it subsequently releases the resource. We extend the discussion and results from to systems scheduled using static-priority scheduling algorithms, with resource access arbitrated using stack resource policy (SRP), or priority ceiling protocol (PCP). We present a method to compute resource hold times for every resource, and an algorithm to decrease them without changing the semantics of the application or compromising application feasibility.

The duration of time for which each application locks each shared resource is critically important in composing multiple independently-developed applications upon a shared "open" platform. The concept of resource hold time (RHT) - the largest length of time that may elapse between the instant that an application system locks a resource and the instant that it subsequently releases the resource - is formally defined and studied in this paper. An algorithm is presented for computing resource hold times for every resource in an application that is scheduled using earliest deadline first scheduling, with resource access arbitrated using the stack resource policy. An algorithm is presented for decreasing these RHT's without changing the semantics of the application or compromising application feasibility

The scheduling of sporadic task systems upon multiprocessor platforms is considered, when inter-processor migration is permitted. It is known that current schedulability tests for such systems perform quite poorly when compared to schedulability tests for partitioned scheduling. Limitations of current tests are identified, which may be responsible for the unsatisfactory performance of these tests. A new test that overcomes some of these limitations is proposed and proved correct.

We study the problem of executing a collection of independently designed and validated task systems upon a common platform comprised of a preemptive processor and additional shared resources. We present an abstract formulation of the problem and identify the major issues that must be addressed in order to solve this problem. We present (and prove the correctness of) algorithms that address these issues, and thereby obtain a design for an open real-time environment in the presence of shared global resources.

The multiprocessor scheduling of collections of real-time jobs is considered. Sufficient tests are derived for determining whether a given collection of jobs can be scheduled to meet all deadlines upon a specified multiprocessor platform - these tests may be applied even when the collection of jobs is incompletely specified. The applicability of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks is discussed

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform with static-priority scheduling on each individual processor. Since the partitioning problem is easily seen to be NP-hard in the strong sense, this algorithm is not optimal. A quantitative characterization of its worst-case performance is provided in terms of sufficient conditions and resource augmentation approximation bounds. The partitioning algorithm is also evaluated over randomly generated task systems

The recurring real-time task model was recently proposed as a model for real-time processes that contain code with conditional branches. In this paper, we present a necessary and sufficient condition for uniprocessor non-preemptive schedulability analysis for this task model. We also derive a polynomial-time approximation algorithm for testing this condition. Preemptive schedulers usually have a larger schedulability region compared to their non-preemptive counterparts. Further, for most realistic task models, schedulability analysis for the non-preemptive version is computationally more complex compared to the corresponding preemptive version. Our results in this paper show that (surprisingly) the recurring real-time task model does not fall in line with these intuitive expectations, i.e. there exists polynomial-time approximation algorithms for both preemptive and non-preemptive versions of schedulability analysis. This has important implications on the applicability of this model, since fully preemptive scheduling algorithms often have significantly larger runtime overheads

The load parameter of a sporadic task system is defined to be the largest possible cumulative execution requirement that can be generated by jobs of the task system over any time interval, normalized by the length of the interval. This parameter is known to play a very important role in the uniprocessor feasibility analysis of sporadic task systems. In this paper, it is shown that the load of a sporadic task system may be used as an accurate indicator of its feasibility upon preemptive multiprocessors as well. Exact algorithms, and approximate ones that can be guaranteed to be accurate to within an arbitrary additive error > 0, for computing a task system's load are presented and proven correct. The performance of these algorithms is evaluated by simulation over randomly generated task systems

Resource sharing in priority-based systems can give rise to priority-inversion and blocking, wherein a job's execution is delayed because a lower-priority job holds some resource that is needed for execution. The stack resource policy (SRP) can be used to reduce such blocking in EDF-scheduled systems. An efficient implementation of an algorithm is presented for determining whether systems scheduled in this manner are feasible. Some interesting properties of such systems are derived. The technique of reducing the duration of blocking by the replication of selected resources is explored: an algorithm is presented which determines the minimum amount of resource replication necessary to achieve specified blocking times

A schedulability test is defined to be sustainable if any task system deemed schedulable by the test remains so if it behaves "better" than mandated by its system specifications. We provide a formal definition of sustainability, and subject the concept to systematic analysis in the context of the uniprocessor scheduling of periodic and sporadic task systems. We argue that it is in general good engineering practice to use sustainable tests if possible, and classify common uniprocessor schedulability tests according to whether they are sustainable or not

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks, each constrained to have its relative-deadline parameter be no larger than its period parameter, among the processors of an identical multiprocessor platform. Since the partitioning problem is easily seen to be NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation. It is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (3-(1/m)) times as fast.

Although preemptive uniprocessor scheduling algorithms are able to successfully schedule some systems that cannot be scheduled by any non-preemptive scheduling algorithm, the run-time overhead associated with implementing preemptive algorithms is often higher than for non-preemptive algorithms. In choosing between preemptive and non-preemptive scheduling algorithms on uniprocessors, the tradeoff is therefore between enhanced feasibility on the one hand, and increased overheads on the other. Hybrid scheduling schemes are proposed and evaluated here: these schemes permit preemption where necessary for feasibility, but attempt to avoid unnecessary preemptions during run-time. This is done by determining, for each task in the system, the longest amount of time for which the task may execute non-preemptively without compromising the feasibility of the system.

Current feasibility tests for the static-priority scheduling on uniprocessors of periodic task systems run in pseudo-polynomial time. We present a fully polynomial-time approximation scheme (FPTAS) for feasibility analysis in static-priority systems with arbitrary relative deadlines. This test is an approximation with respect to the amount of a processor's capacity that must be "sacrificed" for the test to become exact. We show that an arbitrary level of accuracy, /spl epsi/, may be chosen for the approximation scheme, and present a runtime bound that is polynomial in terms of /spl epsi/ and the number of tasks, n.

The partitioning of periodic task systems upon uniform multiprocessors is considered. In the partitioned approach to scheduling periodic tasks upon multiprocessors, each task is assigned to a specific processor and all jobs generated by a task are required to execute upon the processor to which the task is assigned. A uniform heterogeneous multiprocessor is a multiprocessor in which each processor has an associated speed - a processor of speed s operating for t units of time will perform s /spl times/ t units of work. Partitioning of periodic task systems requires solving the bin-packing problem, which is known to be intractable (NP-hard in the strong sense). This paper presents methods for finding an approximate utilization bound for partitioned scheduling on uniform heterogeneous multiprocessors.

In some real-time application systems, there are only a few distinct kinds of tasks, each of which may be instantiated several times during runtime. The scheduling of such sporadic task systems is considered here upon both a single processor, and on multiprocessor platforms under the partitioned paradigm of multiprocessor scheduling. Algorithms that have run-time polynomial in the number of tasks in the system are presented and proved correct.

Most prior theoretical research on partitioning algorithms for real-time multiprocessor platforms has focused on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's processing power. However, many multiprocessor platforms have only limited amounts of local per-processor memory; if the memory limitation of a processor is not respected, thrashing between "main" memory and the processor's local memory may occur during run-time and may result in performance degradation. We formalize the problem of task partitioning in a manner that is cognizant of both memory and processing capacity constraints as the memory constrained multiprocessor partitioning problem, prove that this problem is intractable, and present efficient algorithms for solving it under certain well-defined conditions.

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation; it is shown that any set of sporadic tasks that can be partitioned among the processors of an m-processor identical multiprocessor platform will be partitioned by this algorithm on an m-processor platform in which each processor is (4 - 2/m) times as fast

Multiprocessor implementations of real-time systems tend to be more energy-efficient than uniprocessor implementations. However several factors, including the nonexistence of optimal multiprocessor scheduling algorithms, combine to prevent all the computing capacity of a multiprocessor platform from being guaranteed available for executing the real-time workload. In this paper, this tradeoff - that while increasing the number of processors results in lower energy consumption for a given computing capacity, the fraction of the capacity of a multiprocessor platform that is guaranteed available for executing real-time work decreases as the number of processors increases - is explored in detail. Algorithms are presented for synthesizing multiprocessor implementations of hard-real-time systems comprised of independent periodic tasks in such a manner that the energy consumed by the synthesized system is minimized.

Given a collection of tasks that comprise the software for a real-time system, and a collection of available processing units of different kinds upon which to execute them, the heterogeneous multiprocessor partitioning problem is concerned with determining whether the given tasks can be partitioned among the available processing units in such a manner that all timing constraints are met. It is known that this problem is intractable; efficient implementations of sufficient (albeit not necessary) partitioning algorithms are presented here, and proved correct.

Summary form only given. Given a collection of recurring tasks or processes that comprise the software for an embedded system, and a number of different types of available processing units, the minimum cost synthesis problem is concerned with obtaining an implementation of the embedded system upon a multiprocessor platform comprised of processing units from among the available types, such that the total cost of the platform is minimized. It is shown that this problem is intractable (NP-hard in the strong sense). Approximation algorithms are presented that guarantee to obtain implementations with cost no more than a constant amount greater than twice the cost of an optimal implementation.

Summary form only given. If a periodic task system is scheduled upon an identical multiprocessor platform using the earliest deadline first scheduling algorithm, it is known that the "schedulable utilization" - the largest bound such that any periodic task system with cumulative utilization no larger than this bound is guaranteed to be successfully scheduled - is strictly less than the capacity of the platform. The issue of using the excess processing capacity (the difference between the platform capacity and the schedulable utilization) is addressed here, and an algorithm is presented, and proven correct, that uses this excess capacity to provide guaranteed real-time service to aperiodic jobs.

Given a collection of recurring tasks or processes that comprise the software for a real-time system, and a collection of available processing units of different kinds upon which to execute them, the heterogeneous multiprocessor partitioning problem is concerned with determining whether the given tasks can be partitioned among the available processing units in such a manner that all timing constraints are met. It is shown that this problem is intractable (NP-hard in the strong sense). Efficient implementations of sufficient (albeit not necessary) partitioning algorithms are presented, and proved correct.

Given a collection of recurring tasks or processes that comprise a real-time system, and a collection of available processing units of different kinds upon which to execute them, the heterogeneous multiprocessor feasibility problem is concerned with determining whether the given tasks can be executed on the available processing units in such a manner that all timing constraints are met. A preemptive scheduling model is assumed. Under the partitioned scheduling paradigm - each task may execute on only one processor - this problem has previously been shown to be intractable. Under the global scheduling paradigm, however, a polynomial-time algorithm for heterogeneous multiprocessor feasibility analysis is presented here, and proved correct. An upper bound is derived upon the number of tasks that need to be executed upon multiple processors: even in the worst case, it is shown that this number is reasonable small (of the order of the number of processors), implying that the benefits of global scheduling are available without requiring that too many tasks be forced to execute on multiple processors.

In fixed-priority scheduling, the priority of a job,.once assigned, may not change. A new fixed-priority algorthm for scheduling systems of periodic tasks upon identical multiprocessors is proposed. This algorithm has an achievable utilization of (m+1)/2 upon m unit-capacity processors. It is proven that this algorithm is optimal from the perspective of achievable utilization in the sense that no fixed-priority algorithm for scheduling periodic task systems upon identical multiprocessors may have an achievable utilization greater than (m+1)/2.

The priority-driven scheduling of periodic and sporadic task systems upon identical multiprocessor platforms is considered, under the restrictions that (i) each job may be assigned exactly one priority throughout its lifetime, and (ii) each job may execute upon only a single processor. It is shown that the feasibility-analysis under these restrictions is intractable (NP-hard in the strong sense). A scheduling algorithm is presented that satisfies these restrictions, and that has a worst-case utilization bound comparable to the worst-case utilization bounds of partitioned scheduling algorithms, and of scheduling algorithms that retain the priority-assignment restriction but allow arbitrary interprocessor migration.

In uniform multiprocessor platforms, the various processors comprising the multiprocessor platform may have different computing capacities. The focus of this paper is the design of efficient tests for determining whether the earliest deadline first scheduling algorithm (EDF) can successfully schedule a given real-time task system to meet all deadlines upon a specified uniform multiprocessor platform. Upon uniform multiprocessor platforms, we show that it is often far easier (from a computational complexity perspective) to determine feasibility than it is to check for EDF-schedulability. In designing an EDF-schedulability test for uniform multiprocessors, therefore, our approach is as follows: for a given uniform multiprocessor platform, we attempt to efficiently identify all those uniform multiprocessor platforms such that any real-time instance feasible upon these platforms is guaranteed to be EDF-schedulable upon the platform under consideration. EDF-schedulability upon the given platform can then be determined by ascertaining whether the real-time system is feasible upon any of these platforms.

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s /spl times/ t) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor platforms using the rate-monotonic scheduling algorithm is considered here. A simple, sufficient test is presented for determining whether a given periodic task system will be successfully scheduled by algorithm upon a particular uniform multiprocessor platform-this test generalizes earlier results concerning rate-monotonic scheduling upon identical multiprocessor platforms.

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s /spl times/ t) units of execution. The earliest deadline first (EDF) scheduling of hard-real-time systems upon uniform multiprocessor machines is considered. It is known that online algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit online algorithms in general (EDF in particular) to perform better than may be expected given these inherent limitations. It is shown that EDF scheduling upon uniform multiprocessors is robust with respect to both job execution requirements and processor computing capacity.

The rate-monotonic algorithm is arguably one of the most popular algorithms for scheduling systems of periodic real-time tasks. The rate-monotonic scheduling of systems of periodic tasks on uniform multiprocessor platforms is considered here. A simple, sufficient test is presented for determining whether a given periodic task system will be successfully scheduled by this algorithm upon a particular uniform multiprocessor platform-this test generalizes earlier results concerning rate-monotonic scheduling upon identical multiprocessor platforms.

The earliest-deadline-first (EDF) scheduling of hard-real-time systems upon uniform multiprocessor machines is considered. It is shown that EDF scheduling upon uniform multiprocessors is robust with respect to processor computing capacity. This result is used to derive a new multiprocessor EDF-feasibility analysis algorithm, which is superior to previously-proposed algorithms.

H. Chetto and M. Chetto (1989) presented an algorithm for the online admission control and run-time scheduling of aperiodic real-time jobs in preemptive uniprocessor environments that are executing systems of periodic hard real-time tasks. This algorithm requires a significant degree of preprocessing of the system of periodic tasks - in general, this preprocessing takes a time that is exponential in the representation of the periodic task system. In this paper, we develop techniques for speeding up the preprocessing phase of the Chetto & Chetto algorithm, by adapting it for implementation in parallel environments. We validate the effectiveness of our parallelization both by theoretical results and through simulation experiments.

The preemptive scheduling of systems of periodic tasks on a platform comprised of several identical processors is considered. A scheduling algorithm is proposed for static-priority scheduling of such systems; this algorithm is a simple extension of the uniprocessor rate-monotonic scheduling algorithm. It is proven that this algorithm successfully schedules any periodic task system with a worst-case utilization no more than a third the capacity of the multiprocessor platform. It is also shown that no static-priority multiprocessor scheduling algorithm (partitioned or global) can guarantee schedulability for a periodic task set with a utilization higher than one half the capacity of the multiprocessor platform.

Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s/spl times/t) units of execution. The on-line scheduling of hard-real-time systems, in which all jobs must complete by specified deadlines, on uniform multiprocessor machines is considered It is known that online algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit online algorithms to perform better than may be expected given the inherent limitations. Results derived here are applied to the scheduling of periodic task systems on uniform multiprocessor machines.

A uniform multiprocessor machine is comprised of an integer number of processors. Each processor P is characterized by a computing capacity P.c, with the interpretation that a job j executing on a processor P for t time units completes (P/sub j/.c/spl times/t) units of execution. The scheduling of systems of periodic tasks on uniform multiprocessor systems is considered.

A framework for scheduling a number of different applications on a single shared pre-emptable processor is proposed, such that each application seems to be executing on a slower dedicated processor. A tradeoff is identified and evaluated between how precise a notion of real time (as measured by the granularity of its clock) an application needs to have supported on the one hand, and the added context-switch costs imposed by our scheduling framework on the other.

A framework for scheduling a number of different real-time applications on a single shared preemptable processor is proposed. This framework enforces complete isolation among the different applications, such that the behavior of each application is very similar to its behavior if it had been executing on a slower dedicated processor. A scheduling algorithm that implements this framework is presented and proved correct.

The multiframe model of hard-real-time tasks is a generalization of the well-known periodic task model of C. Liu and J. Layland (1973). The feasibility analysis of systems of multiframe tasks which are assigned priorities according to the rate-monotonic priority assignment scheme is studied. An efficient sufficient feasibility test for such systems of multiframe tasks is presented and proved correct-this generalizes a result of A.K. Mok and D. Chen (1997).

Packet switching in connection-oriented networks that may have multiple parallel links between pairs of switches is considered. An efficient packet scheduling algorithm that guarantees a deterministic quality of service to connections with real time constraints is proposed; this algorithm is a generalization of some recent multiprocessor scheduling algorithms, and offers real time performance guarantees similar to those offered by earlier fair scheduling strategies, such as Weighted Fair Queueing and proportional share schemes.

A new model for hard-real-time tasks-the recurring branching task model-is introduced, which is capable of modelling some restricted forms of conditional real-time process code. This model generalizes earlier models such as the sporadic task model and the generalized multiframe task model. It is shown that feasibility analysis in this model-determining whether a system of several recurring branching tasks that share a processor can all be scheduled to always meet all deadlines-can be performed efficiently, in pseudo-polynomial time.

Temporal load-balancing, spreading out the executions of tasks over time, is desirable in many applications in complex systems. A form of temporal load balancing is discussed, scheduling to maximize minimum inter-completion time (MICT-scheduling) and minimum global inter-completion time (MGICT-scheduling). It is shown that MICT- and MGICT-scheduling are, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MICT- and MGICT-scheduled.

A new model for hard real time tasks-the recurring real time task model-is introduced. This model generalizes earlier models such as the sporadic task model and the generalized multiframe task model. An algorithm is presented for feasibility analysis of a system of independent recurring real time tasks in a preemptive uniprocessor environment.

The on-line scheduling of systems of imprecise computation tasks is investigated. The system objective is to maximize the value obtained. A formal model is defined. Under certain reasonable assumptions-formalized here as the weak feasible mandatory constraint-a competitive on-line scheduling algorithm is presented for the commonly studied uniform-density task systems. It is proven, however, that an on-line algorithm may, in general, perform arbitrarily poorly as compared to a clairvoyant scheduler.

The scheduling of generalized pinwheel task systems is considered. It is shown that pinwheel scheduling is closely related to the fair scheduling of periodic task systems. This relationship is exploited to obtain new scheduling algorithms for generalized pinwheel task systems. When compared to traditional pinwheel scheduling algorithms, these new algorithms are both more efficient from a run-time complexity point of view, and have a higher density threshold, on a very large subclass of generalized pinwheel task systems.

Traffic reshaping and its impact on providing deterministic guarantees of timely data delivery in a packet-switched virtual-circuit fixed-packet network are investigated. Two types of traffic smoothing are considered: global reshaping (when traffic on all network connections is smoothed) and local reshaping (when the traffic specification is changed only for a single connection). The conditions when reshaping is beneficial are derived and the optimal values of traffic model parameters are obtained. In particular, it is shown that, when one tries to minimize end-to-end delay bounds for leaky bucket constrained traffic, the traffic either should be made constant bit rate (CBR) or should not be reshaped at all. It is proven that changing the leaky bucket specification to the dual leaky bucket specification is always able to yield better timeliness guarantees and utilisation of network resources. Finally, local reshaping for the dual leaky bucket model is studied.

The design of programs for broadcast disks which incorporate real-time and fault-tolerance requirements is considered. A generalized model for real-time fault-tolerant broadcast disks is defined. It is shown that designing programs for broadcast disks specified in this model is closely related to the scheduling of pinwheel task systems. Some new results in pinwheel scheduling theory are derived, which facilitate the efficient generation of real-time fault-tolerant broadcast disk programs.

The Processing Graph Method (PGM)-a dataflow model widely used in the design and analysis of embedded signal-processing applications-is studied from a real-time scheduling perspective. It is shown that the problem of deciding if instances of the general model are feasible on a single processor is intractable (co-NP-complete in the strong sense); however, a useful special case is sometimes more tractable. An efficient feasibility test and an optimal preemptive scheduling algorithm are derived for this special case, and a procedure is presented which permits system architects to make efficient use of computational resources and memory requirements for buffers while constructing real-time dataflow applications that offer hard service guarantees.

A general model for traffic flows on packet-switched, virtual-circuit based, fixed-packet networks is introduced, and an exact schedulability test is obtained for systems of such flows. Rules are derived that make the evaluation of this schedulability test feasible and efficient under certain circumstances. The practical relevance of this approach is demonstrated by applying it to a number of standard traffic models.

A model for periodic tasks is proposed that explicitly incorporates jitter-the uncertainty in the arrival times of individual frames. Feasibility-analysis of systems of such tasks is studied in the context of dynamic-priority, preemptive, uniprocessor scheduling. From a computational complexity perspective, the problem is shown to be no more difficult than feasibility analysis in systems of periodic tasks that do not exhibit jitter. Several feasibility analysis algorithms are presented and proven correct.

No on-line scheduling algorithm operating in an uniprocessor environment can guarantee to obtain a useful processor utilization greater than 0.25 under conditions of overload. This result holds in the general case, where the deadlines of the input tasks can be arbitrarily "tight." We address here the issue of improving overload performance in environments where there is a limit on the tightness of task deadlines. In particular, we present a new scheduling algorithm, ROBUST, that efficiently takes advantage of these limits to provide improved overload performance and is asymptotically optimal. We also introduce the concept of overload tolerance, wherein a system's overload performance never falls below its design capacity, and describe how ROBUST may be used to construct overload tolerant systems.

The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints is considered. A new heuristic with the time complexity of O(n/sup 2/m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.

We propose and analyze a proportional share resource allocation algorithm for realizing real-time performance in time-shared operating systems. Processes are assigned a weight which determines a share (percentage) of the resource they are to receive. The resource is then allocated in discrete-sized time quanta in such a manner that each process makes progress at a precise, uniform rate. Proportional share allocation algorithms are of interest because: they provide a natural means of seamlessly integrating real and non-real-time processing; they are easy to implement; they provide a simple and effective means of precisely controlling the real-time performance of a process; and they provide a natural means of policing so that processes that use more of a resource than they request have no ill-effect on well-behaved processes. We analyze our algorithm in the context of an idealized system in which a resource is assumed to be granted in arbitrarily small intervals of time and show that our algorithm guarantees that the difference between the service time that a process should receive and the service time it actually receives is optimally bounded by the size of a time quantum. In addition, the algorithm provides support for dynamic operations, such as processes joining or leaving the competition, and for both fractional and non-uniform time quanta. As a proof of concept we have implemented a prototype of a CPU scheduler under FreeBSD. The experimental results shows that our implementation performs within the theoretical bounds and hence supports real-time execution in a general purpose operating system.

The issue of temporal fairness in periodic real-time scheduling is considered. It is argued that such fairness is often a desirable characteristic in real-time schedules. A concrete criterion for temporal fairness-pfairness-is described. The weight-monotonic scheduling algorithm, a static priority scheduling algorithm for generating pfair schedules, is presented and proven correct. A feasibility test is presented which, if satisfied by a system of periodic tasks, ensures that the weight-monotonic scheduling algorithm will schedule the system in a pfair manner.

The problem of uniprocessor scheduling under conditions of overload is investigated. The system objective is to maximize the number of tasks that complete by their deadlines. For this performance metric it is shown that, in general, any on-line algorithm may perform arbitrarily poorly as compared to a clairvoyant scheduler. Restricted instances of the general problem for which on-line schedulers ran provide a guaranteed level of performance are identified, and on-line algorithms presented for these special cases.>

No on-line scheduling algorithm operating in a uniprocessor environment can guarantee to obtain an effective processor utilization greater than 25% under conditions of overload. This result holds in the most generad case, where incoming tasks may have arbitrary slack times. We address here the issue of improving overload performance in environments where the slack-time charactersitics of all incoming tasks satisfy certain constraints. In particular, we present a new scheduling algorithm, ROBUST, that efficiently takes advantage of these task slack constraints to provide improved overload performance and is asymptotically optimal.

Article Proportionate progress: a notion of fairness in resource allocation Share on Authors: S. K. Baruah View Profile , N. K. Cohen View Profile , C. G. Plaxton View Profile , D. A. Varvel View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 345–354https://doi.org/10.1145/167088.167194Online:01 June 1993Publication History 48citation798DownloadsMetricsTotal Citations48Total Downloads798Last 12 Months19Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The preemptive scheduling of sporadic tasks on a uniprocessor is considered. A task may arrive at any time, and is characterized by a value that reflects its importance, an execution time that is the amount of processor time needed to completely execute the task, and a deadline by which the task is to complete execution. The goal is to maximize the sum of the values of the completed tasks. An online scheduling algorithm that achieves optimal performance when the system is underloaded and provides a nontrivial performance guarantee when the system is overloaded is designed. The algorithm is implemented using simple data structures to run at a cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant. Upper bounds on the best performance guarantee obtainable by an online algorithm in a variety of settings are derived.>

The authors study the performance of online algorithms in environments where no value is obtained for the partial execution of a request. They prove that no online scheduling algorithm can have a competitive factor greater than 0.25 times the optimal. They further refine this bound by considering the effect of the loading factor. Other models of task systems (for example, tasks systems consisting of many types of task requests), are considered. Similar upper bounds on the competitive factor that can be made by online scheduling algorithms in these environments are proved. It is shown that the performance bound of 0.25 is tight by means of a simple online uniprocessor scheduling algorithm has a competitive factor of 1/4. The authors extend the discussion to systems with dual processors. They show that the upper bound for the dual-processor online scheduling problem is 1/2 if all tasks have the same value density. This bound is tight if the tasks all also have zero laxity.>

Consideration is given to the preemptive scheduling of hard-real-time sporadic task systems on one processor. The authors first give necessary and sufficient conditions for a sporadic task system to be feasible (i.e., schedulable). The conditions cannot, in general, be tested efficiently (unless P=NP). They do, however, lead to a feasibility test that runs in efficient pseudo-polynomial time for a very large percentage of sporadic task systems.>