Show simple item record

dc.contributor.authorBasavaraj, Veenaen_US
dc.date.accessioned2014-03-14T20:41:16Z
dc.date.available2014-03-14T20:41:16Z
dc.date.issued2006-07-06en_US
dc.identifier.otheretd-07102006-164018en_US
dc.identifier.urihttp://hdl.handle.net/10919/33953
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_US
dc.publisherVirginia Techen_US
dc.relation.haspartVB_OPTIMALITY_ETD.pdfen_US
dc.rightsI hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to Virginia Tech or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.en_US
dc.subjectreal-timeen_US
dc.subjectutility accrualen_US
dc.subjecttime-utility functionsen_US
dc.subjectoptimalityen_US
dc.titleOptimality of Heuristic Schedulers in Utility Accrual Real-time Scheduling Environmentsen_US
dc.typeThesisen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelmastersen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Scienceen_US
dc.contributor.committeechairBack, Godmar Volkeren_US
dc.contributor.committeememberJensen, E. Douglasen_US
dc.contributor.committeememberCameron, Kirk W.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-07102006-164018/en_US
dc.date.sdate2006-07-10en_US
dc.date.rdate2006-07-11
dc.date.adate2006-07-11en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record