The weakly hard real-time system model is used for describing the real-time systems that allow occasional violations of real-time timing constraints. These systems include real-time control systems, ...multimedia systems, and communication systems. In some approaches that deal with mitigating the system overload in real-time systems with periodic tasks, namely job-skipping algorithms, the constraints defined by the weakly hard real-time model are used as a mechanism for defining the pattern of task instances (jobs) that may be skipped in order to reduce the system load. The performance of these algorithms is usually evaluated with respect to the quality of service metric, which depends on the number of skipped jobs. In this work, we investigate the possibility of using genetic programming in the automated synthesis of scheduling heuristics for optimizing skipping patterns in order to increase the average quality of service in comparison with the conventional job-skipping algorithms. Using genetic programming to automatically synthesize heuristics allows for an easy and quick design of novel heuristics for various problem types and optimization criteria. We present two different approaches for implementing the proposed method. The first approach is to encapsulate the evolved heuristics into job-skipping algorithms known from the literature, namely Red Tasks as Late as Possible (RLP) and Blue When Possible (BWP). The idea of the second approach is to employ the evolved heuristics as standalone job-skipping algorithms. The results show an improvement of up to 15% in comparison with the state-of-the-art algorithms. The novel methods described in this work present a significant upgrade of the standard job-skipping algorithms as they provide a notable improvement in terms of quality of service while ensuring the fulfillment of weakly hard constraints. Moreover, the presented methods are computationally efficient and are therefore suitable for implementation on real-time operating systems, which is not the case with similar methods based on optimization techniques.
•Existing scheduling algorithms can be improved by introducing best-effort techniques.•Novel best-effort techniques based on genetic programming can improve the QoS by 15%.•The developed techniques guarantee the fulfillment of weakly hard constraints.•The presented approach is suitable for implementation in real-time kernels.
The concept of weakly hard real-time systems can be used to model real-time systems that may tolerate occasional deadline misses in a bounded and predictable manner. This model applies to many ...practical applications and is particularly interesting in the context of real-time control systems. In practice, applying hard real-time constraints may be too rigid since a certain amount of deadline misses is acceptable in some applications. In order to maintain system stability, limitations on the amount and distribution of violated deadlines need to be imposed. These limitations can be formally expressed as weakly hard real-time constraints. Current research in the field of weakly hard real-time task scheduling is focused on designing scheduling algorithms that guarantee the fulfillment of constraints, while aiming to maximize the total number of timely completed task instances. This paper provides an extensive literature review of the work related to the weakly hard real-time system model and its link to the field of control systems design. The weakly hard real-time system model and the corresponding scheduling problem are described. Furthermore, an overview of system models derived from the generalized weakly hard real-time system model is provided, with an emphasis on models that apply to real-time control systems. The state-of-the-art algorithms for scheduling tasks with weakly hard real-time constraints are described and compared. Finally, an overview of controller design methods that rely on the weakly hard real-time model is given.
Weakly hard real-time systems can, to some degree, tolerate deadline misses, but their schedulability still needs to be analyzed to ensure their quality of service. Such analysis usually occurs at ...early design stages to provide implementation guidelines to engineers so they can make better design decisions. Estimating worst-case execution times (WCET) is a key input to schedulability analysis. However, early on during system design, estimating WCET values is challenging, and engineers usually determine them as plausible ranges based on their domain knowledge. Our approach aims at finding restricted, safe WCET sub-ranges given a set of ranges initially estimated by experts in the context of weakly hard real-time systems. To this end, we leverage (1) multi-objective search aiming at maximizing the violation of weakly hard constraints to find worst-case scheduling scenarios and (2) polynomial logistic regression to infer safe WCET ranges with a probabilistic interpretation. We evaluated our approach by applying it to an industrial system in the satellite domain and several realistic synthetic systems. The results indicate that our approach significantly outperforms a baseline relying on random search without learning and estimates safe WCET ranges with a high degree of confidence in practical time (< 23 h).
The hard deadline model is very popular in real-time research, but is representative or applicable to a small number of systems. Many applications, including control systems, are capable of ...tolerating occasional deadline misses, but are seriously compromised by a repeating pattern of late terminations. The weakly hard real-time model tries to capture these requirements by analyzing the conditions that guarantee that a maximum number of deadlines can be possibly missed in any set of consecutive activations. We provide a new weakly hard schedulability analysis method that applies to constrained-deadline periodic real-time systems scheduled with fixed priority and without knowledge of the task activation offsets. The analysis is based on a Mixed Integer Linear Programming (MILP) problem formulation; it is very general and can be adapted to include the consideration of resource sharing and activation jitter. A set of experiments conducted on an automotive engine control application and randomly generated tasksets show the applicability and accuracy of the proposed technique.
The weakly hard real-time model is an abstraction for applications, including control systems, that can tolerate occasional deadline misses, but can also be compromised if a sufficiently high number ...of late terminations occur in a given time window. The weakly hard model allows us to constrain the maximum number of acceptable missed deadlines in any set of consecutive task executions. A big challenge for weakly hard systems is to provide a
schedulability analysis
that applies to a general task model, while avoiding excessive pessimism. In this work, we develop a general weakly hard analysis based on a Mixed Integer Linear Programming (MILP) formulation. The analysis applies to constrained-deadline periodic real-time systems scheduled with fixed priority and no knowledge of the task activation offsets, while allowing for activation jitter. Our analysis considers two common policies for handling missed deadlines, i.e., (i) letting the job continue until completion or (ii) killing its execution immediately. For this policy, ours is the first and only m-k analysis currently available. Experiments conducted on randomly generated task sets show the applicability and accuracy of the proposed technique as well as the improvements with respect to competing techniques.
Increasing integrated circuit (IC) power densities and temperatures may hamper multiprocessor system-on-chip (MPSoC) use in hard real-time systems. This paper formalizes the temperature-aware ...real-time MPSoC assignment and scheduling problem and presents an optimal phased steady-state mixed integer linear programming-based solution that considers the impact of scheduling and assignment decisions on MPSoC thermal profiles to directly minimize the chip peak temperature. We also introduce a flexible heuristic framework for task assignment and scheduling that permits system designers to trade off accuracy for running time when solving large problem instances. Finally, for task sets with sufficient slack, we show that inserting idle times between task executions can further reduce the peak temperature of the MPSoC quite significantly.
Distributed embedded systems (DESs) that perform critical tasks in unpredictable environments must be reliable, hard real-time, and adaptive. Since a DES comprises nodes that rely on a network, the ...network must provide adequate support: it must be reliable, convey messages on time, and meet new real-time requirements as the nodes adapt. Ethernet is ill-suited for such hard real-time adaptive systems, but it can be made suitable. The flexible time-triggered (FTT) paradigm already supports hard real-time message exchanges and the necessary flexibility to meet evolving hard real-time requirements, but its Ethernet implementations had reliability limitations. To address these, we designed FTT replicated star for Ethernet (FTTRS), a communication subsystem that tolerates permanent and transient faults, even if they occur simultaneously, while keeping the paradigm's key features: support for both the timely exchange of periodic and sporadic real-time messages, and support for updating the real-time parameters of these messages at runtime. In this paper, we present FTTRS, the first Ethernet-based communication subsystem specifically designed for highly reliable hard real-time adaptive DESs.
The current trend in modeling and analyzing real-time systems is toward tighter yet safe timing constraints. Many practical real-time systems can de facto sustain a bounded number of deadline-misses, ...i.e., they have Weakly-Hard Real-Time (WHRT) constraints rather than hard real-time constraints. Therefore, we strive to provide tight Deadline Miss Models (DMMs) in complement to tight response time bounds for such systems. In this work, we bound the distribution of deadline-misses for task sets running on uniprocessors using the Earliest Deadline First (EDF) scheduling policy. We assume tasks miss their deadlines due to transient overload resulting from sporadic jobs, e.g., interrupt service routines. We use Typical Worst-Case Analysis (TWCA) to tackle the problem in this context. Also, we address the sources of pessimism in computing DMMs, and we discuss the limitations of the proposed analysis. This work is motivated by and validated on a realistic case study inspired by industrial practice (satellite on-board software) and on a set of synthetic test cases. The synthetic experiment is dedicated to extensively study the impact of EDF on DMMs by presenting a comparison between DMMs computed under EDF and Rate Monotonic (RM). The results show the usefulness of this approach for temporarily overloaded systems when EDF scheduling is considered. They also show that EDF is especially useful for WHRT tasks.
Hard real-time systems must obey strict timing constraints. Therefore, one needs to derive guarantees on the worst-case execution times of a system’s tasks. In this context, predictable behavior of ...system components is crucial for the derivation of tight and thus useful bounds. This paper presents results about the predictability of common cache replacement policies. To this end, we introduce three metrics, evict, fill, and mls that capture aspects of cache-state predictability. A thorough analysis of the LRU, FIFO, MRU, and PLRU policies yields the respective values under these metrics. To the best of our knowledge, this work presents the first quantitative, analytical results for the predictability of replacement policies. Our results support empirical evidence in static cache analysis.
PDF
