End-to-end scheduling to meet deadlines in distributed systems

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Bettati, Riccardo

Contributors dc:contributor

• Liu, Jane W.S.

• Computer Science

Statement dc:rights

• Copyright 1994 Bettati, Riccardo

Language dc:language

eng

Identifier

AAI9503139
(UMI)AAI9503139

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/20723