|
Abstract : |
No on-line scheduling algorithm operating in a uniprocessor environment can guarantee to obtain an effective processor utilization greater than 25 % under conditions of overload. This result holds in the most general case, where incoming tasks may have arbitrary slack times. We address here the issue of improving overload performance in environments where the slack-time charactersitics of all incoming tasks satisfy certain constraints. In particular, we present a new scheduling algorithm, ROBUST, that efficiently takes advantage of these task slack constraints to provide improved overload performance and is asymptotically optimal. 1, |
