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.
- 1 Arden, B.W., Galler, B.A., O'Brien, T.C., and Westervelt, F.H. Program and addressing structure in a time-sharing environment. J. ACM 13, 1 (Jan. 1966), 1-16.]] Google ScholarDigital Library
- 2 Batson, A., et al. Measurements of segment size. Proc. 3rd Syrup. on Operating Systems Principles. Stanford U., Oct. 1971, 25-29.]] Google ScholarDigital Library
- 3 Bensoussan, A., Clingen, C.T., and Daley, R.C. The MULTICS virtual memory: concepts and design. Comm. ACM 15, 5 (May 1972), 308-318.]] Google ScholarDigital Library
- 4 Berry, D.M. Introduction to Oregano. In J. Tou and P. Wegner (Eds.). Sigplan Notices--Proc. Symposium on Data Structures in Programming Languages, Vol. 6, No. 2, Feb. 1971, pp. 171-190.]] Google ScholarDigital Library
- 5 Bobrow, D.G., and Wegbreit, B. A model and stack implementation of multiple environments. Comm. ACM 16, l0 (Oct. 1973), 591-603.]] Google ScholarDigital Library
- 6 Burroughs Corporation. Burroughs B5500 Information processing systems reference manual. Detroit, Mich., 1964.]]Google Scholar
- 7 Burroughs Corporation. The descriptor--a definition of the B5000 information processing system. Detroit, Mich., 1961.]]Google Scholar
- 8 Cleary, J.G. Process handling on Burroughs B6500. Proc. Fourth Australian Comp. Conf., Adelaide, South Australia, 1969, pp. 231-239.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 11 Daley, R.C., and Dennis, J.B. Virtual memory, processes, and sharing in MULTICS. Comm. ACM l I , 5 (May 1968), 306-313.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 13 Dennis, J.B. Programming generality, parallelism and computer architecture. Proc. IFIP 1968, North Holland, Amsterdam, pp. CI-7.]]Google Scholar
- 14 Dennis, J.B. Segmentation and the design of multiprogrammed computer systems. J. ACM 12, 4 (Oct. 1965), 589-602.]] Google ScholarDigital Library
- 15 Dennis, J.B., and Van Horn, E.C. Programming semantics for multiprogrammed computations. Comm. ACM 9, 3 (Mar. 1966), 143-155.]] Google ScholarDigital Library
- 16 England, D.M. Architectural features of System 250. In Infotech State of the Art Report or Operating Systems, 1972, 12 pp.]]Google Scholar
- 17 England, D.M. Operating System of System 250. Presented at Internat. Switching Symp., Cambridge, Mass., June 6-9, 1972, 5 pp.]]Google Scholar
- 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.]]Google Scholar
- 19 Fabry, R.S. A user's view of capabilities. ICR Quart. Rep. 15 (Nov. 1967), ICR, U. of Chicago, Sec. IC.]]Google Scholar
- 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.]]Google Scholar
- 21 Fabry, R.S. List-structured addressing. Ph.D. Th., U. of Chicago, 1971.]]Google Scholar
- 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.]]Google Scholar
- 23 Feustal, E.A. On time advantages of tagged architecture. IEEE Trans. on Computers C-22, 7 (July 1973), 644-656.]]Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 27 Iliffe, J.K. Basic maehhw principles. American Elsevier, New York, 1968.]]Google Scholar
- 28 Iliffe, J.K., and Jodeit, J.G. A dynamic storage allocation scheme. Comput. J. 5 (Oct. 1962), 200-209.]]Google ScholarCross Ref
- 29 Jones, A.K. Protection structures. Ph.D. Th., Carnegie- Mellon U., 1973.]]Google Scholar
- 30 Lampson, B.W. On reliable and extendable operating systems. In Techniques in Software Engineering, NATO Science Committee Workshop Material, Vol. 11, Sept. 1969.]]Google Scholar
- 31 Lampson, B.W. Dynamic protection structures. Proc. AFIPS 1969 FJCC, Vol. 35, AFIPS Press, Montvale, N.J., pp. 27-38.]]Google Scholar
- 32 Lampson, B.W. Protection. Proc. 5th Ann. Princeton Conf., Princeton U., Mar. 1971, pp. 437-443.]]Google Scholar
- 33 LeClerc, J.Y. Memory structures for interactive computers. Project GENIE document No. 40.10.110, U. of California, Berkeley, 1966.]] Google ScholarDigital Library
- 34 Needham, R.M. Protection systems and protection implementations. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 571-578.]]Google Scholar
- 35 Organick, E.I. Computer System Organization--the B5700 B6700 Series. Academic Press, New York, 1973.]] Google ScholarDigital Library
- 36 Organick, E.I. Tile Multics System: An Examination of Its Structure. MIT Press, Cambridge, Mass., 1972.]] Google ScholarDigital Library
- 37 Saltzer, J.H. Traffic control in a multiplexed computer system. MAC-TR-30, Proj. MAC, MIT, Cambridge, Mass., 1966.]] Google ScholarDigital Library
- 38 Schroeder, M.D. Performance of the GE-645 associative memory while Multics is in operation. Proc. Workshop on System Performance Evaluation, Cambridge, Mass., 1971, pp. 227-245.]] Google ScholarDigital Library
- 39 Schroeder, M.D. Cooperation of mutually suspicious subsystems in a computer utility. Ph.D. Th., MIT, 1972.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 42 Sturgis, H.E. A postmortem of a time sharing system. Ph.D. Th., U. of California, Berkeley, 1973.]]Google Scholar
- 43 Wilkes, M.V. Time Sharing Computer Systems. 2nd ed., American Elsevier, New York, 1972.]] Google ScholarDigital Library
- 44 Wilner, W.T. Design of the Burroughs BI700. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 489-497.]]Google Scholar
- 45 Wilner, W.T. Burroughs BI700 memory utilization. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 579- 586.]]Google Scholar
- 46 Wulf, W.A., et al. HYDRA: The kernel o f a multiprocessor operating system. Carnegie Mellon U., Comput. Sci. Dep. rep., June 1973.]]Google Scholar
- 47 Yngve, V.H. The Chicago Magic Number Computer. ICR Quart. Rep. 18 (Nov. 1968), ICR, U. of Chicago, Sec. 1-B.]]Google Scholar
Index Terms
- Capability-based addressing
Recommendations
Hierarchical addressing scheme for 6LoWPAN WSN
This paper proposes a hierarchical addressing scheme for 6LoWPAN WSN and aims to reduce the addressing cost and latency. The proposed scheme includes the address initialization and address maintenance algorithms. When the network starts, the address ...
Addressing for 6LoWPAN WBAN
This paper makes a distinction between HoA and CoA, and proposes the addressing algorithms for HoA and CoA, respectively.The CoA addressing is achieved based on the HoA addressing, so the CoA addressing latency is shortened.A WBAN performs the HoA/CoA ...
A survey of addressing algorithms for wireless sensor networks
WiCOM'09: Proceedings of the 5th International Conference on Wireless communications, networking and mobile computingAddressing is an important research topic for wireless sensor networks (WSNs) because addressing makes it possible to guarantee basic levels of network communication, such as unicast. Addressing approaches focus on dynamic autoconfiguration of addresses ...
Comments