Type of Document Dissertation Author Li, Peng Author's Email Address firstname.lastname@example.org URN etd-08092004-230138 Title Utility Accrual Real-Time Scheduling: Models and Algorithms Degree PhD Department Electrical and Computer Engineering Advisory Committee
Advisor Name Title Ravindran, Binoy Committee Chair Keywords
- performance assurance
- real-time scheduling
- utility accrual scheduling
- Time/utility functions
- resource management
- overload scheduling
Date of Defense 2004-07-20 Availability unrestricted AbstractThis 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.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access dissertation-final.pdf 1.19 Mb 00:05:29 00:02:49 00:02:28 00:01:14 00:00:06
If you have questions or technical problems, please Contact DLA.