Minimizing flow time nonclairvoyantly

ABSTRACT

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average flow time. This is the classic CPU scheduling problem faced by time-sharing operating systems where preemption is allowed. It is easy to see that every algorithm that doesn't unnecessarily idle the processor is at worst n-competitive, where n is the number of jobs. Yet there was no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably O(n^1−ε). In this article, we give a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio O(log n log log n) against an oblivious adversary. RMLF is a slight variation of the multilevel feedback (MLF) algorithm used by the UNIX operating system, further justifying the adoption of this algorithm. It is known that every randomized nonclairvoyant algorithm is Ω(log n)-competitive, and that every deterministic nonclairvoyant algorithm is Ω(n^1/3)-competitive.

REFERENCES

• 1: Maurice J. Bach, The design of the UNIX operating system, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 2: Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
• 3: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 4: Peter Brucker, Scheduling Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
• 5: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Jeff Edmonds, Scheduling in the dark, Theoretical Computer Science, v.235 n.1, p.109-141, March 17, 2000 [doi>10.1016/S0304-3975(99)00186-3]
• 8: Evan, M., Hastings, N., and Peacock, B. 1993. Statistical Distributions. Wiley, New York.
• 9: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 10: Lawler, E., Lenstra, J., Kan, A., and Shmoys, D. 1993. Sequencing and scheduling: algorithms and complexity. In Logistics of Production and Inventory. Handbooks in Operations Research and Management Science. Vol. 4. North-Holland, 445--522.
• 11: Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
• 12: Stuart E. Madnick , John J. Donovan, Operating Systems, McGraw-Hill, Inc., New York, NY, 1974
• 13: Tsuyoshi Matsumoto, Competitive Analysis of the Round Robin Algorithm, Proceedings of the Third International Symposium on Algorithms and Computation, p.71-77, December 16-18, 1992
• 14: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 15: Phillips, C. A., Stein, C., Torng, E., and Wein, J. 2002. Optimal time-critical scheduling via resource augmentation. Algorithmica 32, 2, 163--200.
• 16: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 17: Abraham Silberschatz , Peter Baer Galvin, Operating System Concepts, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
Scheduling, flow time, multilevel feedback, randomized algorithm, resource augmentation, shortest elapsed time first