Final Exam

22C:116, Spring 2002

Douglas W. Jones

Please write your answers on the paper provided. Make sure your name is on the front page, in the same form as it appears in the official class list! Illegible and overly long answers are very difficult to grade. Please leave margins around your answers!

This exam is open-book, open-notes, closed neighbor!

NOTE: Essentially all questions on this test can be answered in one short paragraph or less! There are no long essay questions here! Stop and think before writing at any length!

This exam is worth 30 points (30/100 of the final grade) and you have 2 hours; each part of each question is 2 points, so plan on spending no more than 8 minutes each.

Background: Several of the questions on this exam refer to the FinalOS 2002 microkernel. Relevant material is about FinalOS 2002 is provided with each question where it is required. Questions that do not explicitly reference FinalOS 2002 are intended to be answered without reference to this rather poor microkernel design.

  1. Background: Consider a 32-bit machine with a paged segmented address space and the usual 10-10-12 division of the virtual address, so that there are 4k bytes per page and 1K pages per segment. The page table for a segment under this MMU has identically the same structure as the segment table for the address space. Each entry in either of these tables is 32 bits. The most significant 20 bits are a frame number in physical memory (either a pointer to a page or a pointer to the page table for a segment) and the least significant 4 bits are access rights (read, write, execute and valid, in that order).

    Usually, we assume that the memory manager runs in real memory, with the MMU turned off. Suppose, instead, that the memory manager runs as a separate server process with the MMU turned on. In order to allow the memory manager to manipulate physical memory, the segment table for the memory manager has a very strange entry for segment 1023. The access rights bits of segment 1023 are read-write-valid, and the pointer to the page table for segment 1023 points to the segment table itself.

    Part A: Give the virtual address, in the address space of the memory manager, of the page table entry for page 1022 of segment 1023, and give the virtual address of the segment table entry for segment 1022. The self reference in entry 1023 of the segment table guarantees that these addresses exist! (2 points)

    Part B: Given the physical address pa of a word of memory, outline how the memory manager could create va, an address in its virtual address space that is mapped to pa. Assume that segment 1022 and also page 1022 of segment 1023 are available as scratch areas for such efforts. (2 points)

    Part C: Does the memory management server using the tools you have outlined need to run in privileged state? Does the answer depend on some aspect of the architecture? (Consider the problems posed by alternative MMU implementations, for example, those that work from a page-table purely in RAM versus those that maintain some kind of TLB.) (2 points)

  2. Background: One proposed process management model for FinalOS 2002 has the call operation suspend the calling thread (with the suspension stored in the return object) and launches a new thread in the called domain). The state of each thread is completely stored in its return object. The return operation, applied to a return object, enters the associated thread back into the ready list. The return object of a suspended thread holds the parameters it passed at the time it was suspended, and the values to be returned when it is reawakened.

    Part A: In the original FinalOS 2002 specification, the user was able to manipulate all 1024 words of a return object (the kernel constrains 16 to hold capabilities, and it allows 1008 to hold conventional binary data). The above new information requires that some part of the return object be set aside for use by the system, with no user access allowed, ever. Explain the reason for this.

    Part B: The original FinalOS 2002 specificaiton did not include a parameter passing mechanism; in it, the capability for the return object that was passed to the called object offered only one access right, return. Why didn't we give the called object read-write access to the return object? (hint: There was a security problem.) (2 points)

    Part C: Suppose the author of a FinalOS 2002 server makes a programming error that leads to an infinite loop. For every iteration of this loop, the server makes a protected call to itself. What eventually causes this loop to terminate? (2 points)

    Part D: As described in this problem, are FinalOS 2002 threads kernel threads or are they user threads. What in the information hou have been given suggests one model over the other? (2 points)

  3. Background: Consider the following two alternative server designs:

    Domain = Class
    if we equate the concept of domain with the concept of class, and we assume one process per domain, then the server is a process and any requiest for an operation on a file involves this process. There are good reasons to make this a multithreaded process, but all threads execute in the same domain. All objects of each class are stored in the same domain.

    Domain = Object
    if we equate the concept of domain with the concept of object, then creation of a new object creates a new domain, and operations on that object involve entry to that domain. In this case, there is much less reason to use multithreaded processes, and the representations of each object are protected from each other by being in separate domains.

    Part A: Consider the Demos microkernel, where messages are addressed to links, where each link is a capability that names a process and a mailbox of that process. Demos can be used to implement a server using either of the above models, but there is something about the design of Demos that strongly suggests the use of one model and discourages the use of the other. Which model is preferred under Demos, what special support is provided for this model, and what is the penalty would be paid for using the other model? (2 points)

    Part B: Consider the FinalOS 2002 microkernel, where the call operation names a domain and passes parameters to that domain. Can both models be used under this microkernel? What prevents the use of one or the other model? (2 points)

  4. Background: You have been hired by to develop the system software for a highly secure multicomputer system by KaliTronics, a major arms manufacturer. They have concluded that FinalOS 2002 is the ideal microkernel for this project.

    Part A: What particular problem is posed by the FinalOS 2002 kernel in the context of a multicomputer? (2 points)

    Part B: Suppose there is a client-side application on one machine and a server on another machine, where the client needs to call the server, and wishes to do so using a FinalOS 2002 protected interdomain call. What does the caller actually use as a capability for the server? (Hint: How do you hide the use of an RPC protocol from its users.) (2 points)

    Part C: What special problems would the client-side and server-side stubs have in passing parameters across the network for the multicomputer version of FinalOS 2002? (2 points)

  5. Background: WORM-based file systems begin with all sectors of the disk set to 11111, and the only permitted write operations convert one bits to zero; once set to zero, a bit of the WORM can never be set back to one.

    As in most conventional disk-based file systems, most WORM-based file system designs support a directory tree. File names are paths through this tree from the root.

    Part A: Finding the root of the directory tree on a WORM-based file system is harder than on a conventional (read-write disk-based) file system! Demonstrate your understanding of this difficulty by giving an example solution to the problem of finding the root of the directory tree on a WORM based system. (2 points)

    Part B: With a WORM-based file system, it is not difficult to add a variant of the open() service that takes a date and opens a file for read access, giving the file as it appeared on that date. Describe a mechanism that permits this. (Hint: Your solution to Part A may be useful here!) (2 points)

    Part C: With a conventional file system, it is reasonable to expect that each write operation will be immediately recorded on disk. Why is this a bad idea with a WORM-based file system? (Hint: Consider your solutions to parts A and B.) (2 points)