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

Scheduling 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.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2006

Author dc:creator

• Basavaraj, Veena

Chair dc:contributor.committeechair

• Back, Godmar V.

Committee members dc:contributor.committeemember

• Jensen, E. Douglas
• Cameron, Kirk W.

• real-time
• utility accrual
• time-utility functions
• optimality

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-07102006-164018

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/33953