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?