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 Dr. Binoy Ravindran Committee Chair Dr. Amitabh Mishra Committee Member Dr. Y. Thomas Hou Committee Member
Keywords	Variable Cost Functions Time/utility functions utility accrual scheduling
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 speci¯ed 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 speci¯c 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 e®ectiveness 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

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