Scheduling Real-Time Computations With Temporal Distance and Separation Constraints and With Extended Deadlines
Han, Ching-Chih
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/72067
Description
Title
Scheduling Real-Time Computations With Temporal Distance and Separation Constraints and With Extended Deadlines
Author(s)
Han, Ching-Chih
Issue Date
1992
Doctoral Committee Chair(s)
Lin, Kwei-Jay
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
In hard real-time systems, computations not only must be functionally correct but also must meet their strict timing constraints. To guarantee the timing requirements are satisfied, effective scheduling algorithms must be used. Different real-time applications have different timing requirements. Therefore, different timing constraints must be defined for different real-time applications. Also, different scheduling algorithms need to be designed for different real-time systems to effectively and efficiently schedule the computations to meet their timing constraints. We propose new real-time scheduling problems to model real-time systems in which computations have relative timing constraints. For relative timing constraints, we mean that a computation's ready time or deadline is relative to the actual start time (or finishing time) of some other computation. The Job Scheduling with Distance Constraints problem requires certain pairs of jobs to be scheduled within some given distance of each other. The Job Scheduling with Separation Constraints problem requires two related jobs to be scheduled no smaller than the separation constraint between them. We analyze the scheduling problems with these kinds of relative timing constraints and design several scheduling algorithms for some of them. We also propose new real-time scheduling problems to model real-time systems in which computations have more than one deadline. In the Scheduling with Extended Deadline problem, computations can be delayed after their first (primary) deadlines but must be finished before their second (extended) deadlines. We study two variations of this problem. In the first model, the system receives a penalty for each computation that does not finish its execution before its primary deadline. In the second model, there is an extra overhead for each computation that can not be finished before its primary deadline. We discuss the scheduling issues of the problems under these two models and design some algorithms for scheduling real-time computations with extended deadlines.
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.
