Experience with Processes and Monitors in Mesa 1Experience with Processes and Monitors in Mesa1Butler W. LampsonXerox Palo Alto Research CenterDavid D. RedellXerox Business SystemsAbstractThe use of monitors for describing concurrency has been much discussed in the literature. Whenmonitors are used in real systems of any size, however, a number of problems arise which havenot been adequately dealt with: the semantics of nested monitor calls; the various ways ofdefining the meaning of WAIT; priority scheduling; handling of timeouts, aborts and otherexceptional conditions; interactions with process creation and destruction; monitoring largenumbers of small objects. These problems are addressed by the facilities described here forconcurrent programming in Mesa. Experience with several substantial applications gives us someconfidence in the validity of our solutions.Key Words and Phrases: concurrency, condition variable, deadlock, module, monitor, operatingsystem, process, synchronization, taskCR Categories: 4.32, 4.35, 5.241. IntroductionIn early 1977 we began to design the concurrent programming facilities of Pilot, a new operatingsystem for a personal computer [18]. Pilot is a fairly large program itself (24,000 lines of Mesacode). In addition, it must support a variety of quite large application programs, ranging fromdatabase management to inter-network message transmission, which are heavy users ofconcurrency; our experience with some of these applications is discussed later in the paper. Weintended the new facilities to be used at least for the following purposes:Local concurrent programming. An individual application can be implemented as a tightlycoupled group of synchronized processes to express the concurrency inherent in theapplication. 1 This paper appeared in Communications of the ACM 23, 2 (Feb. 1980), pp 105-117. An earlier version waspresented at the 7th ACM Symposium on Operating Systems Principles, Pacific Grove, CA, Dec. 1979. This versionwas created from the published version by scanning and OCR; it may have errors.Permission to copy without fee all or part of this material is granted provided that the copies are not made ordistributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its dateappear, and notice is given that copying is by permission of the Association for Computing Machinery. To copyotherwise, or to republish, requires a fee and/or specific permission.Experience with Processes and Monitors in Mesa 2Global 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 bywaking up an appropriate process, without going through a separate interrupt mechanism (forexample, a forced branch).Pilot is closely coupled to the Mesa language [17], which is used to write both Pilot itself and theapplications programs it supports. Hence it was natural to design these facilities as part of Mesa;this makes them easier to use, and also allows the compiler to detect many kinds of errors in theiruse. The idea of integrating such facilities into a language is certainly not new; it goes back atleast as far as PL/1 [1]. Furthermore, the invention of monitors by Dijkstra, Hoare, and BrinchHansen [3, 5, 8] provided a very attractive framework for reliable concurrent programming.There followed a number of papers on the integration of concurrency into programminglanguages, and at least one implementation [4].We therefore thought that our task would be an easy one: read the literature, compare thealternatives offered there, and pick the one most suitable for our needs. This expectation provedto be naive. Because of the large size and wide variety of our applications, we had to address anumber of issues which were not clearly resolved in the published work on monitors. The mostnotable among these are listed below, with the sections in which they are discussed.(a) Program structure. Mesa has facilities for organizing programs into modules whichcommunicate through well-defined interfaces. Processes must fit into this scheme (seeSection 3.1).(b) Creating processes. A set of processes fixed at compile-time is unacceptable in such ageneral-purpose system (See Section 2). Existing proposals for varying the amount ofconcurrency were limited to concurrent elaboration of the statements in a block, in the styleof Algol 68 (except for the rather complex mechanism in PL/1).(c) Creating monitors. A fixed number of monitors is also unacceptable, since the number ofsynchronizers should be a function of the amount of data, but many of the details of existingproposals depended on a fixed association of a monitor with a block of the program text (seeSection 3.2).(d) WAIT in a nested monitor call. This issue had been (and has continued to be) the source of aconsiderable amount of confusion, which we had to resolve in an acceptable manner beforewe could proceed (see Section 3.1).(e) Exceptions. A realistic system must have timeouts, and it must have a way to abort a process(see Section 4.1). Mesa has an UNWIND mechanism for abandoning part of a sequentialcomputation in an orderly way, and this must interact properly with monitors (see Section3.3).(f) Scheduling. The precise semantics of waiting on a condition variable had been discussed [10]but not agreed upon, and the reasons for making any particular choice had not beenarticulated (see Section 4). No attention had been paid to the interaction between monitorsand priority scheduling of processes (see Section 4.3).Experience with Processes and Monitors in Mesa 3(g) Input-Output. The details of fitting I/O f vices into the framework of monitors and conditionvariables had not been fully worked out (see Section 4.2).Some of these points have also been made by Keedy [12], who discusses the usefulness ofmonitors in a modern general-purpose mainframe operating system. The Modula language [21]addresses (b) and (g), but in a more limited context than ours.Before settling on the monitor scheme described below, we considered other possibilities. Wefelt that our first task was to choose either shared memory (that is, monitors) or message passingas our basic interprocess communication paradigm.Message passing has been used (without language support) in a number of operating systems; fora recent proposal to embed