In this paper we study the performance of off-line multiprocessor real-time schedules that allow task migration compared to those that forbid migration. We consider an off-line scheduling problem in which a given collection of tasks, each with a release time, computation time, and deadline, are to be run on a multiprocessor system. A preemptive schedule allows the execution of a task to be temporarily suspended and resumed at a later time. A migrative schedule allows the task to resume on any processor whereas a nonmigrative schedule allows the task to resume only on the processor in which it was initially started. A schedule value is the summation of all the values of all the tasks that were completed by their deadlines. In this paper we assume that a task's value is proportional to its computation time. We present lower and upper bound results. For a system with n processors, we construct a nonmigrative schedule that is guaranteed to achieve at least $1-( 1-\frac 1{2n}) ^n$ of the optimal migrative schedule value. In addition, we show task sets for which even an optimal nonmigrative schedule achieves at most n/(2n-1) of the optimal migrative value. Asymptotically (as $n\rightarrow \infty $) our upper bound approaches 1/2 and the lower bound approaches $1 - {1\over \sqrt{e}} \sim 0.3935$.

In this paper we show how a real-time time-sharing RtTS architecture can be very useful in resolving many of the formidable problems generally posed by complex real-time systems. In particular, we address dynamic multiple job systems, running on shared-memory multi-processor platforms. Each job is multitasked, with task characteristics assumed to be complex, e.g. some critical, some dependent, some aperiodic. Each job may also have multiple states, and may support several alternate modes of operation. Concurrent job sets, modes, states, and even available processor capacities, are all assumed dynamic. To accommodate such complexities, the RtTS architecture adopts a practical divide-and-conquer approach, which is shown to be very effective. The architecture incorporates three distinct and independent software control layers, which together facilitate automatic near-optimal mode selection, dynamic load-balancing, and reliable real-time time-sharing, in a fully integrated manner. The job-oriented strategy allows each job to be developed independently, as a black box with uniform control requirements, herein described. The unique capabilities of this RtTS architecture are illustrated in a dynamic multimedia context, where it is shown to have several advantages over conventional dynamic load-balancing techniques, in supporting complex task characteristics, best-effort system values, dynamic critical task sets, scalability, and portability.

In applications ranging from video reception to telecommunications and packet communication to aircraft control, tasks enter periodically and have fixed response time constraints, but missing a deadline is acceptable, provided most deadlines are met. We call such tasks "occasionally skippable". We look at the problem of uniprocessor scheduling of occasionally skippable periodic tasks in an environment having periodic tasks. We show that making optimal use of skips is NP-hard. We then look at two algorithms called Skip-Over Algorithms (one a variant of earliest deadline first and one of rate monotonic scheduling) that exploit skips. We give schedulability bounds for both.

Consider a real-time system in which every task has a value that it obtains only if it completes by its deadline. The problem is to design an on-line scheduling algorithm (i.e., the scheduler has no knowledge of a task until it is released) that maximizes the guaranteed value obtained by the system. When such a system is underloaded (i.e., there exists a schedule for which all tasks meet their deadlines), Dertouzos [Proceedings IFIF Congress, 1974, pp. 807–8131 showed that the earliest deadline first algorithm will achieve 100% of the possible value. Locke [Ph.D. thesis, Computer Science Dept., Carnegie-Mellon Univ., Pittsburgh, PA] showed that earliest deadline first performs very badly, however, when the system is overloaded, and he proposed heuristics to deal with overload. This paper presents an optimal on-line scheduling algorithm for overloaded uniprocessor systems. It is optimal in the sense that it gives the best competitive ratio possible relative to an off-line scheduler.

We study competitive on-line scheduling in multiprocessor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e., one in which the scheduler has no knowledge of a task until it is released) with worst case guarantees as to the total value obtained by the system. We study systems with two or more processors. We present an inherent limit on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst case guarantee which is within a small factor from the best possible guarantee in many cases. The models are a distributed system having a centralized scheduler as well as a shared memory multiprocessor.>

An optimal online scheduling algorithm for overloaded systems is presented. It is optimal in the sense that it gives the best competitive factor possible relative to an offline (i.e., clairvoyant) scheduler. It also gives 100% of the value of a clairvoyant scheduler when the system is underloaded. In fact the performance guarantee of D/sup over/ is even stronger: D/sup over/ schedules to completion all tasks in underloaded periods and achieves at least 1/(1+ square root k)/sup 2/ of the value a clairvoyant algorithm can get during overloaded periods. The model accounts for different value densities and generalizes to soft deadlines.>

The preemptive scheduling of sporadic tasks on a uniprocessor is considered. A task may arrive at any time, and is characterized by a value that reflects its importance, an execution time that is the amount of processor time needed to completely execute the task, and a deadline by which the task is to complete execution. The goal is to maximize the sum of the values of the completed tasks. An online scheduling algorithm that achieves optimal performance when the system is underloaded and provides a nontrivial performance guarantee when the system is overloaded is designed. The algorithm is implemented using simple data structures to run at a cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant. Upper bounds on the best performance guarantee obtainable by an online algorithm in a variety of settings are derived.>

The authors study the performance of online algorithms in environments where no value is obtained for the partial execution of a request. They prove that no online scheduling algorithm can have a competitive factor greater than 0.25 times the optimal. They further refine this bound by considering the effect of the loading factor. Other models of task systems (for example, tasks systems consisting of many types of task requests), are considered. Similar upper bounds on the competitive factor that can be made by online scheduling algorithms in these environments are proved. It is shown that the performance bound of 0.25 is tight by means of a simple online uniprocessor scheduling algorithm has a competitive factor of 1/4. The authors extend the discussion to systems with dual processors. They show that the upper bound for the dual-processor online scheduling problem is 1/2 if all tasks have the same value density. This bound is tight if the tasks all also have zero laxity.>