Show simple item record

dc.contributor.authorLi, Pengen_US
dc.date.accessioned2011-08-22T19:02:56Z
dc.date.available2011-08-22T19:02:56Z
dc.date.issued2004-09-14en_US
dc.identifier.otheretd-08092004-230138en_US
dc.identifier.urihttp://hdl.handle.net/10919/11220
dc.description.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.en_US
dc.format.mediumETDen_US
dc.publisherVirginia Techen_US
dc.relation.haspartdissertation-final.pdfen_US
dc.rightsThis Item is protected by copyright and/or related rights. Some uses of this Item may be deemed fair and permitted by law even without permission from the rights holder(s), or the rights holder(s) may have licensed the work for use under certain conditions. For other uses you need to obtain permission from the rights holder(s).en_US
dc.subjectperformance assuranceen_US
dc.subjectreal-time schedulingen_US
dc.subjectutility accrual schedulingen_US
dc.subjectTime/utility functionsen_US
dc.subjectresource managementen_US
dc.subjectoverload schedulingen_US
dc.titleUtility Accrual Real-Time Scheduling: Models and Algorithmsen_US
dc.typeDissertationen_US
dc.contributor.departmentElectrical and Computer Engineeringen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineElectrical and Computer Engineeringen_US
dc.contributor.committeechairRavindran, Binoyen_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-08092004-230138en_US
dc.date.sdate2004-08-09en_US
dc.date.rdate2004-08-10
dc.date.adate2004-08-10en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record