Files in this item
|(no description provided)|
|Title:||Scheduling in Real-Time Systems to Ensure Graceful Degradation: The Imprecise-Computation and the Deferred-Deadline Approaches|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||When a real-time system becomes overloaded, we want the system to degrade in a graceful, predictable manner. Imprecise computations and deferred deadlines are two approaches to provide this graceful, predictable degradation.
This thesis describes efficient algorithms for scheduling tasks in systems based on these two approaches. The first part is concerned with problems of scheduling imprecise computations. In the imprecise computation model, each task is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be executed to completion in order to produce an acceptable result. The optional subtask begins after the mandatory subtask is completed and can be left incompleted. The error in the result of a task is equal to the processing time of the unexecuted portion of the optional subtask. We want to schedule these tasks to meet two objectives: (1) the mandatory subtasks of all tasks complete by their deadlines whenever it is feasible to do so; (2) the optional subtasks are completed as much as possible so that overall result quality is optimized. The algorithms described in the first part are for the preemptive scheduling, on a uniprocessor system, of dependent tasks with rational ready times, deadlines and processing times. Some can handle tasks with different weights. Among the algorithms are the optimal ones for different performance measures used to quantify the overall result quality.
The second part of this thesis is concerned with the problems of scheduling periodic tasks with deferred deadlines. The deferred-deadline approach to graceful degradation is to ensure that the lateness of all tasks is acceptably small during an overload. We describe a semi-static, priority-driven algorithm, called the modified rate-monotone algorithm, for scheduling periodic tasks with deferred deadlines. When some periodic tasks are considered to be urgent because their deadlines cannot be deferred, we can schedule the urgent tasks by the well-known rate-monotone algorithm and the tasks with deferred deadlines by the modified rate-monotone algorithm. The performance of this hybrid strategy for scheduling mixed task sets of urgent tasks and tasks with deferred deadlines is discussed. (Abstract shortened by UMI.)
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993.
|Date Available in IDEALS:||2014-12-17|