Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines

ABSTRACT

Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, that is, the average time spent by jobs in the system between release and completion.The Windows NT and the Unix operating system scheduling policies are based on the Multilevel Feedback algorithm. In this article, we prove that a randomized version of the Multilevel Feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has proven effective in practice along the last two decades.The randomized Multilevel Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs for a single machine achieving an O(log n log log n) competitive ratio to minimize the average flow time against the on-line adaptive adversary, where n is the number of jobs that are released. We present a version of RMLF working for any number m of parallel machines. We show for RMLF a first O(log n log n/m) competitiveness result against the oblivious adversary on parallel machines. We also show that the same RMLF algorithm surprisingly achieves a tight O(log n) competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound for this case.

REFERENCES

• 1: Acharya, S., Muthukrishnan, S., and Sundaram, G. 1999. Scheduling data delivery over multiple channels. Tech. rep., Bell Labs Technical Memo. (Available from acharya@research. bell-labs.com.)
• 2: Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the Flow Time Without Migration, SIAM Journal on Computing, v.31 n.5, p.1370-1382, 2002 [doi>10.1137/S009753970037446X]
• 3: Baker, K. R. 1974. Introduction to Sequencing and Scheduling. Wiley, New York.
• 4: Nikhil Bansal , Kedar Dhamdhere , Jochen Könemann , Amitabh Sinha, Non-clairvoyant Scheduling for Minimizing Mean Slowdown, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.260-270, February 27-March 01, 2003
• 5: Nikhil Bansal , Kirk Pruhs, Server scheduling in the L_p norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780580]
• 6: Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Average stretch without migration, Journal of Computer and System Sciences, v.68 n.1, p.80-95, February 2004 [doi>10.1016/j.jcss.2003.06.001]
• 7: Ben-David, S., Borodin, A., Karp, R., Tardos, G., and Wigderson, A. 1994. On the power of randomization in on-line algorithms. Algorithmica 11, 2--14.
• 8: Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
• 9: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 10: Doeppner, T. W. 1987. Threads, a system for the support of concurrent programming. Tech. Rep. CS-87-11, Brown University.
• 11: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 12: IEEE. 1994. Institute for Electrical and Electronic Engineers. POSIX P1003.4a, Threads Extensions for Portable Operating Systems.
• 13: B. Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance [scheduling problems], Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.214, October 23-25, 1995
• 14: B. Kalyanasundaram , K. R. Pruhs, Minimizing flow time nonclairvoyantly, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.345, October 19-22, 1997
• 15: 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]
• 16: 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]
• 17: Mueller, F. 1993. A library implementation of POSIX threads under UNIX. In Proceedings of the USENIX Winter 1993 Technical Conference. 29--42.
• 18: Gary J. Nutt, Operating System Projects Using Windows NT, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 19: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 20: SUN. 1993. Sunos 5.3 system services.
• 21: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Performance, Theory

Keywords:
Probabilistic analysis, flow time, multilevel feedback, randomized algorithms