### Speed is as powerful as clairvoyanceSpeed is as powerful as clairvoyance

Access Restriction
Subscribed

 Author Kalyanasundaram, Bala ♦ Pruhs, Kirk Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Multi-level feedback scheduling ♦ Resource augmentation ♦ Scheduling Abstract We introduce resource augmentation as a method for analyzing online scheduling problems. In resource augmentation analysis the on-line scheduler is given more resources, say faster processors or more processors, than the adversary. We apply this analysis to two well-known on-line scheduling problems, the classic uniprocessor CPU scheduling problem 1 |ri, pmtn|&Sgr; Fi, and the best-effort firm real-time scheduling problem 1|ri, pmtn| &Sgr; $\textit{wi}($ 1- $\textit{Ui}).$ It is known that there are no constant competitive nonclairvoyant on-line algorithms for these problems. We show that there are simple on-line scheduling algorithms for these problems that are constant competitive if the online scheduler is equipped with a slightly faster processor than the adversary. Thus, a moderate increase in processor speed effectively gives the on-line scheduler the power of clairvoyance. Furthermore, the on-line scheduler can be constant competitive on all inputs that are not closely correlated with processor speed. We also show that the performance of an on-line scheduler is best-effort real time scheduling can be significantly improved if the system is designed in such a way that the laxity of every job is proportional to its length. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2000-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 47 Issue Number 4 Page Count 27 Starting Page 617 Ending Page 643

#### Open content in new tab

Source: ACM Digital Library