Non-clairvoyant scheduling to minimize the average 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, i.e. 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 Multi-level Feedback algorithm [12, 1]. In this paper we prove that a randomized version of the Multi-level 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 been very effective in practice along the last two decades.The randomized Multi-level Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs [7] 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 numberm of parallel machines. We show for RMLF a first O(\log n\log \frac{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 of [10].

REFERENCES

• 1: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 2: Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the flow time without migration, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.198-205, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301304]
• 3: S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
• 4: T. W. Doeppner. Threads, a System for the Support of Concurrent Programming. Technical Report CS-87-11, Brown University, 1987.
• 5: Institute for Electrical and Electronic Engineers. POSIX P1003.4a, Threads Extensions for Portable Operating Systems, 1994.
• 6: 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
• 7: 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
• 8: K.R. Baker. Introduction to Sequencing and Scheduling. Wiley, 1974.
• 9: 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]
• 10: 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]
• 11: F. Mueller. A Library Implementation of POSIX Threads under UNIX. In In Proc. of the Winter 1993 USENIX Technical Conference, pages 29-41, 1993.
• 12: Gary J. Nutt, Operating System Projects Using Windows NT, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 13: K. Pruhs. Personal Communication, 2000.
• 14: 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]
• 15: Sun Microsystems. SunOS 5.3 System Services, 1993.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Performance, Theory, Verification