Loading...
Please wait, while we are loading the content...
Similar Documents
Utility Accrual Scheduling under Arbitrary Time/Utility Functions and Multi-unit Resource Constraints
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wu, Haisang Ravindran, Binoy Jensen, E. Douglas Balli, Umut |
| Copyright Year | 2004 |
| Abstract | We present a uni-processor real-time scheduling algorithm called Resource-contrainted Utility Accrual algorithm (or RUA). RUA considers an application model, where activities can be subject to arbitrarily-shaped time/utility function (TUF) time constraints and resource constraints including mutual exclusion under a multi-unit resource request model. For such a model, we consider the scheduling objective of maximizing the total utility accrued by all activities. This problem was previously open. Since the problem is NP-hard, RUA heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm, including upper bound on blocking time (under multi-unit request model) and deadlock-freedom. We also implement RUA on a POSIX RTOS and conduct experimental comparisons with other TUF scheduling algorithms that address a subset of RUA’s model. Our implementation measurements show that RUA performs generally better than, or as good as, other TUF algorithms for the applicable cases. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.real-time.ece.vt.edu/rtcsa04-rua.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
