Monitor classification

ABSTRACT

One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for systems with shared memory, is the monitor. Over the past twenty years many kinds of monitors have been proposed and implemented, and many modern programming languages provide some form of monitor for concurrency control. This paper presents a taxonomy of monitors that encompasses all the extant monitors and suggests others not found in the literature or in existing programming languages. It discusses the semantics and performance of the various kinds of monitors suggested by the taxonomy, and it discusses programming techniques suitable to each.

REFERENCES

• 1: J. M. Adams , A. P. Black, On proof rules for monitors, ACM SIGOPS Operating Systems Review, v.16 n.2, p.18-27, April 1982 [doi>10.1145/1041474.1041476]
• 2: ADAMS, J. M., AND BLACK, A. P. 1983. Letter to the editor. Oper. Syst. Rev. 17, i (Jan.), 6-8.
• 3: Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983 [doi>10.1145/356901.356903]
• 4: Gregory R. Andrews, Concurrent programming: principles and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 5: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 6: BRINCH HANSEN, P. 1975. The programming language concurrent pascal. IEEE Trans. Softw. Eng. 2 (June), 199--206.
• 7: BUHR, P. A., ANn STROOBOSSCHER, R.A. 1990. The /~System: Providing lightweight concurrency on shared-memory multiprocessor computers running UNIX. Softw. Pract. Exper. 20, 9 (Sept.), 929-963.
• 8: P. A. Buhr , Glen Ditchfield , R. A. Stroobosscher , B. M. Younger , C. Robert Zarnke, &mgr;C++: concurrency in the object-oriented language C++, Software—Practice & Experience, v.22 n.2, p.137-172, Feb. 1992 [doi>10.1002/spe.4380220204]
• 9: Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
• 10: CARDELLI, L., DONAHUE, J., GLASSMAN, L., JORDAN, M., KALSOW, B., AND NELSON, G. 1988. Modula-3 report. Tech. Rep. 31, Systems Research Center, Pale Alto, Calif.
• 11: David R. Cheriton, The Thoth System, Elsevier Science Inc., New York, NY, 1982
• 12: David Cheriton, The V distributed system, Communications of the ACM, v.31 n.3, p.314-333, March 1988 [doi>10.1145/42392.42400]
• 13: P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
• 14: Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
• 15: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 16: FORTT~.R, M. 1989. Study of monitors. Master's thesis, Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ont.
• 17: GENTLEMAN, W.M. 1985. Using the harmony operating system. Tech. Rep. 24685, National Research Council of Canada, Ottawa.
• 18: GOSLING, J., ROSENTHAL, D. S. H., AND ARDEN, R. J. 1989. The NeWS Book. Springer Verlag, New York.
• 19: GRIES, D. 1981. The Science of Computer Programming. Springer Verlag, New York.
• 20: HANSEN, P. B. 1981a. The design of Edison. Softw. Pract. Exper. 11, 4 (Apr.), 363-396.
• 21: HANSEN, P.B. 1981b. Edison--a multiprocessor language. Softw. Pract. Exper. 11, 4 (Apr.), 325-361.
• 22: HANSEN, P. B. 1981c. Edison programs. Softw. Pract. Exper. 11, 4 (Apr.), 397-414.
• 23: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 24: Richard C. Holt , James R. Cordy, The Turing programming language, Communications of the ACM, v.31 n.12, p.1410-1423, Dec. 1988 [doi>10.1145/53580.53581]
• 25: HOLT, R.C. 1992. Turing Reference Manual, 3rd ed. Holt Software Associates, Inc.
• 26: John H. Howard, Proving monitors, Communications of the ACM, v.19 n.5, p.273-279, May 1976 [doi>10.1145/360051.360079]
• 27: John H. Howard, Signaling in monitors, Proceedings of the 2nd international conference on Software engineering, p.47-52, October 13-15, 1976, San Francisco, California, United States
• 28: John H. Howard, Reply to "on proof rules for monitors", ACM SIGOPS Operating Systems Review, v.16 n.4, p.8-9, October 1982 [doi>10.1145/850726.850727]
• 29: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 30: J. L. W. Kessels, An alternative to event queues for synchronization in monitors, Communications of the ACM, v.20 n.7, p.500-503, July 1977 [doi>10.1145/359636.359710]
• 31: Butler W. Lampson , David D. Redell, Experience with processes and monitors in Mesa, Communications of the ACM, v.23 n.2, p.105-117, Feb. 1980 [doi>10.1145/358818.358824]
• 32: MITCHELL, J. G., MAYBURY, W., AND SWEET, R. 1979. Mesa language manual. Tech. Rep. CSL-79-3, Xerox Pale Alto Research Center.
• 33: Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 34: Rajendra K. Raj , Ewan Tempero , Henry M. Levy , Andrew P. Black , Norman C. Hutchinson , Eric Jul, Emerald: a general-purpose programming language, Software—Practice & Experience, v.21 n.1, p.91-118, Jan. 1991 [doi>10.1002/spe.4380210107]
• 35: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Simulation

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures; Control structures
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion; Concurrency; Synchronization; Scheduling

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Languages, Performance

Keywords:
classification, monitors