Fault-tolerant adaptive scheduling for embedded real-time systems

Describes a fault-tolerant algorithm which uses a time-value scheduling approach to detect faults, sustain high processor utilization, and ensure timely execution of critical tasks     

异构分布式实时系统的容错优化调度算法

针对分布式实时系统,在分析了单处理调度算法的基础上,结合版本复制技术和首次适应方法,给出了一种容错调度算法。分析了算法的可调度性,给出任务的可调度性条件。在满足任务容错可调度的情况下,以提高处理器的利用率为目标,对基版本时限进行了优化,给出了基版本优化时限的求取算法。仿真结果表明,本文算法将可以得到比FTEDFFF和FTRMFF更高的处理器利用率。     

An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

The current literature of fixed-priority scheduling algorithms relies on sufficient tests to determine if a set of mixed-criticality sporadic tasks is schedulable on a single processor. The drawback of these safe tests is their pessimism, a matter that could be solved if an exact schedulability analysis is used. However, because of the non-deterministic behavior of tasks in the mentioned setups, exact quantification of worst-case response times, needed for the test, is a difficult problem; more precisely, such a quantification needs evaluation of enormous sequences of job executions. The core problem is thus to merge such sequences to make the analysis practical. This paper, for the first time, gives an algorithm for exact worst-case response time characterization of mixed-criticality sporadic real-time tasks executing according to a given fixed-priority scheduler. We use a set of techniques which carefully consider the task properties and their relation to the worst scenarios to prune the analysis state space. We also show an interesting result that if an exact schedulability test is used, the Audsley’s optimal priority assignment algorithm is not applicable to the mixed-criticality case. Accordingly, we need new priority assignment algorithms to work with the exact test; we give a simple task priority assignment algorithm to this aim. The performance of the proposed exact test (in terms of time complexity) is examined and the effectiveness of some heuristic priority assignment algorithms using the test (in terms of the ratio of task sets which are deemed schedulable) are compared.     

Fault-tolerant rate-monotonic first-fit scheduling inhard-real-time systems

Hard-real-time systems require predictable performance despite the occurrence of failures. In this paper, fault tolerance is implemented by using a novel duplication technique where each task scheduled on a processor has either an active backup copy or a passive backup copy scheduled on a different processor. An active copy is always executed, while a passive copy is executed only in the case of a failure. First, the paper considers the ability of the widely-used rate-monotonic scheduling algorithm to meet the deadlines of periodic tasks in the presence of a processor failure. In particular, the completion time test is extended so as to check the schedulability on a single processor of a task set including backup copies. Then, the paper extends the well-known rate-monotonic first-fit assignment algorithm, where all the task copies, included the backup copies, are considered by rate-monotonic priority order and assigned to the first processor in which they fit. The proposed algorithm determines which tasks must use the active duplication and which can use the passive duplication. Passive duplication is preferred whenever possible, so as to overbook each processor with many passive copies whose primary copies are assigned to different processors. Moreover, the space allocated to active copies is reclaimed as soon as a failure is detected. Passive copy overbooking and active copy deallocation allow many passive copies to be scheduled sharing the same time intervals on the same processor, thus reducing the total number of processors needed. Simulation studies reveal a remarkable saving of processors with respect to those needed by the usual active duplication approach in which the schedule of the non-fault-tolerant case is duplicated on two sets of processors     

Commentary to: An exact schedulability test for fixed-priority preemptive mixed-criticality real-time systems

Real-Time Systems - In this paper we point to some errors in recent paper by Asyaban et al. in which they devise an exact schedulability test. These errors are critical for the correct operation of...     

Memory-centric scheduling for multicore hard real-time systems

Memory resources are a serious bottleneck in many real-time multicore systems. Previous work has shown that, in the worst case, execution time of memory intensive tasks can grow linearly with the number of cores in the system. To improve hard real-time utilization, a real-time multicore system should be scheduled according to a memory-centric scheduling approach if its workload is dominated by memory intensive tasks. In this work, a memory-centric scheduling technique is proposed where (a)?core isolation is provided through a coarse-grained (high-level) Time Division Multiple Access (TDMA) memory schedule; and (b)?the scheduling policy of each core ??promotes?? the priority of its memory intensive computations above CPU-only computation when memory access is permitted by the high-level schedule. Our evaluation reveals that under high memory demand, our scheduling approach can improve hard real-time task utilization significantly compared to traditional multicore scheduling.     

长释放时间间隔优先的混合任务调度算法

针对混合任务实时调度的需求和MUF算法的局限性,提出了一种长释放时间间隔优先的混合任务实时调度算法LRIF,该算法除了可对周期性硬实时任务提供调度保证外,同时还可确保非周期性软实时任务的可调度率。论文还提出了LRIF调度算法的可调度性分析方法,并讨论了LRIF调度算法的实现方法。     

QoC elastic scheduling for real-time control systems

The elastic task model, a significant development in scheduling of real-time control tasks, provides a mechanism for flexible workload management in uncertain environments. It tells how to adjust the control periods to fulfill the workload constraints. However, it is not directly linked to the quality-of-control (QoC) management, the ultimate goal of a control system. As a result, it does not tell how to make the best use of the system resources to maximize the QoC improvement. To fill in this gap, a new feedback scheduling framework, which we refer to as QoC elastic scheduling, is developed in this paper for real-time process control systems. It addresses the QoC directly through embedding both the QoC management and workload adaptation into a constrained optimization problem. The resulting solution for period adjustment is in a closed-form expressed in QoC measurements, enabling closed-loop feedback of the QoC to the task scheduler. Whenever the QoC elastic scheduler is activated, it improves the QoC the most while still meeting the system constraints. Examples are given to demonstrate the effectiveness of the QoC elastic scheduling.     

Fault-tolerant scheduling on parallel systems with non-memoryless failure distributions

As large parallel systems increase in size and complexity, failures are inevitable and exhibit complex space and time dynamics. Most often, in real systems, failure rates are increasing or decreasing over time. Considering non-memoryless failure distributions, we study a bi-objective scheduling problem of optimizing application makespan and reliability. In particular, we determine whether one can optimize both makespan and reliability simultaneously, or whether one metric must be degraded in order to improve the other. We also devise scheduling algorithms for achieving (approximately) optimal makespan or reliability. When failure rates decrease, we prove that makespan and reliability are opposing metrics. In contrast, when failure rates increase, we prove that one can optimize both makespan and reliability simultaneously. Moreover, we show that the largest processing time (LPT) list scheduling algorithm achieves good performance when processors are of uniform speed. The implications of our findings are the accelerated completion and improved reliability of parallel jobs executed across large distributed systems. Finally, we conduct simulations to investigate the impact of failures on the performance, which is done using an actual application of biological sequence comparison.     

On real-time scheduling policies for flexible manufacturing systems

The authors consider a model proposed by J.R. Perkins and P.R. Kumar (ibid., vol.34, no.2, pp. 139-148, Feb. 1989) for real-time control of flexible manufacturing systems. In this model, a machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. To process multiple part types, the machine uses a feedback rule to switch, from time to time, from one part type to another. Such switches incur a setup time of δ time units during which no parts are processed. By introducing the notion of idling, the authors derive a lower bound on the performance, as measured by average buffer size, of any stable feedback scheduling policy for a single machine     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

Implications of classical scheduling results for real-time systems

Knowledge of complexity, fundamental limits and performance bounds-well known for many scheduling problems-helps real time designers choose a good design and algorithm and avoid poor ones. The scheduling problem has so many dimensions that it has no accepted taxonomy. We divide scheduling theory between uniprocessor and multiprocessor results. In the uniprocessor section, we begin with independent tasks and then consider shared resources and overload. In the multiprocessor section, we divide the work between static and dynamic algorithms     

A pre-run-time scheduling algorithm for hard real-time systems

Process scheduling, an important issue in the design and maintenance of hard real-time systems, is discussed. A pre-run-time scheduling algorithm that addresses the problem of process sequencing is presented. The algorithm is designed for multiprocessor applications with preemptable processes having release times, computation times, deadlines and arbitrary precedence and exclusion constraints. The algorithm uses a branch-and-bound implicit enumeration technique to generate a feasible schedule for each processor. The set of feasible schedules ensures that the timing specifications of the processes are observed and that all the precedence and exclusion constraints between pairs of processes are satisfied. the algorithm was tested using a model derived from the F-18 mission computer operational flight program     

Utility accrual real-time scheduling for multiprocessor embedded systems

We present the first Utility Accrual (or UA) real-time scheduling algorithm for multiprocessors, called the global Multiprocessor Utility Accrual scheduling algorithm (or gMUA). The algorithm considers an application model where real-time activities are subject to time/utility function time constraints, variable execution time demands, and resource overloads where the total activity utilization demand exceeds the total capacity of all processors. We consider the scheduling objective of (1) probabilistically satisfying lower bounds on each activity’s maximum utility, and (2) maximizing the system-wide, total accrued utility. We establish several properties of gMUA including optimal total utility (for a special case), conditions under which individual activity utility lower bounds are satisfied, a lower bound on system-wide total accrued utility, and bounded sensitivity for assurances to variations in execution time demand estimates. Finally, our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness.     

Task scheduling in distributed real-time systems

An approach to the flow shop scheduling of the computation process in distributed realtime systems is considered. This approach is based on the concept of a solvable class of systems for which simple optimal scheduling algorithms exist.     

Value-based scheduling in real-time database systems

In a real-time database system, an application may assign avalue to a transaction to reflect the return it expects to receive if the transaction commits before its deadline. Most research on real-time database systems has focused on systems where all transactions are assigned the same value, the performance goal being to minimize the number of missed deadlines. When transactions are assigned different values, the goal of the system shifts to maximizing the sum of the values of those transactions that commit by their deadlines. Minimizing the number of missed deadlines becomes a secondary concern. In this article, we address the problem of establishing a priority ordering among transactions characterized by both values and deadlines that results in maximizing the realized value. Of particular interest is the tradeoff established between these values and deadlines in constructing the priority ordering. Using a detailed simulation model, we evaluate the performance of several priority mappings that make this tradeoff in different, but fixed, ways. In addition, a bucket priority mechanism that allows the relative importannce of values and deadlines to be controlled is introduced and studied. The notion of associating a penalty with transactions whose deadlines are not met is also briefly considered.When this work was done he was with the Computer Sciences Department, University of Wisconsin-Madison.     

An analysis of the non-preemptive mixed-criticality match-up scheduling problem

Many applications have a mixed-criticality nature. They contain tasks with a different criticality, meaning that a task with a lower criticality can be skipped if a task with a higher criticality needs more time to be executed. This paper deals with a mixed-criticality scheduling problem where each task has a criticality given by a positive integer number. The exact processing time of the task is not known. Instead, we use different upper bounds of the processing time for different criticality levels of the schedule. A schedule with different criticality levels is generated off-line, but its on-line execution switches among the criticality levels depending on the actual values of the processing times. The advantage is that after the transient prolongation of a higher criticality task, the system is able to match up with the schedule on a lower criticality level. While using this model, we achieve significant schedule efficiency (assuming that the prolongation of the higher criticality task rarely occurs), and at the same time, we are able to grant a sufficient amount of time to higher criticality tasks (in such cases, some of the lower criticality tasks may be skipped). This paper shows a motivation for the non-preemptive mixed-criticality match-up scheduling problem arising from the area of the communication protocols. Using a polynomial reduction from the 3-partition problem, we prove the problem to be \(\mathcal {NP}\)-hard in the strong sense even when the release dates and deadlines are dropped and only two criticality levels are considered.     

GA-based learning bias selection mechanism for real-time scheduling systems

The use of machine learning technologies in order to develop knowledge bases (KBs) for real-time scheduling (RTS) problems has produced encouraging results in recent researches. However, few researches focus on the manner of selecting proper learning biases in the early developing stage of the RTS system to enhance the generalization ability of the resulting KBs. The selected learning bias usually assumes a set of proper system features that are known in advance. Moreover, the machine learning algorithm for developing scheduling KBs is predetermined. The purpose of this study is to develop a genetic algorithm (GA)-based learning bias selection mechanism to determine an appropriate learning bias that includes the machine learning algorithm, feature subset, and learning parameters. Three machine learning algorithms are considered: the back propagation neural network (BPNN), C4.5 decision tree (DT) learning, and support vector machines (SVMs). The proposed GA-based learning bias selection mechanism can search the best machine learning algorithm and simultaneously determine the optimal subset of features and the learning parameters used to build the RTS system KBs. In terms of the accuracy of prediction of unseen data under various performance criteria, it also offers better generalization ability as compared to the case where the learning bias selection mechanism is not used. Furthermore, the proposed approach to build RTS system KBs can improve the system performance as compared to other classifier KBs under various performance criteria over a long period.     

Power-aware scheduling algorithms for sporadic tasks in real-time systems

In this paper, we consider the canonical sporadic task model with the system-wide energy management problem. Our solution uses a generalized power model, in which the static power and the dynamic power are considered. We present a static solution to schedule the sporadic task set, assuming worst-case execution time for each sporadic tasks release, and propose a dynamic solution to reclaim the slacks left by the earlier completion of tasks than their worst-case estimations. The experimental results show that the proposed static algorithm can reduce the energy consumption by 20.63%–89.70% over the EDF* algorithm and the dynamic algorithm consumes 2.06%–24.89% less energy than that of the existing DVS algorithm.