Midterm Study Questions

22C:116, Fall 2000

Not Due Friday Oct 6, 2000

Study Subject: DreadcOS is an operating system designed for use on any machine with a paged MMU. The access rights associated with each page of the virtual address space are:

read

Data may be read from this page during an instruction fetch or an operand fetch.

write

Data may be stored in this page by an operand store.

read-c

Capabilities may be read from this page by the get-c system call.

write-c

Capabilities stored in this page by the put-c system call.

enter

The enter system call may be used with this page.

Each virtual address space is itself represented by a capability list, where each page of the virtual address space is represented by one capability. The operations on a virtual address space are:

get_c(a,b)

put_c(a,b)

Given a, the address of a page in the user's virtual address space, a is the index of a capability a' in the C-list representing the user's virtual address space. Given b, a memory address that references a page holding a C-list, interpret the word-in-page field of b as refering to a specific capability b' in that C-list. Put copies a' to b'; get copies b' to a'.

enter(a)

Given a, the address of a page in the user's virtual address space, If that page has enter rights, then the state of the user process is saved in page 0 of the current address space, and then the capability list held in page a becomes the current address space of the process and the state of the process is restored from page 0 of this new address space.

1. This system does not contain any mechanisms for passing parameters on domain entry. Can you propose several mechanisms that could be added to this system, any of which would solve this problem?

   Recall that the CPU state is completely loaded from page 0 of the new domain as a side effect of enter, so registers cannot be used to pass parameters. Recall that the complete load of the CPU state on entry to a new domain erases any record of a stack pointer, and that the stack, if any, would have existed in pages of the address space of the old domain.

2. This system does not contain any mechanisms for allowing a domain to operate as a function. Can you think of any mechanisms that would allow this? Consider passing an enter cap for the calling domain as a parameter to the called domain as one solution. Are there other solutions?

3. What is the natural page size on this system, assuming that an address space is 4 gigabytes, that memory is byte addressable, and that capabilities are 64 bits each (8 bytes).

   This question is fully specified! The 4 gigabyte byte-addressable address space sets the number of bits in the memory address. The fact that capabilities are exactly 8 bytes each determines, for any given page size, the number of capabilities that will fit in the page. If all entries in the C-list describing the address space point to pages, there must be a total of 4 gigabytes. Therefore, the product of the page size times the number of capabilities in a C-list must be 4 gigabytes. Finally, the fact that each C-list is constrained to occupy exactly one page sets the final constraint.

   In the event that the exact solution has a page size that is not a power of two bytes long, obviously, you'll have to round things in such a direction that it allows addressing at least 4 gigabytes but no more than 8 gigabytes.

4. On this system, must we allocate one address space per process, or is it possible to support multiple processes within an address space.

   Recall that, on entry to a domain, the CPU state is loaded from page 0 of the new domain, and recall that, whenever a process is suspended, its process state is saved in page 0 of the domain.

5. It is useful to think in terms of two useful operations for forming virtual addresses:

   address(p,b) = (p << log2(bytes_per_page)) + b

   composes a viurtual address from p, a page number in the current address space, and b, a byte number within that page.

   address_c(p,c) = address(p, c << log2(bytes_per_capability))

   composes a viurtual address from p, a page number in the current address space, and c, a capability number within that page.

   Passing familiarity with this set of operations may be useful during the exam.