Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

Control latency for task assignment and scheduling of multiprocessor real-time control systems

For task assignment and scheduling problems of multiprocessor real-time control systems, a new performance index called the control latency, is proposed. In order to ensure smooth operation and good performance of real-time control systems, one must analyse the problem of combined task assignment and scheduling during the conceptual system design stage. The proposed performance index, the control latency, is defined as a weighted sum of feedback, command and monitoring latencies. Given a set of tasks for a specific control application, each task execution time and intra-/interprocessor communication latencies, an algorithm for combined task assignment and scheduling can be solved by minimizing this performance index, thereby providing the minimum time delay and best performance.     

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.     

Modelling heterogeneous processor scheduling for real-time systems

A new model is presented to describe data-flow algorithms implemented in a multiprocessing system. Called the resource/data flow graph (RDFG), the model explicitly represents cyclo-static processor schedules as circuits of processor arcs that reflect the order that processors execute graph nodes. The model also allows the guarantee of meeting hard real-time deadlines. When unfolded, the model identifies statistically the processor schedule. The model therefore is useful for determining the throughput and latency of systems with heterogeneous processors. The applicability of the model is demonstrated using a space surveillance algorithm.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

Schedulability issues for EDZL scheduling on real-time multiprocessor systems

EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3m/4=0.75m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m(1−1/e)≈0.6321m, where e≈2.718 is the Euler's number.     

A design fix to supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

In the article ‘Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks’, Park and Cho presented a systematic way of computing a largest fault-tolerant and schedulable language that provides information on whether the scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. The computation of such a language is mainly dependent on the task execution model presented in their paper. However, the task execution model is unable to capture the situation when the fault of a processor occurs even before the task has arrived. Consequently, a task execution model that does not capture this fact may possibly be assigned for execution on a faulty processor. This problem has been illustrated with an appropriate example. Then, the task execution model of Park and Cho has been modified to strengthen the requirement that none of the tasks are assigned for execution on a faulty processor.     

Global scheduling based reliability-aware power management for multiprocessor real-time systems

Reliability-aware power management (RAPM) has been a recent research focus due to the negative effects of the popular power management technique dynamic voltage and frequency scaling (DVFS) on system reliability. As a result, several RAPM schemes have been studied for uniprocessor real-time systems. In this paper, for a set of frame-based independent real-time tasks running on multiprocessor systems, we study global scheduling based RAPM (G-RAPM) schemes. Depending on how recovery blocks are scheduled and utilized, both individual-recovery and shared-recovery based G-RAPM schemes are investigated. An important dimension of the G-RAPM problem is how to select the appropriate subset of tasks for energy and reliability management (i.e., scale down their executions while ensuring that they can be recovered from transient faults). We show that making such decision optimally (i.e., the static G-RAPM problem) is NP-hard. Then, for the individual-recovery based approach, we study two efficient heuristics, which rely on local and global task selections, respectively. For the shared-recovery based approach, a linear search based scheme is proposed. The schemes are shown to guarantee the timing constraints. Moreover, to reclaim the dynamic slack generated at runtime from early completion of tasks and unused recoveries, we also propose online G-RAPM schemes which exploit the slack-sharing idea studied in previous work. The proposed schemes are evaluated through extensive simulations. The results show the effectiveness of the proposed schemes in yielding energy savings while simultaneously preserving system reliability and timing constraints. For the static version of the problem, the shared-recovery based scheme is shown to provide better energy savings compared to the individual-recovery based scheme, in virtue of its ability to leave more slack for DVFS. Moreover, by reclaiming the dynamic slack generated at runtime, online G-RAPM schemes are shown to yield better energy savings.     

An optimal boundary fair scheduling algorithm for multiprocessor real-time systems

With the emergence of multicore processors, the research on multiprocessor real-time scheduling has caught more researchers’ attention recently. Although the topic has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks with quantum-based computation requirements and implicit deadlines, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which can achieve full system utilization as the well-known Pfair scheduling algorithms. However, different from Pfair algorithms that make scheduling decisions and enforce proportional progress (i.e., fairness) for all tasks at each and every time unit, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries (i.e., deadlines of periodic tasks). The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved and its performance is evaluated through extensive simulations. The results show that, compared to that of Pfair algorithms, Bfair can significantly reduce the number of scheduling points (by up to 94%) and the overhead of Bfair at each scheduling point is comparable to that of the most efficient Pfair algorithm (i.e., PD²). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule can dramatically reduce the number of required context switches and task migrations (as much as 82% and 85%, respectively) when compared to those of Pfair schedules, which in turn reduces the run-time overhead of the system.     

An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems

Scheduling precedence constrained task graphs, with or without duplication, is one of the most challenging NP-complete problems in parallel and distributed computing systems. Duplication heuristics are more effective, in general, for fine grain task graphs and for networks with high communication latencies. However, most of the available duplication algorithms are designed under the assumption of unbounded availability of fully connected processors, and lie in a high complexity range. Low complexity optimal duplication algorithms work under restricted cost and/or shape parameters for the task graphs. Further, the required number of processors grows in proportion to the task-graph size significantly. An improved duplication strategy is proposed that works for arbitrary task graphs, with a limited number of interconnection-constrained processors. Unlike most other algorithms that replicate all possible parents/ancestors of a given task, the proposed algorithm tends to avoid redundant duplications and duplicates the nodes selectively, only if it helps in improving the performance. This results in lower duplications and also lower time and space complexity. Simulation results are presented for clique and an interconnection-constrained network topology with random and regular benchmark task graph suites, representing a variety of parallel numerical applications. Performance, in terms of normalized schedule length and efficiency, is compared with some of the well-known and recently proposed algorithms. The suggested algorithm turns out to be most efficient, as it generates better or comparable schedules with remarkably less processor consumption.     

Rolling-horizon scheduling for energy constrained distributed real-time embedded systems

Energy-efficient scheduling approaches are critical to battery driven real-time embedded systems. Traditional energy-aware scheduling schemes are mainly based on the individual task scheduling. Consequently, the scheduling space for each task is small, and the schedulability and energy saving are very limited, especially when the system is heavily loaded. To remedy this problem, we propose a novel rolling-horizon (RH) strategy that can be applied to any scheduling algorithm to improve schedulability. In addition, we develop a new energy-efficient adaptive scheduling algorithm (EASA) that can adaptively adjust supply voltages according to the system workload for energy efficiency. Both the RH strategy and EASA algorithm are combined to form our scheduling approach, RH-EASA. Experimental results show that in comparison with some typical traditional scheduling schemes, RH-EASA can achieve significant energy savings while meeting most task deadlines (namely, high schedulability) for distributed real-time embedded systems with dynamic workloads.     

Online adaptive utilization control for real-time embedded multiprocessor systems

Many embedded systems have stringent real-time constraints. An effective technique for meeting real-time constraints is to keep the processor utilization on each node at or below the schedulable utilization bound, even though each task’s actual execution time may have large uncertainties and deviate a lot from its estimated value. Recently, researchers have proposed solutions based on Model Predictive Control (MPC) for the utilization control problem. Although these approaches can handle a limited range of execution time estimation errors, the system may suffer performance deterioration or even become unstable with large estimation errors. In this paper, we present two online adaptive optimal control techniques, one is based on Recursive Least Squares (RLS) based model identification plus Linear Quadratic (LQ) optimal controller; the other one is based on Adaptive Critic Design (ACD). Simulation experiments demonstrate both the LQ optimal controller and ACD-based controller have better performance than the MPC-based controller and the ACD-based controller has the smallest aggregate tracking errors.     

A scalable scheduling scheme for functional parallelism ondistributed memory multiprocessor systems

We attempt a new variant of the scheduling problem by investigating the scalability of the schedule length with the required number of processors, by performing scheduling partially at compile time and partially at run time. Assuming infinite number of processors, the compile time schedule is found using a new concept of the threshold of a task that quantifies a trade-off between the schedule-length and the degree of parallelism. The schedule is found to minimize either the schedule length or the number of required processors and it satisfies: A feasibility condition which guarantees that the schedule delay of a task from its earliest start time is below the threshold, and an optimality condition which uses a merit function to decide the best task-processor match for a set of tasks competing for a given processor. At run time, the tasks are merged producing a schedule for a smaller number of available processors. This allows the program to be scaled down to the processors actually available at run time. Usefulness of this scheduling heuristic has been demonstrated by incorporating the scheduler in the compiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on iPSC/860     

Integrated dynamic scheduling of hard and QoS degradable real-time tasks in multiprocessor systems

Many time-critical applications require predictable performance and tasks in these applications have deadlines to be met. For tasks with hard deadlines, a deadline miss can be catastrophic while for Quality of Service (QoS) degradable tasks (soft real-time tasks) timely approximate results of poorer quality or occasional deadline misses are acceptable. Imprecise computation and (m,k)-firm guarantee are two workload models that quantify the trade-off between schedulability and result quality. In this paper, we propose dynamic scheduling algorithms for integrated scheduling of real-time tasks, represented by these workload models, in multiprocessor systems. The algorithms aim at improving the schedulability of tasks by exploiting the properties of these models in QoS degradation. We also show how the proposed algorithms can be adapted for integrated scheduling of multimedia streams and hard real-time tasks, and demonstrate their effectiveness in quantifying QoS degradation. Through simulation, we evaluate the performance of these algorithms using the metrics – success ratio (measure of schedulability) and quality. Our simulation results show that one of the proposed algorithms, multilevel degradation algorithm, outperforms the others in terms of both the performance metrics.     

Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems

This paper is an extended version of a paper that appeared in the proceedings of the IEEE Real-Time Systems Symposium 2009. This paper has been updated with respect to advances made in schedulability analysis, and contains a number of significant additional results.     

An adaptive scheme for fault-tolerant scheduling of soft real-time tasks in multiprocessor systems

The scheduling of real-time tasks with primary-backup-based fault-tolerant requirements has been an important problem for several years. Most of the known scheduling schemes are non-adaptive in nature meaning that they do not adapt to the dynamics of faults and task's parameters in the system. In this paper, we propose an adaptive fault-tolerant scheduling scheme that has a mechanism to control the overlap interval between the primary and backup versions of tasks such that the overall performance of the system is improved. The overlap interval is determined based on the observed fault rate and task's soft laxity. We also propose a new performance index, called SR index, that integrates schedulability (S) and reliability (R) into a single metric. To evaluate the proposed scheme, we have conducted analytical and simulation studies under different fault and deadline scenarios, and found that the proposed adaptive scheme adapts to system dynamics and offers better SR index than that of the non-adaptive schemes.     

Slack-based multiprocessor scheduling of aperiodic real-time tasks

We provide a constant time schedulability test and priority assignment algorithm for an on-line multiprocessor server handling aperiodic tasks. The so called Dhall’s effect is avoided by dividing tasks in two priority classes based on their utilization: heavy and light. The improvement in this paper is due to assigning priority of light tasks based on slack—not on deadlines. We prove that if the load on the multiprocessor stays below \((3 - \sqrt{5} )/2 \approx 38.197\%\), the server can accept an incoming aperiodic task and guarantee that the deadlines of all accepted tasks will be met. This is better than the current state-of-the-art algorithm where the priorities of light tasks are based on deadlines (the corresponding bound is in that case 35.425%).The bound \((3 - \sqrt{5} )/2\) can be improved if the number of processors m is known. There is a formula for the sharp bound \(U_{\mathit{threshold}}(m) = \frac{3m - 2 - \sqrt{5m^{2} - 8m + 4}}{2(m - 1)}\), which converges to \((3 - \sqrt{5} )/2\) from above as m→∞. For m≥3, the bound is higher (i.e., better) than the corresponding sharp bound for the state-of-the-art algorithm where the priorities of light tasks are based on deadlines.A simulation study also indicates that when m>3 the best effort behavior of the priority assignment scheme suggested here is better than that of the traditional scheme where priorities are based on deadlines.     

Globally scheduled real-time multiprocessor systems with GPUs

Graphics processing units, GPUs, are powerful processors that can offer significant performance advantages over traditional CPUs. The last decade has seen rapid advancement in GPU computational power and generality. Recent technologies make it possible to use GPUs as co-processors to CPUs. The performance advantages of GPUs can be great, often outperforming traditional CPUs by orders of magnitude. While the motivations for developing systems with GPUs are clear, little research in the real-time systems field has been done to integrate GPUs into real-time multiprocessor systems. We present two real-time analysis methods, addressing real-world platform constraints, for such an integration into a soft real-time multiprocessor system and show that a GPU can be exploited to achieve greater levels of total system performance.