Capability-based addressing

ABSTRACT

Various addressing schemes making use of segment tables are examined. The inadequacies of these schemes when dealing with shared addresses are explained. These inadequacies are traced to the lack of an efficient absolute address for objects in these systems. The direct use of a capability as an address is shown to overcome these difficulties because it provides the needed absolute address. Implementation of capability-based addressing is discussed. It is predicted that the use of tags to identify capabilities will dominate. A hardware address translation scheme which never requires the modification of the representation of capabilities is suggested. The scheme uses a main memory hash table for obtaining a segment's location in main memory given its unique code. The hash table is avoided for recently accessed segments by means of a set of associative registers. A computer using capability-based addressing may be substantially superior to present systems on the basis of protection, simplicity of programming conventions, and efficient implementation.

REFERENCES

• 1: B. W. Arden , B. A. Galler , T. C. O'Brien , F. H. Westervelt, Program and Addressing Structure in a Time-Sharing Environment, Journal of the ACM (JACM), v.13 n.1, p.1-16, Jan. 1966 [doi>10.1145/321312.321313]
• 2: Batson, A., et al. Measurements of segment size. Proc. 3rd Syrup. on Operating Systems Principles. Stanford U., Oct. 1971, 25-29.
• 3: A. Bensoussan , C. T. Clingen , R. C. Daley, The Multics virtual memory: concepts and design, Communications of the ACM, v.15 n.5, p.308-318, May 1972 [doi>10.1145/355602.361306]
• 4: Daniel M. Berry, Introduction to Oregano, ACM SIGPLAN Notices, v.6 n.2, February 1971 [doi>10.1145/1115880.1115887]
• 5: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 6: Burroughs Corporation. Burroughs B5500 Information processing systems reference manual. Detroit, Mich., 1964.
• 7: Burroughs Corporation. The descriptor--a definition of the B5000 information processing system. Detroit, Mich., 1961.
• 8: Cleary, J.G. Process handling on Burroughs B6500. Proc. Fourth Australian Comp. Conf., Adelaide, South Australia, 1969, pp. 231-239.
• 9: Cosserat, D.C. A capability oriented multi-processor system for real-time applications. Presented at the I.C.C. Conf., Washington, D.C., Oct. 1972, 8 pp.
• 10: Cotton, J.M. The operational requirements for future communications control processors. Presented at lnternat. Switching Symp., Cambridge, Mass., June 6-9, 1972, 5 pp.
• 11: 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]
• 12: Daley, R.C., and Neumann, P.G. A general purpose file system for secondary storage. Proc. AFIPS 1965 FJCC, Vol. 27, Pt. I., AFIPS Press, Montvale, N.J., pp. 213-230.
• 13: Dennis, J.B. Programming generality, parallelism and computer architecture. Proc. IFIP 1968, North Holland, Amsterdam, pp. CI-7.
• 14: 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]
• 15: 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]
• 16: England, D.M. Architectural features of System 250. In Infotech State of the Art Report or Operating Systems, 1972, 12 pp.
• 17: England, D.M. Operating System of System 250. Presented at Internat. Switching Symp., Cambridge, Mass., June 6-9, 1972, 5 pp.
• 18: Evans, D.C., and LeClerc, J.Y. Address mapping and the control of access in an interactive computer. Proc. AFIPS 1967 SJCC, Vol. 30, AFIPS Press, Montvale, N.J., pp. 23-32.
• 19: Fabry, R.S. A user's view of capabilities. ICR Quart. Rep. 15 (Nov. 1967), ICR, U. of Chicago, Sec. IC.
• 20: Fabry, R.S. Preliminary description of a supervisor for a machine oriented around capabilities. ICR Quart. Rep. 18 (Aug. 1968), ICR, U. of Chicago, Sec. lB.
• 21: Fabry, R.S. List-structured addressing. Ph.D. Th., U. of Chicago, 1971.
• 22: Feustal, E.A. The Rice research computer--a tagged architecture. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J. pp. 369-377.
• 23: Feustal, E.A. On time advantages of tagged architecture. IEEE Trans. on Computers C-22, 7 (July 1973), 644-656.
• 24: Graham, G.S., and Denning, P.J. Protection--principles and practice. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J., pp. 417-429.
• 25: Halton, D. Hardware of the System 250 for communication control. Presented at the lnternat. Switching Syrup., Cambridge, Mass., June 6-9, 1972, 7 pp.
• 26: Hamer-Hodges, K.J. Fault resistance and recovery within System 250. Presented at I.C.C. Conf., Washington, D.C., Oct. 1972, 6 pp.
• 27: Iliffe, J.K. Basic maehhw principles. American Elsevier, New York, 1968.
• 28: Iliffe, J.K., and Jodeit, J.G. A dynamic storage allocation scheme. Comput. J. 5 (Oct. 1962), 200-209.
• 29: Jones, A.K. Protection structures. Ph.D. Th., Carnegie- Mellon U., 1973.
• 30: Lampson, B.W. On reliable and extendable operating systems. In Techniques in Software Engineering, NATO Science Committee Workshop Material, Vol. 11, Sept. 1969.
• 31: Lampson, B.W. Dynamic protection structures. Proc. AFIPS 1969 FJCC, Vol. 35, AFIPS Press, Montvale, N.J., pp. 27-38.
• 32: Lampson, B.W. Protection. Proc. 5th Ann. Princeton Conf., Princeton U., Mar. 1971, pp. 437-443.
• 33: Jean-Yves Leclerc, Memory structures for interactive computers, 1966
• 34: Needham, R.M. Protection systems and protection implementations. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 571-578.
• 35: Elliott Irving Organick, Computer system organization: The B5700/B6700 series (ACM monograph series), Academic Press, Inc., Orlando, FL, 1973
• 36: Elliott I. Organick, The Multics System: An Examination of Its Structure, The MIT Press, 1972
• 37: J. H. Saltzer, TRAFFIC CONTROL IN A MULTIPLEXED COMPUTER, Massachusetts Institute of Technology, Cambridge, MA, 1966
• 38: Michael D. Schroeder, Performance of the GE-645 associative memory while Multics is in operation, Proceedings of the SIGOPS workshop on System performance evaluation, p.227-245, January 1971 [doi>10.1145/800024.808361]
• 39: Schroeder, M.D. Cooperation of mutually suspicious subsystems in a computer utility. Ph.D. Th., MIT, 1972.
• 40: Sevick, K.C., et al. Project SUE as a learning experience. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N. J., pp. 331-339.
• 41: Shepherd, J. Principal design features of the multi-computer. (The Chicago Magic Number Computer). ICR Quart. Rep. 19 (Nov. 1968), 1CR, U. of Chicago, Sec. 1-C.
• 42: Sturgis, H.E. A postmortem of a time sharing system. Ph.D. Th., U. of California, Berkeley, 1973.
• 43: M. V. Wilkes, Time Sharing Computer Systems, Elsevier Science Inc., New York, NY, 1975
• 44: Wilner, W.T. Design of the Burroughs BI700. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 489-497.
• 45: Wilner, W.T. Burroughs BI700 memory utilization. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 579- 586.
• 46: Wulf, W.A., et al. HYDRA: The kernel o f a multiprocessor operating system. Carnegie Mellon U., Comput. Sci. Dep. rep., June 1973.
• 47: Yngve, V.H. The Chicago Magic Number Computer. ICR Quart. Rep. 18 (Nov. 1968), ICR, U. of Chicago, Sec. 1-B.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Keywords:
addressing, addressing hardware, capabilities, computer utility, information sharing, operating systems, protection, protection hardware, segmentation, shared addresses, tagged architecture