This dissertation first presents an uniprocessor real-time scheduling algorithm called the Generic Benefit Scheduling algorithm (or GBS). GBS solves a previously open real-time scheduling problem: scheduling activities subject to arbitrarily shaped, time/utility function (TUF) time constraints and mutual exclusion resource constraints. A TUF specifies the utility of completing an application activity as an application- or situation-specific function of when that activity completes. GBS considers the scheduling objective of maximizing system-wide, total accrued utility, while respecting mutual exclusion constraints. Since this problem is NP-hard, GBS heuristically computes schedules in polynomial-time.
The performance of the GBS algorithm is evaluated through simulation and through an implementation on a Portable Operating System Interface (POSIX)-compliant real-time operating system. The simulation studies and implementation measurements reveal that GBS performs close to, if not better than existing algorithms for the cases that they apply. Further, the results verify the effectiveness of GBS for its unique model. We also analytically establish timeliness and non-timeliness properties of GBS including bounds on activity utilities and mutual exclusion.
GBS targets real-time systems that are subject to significant non-determinism inherent in their operating environments e.g., completely unknown activity arrivals. When system uncertainties can be stochastically characterized (e.g., stochastic activity arrivals and execution times), it is possible to provide stochastic assurances on timeliness behavior.
The dissertation also presents algorithmic solutions to fundamental assurance problems in TUF-driven real-time systems, including stochastically satisfying individual, activity utility lower bounds and system-wide, total utility lower bounds. The algorithmic solutions include algorithms for processor bandwidth allocation and TUF scheduling. While bandwidth allocation algorithms allocate processor bandwidth share to activities to satisfy utility lower bounds, TUF scheduling algorithms schedule activities to maximize accrued utility. The algorithmic solutions and analysis are extended with a class of lock-free and lock-based resource access protocols to satisfy mutual exclusion constraints. We show that satisfying utility lower bounds with lock-based resource access protocols does not imply doing so with the lock-free scheme, and vice versa. Finally, the dissertation presents a rule-based framework for trading off assurance requirements on utility lower bound satisfaction. / Ph. D.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/11220 |
| Date | 10 August 2004 |
| Creators | Li, Peng |
| Contributors | Electrical and Computer Engineering, Ravindran, Binoy |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | dissertation-final.pdf |
Page generated in 0.0021 seconds