Final Exam Solutions and Commentary

22C:116, Spring 2002

Douglas W. Jones

Score Distribution

Median = 11.0              X
Mean   = 12.1              X
                   X X     X                     X
   ________X_______X_X___X_X_________X___________X_______X__________
     0 . . . . 5 . . . . 10. . . . 15. . . . 20. . . . 25. . . . 30

Solutions

  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. 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!

    Because of the self-reference, the main segment table is also the page table for segment 1023. Therefore, the page table entry for page 1022 of segment 1023 is identically the same word of memory as the segment table entry for segment 1022. This word is at virtual addrss:
    		   1023   |   1023   |   1022   | 0
    		1111111111 1111111111 1111111110 00
    	
    This problem had nothing to do with FinalOS 2002, but it was based on the first study question! Given this, it was shocking that only one student figured out that the two parts of the question asked for same address, and only 4 got one or the other address correctly!

    Half the class got no credit at all. Most made the same mistake -- they gave the virtual address of the segment and the virtual address of the page instead of the virtual address of the page table entry or the segment table entry.

    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.

    Here is a solution in C:
    	#define segno(addr)  (((addr) >> 22) & 0x3FF)
    	#define pageno(addr) (((addr) >> 12) & 0x3FF)
    	#define byteno(addr) (((addr)      ) & 0xFFF)
    	#define makeva(seg,page,byte) ((seg << 22)|(page << 12)|(byte))
    
    	*makeva( 1023, 1023, 4088 )
    		= makeva( segno(pa), pageno(pa), rights );
    	va = makeva( 1023, 1022, byteno(pa) );
    	
    Nobody came up with anything close to this. Most people wrote long-winded English text, and in this text, it was possible to discern a germ of a workable solution in 5 cases; these earned partial credit. The remainder received no credit.

    A remarkable number set out to describe some kind of search of the page and segment tables for an entry that describes the desired page. This will not work reliably, it ignores the connection to part A (page 1022 of segment 1023) and it is computationally awful!

    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.)

    Given the tools outlined above, the memory management server process can run in user mode, with no privilege. This assumes that the MMU data structures are all in main memory! If the MMU contains a TLB or other cache, we need a way to invalidate or update a cache entry prior to using the address computed in part B. This may require privilege.

    Two did well here, 4 got half credit or better, and 5 more got some credit for the right conclusion based on the wrong reasoning. The remainder got no credit.

    One common way to arrive at a wrong answer was by backward reasoning: The memory management server runs with the MMU turned on. The MMU is turned off in privileged state. Therefore, the memory management unit does not need privilege. This is false, and in fact, the second premise is false (true, some systems have a single privilege bit that enables the MMU, but some have far more complex systems of privilege, and it is dangerous to draw general conclusions from simplified architectural examples!)

  2. Background: One proposed process management model for FinalOS 2002 has the call operation suspend the calling thread and launch 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.

    If the return object itself holds the entire state of each thread, this includes things like the thread's priority and whether or not the thread is allowed to exeucte privileged instructions. There might even be link fields used by the kernel for linking the thread into various lists. Clearly, these should not be generally manipulable.

    6 did well here, while 2 has a basic understanding but did not understand the severity of the threat to the system posed by general access to the thread state by the thread itself. Several of those who had trouble were seriously concerned that a thread should have any access to its own state. This is puzzling, because most of the state of a program is inherently open to manipulation by that program -- the program counter, general registers, and private variables are all part of the state of a thread. Only certain parts are special!

    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.)

    If the called object has read-write access to the state of the caller, it may arbitrarily inspect and corrupt any of the caller's registers. But if one of the capability registers of the caller refers to the entire address space, the domain of the caller, the threat is even larger, because the called routine is given access everything in the caller's domain. In sum, this destroys what would have been a nice solution to the mutual suspicion problem.

    8 did well here, 6 more got partial credit for an answer equivalent to the first sentence above -- they did not appear to understand the seriousness of the problem. Only a few received no credit.

    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?

    If each call launches a new thread, and each thread requires the allocation of a return object that occupies one page frame, this loop will eventually consume all available page frames, allocating them to hold return objects. If our virtual memory mechanism can store these outside of main memory, we will consume the entire swap space before the loop finally terminates.

    9 did well here, while 6 did poorly. There was little partial credit.

    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?

    These are kernel threads because the kernel is launching threads when there is a call.

    6 did well here. 5 more drew the correct conclusion from the wrong reasons to earn some partial credit.

  3. Background: Consider the following two alternative server designs:
    Domain = Class
    Domain = Object

    Part A: 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?

    Which model is preferred? Demos is designed to favor storing all instances of a class in the same domain.

    What special support is there for this? The fact that a link is a capability, holding process ID and box number fields allows this. The process ID names the process implementing the class, while the box number names the instance of the class stored in the domain of that process.

    What is the penalty for using the other model? If we allocated a new domain for each object, we would have one Demos process per object. Demos processes cannot share code, therefore we would have to replicate the entire code for each class in each instance of that class. We can only afford this for classes with very little code or with very few instances.

    Only 2 did well here. 3 explained did not explain the penalty for using one domain per object, one more did this and also gave a poor explanation of the support for multiple objects in a domain, and 2 more merely asserted that Demos favors one domain per class, with no explanation. Half the class received no credit.

    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?

    Can both models be used under FinalOS 2002? No! This system effectively requires that each object be represented by a distinct domain.

    What prevents the use of one or the other model? Capabilities in FinalOS 2002 name only the domain, not the domain and some additional item that can be used to name an object in that domain. Therefore, we cannot have multiple objects per domain. On the other hand, FinalOS 2002 makes it easy to share code between domains, so all objects of a class can easily share everything but a few pages and C-lists unique to the object itself.

    Nobody answered both parts of this question well. 2 had ideas that they explained clearly but that did not lead to secure implementations of protected objects. 2 had weak explanations, and 4 merely said object=domain without giving a clear explanation. The majority earned no credit.

  4. Background: You have been hired by to develop the system software for a highly secure multicomputer system, using FinalOS 2002.

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

    FinalOS 2002 capabilities encapsulate memory addresses, so they can refer only to objects in one physical memory address space.

    2 did well here. 4 got reasonable partial credit by focusing on parameter passing across calls while failing to identify the overall problem. 2 focused prematurely on remote procedure calls, earning half credit while avoiding coming to grips with the issues. 3 focused on the return object itself, avoiding the issues even more while earning some credit.

    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?

    The caller has a capability for the local agent of the remote server. The local agent acts as an RPC stub for the call.

    4 did well here, 2 more were slightly penalized for abuse of technical terminology. 7 earned partial credit for discussion of RPC mechanisms without a clear relationship to FinalOS 2002/

    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?

    In general, capability parameters cause problems. If a capability parameter gives execute-only access to a C-list, we could create an agent object or RPC stub for that C-list on the remote machine. For execute-only return objects, we can do something similar. For read-only pages, we can copy the data. For read-write pages and for C-lists, obvious solutions are hard to find!

    2 did well here. 5 more understood that pointer parameters were difficult in the context of RPCs, but did not relate this to FinalOS 2002. 5 earned half credit with fine grained focus on some small part of the problem but no general answer.

  5. 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.
    Because it is a WORM, we cannot store the root in a fixed sector such as a superblock. Instead, everytime the root changes, we must store the root in a new place. If we put a distinctive mark in the sector used for the root, and if sectors are allocated sequentially, we could first look in the sector allocation table to see which sector is the last one used, then search backward from the last one used to find the most recent version of the root.

    Or, if there is a field in the root that is reserved for the sector number of a newer version of the root, this field would be 11111 in the current root, and we would overwrite it with the sector number of the replacement when we create a new root. This way, the search for the root would begin with the oldest version and search through a list of successively newer versions.

    3 did well, 3 more gave poor explanations, and 2 more were at least on the track to understanding the problem. It was very dissapointing that the remainder of the class was dominated by those who imagined a field of the superblock that pointed to the root directory, as in a conventional magnetic disk.

    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!)

    We must record the effective date for each version of the root. Given this, the operation of opening a file as it was at some time will first search for the root that was in effect at that time, and then open the file found by searching from that root. We may also need to date directory entries if directories can grow without changing the root, so that, in each directory we search for the entry that was effective at the required time.

    2 did well here, 1 more gave apoor explanation, and 6 suggested inherently faulty ideas that were worthy of partial credit.

    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?

    With a WORM file system, each write will consume new space on the storage medium. As a result, if each write is done immediately instead of being written to cache and only written to the WORM later, we will consume space on the WORM very quickly!

    2 gave good answers, and 2 more focused on the need to consolidate writes to each sector, implying that they understood the problem while only speaking of the solution. 4 more got less credit by delving into low level details of one possible solution.