George Mason University

CS491 Great Principles Fall 2002

Design Problem D3 (10 points)

Due 10/28/02

Read the essay Before memory was virtual linked to the resources section of the CS491 web page. Also look at the Art of OS slides about storage systems. This problem will focus on capability addressing, discussed in both readings. NOTE: the essay refers to a two-level mapping scheme for capabilities and the slides to a three-level scheme. The slides are counting the translation from symbols in user programs to virtual addresses as the first level; the essay does not count this level. The other two levels are the same. In this assignment, we'll use the terminology of the essay.

(1) The main benefits of capability addressing are object sharing (the ability to share objects by sharing capabilties for them) and location transparency (the ability to move an object without having to chance anything in any capability pointing to it). Capability addressing uses a two-level mapping scheme to achieve this. Outline the mapping scheme and show that it achieves these two objectives.

(2) Write out pseudo-code for the algorithm in the MMU (memory mapping unit) of a capability addressing system. Make sure your code deals with a TLB (translation looksaside buffer) and various fault conditions that can be encountered when translating an object address (from a task's address space) to a memory address.

(3) Suppose that the system only supports a one-level mapping from an object (segment) number in user address space to to the (base,limit) values of the memory region containing the object. Describe this mapping scheme. How can users share an object with this scheme? What must be done if the object is moved in memory (to a new base-limit region)?

(4) In the 1970s, hardware machines were built for capabilities. These machines used the hardware to guarantee that capabilities could not be altered by users. Users could share capabilities by making copies, but they could not modify the capabilities. This permitted capabilities to be treated as access tickets. If you had a capability, it was assumed that you had the right to access the object. Owners would give out capabilities only to those the owner wanted to share with. Discuss possible methods for handling these basic actions of an access control system: (a) creating capability, (b) protecting it from modification, (c) granting a capability with less access than the owner has, and (d) revoking a capability.

(5) Speculate on why we don't see capability hardware machines any more. In spite of that, where have the concepts of capability addressing survived to this day? Why would you classify capability addressing as a great principle?