Using type-extension to organize virtual-memory mechanisms

ABSTRACT

Much effort is currently being devoted to producing computer systems that are easy to understand, to verify and to develop. The general methodology for designing such a system consists of decomposing it into a structured set of modules so that the modules can be understood, verified and developed individually, and so that the understanding/verification of the system can be derived from the understanding/verification of its modules. While many of the mechanisms in a computer system have been decomposed successfully into a structured set of modules, no technique has been proposed to organize the virtual memory mechanism of a system in such a way.The present paper proposes using type extension for that purpose. The virtaul memory mechanism consists of a set of type manager modules implementing abstract information containers. The structure of the mechanism reflects the structure of the containers that are implemented. While using type extension to organize a virtual memory mechanism is conceptually simple, it is hard to achieve in practice. All existing or proposed uses of type extension assume the existence of information containers that are uniformly accessible, can always be grown and are protected. Using type extension inside a virtual memory mechanism raises implementation problems since such containers are not implemented. Their implementation is precisely the objective of the virtual memory mechanism. In addition to explaining how type extension can be supported inside a virtual memory mechanism, the paper briefly discusses some aspects of its application to the reorganization of the kernal of a commercial, general-purpose, time-sharing system. It concludes by presenting some results of that case study concerning the organization of operating systems.

REFERENCES

• 1: 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]
• 2: Barbara H. Liskov, The design of the Venus operating system, Communications of the ACM, v.15 n.3, p.144-149, March 1972 [doi>10.1145/361268.361272]
• 3: Schiller, W. L. (republished May 1975), The Design and Specification of Security Kernel for the PDP-11/45. ESD-TR-75-69 and MTR-2934, Mitre Corporation.
• 4: Ames, S. R. (April 1975), The Design of a Security Kernel. M75-212 Mitre Corporation.
• 5: William Robert Price, Implications of a virtual memory mechanism for implementing protection in a family of operating systems, 1973
• 6: Saxena, A. R. (Jan. 1976), A Verified Specification of a Hierarchical Operating System. TR-107, Stanford Electronics Labs.
• 7: Butler W. Lampson , Howard E. Sturgis, Reflections on an operating system design, Communications of the ACM, v.19 n.5, p.251-265, May 1976 [doi>10.1145/360051.360074]
• 8: Neumann, P. G. et al. (June 1975, partly modified Dec. 1975), A Provably Secure Operating System, SRI Final Rep.
• 9: Liskov, B. H. (Feb. 1976), A Note on CLU. CSG Memo 136, Laboratory for Computer Science, M.I.T.
• 10: D. D. Redell. , David D. Redell, NAMING AND PROTECTION IN EXTENDABLE OPERATING SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 11: Anita Katherine Jones, Protection in programmed systems., 1973
• 12: W. Wulf , E. Cohen , W. Corwin , A. Jones , R. Levin , C. Pierson , F. Pollack, HYDRA: the kernel of a multiprocessor operating system, Communications of the ACM, v.17 n.6, p.337-345, June 1974 [doi>10.1145/355616.364017]
• 13: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• 14: Liskov, B. H. (1972), A Design Methodology for Reliable Software Systems. Proc. AFIPS FJCC, vol. 41, pp. 191--199.
• 15: Parnas, D. L. (March 1976), Some Hypotheses about the "Uses" Hierarchy for Operating Systems. Res. BS I 76/1, Tech. Hochschule Darmstadt, Fachbereich Informatik.
• 16: A. N. Habermann , Lawrence Flon , Lee Cooprider, Modularization and hierarchy in a family of operating systems, Communications of the ACM, v.19 n.5, p.266-272, May 1976 [doi>10.1145/360051.360076]
• 17: Parnas, D. L. (Aug. 1971), Information Distribution Aspects of Design Methodology. Proc. IFIP Congress, pp. 340--344.
• 18: Elliott I. Organick, The Multics System: An Examination of Its Structure, The MIT Press, 1972
• 19: Introduction to Multics. (Feb. 1974), MAC-TR-123, Laboratory for Computer Science, M.I.T.
• 20: Michael D. Schroeder , David D. Clark , Jerome H. Saltzer, The Multics kernel design project, Proceedings of the sixth ACM symposium on Operating systems principles, p.43-56, November 16-18, 1977, West Lafayette, Indiana, United States
• 21: P. A. Janson, USING TYPE EXTENSION TO ORGANIZE VIRTUAL MEMORY MECHANISMS, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 22: D. P. Reed, PROCESSOR MULTIPLEXING IN A LAYED OPERATING SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1976