Title page for ETD etd-08052005-155355


Type of Document Master's Thesis
Author Balli, Umut
Author's Email Address uballi@vt.edu
URN etd-08052005-155355
Title Utility Accrual Real-Time Scheduling Under Variable Cost Functions
Degree Master of Science
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Ravindran, Binoy Committee Chair
Hou, Yiwei Thomas Committee Member
Mishra, Amitabh Committee Member
Keywords
  • utility accrual scheduling
  • Time/utility functions
  • Variable Cost Functions
Date of Defense 2005-07-28
Availability unrestricted
Abstract
We 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 de-

scribed 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 satis-

fying 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 experi-

ments illustrate CIC-VCUA's effectiveness and superiority.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Umut_Balli_Thesis.pdf 583.80 Kb 00:02:42 00:01:23 00:01:12 00:00:36 00:00:03

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.