Optimality of Heuristic Schedulers in Utility Accrual Real-time Scheduling Environments

Simple item page
dc.contributor.authorBasavaraj, Veenaen
dc.contributor.committeechairBack, Godmar V.en
dc.contributor.committeememberJensen, E. Douglasen
dc.contributor.committeememberCameron, Kirk W.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T20:41:16Zen
dc.date.adate2006-07-11en
dc.date.available2014-03-14T20:41:16Zen
dc.date.issued2006-07-06en
dc.date.rdate2006-07-11en
dc.date.sdate2006-07-10en
dc.description.abstractScheduling decisions in soft real-time environments are based on a utility function. The goal of such schedulers is to use a best-effort approach to maximize the utility function and ensure graceful degradation at overloads. Utility Accrual (UA) schedulers use heuristics to maximize the accrued utility. Heuristic-based scheduling do not always yield the optimal schedule even if there exists one because they do not explore the entire search space of task orderings. In distributed systems, local UA schedulers use the same heuristics along with deadline decomposition for task segments. At present, there has been no evaluation and analysis of the degree to which these polynomial-time, heuristic algorithms succeed in maximizing the total utility accrued. We implemented a preemptive, off-line static scheduling algorithm that performs an exhaustive search of all the possible task orderings to yield the optimal schedules. We simulated two important online dynamic UA schedulers, DASA-ND and LBESA for different system loads, task models, utility and load distribution patterns, and compared their performance with their corresponding optimal schedules. Our experimental analysis indicates that for most scenarios, both DASA-ND and LBESA create optimal schedules. When task utilities are equal or form a geometric sequence with an order of magnitude difference in their utility values, UA schedulers show more than 90% probability of being optimal for single-node workloads. Even though deadline decomposition substantially improves the optimality of both DASA-ND and LBESA under different scenarios for distributed workloads, it can adversely affect the scheduling decisions for some task sets we considered.en
dc.description.degreeMaster of Scienceen
dc.identifier.otheretd-07102006-164018en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-07102006-164018/en
dc.identifier.urihttp://hdl.handle.net/10919/33953en
dc.publisherVirginia Techen
dc.relation.haspartVB_OPTIMALITY_ETD.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectreal-timeen
dc.subjectutility accrualen
dc.subjecttime-utility functionsen
dc.subjectoptimalityen
dc.titleOptimality of Heuristic Schedulers in Utility Accrual Real-time Scheduling Environmentsen
dc.typeThesisen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
VB_OPTIMALITY_ETD.pdf
Size:
2.81 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses