Utility Accrual Real-Time Scheduling Under Variable Cost Functions

by Balli, Umut

Abstract (Summary)
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.
Bibliographical Information:

Advisor:Dr. Y. Thomas Hou; Dr. Amitabh Mishra; Dr. Binoy Ravindran

School:Virginia Polytechnic Institute and State University

School Location:USA - Virginia

Source Type:Master's Thesis

Keywords:electrical and computer engineering


Date of Publication:08/15/2005

© 2009 All Rights Reserved.