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.     

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.     

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.     

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.     

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.     

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.     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

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     

Resource sharing among real-time components under multiprocessor clustered scheduling

In this paper we propose a general synchronization protocol for resource sharing among independently-developed real-time applications (components) on multi-core platforms. This protocol is a generalization of a previously proposed synchronization protocol (MSOS). In our proposed protocol, each component is statically allocated on a dedicated subset of processors (called cluster). A component has its own internal scheduler by which its tasks are scheduled. In this paper we focus on multiprocessor global fixed-priority preemptive scheduling algorithms to be used to schedule the tasks inside each component. Sharing the local resources is handled by the Priority Inheritance Protocol (PIP). For sharing the global resources (inter-component resource sharing) we have studied usage of FIFO and Round-Robin queues for access the resources across the components and usage of FIFO and prioritized queues inside the components. We have derived schedulability analysis for the different queue handling alternatives and compared their performance by using experimental evaluations. Finally, we have shown that the integration phase can be formulated in the form of a nonlinear integer programming problem where solution techniques in this domain can be used to minimize the total number of processors required to guarantee the schedulability of all components. As a proof of concept we have only provided the formulation for FIFO queues.     

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.     

Dynamic scheduling of hard real-time tasks and real-time threads

The authors investigate the dynamic scheduling of tasks with well-defined timing constraints. They present a dynamic uniprocessor scheduling algorithm with an O(n log n) worst-case complexity. The preemptive scheduling performed by the algorithm is shown to be of higher efficiency than that of other known algorithms. Furthermore, tasks may be related by precedence constraints, and they may have arbitrary deadlines and start times (which need not equal their arrival times). An experimental evaluation of the algorithm compares its average case behavior to the worst case. An analytic model used for explanation of the experimental results is validated with actual system measurements. The dynamic scheduling algorithm is the basis of a real-time multiprocessor operating system kernel developed in conjunction with this research. Specifically, this algorithm is used at the lowest, threads-based layer of the kernel whenever threads are created     

MDARTS: a multiprocessor database architecture for hard real-timesystems

Complex real time systems need databases to support concurrent data access and provide well defined interfaces between software modules. However, conventional database systems and prior real time database systems do not provide the performance or predictability needed by high speed, hard real time applications. The authors designed, implemented, and evaluated an object oriented database system called MDARTS (Multiprocessor Database Architecture for Real Time Systems). MDARTS avoids the client server overhead of most prior real time database systems and object oriented, real time systems by moving transaction execution into application tasks. By eliminating these sources of overhead and focusing on basic data management services for control systems (data sharing, serializable transactions, and multiprocessor support), the MDARTS prototype provides hard real time transaction times approximately three orders of magnitude faster than prior real time database systems. MDARTS ensures bounded locking delay by disabling preemption when a transaction is waiting for a lock, and hence, allows for the estimation of worst case transaction execution times. Another contribution of MDARTS is that it supports explicit declarations of real time requirements and semantic constraints within application code. The MDARTS library examines these declarations at application initialization time and attempts to construct objects that are compatible with the requirements. Besides local shared memory transactions with hard real time response time guarantees, MDARTS also supports remote transactions that use remote procedure calls for data access with less stringent timing constraints. The MDARTS prototype is implemented in C++ and it runs on VME based multiprocessors and Sun workstations     

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.     

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.     

A static scheduling algorithm for distributed hard real-time systems

A static scheduling algorithm is presented for off-line scheduling of tasks in distributed hard real-time systems. The tasks considered are instances of periodic jobs and have deadlines, resource requirements and precedence constraints. Tasks are divided into nonpreemptable blocks and all task characteristics are known a priori. The algorithm orders the tasks and iteratively schedules the tasks according to the order. Each task is scheduled globally by selecting a node to which it is assigned. Then, the task is scheduled locally by adding the task to the schedule of the selected node. Heuristics are used for both task ordering and node selection in order to guide the algorithm to a feasible schedule. Whenever local scheduling leads to an infeasible schedule, backtracking is used.Results of simulation studies of randomly generated task sets are presented. Although the scheduling problem is NP-hard, the results show that time performance is acceptable for off-line scheduling, except for extremely difficult task sets which make extensive use of the available resources.     

An improved hard real-time scheduling for the IEEE 802.5

In Responsive, Deterministic IEEE 802.5 Token Ring Scheduling Strosnider and Marchok propose a method to configure an IEEE 802.5 Token Ring so that a set of hard real-time messages meet their deadlines. In this paper, we indicate two corrections that must be made to the formulae proposed by the authors and draw the attention of the reader on two problems that must be solved when implementing Strosnider's solution.     

Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

Optimal online scheduling algorithms are known for sporadic task systems scheduled upon a single processor. Additionally, optimal online scheduling algorithms are also known for restricted subclasses of sporadic task systems upon an identical multiprocessor platform. The research reported in this article addresses the question of existence of optimal online multiprocessor scheduling algorithms for general sporadic task systems. Our main result is a proof of the impossibility of optimal online scheduling for sporadic task systems upon a system comprised of two or more processors. The result is shown by finding a sporadic task system that is feasible on a multiprocessor platform that cannot be correctly scheduled by any possible online, deterministic scheduling algorithm. Since the sporadic task model is a subclass of many more general real-time task models, the nonexistence of optimal scheduling algorithms for the sporadic task systems implies nonexistence for any model which generalizes the sporadic task model.     

Preemptive LCFS scheduling in hard real-time applications

We investigate the real-time behaviour of a (discrete time) single server system with preemptive LCFS task scheduling. The main result deals with the probability distribution of a random variable SRD(T), which describes the time the system operates without violating a fixed task service time deadline T. The tree approach, used for the derivation of our results, is also suitable for revisiting problems in queueing theory.

Relying on a simple general probability model, asymptotic formulas concerning all moments of SRD(T) are determined; for instance, the expectation of SRD(T) is proved to grow exponentially in T, i.e., E[SRD(T)]C^TT^3/2 for some > 1.