Scheduling in Real-Time Systems to Ensure Graceful Degradation: The Imprecise-Computation and the Deferred-Deadline Approaches
Shih, Wei-Kuan
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/72088
Description
Title
Scheduling in Real-Time Systems to Ensure Graceful Degradation: The Imprecise-Computation and the Deferred-Deadline Approaches
Author(s)
Shih, Wei-Kuan
Issue Date
1993
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
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.)
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
