For hard-real time systems, cache memory increases execution time variability, increasing the complexity of timing analysis. As such, cache memory is often treated exclusively as a detractor to schedulability. Cache-aware co-located scheduling aims at improving schedulability by carefully scheduling threads to share cached values. Cache sharing between threads potentially reduces task execution times and increases schedulability with fewer resources. Antithetically, co-located scheduling may reduce parallelism, decreasing efficiency. Thus, identifying the optimal set of threads to co-locate that minimizes the resources required while ensuring timing constraints is a complex challenge. This work establishes optimal co-location as NP-Hard in the strong sense. It offers an approximation method for the co-located scheduling of Fork-Join tasks named 3-parm-hd . The approximation has a 3-factor guarantee and a resource augmentation bound of 3. The simulated evaluation shows 3-parm-hd increases schedulability compared to an optimal intractable algorithm (without co-location) scheduling 28% more tasks with 30% fewer cores. Simulated results show 3-parm-hd outperforms a 2-factor approximation for traditional makespan, scheduling 45 % more tasks with 41% fewer cores. An experimental RISC-V evaluation running on a QEMU platform confirms the benefits of 3-parm-hd , scheduling and executing tasks deemed unschedulable by a 2-factor makespan approximation without co-location.

Robotic teleoperation over long communication distances poses challenges due to delays in commands and feedback from network latency. One simple yet effective strategy to reduce errors and increase performance under delay is to downscale the relative motion between the operating surgeon and the robot. The question remains as to what is the optimal scaling factor, and how this value changes depending on the level of latency as well as operator tendencies. We present user studies investigating the relationship between latency, scaling factor, and performance. The results of our studies demonstrate a statistically significant difference in performance between users and across scaling factors for certain levels of delay. These findings indicate that the optimal scaling factor for a given level of delay is specific to each user, motivating the need for personalized models for optimal performance. We present techniques to model the user-specific mapping of latency level to scaling factor for optimal performance, leading to an efficient and effective solution to optimizing performance of robotic teleoperation and specifically telesurgery under large communication delay.

In safety critical computing, real-time and security concerns are often considered separately, though the behavior of a scheduling model itself may be an attack surface which can be exploited by an attacker to reduce system performance. In this work, we explore how the semantics of mode changes in mixed-criticality systems could be used as one such attack vector. This attack, dubbed Mad Monk, uses a mixed criticality scheduler's mode switches against itself by allowing a task of a lower criticality to interfere with tasks of a higher criticality, thereby forcing a disruptive mode switch which could possibly reduce service to some tasks. We describe this attack in detail, along with a case study demonstrating its risk. Furthermore, extensive simulations of this attack demonstrate its potential effectiveness based on a variety of timing and system factors.

Safety-critical embedded systems often have very limited computational capabilities that must be carefully managed to provide the required functionalities. Since such systems are increasingly becoming a target of attacks, there is a need for real-time resource-allocation techniques that are resistant to such attacks. We extend the widely used sporadic task model to additionally enable the representation of certain kinds of security requirements, develop a corresponding scheduling algorithm and associated schedulability test, and experimentally evaluate the effectiveness of our proposed algorithm and test.

Power Distribution Systems (PDSes) protect Cyber-Physical Systems from power faults. This work proposes an intelligent PDS with real-time current monitoring to improve fault tolerance. To bound the real-time task utilization, we define linear and nonlinear utilization bounding techniques unique to PDSes. We exploit sub-maximal loading inherent in all practical PDSes, providing a total task set utilization bound less than the sum of individual task bounds. We show these techniques are safe and applicable to real PDSs. Simulation of existing and randomly generated PDSes show up to 90 % utilization reduction versus a naive approach. An experimental, open-source PDS implementation is also provided to validate feasibility.

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.

Following the trend of increasing autonomy in real-time systems, multi-core System-on-Chips (SoCs) have enabled devices to better handle the large streams of data and intensive computation required by such autonomous systems. In modern multi-core SoCs, each L1 cache is designed to be tied to an individual processor, and a processor can only access its own L1 cache. This design method ensures the system's average throughput, but also limits the possibility of parallelism, significantly reducing the system's real-time schedulability. To overcome this problem, we present a new system framework for highly-parallel multi-core systems,Hopscotch.Hopscotchintroduces re-sizable L1 cache which is shared between processors in the same computing cluster. At execution,Hopscotchdynamically allocates L1 cache capacity to the tasks executed by the processors, unblocking the available parallelism in the system. Based on the new hardware architecture, we also present a new theoretical model and schedulability analysis providing cache size selection methods and corresponding timing guarantees for the system. As demonstrated in the evaluations,Hopscotcheffectively improves system-level schedulability with negligible extra overhead.

In modern real-time heterogeneous System-on-Chips, ensuring real-time performance is increasingly important. However, with ever-increasing hardware and architectural complexity, satisfying such timing requirements becomes very challenging due to both hardware heterogeneity and the complicated access paths induced by the on-chip accelerators. In this paper, inspired by an interesting observation from accelerable real-time task scheduling, we propose a new core-accelerator interface, BlueFace, which is integrated into the memory access stage of the CPU pipeline, effectively avoiding the complicated HA access paths. The BlueFace design constructs a priority queue to schedule the HA operations at the hardware level, ensuring simultaneous throughput and real-time performance. The evaluation demonstrates the performance benefits and gives the overhead of BlueFace.

Autonomous mobile robots (AMRs) have the capability to execute a wide range of tasks with minimal human intervention. However, one of the major limitations of AMRs is their limited battery life, which often results in interruptions to their task execution and the need to reach the nearest charging station. Optimizing energy consumption in AMRs has become a critical challenge in their deployment. Through empirical studies on real AMRs, we have identified a lack of coordination between computation and control as a major source of energy inefficiency. In this paper, we propose a comprehensive energy prediction model that provides real-time energy consumption for each component of the AMR. Additionally, we propose three path models to address the obstacle avoidance problem for AMRs. To evaluate the performance of our energy prediction and path models, we have developed a customized AMR called Donkey, which has the capability for fine-grained (millisecond-level) end-to-end power profiling. Our energy prediction model demonstrated an accuracy of over 90% in our evaluations. Finally, we applied our energy prediction model to obstacle avoidance and guided energy-efficient path selection, resulting in up to a 44.8% reduction in energy consumption compared to the baseline.

Deploying humans in a high-risk environment to extract casualties in order to provide medical attention is an inherently dangerous endeavor. To minimize this risk, Robotics and Autonomous Systems can be deployed in hazardous areas in place of human personnel to limit the exposure of first responders to various life-threatening conditions. The success of robotic extraction of injured persons depends heavily on how safely the human subject is handled. Therefore, the integration of intelligent technologies for secure control and motion planning is crucial in overcoming the dynamic and complex challenges of robotic grasping and manipulation. In this regard, the measurement of the target human subject's weight is an essential factor for safe grasping and maneuvering during robotic interactions with humans. This paper presents a contactless vision-based approach for estimating the weight of the human body. This approach employs visual body perception, 3D body point cloud representation, and a deep learning network for body segmentation to measure specific body parameters. Next, the body parameters are fed into a neural network model to predict the total body weight. This prediction then enables an approximation of the weight of individual body segments to be obtained.

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.

In emergency rescue scenarios, rapid identification of human casualties is a critical first step in enhancing emergency medical response. This task can be limited by the physical and cognitive capacity of rescue personnel, who are exposed to significant risk. The use of small unmanned aerial systems (sUAS) equipped with autonomous casualty assessment abilities can reduce these limitations and risks by enabling remote casualty detection, identification, and vitals assessment, providing standoff protection, and eliminating the need for human personnel to access the potentially hazardous scene. This paper presents a vision-based casualty assessment framework and specifically discusses our casualty identification software, which is designed to recognize the faces of casualties and identify their nametapes in images captured by sUAS under realistic conditions. Our approach addresses the limitations of the sUAS-captured long-distance images to enable accurate identification in challenging casualty monitoring situations. The face and nametape recognition algorithms will be integrated into the larger casualty perception framework and embedded into sUAS platforms to assist with emergency rescue operations. The total casualty perception system will detect, identify, and evaluate the condition of casualties from a remote location, providing standoff protection to first responders and rapid information to inform a suitable medical treatment plan.

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.

For hard-real time systems, cache memory increases execution time variability, increasing the complexity of timing analysis. As such, cache memory is often treated exclusively as a detractor to schedulability. Cache-aware co-located scheduling aims to improve schedulability by carefully scheduling threads to share cached values. Cache sharing between threads potentially reduces task execution times and increases schedulability with fewer resources. Antithetically, co-located scheduling may reduce parallelism, decreasing efficiency. Thus, identifying the optimal set of threads to co-locate that minimizes the resources required while ensuring timing constraints is a complex challenge. This work establishes optimal co-location as NP-Hard in the strong sense. It offers an approximation method for the co-located scheduling of Fork-Join tasks named 3-PARM-HD. The approximation has a 3-factor guarantee and a resource augmentation bound of 3. The simulated evaluation shows 3-PARM-HD increases schedulability compared to an optimal intractable algorithm (without co-location) scheduling 28% more tasks with 30% fewer cores. Simulated results show 3-PARM-HD outperforms a 2-factor approximation for traditional makespan, scheduling 39% more tasks with 44% fewer cores. An experimental RISC-V evaluation running on a QEMU platform confirms the benefits of 3-PARM-HD, scheduling and executing tasks deemed unschedulable by a 2-factor makespan approximation without co-location.

In modern real-time heterogeneous System-on-Chips (SoCs), ensuring the predictability of interconnects is becoming increasingly important. Most of the existing interconnects are mainly designed to achieve high throughput, with their micro-architectures usually based on FIFO queues. The FIFO-based design prevents transaction prioritization based on importance and leads to occurrences of physical priority inversion. Such problems lead to difficulties in ensuring transaction predictability, especially when the system scales to a large number of elements. In this paper, we introduce AXI-Interconnect^{rt} (AXI-IC^{rt}, for short) -- a real-time AXI interconnect for heterogeneous SoCs, which redefines the micro-architecture of interconnects by enabling random accesses of buffered transactions and organizing transactions through compositional scheduling. This hardware-software co-design approach provides predictable and scalable real-time performance for highly integrated SoCs.

In safety-critical computing systems, the I/O virtualization must simultaneously satisfy different requirements, including time-predictability, performance, and energy-efficiency. However, these requirements are challenging to achieve due to complex I/O access path and resource management at the system level, lack of support from preemptive scheduling at I/O hardware level, and missing an effective energy management method. In this paper, we propose a new framework, I/O-GUARD, which reconstructs the system architecture of I/O virtualization, bringing a dedicated hardware hypervisor to handle resource management throughout the system. The hypervisor improves system real-time performance by enabling preemptive scheduling in I/O virtualization with both analytical and experimental real-time guarantees. Furthermore, we also present a dedicated energy management unit to adjustI/O-GUARD's dynamic energy using frequency scaling. Associated with that, a frequency identification algorithm is proposed to find the appropriate executing frequency at run-time. As shown in experiments,I/O-GUARDsimultaneously improves the predictability, performance and energy-efficiency compared to the state-of-the-art I/O virtualization.

In real-time embedded computing, time-predictability and performance are required simultaneously by memory transactions. However, with increasingly more elements being integrated into hardware, memory interconnects become a critical stumbling block to satisfying timing correctness, due to lack of hardware and scheduling scalability. In this paper, we propose a new hierarchically distributed memory interconnect, BlueScale, managing memory transactions using identical Scale Elements, which ensures hardware scalability. The Scale Element introduces two nested priority queues, achieving iterative compositional scheduling for memory transactions, guaranteeing transaction tasks' scheduling schedulability. Associated with the new architecture, a theoretical model is established to improve BlueScale's real-time performance.

We design a parallel algorithm for the Constrained Shortest Path (CSP) problem. The CSP problem is known to be NP-hard and there exists a pseudo-polynomial time sequential algorithm that solves it. To design the parallel algorithm, we extend the techniques used in the design of the Δ-stepping algorithm for the single-source shortest paths problem.

For safety-critical| computer systems, time-predictability and performance are usually required simultaneously in I/O virtualization. However, both requirements are challenging to achieve due to complex I/O access path and resource management at system level and lack of support from preemptive scheduling at I/O hardware level. In this paper, we propose a new framework, I/O-GUARD, which reconstructs the system architecture of I/O virtualization, bringing a dedicated hardware hypervisor to handle resource management throughout the system. The hypervisor improves system real-time performance by enabling preemptive scheduling in I/O virtualization with both analytical and experimental real-time guarantees. Specifically, I/O-GUARD is a First-of-Its-Kind framework for multi-/many-core I/O virtualization.

In modern, real-time heterogeneous systems, ensuring the predictability of interconnects is becoming increasingly important. Existing interconnects are mainly designed to achieve high throughput, with their micro-architectures usually based on FIFO queues. This FIFO-based design prevents prioritization of transactions based on their importance, leading to difficulties in ensuring transaction predictability, especially in a system with a large number of system components. In this paper, we introduce AXI-InterconnectRT, a real-time AXI interconnect for heterogeneous SoCs, which redefines the micro-architecture of interconnects by enabling random accesses of buffered transactions and organizing transactions using dedicated hardware units. With the new micro-architecture, AXI-InterconnectRTcan manage transactions based on their importance, guaranteeing their predictability.

Characterizing computational demand of Cyber-Physical Systems (CPS) is critical for guaranteeing that multiple hard real-time tasks may be scheduled on shared resources without missing deadlines. In a CPS involving repetition such as industrial automation systems found in chemical process control or robotic manufacturing, sensors and actuators used as part of the industrial process may be conditionally enabled (and disabled) as a sequence of repeated steps is executed. In robotic manufacturing, for example, these steps may be the movement of a robotic arm through some trajectories followed by activation of end-effector sensors and actuators at the end of each completed motion. The conditional enabling of sensors and actuators produces a sequence of Monotonically Ascending Execution times (MAE) with lower WCET when the sensors are disabled and higher WCET when enabled. Since these systems may have several predefined steps to follow before repeating the entire sequence each unique step may result in several consecutive sequences of MAE. The repetition of these unique sequences of MAE result in a repeating WCET sequence. In the absence of an efficient demand characterization technique for repeating WCET sequences composed of subsequences with monotonically increasing execution time, this work proposes a new task model to describe the behavior of real-world systems which generate large repeating WCET sequences with subsequences of monotonically increasing execution times. In comparison to the most applicable current model, the Generalized Multiframe model (GMF), an empirically and theoretically faster method for characterizing the demand is provided. The demand characterization algorithm is evaluated through a case study of a robotic arm and simulation of 10,000 randomly generated tasks where, on average, the proposed approach is 231 and 179 times faster than the state-of-the-art in the case study and simulation respectively.

Following the trend of increasing autonomy in cyber-physical systems, parallel embedded architectures have enabled devices to better handle the large streams of data and intensive computation required by such autonomous systems. However, while the explosion of highly-parallel platforms has seen a proportional growth in the number of applications/devices that utilize these platforms, the embedded systems community's understanding of how to build time-predictable, safety-critical systems with parallel platforms has not kept pace. As a well-motivated but challenging parallel scheduling model, gang scheduling requires all parallel threads of each parallel task to simultaneously execute in unison, which is in contrast to traditional, multi-threaded parallel scheduling, where a parallel task may spawn multiple threads, and each thread will be scheduled independently of other threads of the same task. While increasing research efforts on hard real-time (HRT) gang scheduling have recently been seen, the problem of gang scheduling in the context of soft real-time (SRT) systems, where provably bounded deadline tardiness can be tolerated, has hardly been studied yet. In this article, we derive and prove the first tardiness bounds for sporadic gang task systems under preemptive GEDF scheduling. A total utilization bound for SRT-schedulability is required for ensuring such tardiness bounds but it is shown to be tight with respect to the platform capacity and maximum parallelism-induced idleness. Furthermore, we also empirically evaluate the effects of different degrees of task parallelism upon the SRT-schedulability.

Both energy-efficiency and real-time performance are critical requirements in many embedded systems applications such as self-driving car, robotic system, disaster response, and security/safety control. These systems entail a myriad of real-time tasks, where each task itself is a parallel task that can utilize multiple computing units at the same time. Driven by the increasing demand for parallel tasks, multi-core embedded processors are inevitably evolving to many-core. Existing work on real-time parallel tasks mostly focused on real-time scheduling without addressing energy consumption. In this paper, we address hard real-time scheduling of parallel tasks while minimizing their CPU energy consumption on multicore embedded systems. Each task is represented as a directed acyclic graph (DAG) with nodes indicating different threads of execution and edges indicating their dependencies. Our technique is to determine the execution speeds of the nodes of the DAGs to minimize the overall energy consumption while meeting all task deadlines. It incorporates a frequency optimization engine and the dynamic voltage and frequency scaling (DVFS) scheme into the classical real-time scheduling policies (both federated and global) and makes them energy-aware. The contributions of this paper thus include the first energy-aware online federated scheduling and also the first energy-aware global scheduling of DAGs. Evaluation using synthetic workload through simulation shows that our energy-aware real-time scheduling policies can achieve up to 68% energy-saving compared to classical (energy-unaware) policies. We have also performed a proof of concept system evaluation using physical hardware demonstrating the energy efficiency through our proposed approach.

Multiprocessor scheduling of hard real-time tasks modeled by directed acyclic graphs (DAGs) exploits the inherent parallelism presented by the model. For DAG tasks, a node represents a request to execute an object on one of the available processors. In one DAG task, there may be multiple execution requests for one object, each represented by a distinct node. These distinct execution requests offer an opportunity to reduce their combined cache overhead through coordinated scheduling of objects as threads within a parallel task. The goal of this work is to realize this opportunity by incorporating the cache-aware BUNDLE-scheduling algorithm into federated scheduling of sporadic DAG task sets.This is the first work to incorporate instruction cache sharing into federated scheduling. The result is a modification of the DAG model named the DAG with objects and threads (DAG-OT). Under the DAG-OT model, descriptions of nodes explicitly include their underlying executable object and number of threads. When possible, nodes assigned the same executable object are collapsed into a single node; joining their threads when BUNDLE-scheduled. Compared to the DAG model, the DAG-OT model with cache-aware scheduling reduces the number of cores allocated to individual tasks by approximately 20 percent in the synthetic evaluation and up to 50 percent on a novel parallel computing platform implementation. By reducing the number of allocated cores, the DAG-OT model is able to schedule a subset of previously infeasible task sets.

The benefits of the limited preemption scheduling model serve to minimize preemption overhead while enabling cooperative scheduling between real-time tasks. Preemption point placement (PPP) algorithms are employed to select a suitable subset of preemption locations for limited preemption scheduling that optimize task worst case execution time. Similarly, preemption threshold scheduling enhances schedulability in a fully-preemptive environment by taking advantage of execution time slack in a task set by adjusting preemption thresholds to permit tasks to completely execute non-preemptively where possible. The ability to execute non-preemptively offers reduced cache related preemption delay (CRPD) further enhancing limited preemption schedulability. In this work, we integrate limited preemption scheduling using preemption placement with preemption threshold scheduling to realize further task set schedulability benefits. A case study using synthetically generated tasksets will demonstrate the significantly improved (up to a 30% increase in breakdown utilization) schedulability benefits of our proposed integrated PPP and optimal threshold assignment (OTA) algorithm.

In mixed-criticality systems, mode switch is a key strategy which dynamically provides a balance between system performance and safety. In conventional MCS frameworks, mode switch is triggered by the over-execution of a task; i.e., a task overruns the less pessimistic worst-case execution time. In cyber-physical systems, the data volume generated by I/O affects and can even dominate task computation time. With this in mind, we introduce a novel MCS architecture, termed Pythia-MCS, which predicts task execution time according to I/O run-time behaviors. With the new feature of future-prediction, the Pythia-MCS provides more timely, but still accurate, mode switch. We also present a new theoretical model (quarter-clairvoyance), which guarantees the timing predictability of the design, and a new schedulability analysis for the Pythia-MCS, which demonstrates improved schedulability compared to conventional MCS frameworks. The Pythia-MCS is the first MCS framework enabling the clairvoyance functionality.

Task parameters in traditional models, e.g., the generalized multiframe (GMF) model, are fixed after task specification time. When tasks whose parameters can be assigned within a range, such as the frame parameters in self-suspending tasks and end-to-end tasks, the optimal offline assignment towards schedulability of such parameters becomes important. The GMF-PA (GMF with parameter adaptation) model proposed in recent work allows frame parameters to be flexibly chosen (offline) in arbitrary-deadline systems. Based on the GMF-PA model, a mixed-integer linear programming (MILP)-based schedulability test was previously given under EDF scheduling for a given assignment of frame parameters in uniprocessor systems. Due to the NP-hardness of the MILP, we present a pseudo-polynomial linear programming (LP)-based heuristic algorithm guided by a concave approximation algorithm to achieve a feasible parameter assignment at a fraction of the time overhead of the MILP-based approach. The concave programming approximation algorithm closely approximates the MILP algorithm, and we prove its speed-up factor is (1+delta)^2 where delta > 0 can be arbitrarily small, with respect to the exact schedulability test of GMF-PA tasks under EDF. Extensive experiments involving self-suspending tasks (an application of the GMF-PA model) reveal that the schedulability ratio is significantly improved compared to other previously proposed polynomial-time approaches in medium and moderately highly loaded systems.

The BUNDLE and BUNDLEP scheduling algorithms are cache-cognizant thread-level scheduling algorithms and associated worst case execution time and cache overhead (WCETO) techniques for hard real-time multi-threaded tasks. The BUNDLE-based approaches utilize the inter-thread cache benefit to reduce WCETO values for jobs. Currently, the BUNDLE-based approaches are limited to scheduling a single task. This work aims to expand the applicability of BUNDLE-based scheduling to multiple task multi-threaded task sets. BUNDLE-based scheduling leverages knowledge of potential cache conflicts to selectively preempt one thread in favor of another from the same job. This thread-level preemption is a requirement for the run-time behavior and WCETO calculation to receive the benefit of BUNDLE-based approaches. This work proposes scheduling BUNDLE-based jobs non-preemptively according to the earliest deadline first (EDF) policy. Jobs are forbidden from preempting one another, while threads within a job are allowed to preempt other threads. An accompanying schedulability test is provided, named Threads Per Job (TPJ). TPJ is a novel schedulability test, input is a task set specification which may be transformed (under certain restrictions); dividing threads among tasks in an effort to find a feasible task set. Enhanced by the flexibility to transform task sets and taking advantage of the inter-thread cache benefit, the evaluation shows TPJ scheduling task sets fully preemptive EDF cannot.

Engine-triggered tasks are real-time tasks that are released when the crankshaft in an engine completes a rotation, which depends on the angular speed and acceleration of the crankshaft itself. In addition, the execution time of an engine-triggered task depends on the speed of the crankshaft. Tasks whose execution times depend on a variable period are referred to as adaptive-variable rate (AVR) tasks. Existing techniques to calculate the worst-case demand of AVR tasks are either inexact or computationally intractable. In this paper, we transform the problem of finding the worst-case demand of AVR tasks over a given time interval into a variant of the knapsack problem to efficiently find the exact solution. We then propose a framework to systematically reduce the search space associated with finding the worst-case demand of AVR tasks. Experimental results reveal that our approach is at least 10 times faster, with an average runtime improvement of 146 times, for randomly generated tasksets when compared to the state-of-the-art technique.

In "BUNDLE: Real-Time Multi-Threaded Scheduling to Reduce Cache Contention", Tessler and Fisher propose a scheduling mechanism and combined worst-case execution time calculation method that treats the instruction cache as a beneficial resource shared between threads. Object analysis produces a worst-case execution time bound and separates code segments into regions. Threads are dynamically placed in bundles associated with regions at run time by the BUNDLE scheduling algorithm where they benefit from shared cache values. In the evaluation of the previous work, tasks were created with a predetermined worst-case execution time path through the control flow graph. Apriori knowledge of the worst-case path is an impractical restriction on any analysis. At the time, the only other solution available was an all-paths search of the graph, which is an equally impractical approach due to its complexity. The primary focus of this work is to build upon BUNDLE, expanding its applicability beyond a proof of concept. We present a complete worst-case execution time calculation method that includes thread level context switch costs, operating on real programs, with representative architecture parameters, and compare our results to those produced by Heptane's state of the art method. To these ends, we propose a modification to the BUNDLE scheduling algorithm called BUNDLEP. Bundles are assigned priorities that enforce an ordered flow of threads through the control flow graph - avoiding the need for multiple all-paths searches through the graph. In many cases, our evaluation shows a run-time and analytical benefit for BUNLDEP compared to serialized thread execution and state of the art WCET analysis.

The mission-critical nature of wireless networked sensing and control (WSC) systems, such as the control of industrial plants, requires stringent real-time delivery of packets. Due to inherent dynamics and uncertainties in wireless communication, real-time communication guarantees are probabilistic in nature. In this paper, a probabilistic framework is therefore proposed for per-packet real-time delivery guarantee. The notion of real-time in this paper differs from the existing work in the sense that it ensures, in an execution history of arbitrary length, every packet is successfully delivered before its deadline with a probability no less than a user-specified threshold (e.g., 99%). The framework has several novel building blocks: First, “R3 (requirement-reliability-resource) mapping” translates the upper layer probabilistic real-time communication requirement, and the lower layer links reliability into the resource (i.e., optimal number of transmission opportunities) reserved for each packet. Second, “EDF (earliest deadline first) based real-time scheduling” as well as the “admission test” and “traffic load optimization” maximize system utility while satisfying per-packet real-time communication requirements. The proposed admission test is proved to be both sufficient and necessary, and the simulation results show that the proposed framework ensures probabilistic per-packet real-time communication.

In "BUNDLE: Real-Time Multi-Threaded Scheduling to Reduce Cache Contention" Tessler and Fisher present a positive perspective of instruction caches for hard real-time multithreaded tasks. The thread-aware scheduling algorithm limits the execution of threads to sets of instructions that cannot result in cache conflicts. Identification of these sets result in conflict free regions which are used to identify scheduling groups called bundles in the BUNDLE scheduling algorithm. Placement of a thread in a particular bundle depends on, what the authors call, "anticipating execution". However, they do not define a complete mechanism to anticipate execution. In this work, we propose a method to anticipate execution that modifies cache hardware and introduces a new interrupt raised prior to a cache conflict. This new interrupt is combined with (a slightly modified version of) the BUNDLE scheduling algorithm. The intent is to implement these hardware modifications for ARM on the gem5 simulator with the scheduling algorithm integrated into the RTEMS operating system. The hope is this work serves as further motivation to bring the positive perspective of caches to physical processors and operating systems.

Short-circuit faults are a potential source of damage to circuitry in DC-powered systems. Industrial applications including power converters, inverters, and insulated-gate bipolar transistors (IGBTs) often rely on fault detection systems in the form of dedicated circuitry to prevent damage. To increase flexibility in short-circuit detection and decrease dedicated circuitry, a software-based approach is presented. This implementation requires minimal circuitry and allows for tradeoff between board space and processor utilization. The design relies on a single inductor and microprocessor running a real-time task for identifying current and monitoring circuitry for faults. Experiments demonstrate detection of both hard-switching faults (HSF) and fault under load (FUL) shorts. The depicted relationship between processor utilization and board space consumed by the circuitry is confirmed through experimentation and allows optimization of board space with respect to utilization and vice versa. As a result, the proposed software-based detection is implementable with the addition of a single component and protects against damage from both HSF and FUL shorts.

Summary form only given. Research on hard real-time systems and their models has predominately focused upon single-threaded tasks. When multithreaded tasks are introduced to the classical real-time model the individual threads are treated as distinct tasks, one for each thread. These artificial tasks share the deadline, period, and worst case execution time of their parent task. In the presence of instruction and data caches this model is overly pessimistic, failing to account for the execution time benefit of cache hits when multiple threads of execution share a memory address space. This work takes a new perspective on instruction caches. Treating the cache as a benefit to schedulability for a single task with m threads. To realize the “inter-thread cache benefit” a new scheduling algorithm and accompanying worst-case execution time (WCET) calculation method are proposed. The scheduling algorithm permits threads to execute across conflict free regions, and blocks those threads that would create an unnecessary cache conflict. The WCET bound is determined for the entire set of m threads, rather than treating each thread as a distinct task. Both the scheduler and WCET method rely on the calculation of conflict free regions which are found by a static analysis method that relies on no external information from the system designer. By virtue of this perspective the system's total execution execution time is reduced and is reflected in a tighter WCET bound compared to the techniques applied to the classical model. Obtaining this tighter bound requires the integration of three typically independent areas: WCET, schedulability, and cache-related preemption delay analysis.

The generalized multiframe task model (GMF) extends the sporadic task model and multiframe task model. Each frame in the GMF model contains an execution time, a relative deadline, and a minimum inter-arrival time. These parameters are fixed after task specification time in the GMF model. However, multimedia and adaptive control systems may be overloaded and no longer stabilized when the task parameters in such systems are not flexible. In order to address this problem, deadlines and periods may change to alleviate temporal overload, for example in the parameter adaption and elastic scheduling model. In this paper, we propose a new model GMF-PA (the GMF model with parameter adaption). This model allows task parameters to be flexible in arbitrary-deadline systems. A necessary schedulability test based on mixed-integer linear programming (MILP) is given to check the schedulability under EDF scheduling and optimally assign deadlines and periods at the same time. We also prove that the test is a sufficient and necessary schedulability test when task parameters must be integers. An approximation algorithm is also deployed to reduce computational running time. The speed-up factor of our approximation algorithm is 1+ϵ where ϵ can be arbitrarily small, with respect to the exact schedulability test of GMF-PA tasks under EDF. We also apply the GMF model to self-suspending tasks. By extending recent work on scheduling self-suspending tasks, we remove the assumption that deadlines are equally assigned in self-suspending tasks, and the system is extended from constrained-deadline systems to arbitrary-deadline systems. We have done exhaustive experiments to show that the schedulability ratio is improved using our techniques in our GMF-PA model.

Research on hard real-time systems and their models has predominately focused upon single-threaded tasks. When multi-threaded tasks are introduced to the classical real-time model the individual threads are treated as distinct tasks, one for each thread. These artificial tasks often share the deadline, period, and worst case execution time of their parent task. In the presence of instruction and data caches this view is overly pessimistic, failing to account for the execution time benefit of cache hits when multiple threads of execution share a memory address space.This work takes a new perspective on instruction caches. Treating the cache as a benefit to schedulability for a single task with m threads. To realize the "inter-thread cache benefit" a new scheduling algorithm, BUNDLE, and accompanying method for calculating the worst-case execution time (WCET) including cache overhead (WCET+O) method are proposed. BUNDLE permits threads to execute across conflict free regions, and blocks those threads that would create an unnecessary cache conflict. The WCET bound is determined for the entire set of m threads, rather than treating each thread as a distinct task. Both the scheduler and WCET+O method rely on the calculation of conflict free regions which are found by a static analysis method of the task object. By virtue of this perspective the system's total execution execution time is reduced and is reflected in a tighter WCET+O bound compared to the techniques applied to the classical model. Obtaining this tighter bound requires the integration of three typically independent areas: WCET, schedulability, and cache-related preemption delay analysis.

We consider a competitive environment for reward-based scheduling of periodic tasks, where the execution of each task consists of a mandatory and an optional part. Each task obtains a value if the processor successfully schedules all its mandatory part, and also an additional reward value if the processor successfully schedules a part of its optional execution. Each task is owned by a self-interested agent who has multiple choices for its requests based on its optional part. We model the reward-based scheduling problem by considering such multi-minded agents. However, the agent may try to manipulate the system to obtain an unfair optional allocation. We address this challenge by designing novel truthful mechanisms in which it is always in the agent's best interest to report their true task characteristics. We propose two truthful mechanisms (an exact and approximate) for selecting a feasible subset of agents and an allocation of optional execution that maximizes the total reward obtained by the selected tasks. To address the pseudo-polynomial complexity of the exact mechanism, we show that our proposed approximate mechanism is a polynomial-time approximation scheme (PTAS). Our extensive experiments show that our proposed approximation mechanism is capable of finding near-optimal solutions efficiently while guaranteeing truthfulness.

Schedulability analysis for real-time systems has been the subject of prominent research over the past several decades. One of the key foundations of schedulability analysis is an accurate worst case execution time (WCET) measurement for each task. In real-time systems that support preemption, the cache related preemption delay (CRPD) can represent a significant component (up to 44% as documented in research literature) [1] -- [3] of variability to overall task WCET. Several methods have been employed to calculate CRPD with significant levels of pessimism that may result in a task set erroneously declared as non-schedulable. Furthermore, they do not take into account that CRPD cost is inherently a function of where preemptions actually occur. Our approach for computing CRPD via loaded cache blocks (LCBs) is more accurate in the sense that cache state reflects which cache blocks and the specific program locations where they are reloaded. Limited preemption models attempt to minimize preemption overhead (CRPD) by reducing the number of allowed preemptions and/or allowing preemption at program locations where the CRPD effect is minimized. These algorithms rely heavily on accurate CRPD measurements or estimation models in order to identify an optimal set of preemption points. Our approach improves the effectiveness of limited optimal preemption point placement algorithms by calculating the LCBs for each pair of adjacent preemptions to more accurately model task WCET and maximize schedulability as compared to existing preemption point placement approaches. We propose an optimal preemption point placement algorithm using dynamic programming. Lastly, we will demonstrate, using a case study, improved task set schedulability and optimal preemption point placement via our new LCB characterization.

This paper investigates schedulability analysis for thermal-aware real-time systems. Thermal constraints are becoming more and more critical in new generation miniaturized embedded systems, e.g. Medicals implants. As part of this work, we adapt the PFPasapalgorithm proposed in [1] for energy-harvesting systems to thermal-aware ones. We prove its optimality for non-concrete1fixed-priority task sets and propose a response-time analysis based on worst-case response-time upper bounds. We evaluate the efficacy of the proposed bounds via extensive simulation over randomly-generated task systems.

The interaction of a cyber-physical system (CPS) may impose additional constraints upon cyber aspects of the system. For instance, sensing and actuation often require non-preemption to ensure “accuracy” in data acquisition (e.g., radar sensors in automotive a cruise control system). Furthermore, CPS may require that a system adapts to changing environment which requires support for multiple operating modes. A multimode CPS may also enable resource-efficient solution by providing shared processing platforms to subsystems. Recent development [1] of multi-modal fixed-priority schedulability with non-preemption can facilitate multi-modal CPS-based design. In this demo, we present the benefits of such design choices by devloping a simple automotive adaptive cruise control (ACC) system using System objectsTMand Phased Array System ToolboxTM, which provides state-of-the-art tools for radar simulation. The ACC application composes tasks for radar transmission, reception, and controller upon a single processing platform. We consider radar transmission and signal receiving tasks to have non-preemptible execution regions.

Over the years, multiple hardware and software operating modes have been employed in many computing devices (e.g., tablets, smart-phones, GPS receivers) to efficiently utilize device resources. Similar advantages are also preferred in realtime systems (RTS) due to the requirement that a RTS must respond in a timely manner to a physical environment that may change sporadically. An efficient multi-modal system (MMS) is also a prerequisite for the development of real-time control systems which can maintain stable system behavior while ensuring timing guarantees for a changing set of real-time tasks. However, the currently-available fixed-priority (FP) schedulability analysis for multi-modal systems with both software/hardware modes is computationally expensive. In addition, current schedulability analysis for systems that support mode changes requires an assumption that is often not suitable for cyber-physical systems (CPS): sensing and actuation in the underlying physical plant are preemptible activities. However, sensors such as radar transmitter/ receiver requires non-preemptible access to the processor upon sending and then processing the return signal for accuracy. In this research, we develop a framework for multi-modal RTS scheduled by FP algorithm along with efficient schedulability analysis with pseudo-polynomial complexity considering the advantages and limitations of specific software/hardware model. Two simulations: a case study on adaptive cruise control in automotive systems, and schedulability comparison are included to corroborate the performance of the schedulability analysis.

In the limited-preemption scheduling model, tasks cooperate to offer suitable preemption points for reducing the overall preemption overhead. In the fixed preemption-point model, tasks are allowed to preempt only at statically defined preemption points, reducing the variability of the preemption delay and making the system more predictable. Different works have been proposed to determine the optimal selection of preemption points for minimizing the preemption overhead without affecting the system schedulability due to increased non-preemptivity. However, all works are based on very restrictive task models, without being able to deal with common coding structures like branches, conditional statements and loops. In this work, we overcome this limitation, by proposing a pseudo-polynomial-time algorithm that is capable of determining the optimal set of preemption points to minimize the worst-case execution time of jobs represented by control flow graphs with arbitrarily-nested conditional structures, while preserving system schedulability. Exhaustive experiments are included to show that the proposed approach is able to significantly improve the bounds on the worst-case execution times of limited preemptive tasks.

In this work, we investigate the potential benefit of parallelization for both meeting real-time constraints and minimizing power consumption. We consider malleable Gang scheduling of implicit-deadline sporadic tasks upon multiprocessors. By extending schedulability criteria for malleable jobs to DPM/DVFS-enabled multiprocessor platforms, we are able to derive an offline polynomial-time optimal processor/frequency-selection algorithm. Simulations of our algorithm on randomly generated task systems executing on platforms having up to 16 processing cores show that the theoretical power consumption is reduced by a factor of 36 compared to the optimal non-parallel approach.

In a non-competitive environment, sporadic real-time task scheduling on a single processor is well understood. In this paper, we consider a competitive environment comprising several real-time tasks vying for execution upon a shared single processor. Each task obtains a value if the processor successfully schedules all its jobs. Our objective is to select a feasible subset of these tasks to maximize the sum of values of selected tasks. We consider both dynamic-priority and static-priority scheduling algorithms. There are algorithms for solving these problems in non-competitive settings. However, we consider these problems in an economic setting in which each task is owned by a selfish agent. Each agent reports the characteristics of her own task to the processor owner. The processor owner uses a mechanism to allocate the processor to a subset of agents and to determine the payment of each agent. Since agents are selfish, they may try to manipulate the mechanism to obtain the processor. We are interested in truthful mechanisms in which it is always in agents’ best interest to report the true characteristics of their tasks. We design exact and approximate truthful mechanisms for this competitive environment and study their performance.

Real-time multimedia subsystems often require support for switching between different resource and application execution modes. To ensure that timing constraints are not violated during or after a subsystem mode change, real-time schedulability analysis is required. However, existing time-efficient multimode schedulability analysis techniques for application-only mode changes are not appropriate for subsystems that require changes in the resource execution behavior (e.g., processors with dynamic power modes). Furthermore, all existing multimode schedulability analysis that handles both resource and application mode changes is highly exponential and not scalable for subsystems with a moderate or large number of modes. As a result, the notion of resource optimality is still unaddressed for real-time multimodal systems. In this report, we first address the lack of tractable schedulability analysis for such subsystems by proposing a model for characterizing multiple resource and application modes and by deriving a sufficient schedulability test that has pseudo-polynomial time complexity. Finally, we propose an algorithm which leverages this pseudo-polynomial schedulability analysis to optimize the resource usages (e.g., to minimize peak-power load) of a multimodal real-time system. Simulation results show that our proposed algorithms for schedulability analysis and resource allocation, when compared with previously-proposed approaches, require significantly less time and are just as precise.

Recent research in compositional real-time systems has focused on determination of a component's real-time interface parameters. An important objective in interface-parameter determination is minimizing the bandwidth allocated to each component of the system while simultaneously guaranteeing component schedulability. With this goal in mind, in this article, we explore fixed-priority schedulability in compositional setting. First we derive an efficient exact test based on iterative convergence for sporadic task systems scheduled by fixed-priority (e.g., deadline monotonic, rate monotonic) upon an explicit-deadline periodic (EDP) resource. Then we address the time complexity of the exact test by developing a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth to components. Our parametric algorithm takes the task system and an accuracy parameter ε > 0 as input and returns a bandwidth which is guaranteed to be at most a factor (1 + ε) times the optimal minimum bandwidth required to successfully schedule the task system. We perform thorough simulation over synthetically generated task systems to compare the performance of our proposed efficient-exact and the approximate algorithm and observe a significant decrease in runtime and a very small relative error when comparing the approximate algorithm with the exact algorithm and the sufficient algorithm.

We address the challenge of designing predictable real-time systems in an unpredictable thermal environment where environmental temperature may dynamically change (e.g., implantable medical devices). Towards this challenge, we propose a control-theoretic design methodology that permits a system designer to specify a set of hard real-time performance modes under which the system may operate. The system automatically adjusts the real-time performance mode based on the external thermal stress. We show (via analysis, simulations, and a hardware testbed implementation) that our control design framework is stable and control performance is equivalent to previous real-time thermal approaches, even under dynamic temperature changes. A crucial and novel advantage of our framework over previous real-time control is the ability to guarantee hard deadlines even under transitions between modes. Furthermore, our system design permits the calculation of a new metric called thermal resiliency that characterizes the maximum external thermal stress that any hard real-time performance mode can withstand. Thus, our design framework and analysis may be classified as a thermal stress analysis for real-time systems.

Multicore processor based system designs are increasingly utilized as the processing platform for complex hard-real-time and embedded applications. These real-time systems need to operate under various physical and design constraints. Much research has focused on thermal-aware real-time systems designs. However, no results exist to investigate the resource allocation and the system degradation under external thermal constraints in a predictable manner. This paper proposes a control-theoretic framework to ensure hard-real-time deadlines on a multiprocessor platform in a dynamic thermal environment. We use real-time performance modes to permit the system to adapt to changing conditions. Also, we show how the system designer can use our framework to allocate asymmetric processing resources upon a multicore CPU and still maintain thermal constraints. We develop analysis for determining what modes the system can support for a given external thermal condition. Our system design extends the derivation of thermal-resiliency (originally proposed for uniprocessor systems) to multicore systems and determines the limitations of external thermal stress that any hard-real-time performance mode can withstand. Simulations and physical test bed results show that our algorithm predicts how a system will gracefully and predictably degrade under external thermal stress.

In a non-competitive environment, sporadic real time task scheduling on a single processor is well understood. In this paper, we consider a competitive environment comprising several real-time tasks vying for execution upon a shared single processor. Each task obtains a value if the processor successfully schedules all its jobs. Our objective is to select a feasible subset of these tasks to maximize the sum of values of selected tasks. There are algorithms for solving this problem in non-competitive settings. However, we consider this problem in an economic setting in which each task is owned by a selfish agent. Each agent reports the characteristics of her own task to the processor owner. The processor owner uses a mechanism to allocate the processor to a subset of agents and to determine the payment of each agent. Since agents are selfish, they may try to manipulate the mechanism to obtain the processor. We are interested in truthful mechanisms in which it is always in agents' best interest to report the true characteristics of their tasks. We design exact and approximate truthful mechanisms for this competitive environment and study their performance.

We address the challenge of designing predictable real-time systems in an unpredictable thermal environment where environmental temperature may dynamically change (e.g., implantable medical devices). Towards this challenge, we propose a control-theoretic design methodology which permits a system designer to specify a set of hard-real-time performance modes under which the system may operate. The system automatically adjusts the real-time performance mode based on the external thermal stress. We show (via analysis, simulations, and a hardware testbed implementation) that our control-design framework is stable and control performance is equivalent to previous real-time thermal approaches, even under dynamic temperature changes. A crucial and novel advantage of our framework over previous real-time control is the ability to guarantee hard deadlines even under transitions between modes. Furthermore, our system design permits the calculation of a new metric called thermal resiliency which characterizes the maximum external thermal stress that any hard-real-time performance mode can withstand. Thus, our design framework and analysis may be classified as a thermal stress analysis for real-time systems.

Modern real-time embedded systems often require the capability of switching between operating modes to adapt in dynamically changing environments. The development of such real-time multi-modal systems fundamentally relies upon effective schedulability analysis. Recently, researchers have proposed serial schedulability analysis algorithms for multi-modal systems that account for mode changes at both software level (e.g., changing the set of executing tasks) and hardware level (e.g., changing the operating speed of a processor). However, these algorithms have high runtime complexity which limits their practical usage as schedulability analysis in system design-space exploration. In this paper, we design a parallel algorithm as an efficient solution to the problem of determining the schedulability of uniprocessor multi-modal real-time systems scheduled by EDF. By emphasizing a balanced workload distribution and restricting the number of synchronizations, our parallel algorithm achieves a near-perfect speedup observable both theoretically and experimentally. Experimental results show that the runtime of our parallel algorithm is very low even for systems with large number of modes, making it a tractable choice for design-space exploration of real-time multi-modal systems.

Schedulability for compositional real-time systems has been the focus of a great deal of recent research. In this problem domain, we consider the fixed-priority (FP) scheduling of arbitrary-deadline sporadic task systems upon periodic resources. Existing exact or approximate schedulability tests for dedicated uniprocessor scheduling can be used in this setting by modeling the "no-supply period" of the periodic resource model as a special highest priority task. However, the exact schedulability test is highly inefficient from computational perspective, and the straightforward approximate test is pessimistic due to the approximation on the resource unavailability along with the resource demand. In this paper, along with obtaining an exact characterization of schedulability for this setting, we address the need for efficient and effective schedulability results for the large and important class of arbitrary-deadline task systems by deriving a polynomial-time sufficient schedulability algorithm. By simulations, we show that this algorithm performs very well compared with the exact test, and even better than the approximate test.

Server-based resource reservation protocols (e.g., periodic and bandwidth-sharing servers) have the advantage of providing temporal isolation between subsystems co-executing upon a shared processing platform. For many of these protocols, temporal isolation is often obtained at the price of over-provisioned reservations. Other more fine-grained approaches such as real-time calculus permit a precise characterization of the resources required by a subsystem via demand-curve interfaces. However, an important, unsolved challenge for subsystems specified by such interfaces is the development of efficient enforcement techniques to guarantee temporal isolation between the subsystems. Admission control algorithms can be used in this regard to ensure that the cumulative subsystem demand never violates the demand-curve specified by the interface. In this paper, we address the challenge by designing admission controllers for complex, arbitrary demand-curve interfaces and proposing enforcement techniques. First, we propose an exact algorithm and show that its complexity is infeasible for long-running systems. To address this drawback, we then design an approximation algorithm and associated enforcement techniques to handle unpredictable execution times. We validate, via simulations, that our approximate approach is significantly more efficient than the exact approach with only minor decrease in the accuracy of the admission controller.

The Hierarchical Scheduling Framework (HSF) has been introduced as a design-time framework enabling compositional schedulability analysis of embedded software systems with real-time properties. However, supporting resource sharing in HSF is a major challenge, since it increases the amount of CPU resources required to guarantee schedulability of the hard real time tasks, and it decreases the composability at the system level. In this paper, we focus on a compositional framework called the bounded-delay resource open environment (BROE) server, and we identify key parameters of this framework that have a great effect on how the framework will utilize CPU resources. In addition, we show how to select optimal values for these parameters in order to reduce the required CPU resource.

Recent research in compositional real-time systems has focused on determination of a component's real-time interface parameters. An important objective in interface-parameter determination is minimizing the bandwidth allocated to each component of the system while simultaneously guaranteeing component schedulability. With this goal in mind, in this paper we develop a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth for sporadic task systems scheduled by fixed priority (e.g., deadline monotonic, rate monotonic) upon an Explicit-Deadline Periodic (EDP) resource. Our parametric algorithm takes the task system and an accuracy parameter ¿ > 0 as input, and returns a bandwidth which is guaranteed to be at most a factor 1 + ¿ times the optimal minimum bandwidth required to successfully schedule the task system. By simulations over synthetically generated task systems, we observe a significant decrease in runtime and a small relative error when comparing our proposed algorithm with the exact algorithm and the sufficient algorithm.

Allocation of bandwidth among components is a fundamental problem in compositional real-time systems. State-of-the-art algorithms for bandwidth allocation use either exponential-time or pseudo-polynomial-time techniques for exact allocation, or linear-time, utilization-based techniques which may over-provision bandwidth. In this paper, we develop a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth for sporadic task systems scheduled by earliest-deadline first (EDF) upon an Explicit- Deadline Periodic (EDP) resource. Our algorithm takes, as parameters, the task system and an accuracy parameter epsi > 0, and returns a bandwidth which is guaranteed to be at most a factor (1 + epsi) more than the optimal minimum bandwidth required to successfully schedule the task system. Furthermore, the algorithm has time complexity that is polynomial in the number of tasks and 1/e. Via simulations over randomly-generated task systems, we have observed a several orders of magnitude decrease in runtime and a small relative error when comparing our proposed algorithm with the exact algorithm, even for medium-sized values of epsi (e.g., epsi ap .3).

As the power density of modern electronic circuits increases dramatically, systems are prone to overheating. Thermal management has become a prominent issue in system design. This paper explores thermal-aware scheduling for sporadic real-time tasks to minimize the peak temperature in a homogeneous multicore system, in which heat might transfer among some cores. By deriving an ideally preferred speed for each core, we propose global scheduling algorithms which can exploit the flexibility of multicore platforms at low temperature. Compared with load-balancing strategies, the proposed algorithms can significantly reduce the peak temperature by up to 30degC to 70degC for simulated platforms.

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.

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).

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

Feasibility analysis algorithms are based on particular metrics such as processor utilization, load factor, processor demand, response-times, etc. The design of efficient algorithms for computing these metrics is a major issue in real-time scheduling theory. In this paper we propose two FPTASs (fully-polynomial time approximation schemes) for checking feasibility of static-priority tasks subjected to release jitters executed upon a uniprocessor platform. We then use these FPTASs for computing two upper bounds of worst-case response-times. Lastly, we show that these bounds do not achieve constant error bounds in comparison with values computed by an exact worst-case response-time analysis (performed in pseudo-polynomial time), and we present numerical experiments.

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 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

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.

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.

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