Improving utility accrual scheduling algorithm for adaptive real-time system

Abstract

In this paper, we proposed a preemptive utility accrual scheduling (or PUAS) algorithm to further extend the functionalities of General Utility Scheduling (or GUS) algorithm proposed by Peng Li. Both of these algorithms are developed for adaptive real-lime system environment where untoward effects such as deadline misses and overloads are tolerable. The proposed algorithm focused on an independent task model, which works on deadline constraints that are specified by using step time/utility functions (or TUFs). The proposed algorithm improves the GUS algorithm by preempting the tasks that GUS abort due to its lower PUD, lowering abortion ratio which in turn increase accrued utility. This met the scheduling objective of maximizing utility, which are achieved thru completion of all tasks. Results from our simulations showed that the proposed algorithm PUAS achieved higher utility and lower abortion ration compared to GUS algorithm. This in effect, produced a much lower average response time, making PUAS more efficient in time-critical application domain.