Process synchronization without long-term interlock

ABSTRACT

A technique is presented for replacing long-term interlocking of shared data by the possible repetition of unprivileged code in case a version number (associated with the shared data) has been changed by another process. Four principles of operating system architecture (which have desirable effects on the intrinsic reliability of a system) are presented; implementation of a system adhering to these principles requires that long-term lockout be avoided.

REFERENCES

• 1: Corbató, F. J., and Vyssotsky, V. A. Introduction and overview of the MULTICS system. Proc. AFIPS 1965 Fall Joint Comput. Conf., Vol. 27, Part 1. Spartan Books, New York, pp. 185-197.
• 2: Robert C. Daley , Jack B. Dennis, Virtual memory, processes, and sharing in MULTICS, Communications of the ACM, v.11 n.5, p.306-312, May 1968 [doi>10.1145/363095.363139]
• 3: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 4: Jack B. Dennis, Segmentation and the Design of Multiprogrammed Computer Systems, Journal of the ACM (JACM), v.12 n.4, p.589-602, Oct. 1965 [doi>10.1145/321296.321310]
• 5: Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
• 6: 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]
• 7: Evans, D. C., and LeClerc, J. Y. Address mapping and the control of access in an interactive computer. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30. Thompson Book Co., Washington, D. C., pp. 23-30.
• 8: Robert R. Fenichel, On implementation of label, variables, Communications of the ACM, v.14 n.5, p.349-350, May 1971 [doi>10.1145/362588.362597]
• 9: Gray, J. Locking. Record of the Project MAC conference on concurrent systems and parallel computation. ACM, New York, 1970, pp. 169-176.
• 10: Lampson, B. W. Dynamic protection structures. Proc. AFIPS 1969 Fall Joint Comput. Conf., Vol. 35. AFIPS Press, Montvale, New Jersey, pp. 27-38.
• 11: Butler W. Lampson, A scheduling philosophy for multiprocessing systems, Communications of the ACM, v.11 n.5, p.347-360, May 1968 [doi>10.1145/363095.363144]
• 12: J. H. Saltzer, TRAFFIC CONTROL IN A MULTIPLEXED COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1966
• 13: Jerome H. Saltzer , John W. Gintell, The instrumentation of multics, Communications of the ACM, v.13 n.8, p.495-500, Aug. 1970 [doi>10.1145/362705.362711]
• 14: Richard W Watson, Timesharing system design concepts (McGraw-Hill computer science series), McGraw-Hill Pub. Co., 1970

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Management