Utility Accrual Real-Time Scheduling Under Variable Cost Functions

Simple item page
dc.contributor.authorBalli, Umuten
dc.contributor.committeechairRavindran, Binoyen
dc.contributor.committeememberHou, Yiwei Thomasen
dc.contributor.committeememberMishra, Amitabhen
dc.contributor.departmentElectrical and Computer Engineeringen
dc.date.accessioned2014-03-14T20:42:47Zen
dc.date.adate2005-08-15en
dc.date.available2014-03-14T20:42:47Zen
dc.date.issued2005-07-28en
dc.date.rdate2008-08-15en
dc.date.sdate2005-08-05en
dc.description.abstractWe present a utility accrual real-time scheduling algorithm called CIC-VCUA, for tasks whose execution times are functions of their starting times. We model such variable execution times employing variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints (or TUFs), execution times described using VCFs, and concurrent, mutually exclusive sharing of non-CPU resources. We consider the multi-criteria scheduling objective of (1) assuring that the maximum interval between any two consecutive, successful completions of jobs of a task must not exceed a specified upper bound, and (2) maximizing the system's total accrued utility, while satisfying mutual exclusion resource constraints. Since the scheduling problem is intractable, CIC-VCUA statically computes worst-case sojourn times of tasks, selects tasks for execution based on their potential utility density, and completes them at specific times, in polynomial-time. We establish that CIC-VCUA achieves optimal timeliness during under-loads. Further, we identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate CIC-VCUA's effectiveness and superiority.en
dc.description.degreeMaster of Scienceen
dc.identifier.otheretd-08052005-155355en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-08052005-155355/en
dc.identifier.urihttp://hdl.handle.net/10919/34358en
dc.publisherVirginia Techen
dc.relation.haspartUmut_Balli_Thesis.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectutility accrual schedulingen
dc.subjectTime/utility functionsen
dc.subjectVariable Cost Functionsen
dc.titleUtility Accrual Real-Time Scheduling Under Variable Cost Functionsen
dc.typeThesisen
thesis.degree.disciplineElectrical and Computer Engineeringen
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:
Umut_Balli_Thesis.pdf
Size:
570.12 KB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses