Scheduler activations: effective kernel support for the user-level management of parallelism

ABSTRACT

Threads are the vehicle for concurrency in many approaches to parallel programming. Threads separate the notion of a sequential execution stream from the other aspects of traditional UNIX-like processes, such as address spaces and I/O descriptors. The objective of this separation is to make the expression and control of parallelism sufficiently cheap that the programmer or compiler can exploit even fine-grained parallelism with acceptable overhead.Threads can be supported either by the operating system kernel or by user-level library code in the application address space, but neither approach has been fully satisfactory. This paper addresses this dilemma. First, we argue that the performance of kernel threads is inherently worse than that of user-level threads, rather than this being an artifact of existing implementations; we thus argue that managing parallelism at the user level is essential to high-performance parallel computing. Next, we argue that the lack of system integration exhibited by user-level threads is a consequence of the lack of kernel support for user-level threads provided by contemporary multiprocessor operating systems; we thus argue that kernel threads or processes, as currently conceived, are the wrong abstraction on which to support user-level management of parallelism. Finally, we describe the design, implementation, and performance of a new kernel interface and user-level thread package that together provide the same functionality as kernel threads without compromising the performance and flexibility advantages of user-level management of parallelism.

REFERENCES

• Agha 86: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• Anderson et al. 89: T. E. Anderson , E. D. Lazowska , H. M. Levy, The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.38 n.12, p.1631-1644, December 1989 [doi>10.1109/12.40843]
• Barnes & Hut 86: Barnes, J. and Hut, P. A Hierarchical O(N log N) Force-Calculation Algorithm. Nature, 324:446-449, 1986.
• Birrell et al. 87: A. Birrell , J. Guttag , J. Horning , R. Levin, Synchronization primitives for a multiprocessor: a formal specification, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.94-102, November 08-11, 1987, Austin, Texas, United States
• Black 90: David L. Black, Scheduling Support for Concurrency and Parallelism in the Mach Operating System, Computer, v.23 n.5, p.35-43, May 1990 [doi>10.1109/2.53353]
• Chase et al. 89: J. Chase , F. Amador , E. Lazowska , H. Levy , R. Littlefield, The Amber system: parallel programming on a network of multiprocessors, Proceedings of the twelfth ACM symposium on Operating systems principles, p.147-158, November 1989
• Cheriton 88: David Cheriton, The V distributed system, Communications of the ACM, v.31 n.3, p.314-333, March 1988 [doi>10.1145/42392.42400]
• Draves & Cooper 88: Draves, R. and Cooper, E. C Threads. Technical Report CMU-CS-88-154, School of Computer Science, Carnegie-Mellon University, June 1988.
• Edler et al. 88: Edler, J., Lipkis, J., and Schonberg, E. Process Management for Highly Parallel UNIX Systems. In Proceedings o/the USENIX Workshop on UNIX and Supercomputers, pages 1-17, September 1988.
• Halstead 85: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• Herlihy 90: M. Herlihy, A methodology for implementing highly concurrent data structures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.197-206, March 14-16, 1990, Seattle, Washington, United States
• Karlin et al. 91: 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
• Lampson & Redell 80: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa, Communications of the ACM, v.23 n.2, p.105-117, Feb. 1980 [doi>10.1145/358818.358824]
• Lo & Gligor 87: Lo, S.-P. and Gligor, V. A Comparative Analysis of Multiprocessor Scheduling Algorithms. In Proceedings of the 7th International Conference on Distributed Computing Systems, pages 356-363, September 1987.
• Marsh et al. 91: Brian D. Marsh , Michael L. Scott , Thomas J. LeBlanc , Evangelos P. Markatos, First-class user-level threads, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.110-121, October 13-16, 1991, Pacific Grove, California, United States
• Moeller-Nielsen & Staunstrup 87: Moeller-Nielsen, P. and Staunstrup, J. Problem-Heap: A Paradigm for Multiprocessor Algorithms. Parallel Computing, 4(1):63-74, February 1987.
• Moss & Kohler 87: J. Eliot B. Moss , Walter H. Kohler, Concurrency features for the Trellis/Owl language, European conference on object-oriented programming on ECOOP '87, p.171-180, October 1987, Paris, France
• Redell 88: Redell, D. The Topaz Tele-Debugger. In Proceedings of the A CM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging, May 1988.
• Schroeder & Burrows 90: Michael D. Schroeder , Michael Burrows, Performance of the Firefly RPC, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.1-17, Feb. 1990 [doi>10.1145/77648.77653]
• Scott et al. 90: M. L. Scott , T. J. LeBlanc , B. D. Marsh, Multi-model parallel programming in psyche, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.70-78, March 14-16, 1990, Seattle, Washington, United States
• Tevanian et al. 87: Tevanian, A., Rashid, R., Golub, D., Black, D., Cooper, E., and Young, M. Mach Threads and the Unix Kernel: The Battle for Control. in Proceedings of the 1987 USENIX Summer Conference, pages 185-197, 1987.
• Thacker et al. 88: 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]
• Tucker & Gupta 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
• Vandevoorde & Roberts 88: Mark T. Vandevoorde , Eric S. Roberts, Workcrews: an abstraction for controlling parallelism, International Journal of Parallel Programming, v.17 n.4, p.347-366, Aug. 1988 [doi>10.1007/BF01407910]
• Weiser et al. 89: M. Weiser , A. Demers , C. Hauser, The portable common runtime approach to interoperability, Proceedings of the twelfth ACM symposium on Operating systems principles, p.114-122, November 1989
• Wulf et al. 81: Wulf, W., Levin, R., and Harbison, S. Hydra/C, mmp: An Experimental Computer System. McGraw-Hill, 1981.
• Zahorjan & McCann 90: 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
• Zahorjan et al. 91: 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]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Multiprocessing/multiprogramming/multitasking
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Design, Performance