Evaluating synchronization mechanisms

ABSTRACT

In recent years, many high-level synchronization constructs have been proposed. Each claims to satisfy criteria such as expressive power, ease of use, and modifiability. Because these terms are so imprecise, we have no good methods for evaluating how well these mechanisms actually meet such requirements. This paper presents a methodology for performing such an evaluation. Synchronization problems are categorized according to some basic properties, and this categorization is used in formulating more precise definitions of the criteria mentioned, and in devising techniques for assessing how well those criteria are met.

REFERENCES

• 1: Andler, S., "Synchronization Primitives and the Verification of Concurrent Programs", Dept. of Computer Science, Carnegie-Mellon University, Pittsburgh, Pa., May 1977.
• 2: Andler, S., Private communication, May, 1978.
• 3: Atkinson, R., and C. Hewitt, "Synchronization and Proof Techniques for Serializers", IEEE Transactions on Software Engineering, (5, 1), Jan. 1979.
• 4: Atkinson, R., Private communication.
• 5: T. Bloom, SYNCHRONIZATION MECHANISMS FOR MODULAR PROGRAMMING LANGUAGE, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 6: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 7: 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
• 8: 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]
• 9: Dijkstra, E.W., "Cooperating Sequential Processes", Programming Languages, (F. Genuys, ed.), Academic Press, N.Y. 1968.
• 10: L. Flon , A. N. Habermann, Towards the construction of verifiable software systems, Proceedings of the 1976 conference on Data : Abstraction, definition and structure, p.141-148, March 22-24, 1976, Salt Lake City, Utah, United States
• 11: Habermann, A.N., "Path Expressions", Dept. of Computer Science, Carnegie-Mellon University, Pittsburgh, Pennsylvania, June 1975.
• 12: Bruce K. Haddon, Nested monitor calls, ACM SIGOPS Operating Systems Review, v.11 n.4, p.18-23, October 1977 [doi>10.1145/850648.850650]
• 13: 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]
• 14: 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
• 15: M. S. Laventhal, SYNTHESIS OF SYNCHRONIZATION CODE FOR DATA ABSTRACTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 16: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 17: Liskov, B.H., "An Introduction to CLU", Computation Structures Group Memo 136, Laboratory for Computer Science, M.I.T., Cambridge, Mass., Feb. 1976.
• 18: Andrew Lister, The problem of nested monitor calls, ACM SIGOPS Operating Systems Review, v.11 n.3, p.5-7, July 1977 [doi>10.1145/850644.850645]
• 19: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 20: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Performance, Verification