Dynamic priority scheduling of periodic and aperiodic tasks in hard real-time systems

This paper addresses the problem of scheduling aperiodic tasks in real-time systems. The proposed scheme combines the Earliest-Deadline-First algorithm for scheduling periodic tasks with the Deferrable Server approach for servicing aperiodic tasks. Necessary and sufficient conditions are derived for guaranteeing feasibility of a given periodic task set when a deferrable server is present. An analytic model is proposed for selecting the best feasible period and computation time of the server to minimize the mean response time of aperiodic tasks. An evaluation of the proposed model using a simulator indicates that the server parameters selected by the model result in mean response times that are close to the best mean response time determined by the simulator.     

Scheduling aperiodic tasks in dynamic priority systems

In this paper we present five new on-line algorithms for servicing soft aperiodic requests in realtime systems, where a set of hard periodic tasks is scheduled using the Earliest Deadline First (EDF) algorithm. All the proposed solutions can achieve full processor utilization and enhance aperiodic responsiveness, still guaranteeing the execution of the periodic tasks. Operation of the algorithms, performance, schedulability analysis, and implementation complexity are discussed and compared with classical alternative solutions, such as background and polling service. Extensive simulations show that algorithms with contained run-time overhead present nearly optimal responsiveness.A valuable contribution of this work is to provide the real-time system designer with a wide range of practical solutions which allow to balance efficiency against implementation complexity.     

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.     

End-to-end deadline control for aperiodic tasks in distributed real-time systems

A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving the system throughput.

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

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.     

Improving responsiveness of soft aperiodic tasks using proportional slack time

In a real-time system with both hard real-time periodic jobs and soft real-time aperiodic jobs, it is important to guarantee that the deadline of each periodic job is met, as well as to provide a fast response time for each aperiodic job. We propose an algorithm, called Proportional Slack Reserve (PSR), that produces an efficient schedule for such an environment. For every execution unit of a periodic job, the PSR algorithm reserves time which can be used for execution of aperiodic jobs. If reserved time is not available, the algorithm assigns a deadline to an aperiodic job for achieving better responsiveness of aperiodic jobs. The proposed algorithm can fully utilize processing power while meeting all deadlines of periodic jobs. It can also easily reclaim the time unused by the periodic job. We analytically show that for each aperiodic job, the response time in a PSR schedule is no longer than that in a TBS schedule, which is known to be efficient for servicing aperiodic jobs. We also present simulation results in which the response time of PSR is significantly improved over that of TBS, and moreover the performance of PSR compares favorably with TB(N) considering scheduling overhead.     

Fault-tolerance through scheduling of aperiodic tasks in hardreal-time multiprocessor systems

Real time systems are being increasingly used in several applications which are time critical in nature. Fault tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. We study a scheme that provides fault tolerance through scheduling in real time multiprocessor systems. We schedule multiple copies of dynamic, aperiodic, nonpreemptive tasks in the system, and use two techniques that we call deallocation and overloading to achieve high acceptance ratio (percentage of arriving tasks scheduled by the system). The paper compares the performance of our scheme with that of other fault tolerant scheduling schemes, and determines how much each of deallocation and overloading affects the acceptance ratio of tasks. The paper also provides a technique that can help real time system designers determine the number of processors required to provide fault tolerance in dynamic systems. Lastly, a formal model is developed for the analysis of systems with uniform tasks     

Robust learning control for a class of nonlinear systems with periodic and aperiodic uncertainties

This paper addresses the robust learning control problem for a class of nonlinear systems with structured periodic and unstructured aperiodic uncertainties. A recursive technique is proposed which extends the backstepping idea to the robust repetitive learning control systems. A learning evaluation function instead of a Lyapunov function is formulated as a guideline for derivation of the control strategy which guarantees the asymptotic stability of the tracking system. A design example is given.     

Allocation and scheduling of precedence-related periodic tasks

This paper discusses a static algorithm for allocating and scheduling components of periodic tasks across sites in distributed systems. Besides dealing with the periodicity constraints, (which have been the sole concern of many previous algorithms), this algorithm handles precedence, communication, as well as replication requirements of subtasks of the tasks. The algorithm determines the allocation of subtasks of periodic tasks to sites, the scheduled start times of subtasks allocated to a site, and the schedule for communication along the communication channel(s). Simulation results show that the heuristics and search techniques incorporated in the algorithm are very effective     

A new algorithm for scheduling periodic,real-time tasks

Algorithmica - We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called...     

A new algorithm for scheduling periodic, real-time tasks

We consider the problem of preemptively scheduling a set of periodic, real-time tasks on a multiprocessor computer system. We give a new scheduling algorithm, the so-called Slack-Time Algorithm, and show that it is more effective than the known Deadline Algorithm. We also give an (exponential-time) algorithm to decide if a task system is schedulable by the Slack-Time or the Deadline Algorithm. The same algorithm can also be used to decide if a task system is schedulable by any given fixed-priority scheduling algorithm. This resolves an open question posed by Leung and Whitehead. Finally, it is shown that the problem of deciding if a task system is schedulable by the Slack-Time, the Deadline, or any given fixed-priority scheduling algorithm is co-NP-hard for each fixedm.     

Neighboring optimal control for periodic tasks for systems with discontinuous dynamics

We propose a trajectory-based optimal control method for periodic tasks for systems with discontinuous dynamics. A general method, dynamic programming, suffers from the problem of dimensionality. We use local models of the optimal control law to construct a local controller. We combine a parametric trajectory optimization method and differential dynamic programming (DDP) to find the optimal periodic trajectory in a periodic task. By formulating the optimal control problem with an infinite time horizon, DDP ...     

A new fair scheduling algorithm for periodic tasks on multiprocessors

We present a new scheduling algorithm, called PL that is work-conserving and in terms of schedulability, optimal on multiprocessors for a synchronous periodic task set. The PL algorithm is a laxity based algorithm and ensures execution of a task with approximate proportional fairness at each task's period. Existing optimal algorithms on multiprocessors may cause excessive scheduling decisions and preemptions or may not be applied in a discrete environment. The proposed algorithm can be applied in a discrete environment and reduce the number of scheduling decisions and preemptions compared with a Pfair algorithm.     

Exact scheduling analysis of non-accumulatively monotonic multiframe tasks

In this paper, we present exact analysis for the worst case response time of the general multiframe (MF) task model executing on a uniprocessor according to the fixed priority scheduling scheme. The analysis is developed in four stages. Firstly, we present the basic response time analysis where we optimize the number of frames that have to be considered in such analysis; we show how their number can be significantly reduced by eliminating non critical frames that are dominated by other frames. Secondly, we extend this analysis to be applicable to MF tasks with arbitrary deadlines. Thirdly, the basic analysis is extended to cope with frame specific deadlines. Lastly, the two models of frame specific deadlines and arbitrary deadlines are combined and the relative analysis is presented. An optimal priority assignment scheme for the frame specific deadline scenario is also presented in this paper.     

Exact maximum likelihood estimation for non-stationary periodic time series models

Time series models with parameter values that depend on the seasonal index are commonly referred to as periodic models. Periodic formulations for two classes of time series models are considered: seasonal autoregressive integrated moving average and unobserved components models. Convenient state space representations of the periodic models are proposed to facilitate model identification, specification and exact maximum likelihood estimation of the periodic parameters. These formulations do not require a priori (seasonal) differencing of the time series. The time-varying state space representation is an attractive alternative to the time-invariant vector representation of periodic models which typically leads to a high dimensional state vector in monthly periodic time series models. A key development is our method for computing the variance-covariance matrix of the initial set of observations which is required for exact maximum likelihood estimation. The two classes of periodic models are illustrated for a monthly postwar US unemployment time series.     

Approximation algorithm for periodic real-time tasks with workload-dependent running-time functions

This paper addresses the problem of resource allocation for distributed real-time periodic tasks, operating in environments that undergo unpredictable changes and that defy the specification of meaningful worst-case execution times. These tasks are supplied by input data originating from various environmental workload sources. Rather than using worst-case execution times (WCETs) to describe the CPU usage of the tasks, we assume here that execution profiles are given to describe the running time of the tasks in terms of the size of the input data of each workload source. The objective of resource allocation is to produce an initial allocation that is robust against fluctuations in the environmental parameters. We try to maximize the input size (workload) that can be handled by the system, and hence to delay possible (costly) reallocations as long as possible. We present an approximation algorithm based on first-fit and binary search that we call FFBS. As we show here, the first-fit algorithm produces solutions that are often close to optimal. In particular, we show analytically that FFBS is guaranteed to produce a solution that is at least 41% of optimal, asymptotically, under certain reasonable restrictions on the running times of tasks in the system. Moreover, we show that if at most 12% of the system utilization is consumed by input independent tasks (e.g., constant time tasks), then FFBS is guaranteed to produce a solution that is at least 33% of optimal, asymptotically. Moreover, we present simulations to compare FFBS approximation algorithm with a set of standard (local search) heuristics such as hill-climbing, simulated annealing, and random search. The results suggest that FFBS, in combination with other local improvement strategies, may be a reasonable approach for resource allocation in dynamic real-time systems. David Juedes is a tenured associate professor and assistant chair for computer science in the School of Electrical Engineering and Computer Science at Ohio University. Dr. Juedes received his Ph.D. in Computer Science from Iowa State University in 1994, and his main research interests are algorithm design and analysis, the theory of computation, algorithms for real-time systems, and bioinformatics. Dr. Juedes has published numerous conference and journal papers and has acted as a referee for IEEE Transactions on Computers, Algorithmica, SIAM Journal on Computing, Theoretical Computer Science, Information and Computation, Information Processing Letters, and other conferences and journals. Dazhang Gu is a software architect and researcher at Pegasus Technologies (NeuCo), Inc. He received his Ph.D. in Electrical Engineering and Computer Science from Ohio University in 2005. His main research interests are real-time systems, distributed systems, and resource optimization. He has published conference and journal papers on these subjects and has refereed for the Journal of Real-Time Systems, IEEE Transactions on Computers, and IEEE Transactions on Parallel and Distributed Systems among others. He also served as a session chair and publications chair for several conferences. Frank Drews is an Assistant Professor of Electical Engineering and Computer Science at Ohio Unversity. Dr. Drews received his Ph.D. in Computer Science from the Clausthal Unversity of Technolgy in Germany in 2002. His main research interests are resource management for operating systems and real-time systems, and bioinformatics. Dr. Drews has numerous publications in conferences and journals and has served as a reviewer for IEEE Transactions on Computers, the Journal of Systems and Software, and other conferences and Journals. He was Publication Chair for the OCCBIO’06 conference, Guest Editor of a Special Issue of the Journal of Systems and Software on “Dynamic Resource Management for Distributed Real-Time Systems”, organizer of special tracks at the IEEE IPDPS WPDRTS workshops in 2005 and 2006. Klaus Ecker received his Ph.D. in Theoretical Physics from the University of Graz, Austria, and his Dr. habil. in Computer Science from the University of Bonn. Since 1978 he is professor in the Department of Computer Science at the Clausthal University of Technology, Germany, and since 2005 he is visiting professor at the Ohio University. His research interests are parallel processing and theory of scheduling, especially in real time systems, and bioinformatics. Prof. Ecker published widely in the above mentioned areas in well reputed journals and proceedings of international conferences as well. He is also the author of two monographs on scheduling theory. Since 1981 he is organizing annually international workshops on parallel processing. He is associate editor of Real Time Systems, and member of the German Gesellschaft fuer Informatik (GI) and of the Association for Computing Machinery (ACM). Lonnie R. Welch received a Ph.D. in Computer and Information Science from the Ohio State University. Currently, he is the Stuckey Professor of Electrical Engineering and Computer Science at Ohio University. Dr. Welch performs research in the areas of real-time systems, distributed computing and bioinformatics. His research has been sponsored by the Defense Advanced Research Projects Agency, the Navy, NASA, the National Science Foundation and the Army. Dr. Welch has twenty years of research experience in the area of high performance computing. In his graduate work at Ohio State University, he developed a high performance 3-D graphics rendering algorithm, and he invented a parallel virtual machine for object-oriented software. For the past 15 years his research has focused on middleware and optimization algorithms for high performance computing. His research has produced three successive generations of adaptive resource management (RM) middleware for high performance real-time systems. The project has resulted in two patents and more than 150 publications. Professor Welch also collaborates on diabetes research with faculty at Edison Biotechnology Institute and on genomics research with faculty in the Department of Environmental and Plant Biology at Ohio University. Dr. Welch is a member of the editorial boards of IEEE Transactions on Computers, The Journal of Scalable Computing: Practice and Experience, and The International Journal of Computers and Applications. He is also the founder of the International Workshop on Parallel and Distributed Real-time Systems and of the Ohio Collaborative Conference on Bioinformatics. Silke Schomann graduated in 2003 with a M.Sc. in Computer Science from Clausthal University Of Technology, where she has been working as a scientific assistant since then. She is currently working on her Ph.D. thesis in computer science at the same university.     

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.     

Allocating fixed-priority periodic tasks on multiprocessor systems

In this paper, we study the problem of allocating a set of periodic tasks on a multiprocessor system such that tasks are scheduled to meet their deadlines on individual processors by the Rate-Monotonic scheduling algorithm. A new schedulability condition is developed for the Rate-Monotonic scheduling that allows us to develop more efficient on-line allocation algorithms. Two on-line allocation algorithms—RM-FF and RM-BF are presented, and shown that their worst-case performance, over the optimal allocation, is upper bounded by 2.33 and lower bounded by 2.28. Then RM-FF and RM-BF are further improved to form two new algorithms: Refined-RM-FF (RRM-FF) and Refined-RM-BF (RRM-BF), both of which have a worst-case performance bound of 2. We also show that when the maximum allowable utilization of a task is small, the worst-case performance of all the new algorithms can be significantly improved. The worst-case performance bounds of RRM-FF and RRM-BF are currently the best bounds in the class of on-line scheduling algorithms proposed to solve the same scheduling problem. Simulation studies show that the average-case performance of the newly proposed algorithms is significantly superior to those in the existing literature.