End-to-end scheduling to meet deadlines in distributed systems
Bettati, Riccardo
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/20723
Description
Title
End-to-end scheduling to meet deadlines in distributed systems
Author(s)
Bettati, Riccardo
Issue Date
1994
Doctoral Committee Chair(s)
Liu, Jane W.S.
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
Language
eng
Abstract
In a distributed real-time system or communication network, tasks may need to be executed on more than one processor. For time-critical tasks, the timing constraints are typically given as end-to-end release times and deadlines. This thesis describes algorithms to schedule a class of systems where all the tasks execute on different processors in turn in the same order. This end-to-end scheduling problem is known as the flow-shop problem. We present several cases where the problem is tractable and evaluate two heuristic algorithms for the NP-hard general case. We generalize the traditional flow-shop model in two directions. First, we present two algorithms for scheduling flow shops where tasks can be serviced more than once by some processors. Second, we describe a technique to schedule flow shops that consist of periodic tasks and to analyze their schedulability. We generalize this technique and describe how it can be used to schedule distributed systems that can not be modeled by flow shops. We then describe how to combine local or global resource access protocols and end-to-end scheduling. Finally, we show that by using end-to-end scheduling we can simplify resource access protocols and thus increase the utilization of resources.
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.
