New version page

UT CS 372 - Experience with Processes and Monitors in Mesa

Documents in this Course
MapReduce

MapReduce

17 pages

Processes

Processes

19 pages

MapReduce

MapReduce

17 pages

Load more

This preview shows page 1-2-22-23 out of 23 pages.

View Full Document
View Full Document

End of preview. Want to read all 23 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

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


View Full Document
Loading Unlocking...
Login

Join to view Experience with Processes and Monitors in Mesa and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Experience with Processes and Monitors in Mesa and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?