The duality of memory and communication in the implementation of a multiprocessor operating system

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The duality of memory and communication in the implementation of a multiprocessor operating system

Full text

Pdf (1.26 MB)

Source

ACM Symposium on Operating Systems Principles archive
Proceedings of the eleventh ACM Symposium on Operating systems principles table of contents

Austin, Texas, United States

Pages: 63 - 76

Year of Publication: 1987

ISBN:0-89791-242-X

Also published in ...

Authors

M. Young	Carnegie Mellon Univ., Pittsburgh, PA
A. Tevanian	Carnegie Mellon Univ., Pittsburgh, PA
R. Rashid	Carnegie Mellon Univ., Pittsburgh, PA
D. Golub	CArnegie Mellon Univ., Pittsburgh, PA
J. Eppinger	Carnegie Mellon Univ., Pittsburgh, PA

Sponsor

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 29, Downloads (12 Months): 131, Citation Count: 64

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/41457.37507 What is a DOI?

ABSTRACT

Mach is a multiprocessor operating system being implemented at Carnegie-Mellon University. An important component of the Mach design is the use of memory objects which can be managed either by the kernel or by user programs through a message interface. This feature allows applications such as transaction management systems to participate in decisions regarding secondary storage management and page replacement.This paper explores the goals, design and implementation of Mach and its external memory management facility. The relationship between memory and communication in Mach is examined as it relates to overall performance, applicability of Mach to new multiprocessor architectures, and the structure of application programs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Accetta, M.J., Baron, R.V., Bolosky, W., Golub, D.B., Rashid, R.F., Tevanian, A., and Young, M.W. Mach: A New Kernel Foundation for UNIX Development. Proceedings of Summer Usenix, July, 1986.
	2	BBNLaboratories. Butterfly Parallel ProcessorOverview. BBN Computer Company, Cambridge, MA, June, 1985.
	3	Bisiani, R., Alleva, F., Forin, A. and Lemer, R. Agora: A Distributed System Architecture for Speech Recognition. International Conference on Acoustics, Speech and Signal Processing, IEEE, April, 1986.
	4	ELXSI Computer, Inc. System Programmer's Reference Manual. ELXSI Computer, Inc., 1983.
	5	Eppinger, J.L., and Spector, A.Z. Virtual Memory Management for Recoverable Objects in the TABS Prototype. Tech. Rept. CMU- CS-85-163, Carnegie-Mellon University, December, 1985.
	6	French, R.E., R.W. Collins and L.W. Loen. 'System/38 Machine Storage Management". IBM Systerr#38 Technical Developments, IBM General Systems Division (1978), 6346.
	7	Anoop Gupta, Parallelism in production systems, 1986
	8	Homig, D.A. Automatic Partitioning and Scheduling on a Network of Personal Computers. Ph.D. Th., Department of Computer Science, Camegie-Mellon University, November 1984.
	9	Kevin C. Kahn , William M. Corwin , T. Don Dennis , Herman D'Hooge , David E. Hubka , Linda A. Hutchins , John T. Montague , Fred J. Pollack, iMAX: A multiprocessor operating system for an object-based computer, Proceedings of the eighth ACM symposium on Operating systems principles, p.127-136, December 14-16, 1981, Pacific Grove, California, United States
	10	Anita K. Jones, The Object Model: A Conceptual Tool for Structuring Software, Operating Systems, An Advanced Course, p.7-16, January 1978
	11	Anita K. Jones , Robert J. Chansler, Jr. , Ivor Durham , Karsten Schwans , Steven R. Vegdahl, StarOS, a multiprocessor operating system for the support of task forces, Proceedings of the seventh ACM symposium on Operating systems principles, p.117-127, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806579]
	12	Jones, M.B., Rashid, ILF., and Thompson, M.R. Sesame: The Spice File System. Department of Computer Science, Carnegie- Mellon University, October, 1982.
	13	Leach, P.L., P.H. Levine, B.P. Douros, J.A. Hamilton, D.L. Nelson and B.L. Stumpf. "The Architecture of an Integrated Local Network". IEEE Journal on Selected Areas in Communications SAC-l, 5 (November 1983), 842-857.
	14	Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.229-239, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10610]
	15	Richard F. Rashid , George G. Robertson, Accent: A communication oriented network operating system kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.64-75, December 14-16, 1981, Pacific Grove, California, United States
	16	Richard F. Rashid, From RIG to Accent to Mach: the evolution of a network operating system, Proceedings of 1986 ACM Fall joint computer conference, p.1128-1137, November 1986, Dallas, Texas, United States
	17	Richard Rashid , Avadis Tevanian , Michael Young , David Golub , Robert Baron, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.31-39, October 1987, Palo Alto, California, United States
	18	Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
	19	M. Satyanarayanan , John H. Howard , David A. Nichols , Robert N. Sidebotham , Alfred Z. Spector , Michael J. West, The ITC distributed file system: principles and design, Proceedings of the tenth ACM symposium on Operating systems principles, p.35-50, December 1985, Orcas Island, Washington, United States
	20	Specter, A.Z., Butcher, J., Daniels, D.S., Duchamp, D.I., Eppinger, J.L, Fineman, C.E., Heddaya, A., Schwarz, P.M. Support for Distributed Transactions in the TABS Prototype~ Proceedings of the 4th Symposium on Reliability In Distributed Software and Database Systems, October, 1984. Also available as Camegie-Mellon Report CMU-CS-84-132, July 1984..
	21	Specter, A.Z. NATO Advanced Study institute - Computer and Systems Sciences. Volume: Distributed Transaction Processing and the Camelot System. In Distributed Operating Systems: Theory and Practice, Yakup Paker, Ed., Springer-Verlag, 1987. Also available as Carnegie-Mellon Report CMU-CS-87-100, January 1987..
	22	Thacker, C.P., et al. Alto: A personal computer. In Computer Structures: Rea&'ngs and Examples, McGraw-Hi!l, 1980. Edited by D. Siewiorek, C.G. Bell, and A. Newell, second edition..
	23	Wulf, W.A., Levin, R., and Harbison, S.P.. Hydra/C.rmnp: An Experimental Computer System. McGraw-Hill, 1981.
	24	Edward R. Zayas, The use of copy-on-reference in a process migration system, 1987

CITED BY 64

	C.-D. Jung , E. Siberrt, Polling in concurrent programming, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.204-209, February 21-23, 1989, Louisville, Kentucky
	K. Kahn , Vijay A. Saraswat, Actors as a special case of concurrent constraint (logic) programming, ACM SIGPLAN Notices, v.25 n.10, p.57-66, Oct. 1990
	Jeff Chase , Valérie Issarny , Hank Levy, Distribution in a single address space operating system, Proceedings of the 5th workshop on ACM SIGOPS European workshop: Models and paradigms for distributed systems structuring, September 21-23, 1992, Mont Saint-Michel, France
	John Zahorjan , Cathy McCann, Processor scheduling in shared memory multiprocessors, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.214-225, May 1990
	Douglas Z. Pan , Mark A. Linton, Supporting reverse execution for parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.124-129, Jan. 1989
	Kieran Harty , David R. Cheriton, Application-controlled physical memory using external page-cache management, ACM SIGPLAN Notices, v.27 n.9, p.187-197, Sept. 1992
	D. R. Cheriton , H. A. Goosen , P. D. Boyle, Multi-level shared caching techniques for scalability in VMP-M/C, ACM SIGARCH Computer Architecture News, v.17 n.3, p.16-24, June 1989
	Eric Cooper , Scott Nettles , Indira Subramanian, Improving the performance of SML garbage collection using application-specific virtual memory management, ACM SIGPLAN Lisp Pointers, v.V n.1, p.43-52, Jan. 1992
	E. Abrossimov , M. Rozier , M. Shapiro, Generic virtual memory management for operating system kernels, ACM SIGOPS Operating Systems Review, v.23 n.5, p.123-136, Dec. 3–6, 1989
	Mohit Aron , Jochen Liedtke , Kevin Elphinstone , Yoonho Park , Trent Jaeger , Luke Deller, The sawmill framework for virtual memory diversity, Australian Computer Science Communications, v.23 n.4, p.3-10, January 2001
	Nicholas Carriero , David Gelernter, How to write parallel programs: a guide to the perplexed, ACM Computing Surveys (CSUR), v.21 n.3, p.323-357, Sep. 1989
	D. L. Black , R. F. Rashid , D. B. Golub , C. R. Hill, Translation lookaside buffer consistency: a software approach, ACM SIGARCH Computer Architecture News, v.17 n.2, p.113-122, April 1989
	W. Bolosky , R. Fitzgerald , M. Scott, Simple but effective techniques for NUMA memory management, ACM SIGOPS Operating Systems Review, v.23 n.5, p.19-31, Dec. 3–6, 1989
	Jeffrey S. Chase , Henry M. Levy , Edward D. Lazowska , Miche Baker-Harvey, Lightweight shared objects in a 64-bit operating system, ACM SIGPLAN Notices, v.27 n.10, p.397-413, Oct. 1992
	Theodore H. Romer , Wayne H. Ohlrich , Anna R. Karlin , Brian N. Bershad, Reducing TLB and memory overhead using online superpage promotion, ACM SIGARCH Computer Architecture News, v.23 n.2, p.176-187, May 1995
	Bob Wheeler , Brian N. Bershad, Consistency management for virtually indexed caches, ACM SIGPLAN Notices, v.27 n.9, p.124-136, Sept. 1992
	D. R. Cheriton , A. Gupta , P. D. Boyle , H. A. Goosen, The VMP multiprocessor: initial experience, refinements, and performance evaluation, ACM SIGARCH Computer Architecture News, v.16 n.2, p.410-421, May 1988
	David K. Gifford , Nathan Glasser, Remote pipes and procedures for efficient distributed communication, ACM Transactions on Computer Systems (TOCS), v.6 n.3, p.258-283, Aug. 1988
	B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, ACM SIGOPS Operating Systems Review, v.29 n.5, p.267-283, Dec. 3, 1995
	Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989
	Michael Fry, Practical trade-offs for open interconnection, Proceedings of the 1992 ACM annual conference on Communications, p.1-8, March 03-05, 1992, Kansas City, Missouri, United States
	Jeffrey S. Chase , Henry M. Levy , Michael J. Feeley , Edward D. Lazowska, Sharing and protection in a single-address-space operating system, ACM Transactions on Computer Systems (TOCS), v.12 n.4, p.271-307, Nov. 1994
	Gideon Glass , Pei Cao, Adaptive page replacement based on memory reference behavior, ACM SIGMETRICS Performance Evaluation Review, v.25 n.1, p.115-126, June 1997
	B. Rosenburg, Low-synchronization translation lookaside buffer consistency in large-scale shared-memory multiprocessors, ACM SIGOPS Operating Systems Review, v.23 n.5, p.137-146, Dec. 3–6, 1989
	Thomas E. Anderson , Henry M. Levy , Brian N. Bershad , Edward D. Lazowska, The interaction of architecture and operating system design, ACM SIGPLAN Notices, v.26 n.4, p.108-120, Apr. 1991
	Keith Krueger , David Loftesness , Amin Vahdat , Thomas Anderson, Tools for the development of application-specific virtual memory management, ACM SIGPLAN Notices, v.28 n.10, p.48-64, Oct. 1, 1993
	Mendel Rosenblum , John Chapin , Dan Teodosiu , Scott Devine , Tirthankar Lahiri , Anoop Gupta, Implementing efficient fault containment for multiprocessors: confining faults in a shared-memory multiprocessor environment, Communications of the ACM, v.39 n.9, p.52-61, Sept. 1996
	Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, ACM SIGPLAN Notices, v.27 n.9, p.175-186, Sept. 1992
	Jochen Liedtke, Toward real microkernels, Communications of the ACM, v.39 n.9, p.70-77, Sept. 1996
	Karsten Schwan , Win Bo, “Topologies”—distributed objects on multicomputers, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.111-157, May 1990
	Richard P. Draves , Brian N. Bershad , Richard F. Rashid , Randall W. Dean, Using continuations to implement thread management and communication in operating systems, ACM SIGOPS Operating Systems Review, v.25 n.5, p.122-136, Oct. 1991
	Steven M. Hand, Self-paging in the Nemesis operating system, Proceedings of the third symposium on Operating systems design and implementation, p.73-86, February 1999, New Orleans, Louisiana, United States
	Richard Rashid , Avadis Tevanin, Jr. , Michael Young , David Golub , Robert Baron, Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures, IEEE Transactions on Computers, v.37 n.8, p.896-908, August 1988
	Chris Bentley , Scott A. Watterson , David K. Lowenthal , Barry Rountree, Implicit java array bounds checking on 64-bit architecture, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Richard Rashid , Avadis Tevanian , Michael Young , David Golub , Robert Baron, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures, ACM SIGARCH Computer Architecture News, v.15 n.5, p.31-39, Oct. 1987
	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
	Lanfranco Lopriore, Access Control Mechanisms in a Distributed, Persistent Memory System, IEEE Transactions on Parallel and Distributed Systems, v.13 n.10, p.1066-1083, October 2002
	Gernot Heiser , Volkmar Uhlig , Joshua LeVasseur, Are virtual-machine monitors microkernels done right?, ACM SIGOPS Operating Systems Review, v.40 n.1, p.95-99, January 2006
	Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , Nathan C. Burnett , Timothy E. Denehy , Thomas J. Engle , Haryadi S. Gunawi , James A. Nugent , Florentina I. Popovici, Transforming policies into mechanisms with infokernel, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
	Jeff Chase , Valérie Issarnay , Hank Levy, Distribution in a single address space operating system, ACM SIGOPS Operating Systems Review, v.27 n.2, p.61-65, April 1993
	Michael D. Kupfer, Sprite on Mach, Proceedings of the 3rd conference on USENIX MACH III Symposium, p.7-7, April 19-21, 1993, Santa Fe, New Mexico
	Paul J. Roy, Unix file access and caching in a multicomputer environment, Proceedings of the 3rd conference on USENIX MACH III Symposium, p.1-1, April 19-21, 1993, Santa Fe, New Mexico
	Douglas P. Ghormley , David Petrou , Steven H. Rodrigues , Thomas E. Anderson, SLIC: an extensibility system for commodity operating systems, Proceedings of the Annual Technical Conference on USENIX Annual Technical Conference, 1998, p.4-4, June 15-19, 1998, New Orleans, Louisiana
	Yasushi Saito , Brian Bershad, A transactional memory service in an extensible operating system, Proceedings of the Annual Technical Conference on USENIX Annual Technical Conference, 1998, p.5-5, June 15-19, 1998, New Orleans, Louisiana
	Chris Bentley , Scott A. Watterson , David K. Lowenthal , Barry Rountree, Implicit array bounds checking on 64-bit architectures, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.4, p.502-527, December 2006
	Andrew Whitaker , Richard S. Cox , Marianne Shaw , Steven D. Grible, Constructing services with interposable virtual hardware, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.13-13, March 29-31, 2004, San Francisco, California
	Steven Hand , Andrew Warfield , Keir Fraser , Evangelos Kotsovinos , Dan Magenheimer, Are virtual machine monitors microkernels done right?, Proceedings of the 10th conference on Hot Topics in Operating Systems, p.1-1, June 12-15, 2005, Santa Fe, NM
	Bennet Yee , J. D. Tygar, Secure coprocessors in electronic commerce applications, Proceedings of the 1st conference on USENIX Workshop on Electronic Commerce, p.14-14, July 11-12, 1995, New York, New York
	Pei Cao , Edward W. Felten , Kai Li, Application-controlled file caching policies, Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, p.11-11, June 06-10, 1994, Boston, Massachusetts
	William J. Bolosky , Scott Corbin , David Goebel , John R. Douceur, Single instance storage in Windows® 2000, Proceedings of the 4th conference on USENIX Windows Systems Symposium, p.2-2, August 03-04, 2000, Seattle, Washington
	Matthew J. Zekauskas , Wayne A. Sawdon , Brian N. Bershad, Software write detection for a distributed shared memory, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.8-es, November 14-17, 1994, Monterey, California
	Drew Major , Greg Minshall , Kyle Powell, An overview of the NetWare operating system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.27-27, January 17-21, 1994, San Francisco, California
	Chao-Hsien Lee , Meng Chang Chen , Ruei-Chuan Chang, HiPEC: high performance external virtual memory caching, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.12-es, November 14-17, 1994, Monterey, California
	Carlos Maltzahn , Kathy J. Richardson , Dirk Grunwald, Reducing the disk I/O of web proxy server caches, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.17-17, June 06-11, 1999, Monterey, California
	David R. Cheriton , Kenneth J. Duda, A caching model of operating system kernel functionality, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.14-es, November 14-17, 1994, Monterey, California
	Gaurav Banga , Jeffrey C. Mogul , Peter Druschel, A scalable and explicit event delivery mechanism for UNIX, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.19-19, June 06-11, 1999, Monterey, California
	Mark Sullivan , Michael Stonebraker, Using Write Protected Data Structures To Improve Software Fault Tolerance in Highly Available Database Management Systems, Proceedings of the 17th International Conference on Very Large Data Bases, p.171-180, September 03-06, 1991
	Cui-Qing Yang, Distributed computing in a NUMP (Non-Uniform Message-Passing) environment, ACM SIGOPS Operating Systems Review, v.26 n.2, p.82-91, April 1992
	M. Rasit Eskicioglu, A comprehensive bibliography of distributed shared memory, ACM SIGOPS Operating Systems Review, v.30 n.1, p.71-96, Jan. 1996
	Ming-Chit Tam , Jonathan M. Smith , David J. Farber, A taxonomy-based comparison of several distributed shared memory systems, ACM SIGOPS Operating Systems Review, v.24 n.3, p.40-67, July 1990
	Alberto R. Cunha , Carlos N. Ribeiro , José A. Marques, The architecture of a memory management unit for object-oriented systems, ACM SIGARCH Computer Architecture News, v.19 n.4, p.109-116, June 1991
	Jochen Liedtke , Ulrich Bartling , Uwe Beyer , Dietmar Heinrichs , Rudolf Ruland , Gyula Szalay, Two years of experience with a &mgr;-Kernel based OS, ACM SIGOPS Operating Systems Review, v.25 n.2, p.51-62, April 1991
	Jonathan Appavoo , Dilma Da Silva , Orran Krieger , Marc Auslander , Michal Ostrowski , Bryan Rosenburg , Amos Waterland , Robert W. Wisniewski , Jimi Xenidis , Michael Stumm , Livio Soares, Experience distributing objects in an SMMP OS, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.6-es, August 2007
	Neal H. Walfield , Marcus Brinkmann, A critique of the GNU hurd multi-server operating system, ACM SIGOPS Operating Systems Review, v.41 n.4, July 2007