Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Threads are the vehicle for concurrency in many approaches to parallel programming. 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; managing parallelism at the user level is essential to high-performance parallel computing. Next, we argue that the problems encountered in integrating user-level threads with other system services is a consequence of the lack of kernel support for user-level threads provided by contemporary multiprocessor operating systems; kernel threads 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

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: 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]
• 3: BARNES, J., AND HUT, P. A hierarchical O(N log N) force-calculation algorithm. Nature 324 (1986), 446-449.
• 4: 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
• 5: 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]
• 6: 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
• 7: David Cheriton, The V distributed system, Communications of the ACM, v.31 n.3, p.314-333, March 1988 [doi>10.1145/42392.42400]
• 8: DRAVES, R., AND COOPER, E. C Threads. Tech. Rep. CMU-CS-88-154, School of Computer Science, Carnegie Mellon Umv., June 1988.
• 9: EDLER, J., LIPKIS, J., AND SCHONBERG, E Process management for highly parallel UNIX systems. In Proceedings of the USEN{X Workshop on UNIX and Supercomputers (Sept. 1988), pp. 1-17.
• 9A: Anoop Gupta , Andrew Tucker , Luis Stevens, Making effective use of shared-memory multiprocessors: the process control approach, Stanford University, Stanford, CA, 1991
• 10: 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]
• 11: 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
• 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: 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]
• 14: Lo, S.-P., AND GL~GOR, V. A comparative analysis of multiprocessor scheduling algorithms. In Proceedings of the 7th International Conference on Distributed Computing Systems (Sept. 1987), pp 356~363.
• 15: 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
• 16: MOELLER-N~ELSEN, P., AND STAUNSTRUP, J. Problem-heap: A paradigm for multiprocessor algorithms. Parallel Comput. 4, I (Feb. 1987), 63-74.
• 17: 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
• 18: David D. Redell, Experience with topaz telebugging, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.35-44, May 05-06, 1988, Madison, Wisconsin, United States
• 19: 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]
• 20: 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
• 21: 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 (1987), pp. 185-197.
• 22: 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]
• 23: 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
• 24: 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]
• 25: 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
• 26: WULF, W., LEVIN, R., AND HARmSON, S. Hydra/C. mmp: An Experimental Computer System. McGraw-Hill, New York, 1981.
• 27: 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
• 28: 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.4 Communications Management
          Subjects: Input/output

General Terms:
Design, Measurement, Performance

Keywords:
multiprocessor, thread