Validating timing constraints in multiprocessor and distributed systems

In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods for determining whether all the timing constraints are met do not yet exist for systems using modern dynamic scheduling strategies, and exhaustive methods are often infeasible or unreliable since the execution time and release time of each job may vary. In this thesis, we present solutions to the problem of how to validate systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. We begin by considering the simplest case of this problem where jobs are independent and processors are identical. We then generalize the validation problem to deal with the case where the processors are heterogeneous and the jobs are dependent. For each case we present conditions under which the jobs execute in a predictable manner, i.e., the completion times of jobs are no later when the execution times of some jobs decrease. We also present algorithms and bounds with which the latest completion times of all jobs can be bounded.

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

• Ha, Rhan

Contributors dc:contributor

• Liu, Jane W.S.

• Computer Science

Statement dc:rights

• Copyright 1995 Ha, Rhan

Language dc:language

eng

Identifier

AAI9543600
(UMI)AAI9543600

OAI identifier oai:identifier

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