Acknowledgments The authors wish to thank Prof Nico Habermann whose comments concerning both the operating system and this paper have been extremely helpful Received June 1979 accepted September 1979 revised November 1979 References 1 Baskett F Howard J H and Montague J T Task communication in DEMOS Proc 6th Symp Operating Systems Principles SIGOPS 1977 pp 23 32 2 Bell G C and Newell A Computer Structures Readings and Examples McGraw Hill New York 1971 3 Cheriton D R Malcolm M A Melen L S and Sager G R Thoth a portable real time operating system Comm A C M 22 2 Feb 1979 105 114 4 Cohen E and Jefferson D Protection in the Hydra operating system Proc 5th Symp Operating Systems Principles SIGOPS 1975 pp 141 160 5 Denning P J Fault tolerant operating systems Comput Surv 8 4 Dec 1976 359 389 6 Fuller S H Jones A K Durham I Eds Cm Review June 1977 Carnegie Mellon Univ June 1977 7 Fuller S H Ousterhout J K Raskin L Rubinfeld P Sindhu P S and Swan R J Multi microprocessors An overview and working example Proc IEEE 66 2 1978 216 228 8 Goodenough J B Exception handling Issues and a proposed notation Comm A C M 18 12 Dec 1975 683 696 9 Habermann A N Flon L and Cooprider L Modularization and hierarchy in a family of operating systems Comm A CM 19 5 May 1976 266 272 10 Jones A K Chansler R J Jr Durham I Feiler P and Schwans K Software management of Cm A distributed multiprocessor Proc AFIPS 1977 NCC Vol 46 AFIPS Press Arlington Va 1977 pp 657 663 il Jones A K Chansler R J Jr Durham I Feiler P Scelza D A Schwans K and Vegdahl S R Programming issues raised by a multiprocessor Proc IEEE 66 2 1978 229 237 12 Jones A K et al StarOS a multiprocessor operating system for the support of task forces Proc 7th Symp Operating Systems Principles SIGOPS 1979 pp 117 127 13 Jones A K and Schwans K TASK forces Distributed software for solving problems of substantial size 4th Int Conf Software Eng SIGSOFT 1979 pp 315 330 14 Jones A K Protection in programmed systems Ph D Th Carnegie Mellon Univ Pittsburgh Pa 1973 15 Lauer H C and Needham R M On the duality of operating system structures Proc 2nd Int Symp Operating Systems 1RIA 1978 Reprinted in Operating Syst Rev 13 2 April 1979 3 19 16 Levin R Program structures for exceptional condition handling Ph D Th Carnegie Mellon Univ Pittsburgh Pa June 1977 17 Liskov B and Snyder A Structured exception handling Lab for Computer Science M I T Cambridge Mass March 1979 18 Parnas D L On the criteria to be used in decomposing systems into modules Comm A C M 15 12 Dec 1972 1053 1058 19 Raskin L Performance evaluation of multiple processor systems Ph D Th Carnegie Mellon Univ Pittsburgh Pa Aug 1978 20 Ritchie D M and Thompson K The UNIX time sharing system Comm A C M 17 7 July 1974 365 375 21 Saltzer J H and Schroeder M D The protection of information in computer systems Proc IEEE 63 9 1975 1278 1308 22 Schroeder M D Clark D D and Saltzer J H The Multics kernel design project Proc 6th Symp Operating Systems Principles SIGOPS 1977 pp 43 56 23 Sutherland I E and Mead C A Microelectronics and computer science Sci Amer 237 3 Sept 1977 210 229 24 Swan R J The switching structure and addressing architecture of an extensible multiprocessor Cm Ph D Th Carnegie Mellon Univ Pittsburgh Pa Aug 1978 25 Swan R J Bechtolsheim A Lai K and Ousterhout J K The implementation of the Cm multi microprocessor Proc AFIPS 1977 NCC Vol 46 AFIPS Press Arlington Va 1977 pp 645 655 26 Swan R J Fuller S H and Siewiorek D P Cm A modular multi microprocessor Proc AFIPS 1977 NCC Vol 46 AFIPS Press Arlington Va 1977 pp 637 644 105 Operating Systems R Stockton Gaines Editor Experience with Processes and Monitors in Mesa Butler W Lampson Xerox Palo Alto Research Center David D Redell Xerox Business Systems The use of monitors for describing concurrency has been much discussed in the literature When monitors are used in real systems of any size however a number of problems arise which have not been adequately dealt with the semantics of nested monitor calls the various ways of defining the meaning of WAIT priority scheduling handling of timeouts aborts and other exceptional conditions interactions with process creation and destruction monitoring large numbers of small objects These problems are addressed by the facilities described here for concurrent programming in Mesa Experience with several substantial applications gives us some confidence in the validity of our solutions Key Words and Phrases concurrency condition variable deadlock module monitor operating system process synchronization task CR Categories 4 32 4 35 5 24 Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage the ACM copyright notice and the title of the publication and its date appear and notice is given that copying is by permission of the Association for Computing Machinery To copy otherwise or to republish requires a fee and or specific permission A version of this paper was presented at the 7th ACM Symposium on Operating Systems Principles Pacific Grove Calif Dec 10 12 1979 Authors present address B W Lampson and D D Redell Xerox Corporation 3333 Coyote Hill Road Palo Alto CA 94304 1980 ACM 0001 0782 80 0200 0105 00 75 Communications of the ACM February 1980 Volume 23 Number 2 1 Introduction In early 1977 we began to design the concurrent programming facilities of Pilot a new operating system for a personal computer 18 Pilot is a fairly large program itself 24 000 lines of Mesa code In addition it must support a variety of quite large application programs ranging from database management to internetwork message transmission which are heavy users of concurrency our experience with some of these applications is discussed later in the paper We intended the new facilities to be used at least for the following purposes Local concurrent programming An individual application can be implemented as a tightly coupled group of synchronized processes to express the concurrency inherent in the application Global resource sharing Independent applications can run together on the same machine cooperatively sharing the resources in particular their processes can share the processor Replacing interrupts A request for software attention to a device can be handled directly by waking up an appropriate process without going through a separate interrupt mechanism e g a forced branch Pilot is closely coupled to the Mesa language 17 which is used to write