The performance of multiprogrammed multiprocessor scheduling algorithms

ABSTRACT

Scheduling policies for general purpose multiprogrammed multiprocessors are not well understood. This paper examines various policies to determine which properties of a scheduling policy are the most significant determinants of performance. We compare a more comprehensive set of policies than previous work, including one important scheduling policy that has not previously been examined. We also compare the policies under workloads that we feel are more realistic than previous studies have used. Using these new workloads, we arrive at different conclusions than reported in earlier work. In particular, we find that the “smallest number of processes first” (SNPF) scheduling discipline performs poorly, even when the number of processes in a job is positively correlated with the total service demand of the job. We also find that policies that allocate an equal fraction of the processing power to each job in the system perform better, on the whole, than policies that allocate processing power unequally. Finally, we find that for lock access synchronization, dividing processing power equally among all jobs in the system is a more effective property of a scheduling policy than the property of minimizing synchronization spin-waiting, unless demand for synchronization is extremely high. (The latter property is implemented by coscheduling processes within a job, or by using a thread management package that avoids preemption of processes that hold spinlocks.) Our studies are done by simulating abstract models of the system and the workloads.

REFERENCES

• BeLL 88: Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, PRESTO: a system for object-oriented parallel programming, Software—Practice & Experience, v.18 n.8, p.713-732, August 1988 [doi>10.1002/spe.4380180802]
• Doep 87: Doeppner, T.W., "l'hreads: A System for the Supporst of Concurrent Programming," Technical Report CS-87-11, Department of Computer Science, Brown University, 1987.
• EaZL 86: Eager, D.L, Zahorjan, J., Lazowska, E.D., "Speedup Versus Efficiency in Parallel Systems," Research Report 86-12, Dept. of Computational Science, University of Saskatchewan, Saskatoon, Canada, 1986 {to appear in IEEETC}.
• Gust 88: John L. Gustafson, Reevaluating Amdahl's law, Communications of the ACM, v.31 n.5, p.532-533, May 1988 [doi>10.1145/42411.42415]
• Klei 76: Kleinrock, L., Queueing Systems, Vol. II: Computer Applications, John Wiley and Sons, 1976.
• LiCh 89: Lionel M. Ni , Ching-Farn E. Wu, Design Tradeoffs for Process Scheduling in Shared Memory Multiprocessor Systems, IEEE Transactions on Software Engineering, v.15 n.3, p.327-334, March 1989 [doi>10.1109/32.21760]
• Livn 88: Livny, M., DeNet User's Guide, Version 1.0, Computer Sciences Deptartment, University of Wisconsin, Madison, 1988.
• NeTT 87: Randolph Nelson , Don Towsley , Asser N. Tantawi, Performance Analysis of Parallel Processing Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.532-540, April 1988 [doi>10.1109/32.4676]
• Maju 88: Shikharesh Majumdar, Processor scheduling in multiprogrammed parallel systems, 1988
• MaEa 89: Majumdar, S., Eager, D., Private communications, 1989.
• MaEB 88: S. Majumdar , D. L. Eager , R. B. Bunt, Scheduling in multiprogrammed parallel systems, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.104-113, May 24-27, 1988, Santa Fe, New Mexico, United States
• Oust 82: Ousterhout, J., "Scheduling Techniques for Concurrent Systems," Proc, of Distributed Computing Systems Conference, 1982, pp. 22-30.
• Shra 68: Shrage, Linus, "A Proof of the Optimality of the Shortest Remaining Processing Time Discipline," Operations Research, 1968, pp. 687-690.
• SaCh 89: Sauer, C.H., Chandy, K.M., "Computer System Performance Modeling", Prentice-Hall, 1981, page 16.
• TuGu 89: A. Tucker , A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.159-166, November 1989
• ZaLE 89: Zahorjan, J., Lazowska, E.D., Eager, D.L., "The Effect of Scheduling Discipline on Spin Overhead in Shared Memory Parallel Systems," Technical Report 89-07-03, Department of Computer Science, University of Wshington, Seattle, July 1989.
• ZaLE 88: Zahorjan, J., Lazowska, E.D., Eager, D.L., "Spinning Versus Blocking in Parallel Systems with Uncertainty," Proc. of International Seminar on Performance of Distributed and Parallel Systems, Kyoto Japan, December 7-11, 1988, pp. 445-462.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Scheduling

General Terms:
Design, Performance