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. ACM 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. ACM 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. ACM 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. ACM 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 R. Stockton Gaines Systems 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 February 1980 of Volume 23 the ACM Number 21. 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 inter- network message transmission, which are heavy users of concurrency; our experience with some of these appli- cations is discussed