A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors

ABSTRACT

We propose and evaluate empirically the performance of a dynamic processor-scheduling policy for multiprogrammed shared-memory multiprocessors. The policy is dynamic in that it reallocates processors from one parallel job to another based on the currently realized parallelism of those jobs. The policy is suitable for implementation in production systems in that: —It interacts well with very efficient user-level thread packages, leaving to them many low-level thread operations that do not require kernel intervention. —It deals with thread blocking due to user I/O and page faults. —It ensures fairness in delivering resources to jobs. —Its performance, measured in terms of average job response time, is superior to that of previously proposed schedulers, including those implemented in existing systems. It provides good performance to very short, sequential (e.g., interactive) requests. We have evaluated our scheduler and compared it to alternatives using a set of prototype implementations running on a Sequent Symmetry multiprocessor. Using a number of parallel applications with distinct qualitative behaviors, we have both evaluated the policies according to the major criterion of overall performance and examined a number of more general policy issues, including the advantage of “space sharing” over “time sharing” the processors of a multiprocessor, and the importance of cooperation between the kernel and the application in reallocating processors between jobs. We have also compared the policies according to other criteia important in real implementations, in particular, fairness and respone time to short, sequential requests. We conclude that a combination of performance and implementation considerations makes a compelling case for our dynamic scheduling policy.

REFERENCES

• 1: AI,MQUIST, K., ANDERSON, R. J., AND LAZOWSKA, E.D. The measured performance of parallel dynamic programming implementations. In Proceedings of the 1989 International Conference on Parallel Processing (Aug. 1989).
• 2: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Money Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 3: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.53-79, Feb. 1992 [doi>10.1145/146941.146944]
• 4: BARNES, J., AND HUT, P. A hierarchical O(NlogN) force-calculation algorithm. Nature 24 (1986), 446-449.
• 5: 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]
• 6: BIRRELL, A. D. An introduction to programming with threads. DEC System Research Center, 1989.
• 7: EDLER, J., LmKIS, J., AND SCHONBERa, E. Process management for highly parallel UNIX systems. In Proceedings of the USENIX Workshop on UNIX and Supercomputers (Sept. 1988). USENIX.
• 8: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 9: Gary Granunke , Shreekant Thakkar, Synchronization Algorithms for Shared-Memory Multiprocessors, Computer, v.23 n.6, p.60-69, June 1990 [doi>10.1109/2.55501 ]
• 10: Anoop Gupta , Andrew Tucker , Luis Stevens, Making effective use of shared-memory multiprocessors: the process control approach, Stanford University, Stanford, CA, 1991
• 11: Anoop Gupta , Andrew Tucker , Shigeru Urushibara, The impact of operating system scheduling policies and synchronization methods of performance of parallel applications, Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.120-132, May 21-24, 1991, San Diego, California, United States
• 12: Anna R. Karlin , Kai Li , Mark S. Manasse , Susan Owicki, Empirical studies of competitve spinning for a shared-memory multiprocessor, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.41-55, October 13-16, 1991, Pacific Grove, California, United States
• 13: Will Leland , Teunis J. Ott, Load-balancing heuristics and process behavior, Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation, p.54-69, May 1986, Raleigh, North Carolina, United States
• 14: Scott T. Leutenegger , Mary K. Vernon, The performance of multiprogrammed multiprocessor scheduling algorithms, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.226-236, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 15: Lo, S.-P., AND GLIGOR, V. D. A comparative analysis of mult~processor scheduling algorithms. In Proceedzngs of the 7th International Conference on Dtstrzbuted Computzng Systems (Sept. 1987).
• 16: LOVETT, T., AND THAKKAR, S. The symmetry multiprocessor system. In Proceedings of the 1988 lnternatwnal Conference on Parallel Processing (Aug. 1988).
• 17: 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
• 18: O~TSTERHOUT, J.K. Scheduling techniques for concurrent systems. In Proceedings of the 3rd Internatzonal Conference on D~str~buted Computing Systems (Oct. 1982).
• 19: POLYCHRONOPOULOS, C.D. Multiprocessing versus mult~programming. In Proceedings of the 1989 Internatzonal Conference on Parallel Processing (Aug. 1989).
• 20: M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980 [doi>10.1145/322186.322195]
• 21: K. C. Sevcik, Characterizations of parallelism in applications and their use in scheduling, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.171-180, May 23-26, 1989, Oakland, California, United States
• 22: 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
• 23: Charles P. Thacker , Lawrence C. Stewart , Edwin H. Satterthwaite, Jr., Firefly: A Multiprocessor Workstation, IEEE Transactions on Computers, v.37 n.8, p.909-920, August 1988 [doi>10.1109/12.2243 ]
• 24: Raj Vaswani , John Zahorjan, The implications of cache affinity on processor scheduling for multiprogrammed, shared memory multiprocessors, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.26-40, October 13-16, 1991, Pacific Grove, California, United States
• 25: John Zahorjan , Cathy McCann, Processor scheduling in shared memory multiprocessors, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.214-225, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 26: J. Zahorjan , E. D. Lazowska , D. L. Eager, The Effect of Scheduling Discipline on Spin Overhead in Shared Memory Parallel Systems, IEEE Transactions on Parallel and Distributed Systems, v.2 n.2, p.180-198, April 1991 [doi>10.1109/71.89064 ]
• 27: ZAHOaJAN, J., LAZOWSKA, E. D., AND EAGER, D. L. Spinning versus blocking in parallel systems with uncertainty. In Proceedings of the International Symposium on Performance of Dzstributed and Parallel Systems (Kyoto, Japan, Dec. 1988).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Design, Measurement, Performance

Keywords:
shared memory parallel processors, threads, two-level scheduling