A Utility Accrual Scheduling
Algorithm for Real-Time Activities With Mutual Exclusion Resource Constraints
April 2004
Peng Li, Virginia Polytechnic Institute and State University
Binoy Ravindran, Virginia Polytechnic Institute and State University
Haisang Wu, Virginia Polytechnic Institute and State University
E. Douglas Jensen, The MITRE Corporation
ABSTRACT
This paper presents a uni-processor real-time scheduling algorithm
called the Generic Utility Scheduling algorithm (which we will refer
to simply as GUS). GUS solves an open real-time scheduling problem—scheduling application activities that have time constraints specified
using arbitrarily shaped time/utility functions, and have mutual exclusion
resource constraints. A time/utility function is a time constraint specification
that describes an activity's utility to the system as a function
of that activity's completion time. Given such time and resource
constraints, we consider the scheduling objective of maximizing the
total utility that is accrued by the completion of all activities. Since
this problem is NP-hard, GUS heuristically computes schedules with a
polynomial-time cost of O(n3) at each scheduling event, where n is the
number of activities in the ready queue. We evaluate the performance
of GUS through simulation and by an actual implementation on a real-time
POSIX operating system. Our simulation studies and implementation measurements
reveal that GUS performs close to, if not better than, the existing
algorithms for the cases that they apply. Furthermore, we analytically
establish several timeliness and non-timeliness properties of GUS.
Additional Search Keywords
Real-time scheduling, time/utility functions, utility accrual scheduling,
resource dependency, mutual exclusion, overload management, resource management
|
