Files in this item



application/pdf9503139.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:End-to-end scheduling to meet deadlines in distributed systems
Author(s):Bettati, Riccardo
Doctoral Committee Chair(s):Liu, Jane W.S.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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.
Issue Date:1994
Rights Information:Copyright 1994 Bettati, Riccardo
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9503139
OCLC Identifier:(UMI)AAI9503139

This item appears in the following Collection(s)

Item Statistics