Final Solutions

22C:116, Fall 1997

Douglas W. Jones

Overall final score distribution

Median = 65              X
                         X X
                         X X X X   X X X   X     X     X
_____X_X_________X_X___X_X_X_X_X_X_X_X_X___X_X___X_X___X_____
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
5                   6                   7
 - - - C C C C + + + - - - B B B B + + + - - - A A A A + + +

Final exam score distribution

    Median = 15.0            X
                             X   X         X
                        XX   X   XX  XXXX  X
    ______________X_____XX_XXX___XX__XXXXX_XXXX__________________
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
                        1                   2

Solutions

  1. Part A: Is the Amoeba age and touch mechanism for reclamation formally correct? No! It is quite easy to construct examples where an object ages and is deleted while some user retains the capability to access that object.

    Part B: Is this mechanism leak free? Assuming that a server periodically remembers to age all of its objects, yes, all garbage will eventually be reclaimed.

  2. The UNIX file system maintains, in the I-node of every file, a count of the number of links (pointers) to that file from various directories. The file will be retained so long as this reference count field is greater than zero, and it will be deleted as soon as the reference count reaches zero. This rule guarantees formal correctness, but it does not guarantee that the UNIX file system is leak free.

    Recall that the UNIX command "ln x y" creates a new link named "y" for a preexisting file reached by the name "x", and that the UNIX command "rm x" deletes the link named "x". Recall also that each directory contains a link to itself, named "." and a link to its parent, named ".."; the "mkdir" and "rmdir" commands maintain these structures.

    Part A: Why, under UNIX, must "rm" and "ln" be restricted, so that "rm" may not be used to delete the link to a directory? Because the directory will not be reclaimed until the reference count reaches zero, and the . link of the directory and the .. links of its children will prevent an unreachable directory from being reclaimed if rm were allowed to simply delete the link to the directory. In contrast, rmdir assures that no .. links to a directory exist, then deletes the . link, then deletes the link to the directory, allowing the reference count to properly reach zero so the directory will be reclaimed.

    Why is it that "ln" may not be used to create a link to a directory? Because freely allowing users to create a link to any directory to any other directory would allow users to create arbitrarily constructed cycles in the graph of links, and these cycles would circular linkages that rmdir could not remove. As a result, unreclaimable and unreachable directories could accumulate and fill the file system.

    Part B: If UNIX used a mark-sweep garbage collector to reclaim unreachable files instead of the reference count algorithm outlined above, would your answer to part A be different? Absolutely! A mark-sweep collector would remove any unreachable file or directory, so there would be no limit on the use of ln to create arbitrarily complex linkages, nor would there be limits on the use of rm to delete arbitrary links.

  3. If your primary concern is efficient implementation of deadlock detection algorithms, which enforcement mechanism would be preferable, and why? Deadlock detection algorithms require knowledge of who may unblock any any given blocked process. Access control lists explicitly list who may access a resource. If processes are resources, then the ACL for a process would list all processes that could unblock that process.

    In contrast, with capability lists, the of finding all users who could do something is difficult -- the set of capabilities held by each and every user must be scanned to find who has capabilities for the indicated resource.

  4. Part A: Describe a deadlock detection protocol appropriate for this system. It was given that a single-resource model is applicable, so the problem reduces to one of figuring out how to map this system to a single resource model.

    On an attempt to read or write an object, if that object is locked in such a way that the read or write must block, the user can be sent a message saying wait. The user, after waiting a modest interval, can initiate deadlock detection by sending a probe message to the locked object.

    On receiving a probe, a locked object forwards the probe to the process that holds the lock. If the object isn't locked, it sends a reply to the originator of the probe saying no deadlock.

    On receiving a probe, a blocked process (or the agent of the process, or the kernel hosting that process) forwards the probe to the object on which the process is blocked. If the process is not blocked, it replies to the originator of the probe saying no deadlock.

    Termination in case of deadlock requires that each probe carry with it some identification. Either each process or object receiving a probe must retain a record of the probes it has received, in order to recoginze that this probe has already been there before, or each probe must carry a record of all processes and objects it has visited, to allow recognition of multiple visits. In either case, when it is detected that a probe has visited some process or object twice, the probe is discarded and a message is returned to the originator of the probe saying deadlock.

    On receipt of a notice of deadlock, a process aborts the current transaction. (4.0 points)

    Part B: Addressing messages to actual user process participating in the protocol would cause problems if those processes are blocked. It is unlikely that a blocked process could receive a probe and act on it, since it is not currently running and able to do so.

    If probes are addressed to the agents of processes instead of to those processes themselves, replies are practical. Similarly, the system hosting a process could itself act as the agent for probe handling, although this is rare!

  5. Part A: Here is a proposed fault handler illustrating the handling of non-page objects.
    	page fault handler
    	    -- given va = virtual address, with field va.page and va.word
    	    -- given pc = user's pc at the time of the fault
    	    if page_table[va.page].type = page_object
    		-- handle fault as a normal page fault
    	    else if page_table[va.page].type = dequeue_object
    		-- this fault involves a dequeue
    		instr = *pc;
    		if is_load_instruction_at(instr)
    		    if va.word = 0
    			t = dequeue_head( va.page );
    			simulate_load_instr(instr,t);
    			pc = pc + 1;
    		    else if va.word = 1
    			t = dequeue_tail( va.page );
    			simulate_load_instr(instr,t);
    			pc = pc + 1;
    		    else if va.word = 2
    			t = get_dequeue_size( va.page );
    			simulate_load_instr(instr,t);
    			pc = pc + 1;
    		    else
                            error
                        endif
                    else if is_store_instruction_at(instr)
                        if va.word = 0
                            enqueue_head( va.page, simulate_store_instr(instr,t) );
                            pc = pc + 1;
                        else if va.word = 1
                            enqueue_tail( va.page, simulate_store_instr(instr,t) );
                            pc = pc + 1;
                        else
                            error
                        endif
                    else
    		    error
    		endif
    	    else
    		... other object types?
                endif
    	return
    
    

    Part B: A reasonable set of operations on capability lists, as a class of non-page objects, would be:

    Either the software would maintain, parallel to every loadable register, a capability register, so that load and store operations could move capabilities from list to list, or the software would deliver capabilities to the user in the normal data registers, but in cryptographically protected form.

    This solution is predicated on the idea that each capability list is fixed size, holding a number of capabilities no greater than the number of bytes per page.

    The next problem to address is how the user can put one of these capabilities into the virtual address map itself, allowing addressing of the object referenced by the capability. Here are two solutions: Either we could, by convention, make page zero of each address space be a reference to the capability list representing that address space, or we could add new supervisor calls to allow a user to insert a capabilty into a designated slot in the address space. If address spaces are large, the former solution is cleaner. If they are small, so that each slot is precious, the latter would be preferable.

    Part C: I'd use jump(A+n) to transfer control from the current domain to the domain modeled by capability n in the capability list at A in my address space.

    I'd use call(A+n) to do a procedure-call like transfer from the current domain to the destination, delivering a capability to the destination that could be used to re-enter the calling domain.

  6. What services would you expect from a minimal process manager? The object types are process and semaphore. Processes are never explicitly manipulated. Semaphores are explicitly manipulated.