Continuation-based multiprocessing

ABSTRACT

Any multiprocessing facility must include three features: elementary exclusion, data protection, and process saving. While elementary exclusion must rest on some hardware facility (e.g. a test-and-set instruction), the other two requirements are fulfilled by features already present in applicative languages. Data protection may be obtained through the use of procedures (closures or funargs),and process saving may be obtained through the use of the CATCH operator. The use of CATCH, in particular, allows an elegant treatment of process saving. We demonstrate these techniques by writing the kernel and some modules for a multiprocessing system. The kernel is very small. Many functions which one would normally expect to find inside the kernel are completely decentralized. We consider the implementation of other schedulers, interrupts, and the implications of these ideas for language design.

REFERENCES

• 1: Russell Atkinson , Carl Hewitt, Synchronization in actor systems, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.267-280, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512975]
• 2: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 3: Per Brinch Hansen, The Architecture of Concurrent Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 4: Per Brinch Hansen, Distributed processes: a concurrent programming concept, Communications of the ACM, v.21 n.11, p.934-941, Nov. 1978 [doi>10.1145/359642.359651]
• 5: Alonzo Church, The Calculi of Lambda Conversion. (AM-6) (Annals of Mathematics Studies), Princeton University Press, Princeton, NJ, 1985
• 6: Dahl, O-J., and Hoare, C.A.R., "Hierarchical Program Structures," in Dahl, O-J., Dijkstra, E.W., and Hoare, C.A.R., Structured Programming, Academic Press, London, 1972, pp. 175-220.
• 7: Alan J. Demers , James E. Donahue, Data types, parameters and type checking, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-23, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567448]
• 8: Edsger W. Dijkstra, Letters to the editor: go to statement considered harmful, Communications of the ACM, v.11 n.3, p.147-148, March 1968 [doi>10.1145/362929.362947]
• 9: Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 10: Hewitt, C.E., "Viewing Control Structures as Patterns of Passing Messages," Artificial Intelligence 8 (1977), 323-364.
• 11: 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]
• 12: Holloway, J., Steele, G.L., Sussman, G.J., and Bell, A., "The SCHEME-79 Chip," MIT Art. Intell. Memo. No. 559 (Dec. 1979).
• 13: John S. James, FORTH for microcomputers, ACM SIGPLAN Notices, v.13 n.10, October 1978 [doi>10.1145/987508.987510]
• 14: P. J. Landin, Correspondence between ALGOL 60 and Church's Lambda-notation: part I, Communications of the ACM, v.8 n.2, p.89-101, Feb. 1965 [doi>10.1145/363744.363749]
• 15: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 16: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 17: Robert Milne , C. Strachey, A Theory of Programming Language Semantics, Halsted Press, New York, NY, 1977
• 18: Marvin Minsky, Form and Content in Computer Science (1970 ACM turing lecture), Journal of the ACM (JACM), v.17 n.2, p.197-215, April 1970 [doi>10.1145/321574.321575]
• 19: James H. Morris, Jr., Protection in programming languages, Communications of the ACM, v.16 n.1, p.15-21, Jan. 1973 [doi>10.1145/361932.361937]
• 20: John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970 [doi>10.1145/362349.362364]
• 21: John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
• 22: Alan C. Shaw, The Logical Design of Operating Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1974
• 23: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 24: Steele, G.L., and Sussman, G.J., "The Revised Report on SCHEME," MIT Art. Intell. Memo No. 452 (January, 1978).
• 25: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• 26: Wand, M., "SCHEME Version 3.1 Reference Manual," Indiana University Computer Science Department, Technical Report No. 93, June, 1980.
• 27: Wirth, N., "Modula: a Language for Modular Multiprogramming," Software - Practice and Experience 7 (1977), 3-35.
• 28: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Design, Languages, Performance