Final Solutions

22C:116, Fall 1998

Douglas W. Jones

Grade Distribution

Mean   = 15.8
Median = 15.4   X   X       X X
                X X X X     X X
______X___X_X___X_X_X_X_X_X_X_X_X___X_____X____
 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 

Solutions

  1. Part A:

    floating_point_error_trap_service_routine: -- UNIX
        save state of user process
        push user's signal mask on user's stack (as if it were a parameter)
        push SIGFPE on user's stack (as if it were a parameter)
        edit user's signal mask to block delivery of SIGFPE 
        push user's PC on user's stack (as if a call had been done)
        set user's PC to the address of the signal dispatcher
        restore state of user process
        return from trap
    
    We assume that the signal dispatcher is a bit of code in the user's address space that is something like the following:
        signal_dispatcher( int mask, int signal)
        {
    	(signal_vec[signal])();
    	setsigmask(mask);
        }
    
    This is needed so that the return from signal can automatically restore the signal mask that was saved when the signal was delivered. It assumes that signal_vec is an array of pointers to signal handlers.

    Half clearly understood the UNIX semantics, but only one gave a good description of the mechanism needed to implement this semantics. One in four received no credit. The most common error leading to partial credit was the assumtion that the trap handler can directly call the user's signal handler. In general, this cannot be done.

    Part B:

    floating_point_error_trap_service_routine: -- Mach
        save state of thread that caused trap
        block thread that caused trap
        formulate message describing the exception
        send message to the exception handler of the thread's process
        pick a ready thread to be the new current thread
        restore state of new thread
        return from trap
    
    Three in five clearly understood Mach semantics, and one in six gave good descriptions of a mechanism that would implement this semantics. One in four received no credit. The most common error was to focus on the exception handler that receives the message, as if the hardware itself sent the exception message.

    Part C:

    floating_point_error_trap_service_routine: -- VM
        save state of process that caused trap
        find process's virtual trap vector entry for floating point error trap
        save process's PC and virtual PSW as requried for virtual trap delivery
        set process's PC and virtual PSW from trap vector entry
        restore state of process that caused trap
        return from trap
    
    One in three clearly understood VM semantics, but only two gave good descriptions of mechanisms that would implement this semantics. One in five received no credit. One common error was to assume that VM could directly call the user's trap handler. Another common error was to assume that the trap handler needed to know whether the system was running on a real or virtual machine, or whether the user was running an operating system or a bare-machine application.

  2. Under IBM's VM operating system, the page fault trap handler may do one of the following in response to a trap request from the memory management unit: The trap handler decides between these options by inspecting the virtual address that caused the trap and the page table for the current user. If the virtual address was outside the bounds of the page table for the current user, or if the page table entry is marked as "unimplemented memory," the trap service routine forces a virtual bus trap for the user.

    If the page table entry is marked as "page is on disk", the trap service routine goes through the normal page replacement algorithm.

    If the page table entry is marked as "page not mapped to virtual address", the page fault service routine forces a virtual page-fault for the user.

    Two students got no dredit here, while around half proposed PSW-based decision algorithms, modelled after the pseudocode presented in class for VM's privileged instruction trap handler (see next question).

  3. privileged_instruction_trap_handler: -- VM
        save state of user process
        if user's virtual PSW indicates user virtual privileged mode
    	i = instruction that caused trap)
            emulate(i)
        else
            find process's virtual trap vector entry for privileged instruciton trap
            save process's PC and virtual PSW as requried for virtual trap delivery
            set process's PC and virtual PSW from trap vector entry
        endif
        restore state of user process
        return from trap
    
    Two in five did well here, almost as many got no credit at all. Common errors involved misreading the question, for example, by trying to write code for emulate(i), or assuming that the trap service routine could directly call the user's virtual trap service routine.

  4. An exception handler can be written so that exceptions raised in a Mach process will be handled to create VM-like semantics -- that is, so that attempts to execute privileged instructions will lead to either virtual privileged instruction traps or to emulation of the effects of these privileged instructions on the user's virtual machine. The only exception to this involves the instructions used to actually send messages under Mach. The Mach kernel must reserve at least two trapped instructions, one for receiving a message and one for sending a message, and these cannot be virtualized.

    Over half received no credit here, despite the fact that this question was lifted directly from the study questions. The wrong answers that were given ranged over a wide variety of topics, and only one really good answer was given.

  5. The study question outlining the design of an object oriented operating system omitted a number of important details, most notably: Two did well here, one in three received no credit.

  6. If the object oriented operating system suggested in the study question were to be used in a network environment, where a user on one machine should be able to manipulate objects on another machine, one way to expose the network to the users would be to use stub objects. Where a user has access to a remote object, this access would be expressed, on the local machine of that user, as a stub object that would encapsulate all of the network protocols used to access the remote object. When a user calls a method of the stub, this call would be translated to an RPC-like protocol communicating with a server-side stub process on the remote machine. The server-side stub process would then call the actual object before returning the results to the client stub.

    Most did well here, but two got no credit.

  7. Part A The trap service routine on our hypothetical object-oriented operating system can distinguish between unmapped pages and references to objects by using a software field in the virtual address map.

    Just under half had good answers here, while one in four got no credit. The most common error was to associate state information with the page itself (for example, reserving the first word of every page) instead of with the page-table entry.

    Part B

    page_fault_trap_service_routine:
        save state of calling thread
        va = virtual address that caused trap
        pte = page_table[ va.page ]
        if pte.type = object_reference
            block calling thread
            i = instruction at address va caller's address space
            -- assume i.opcode is either LOAD or STORE (the only mem ref instrs)
            create new thread in address space of object
    	make this thread the current thread
            push va.byte_in_page on stack of current thread (parameter)
            push i.operand_size on stack of current thread (parameter)
            if i.opcode = LOAD
    	    thread.pc = word 0 of current address space
            else i.opcode = STORE
    	    push user's register i.register on stack (parameter)
    	    thread.pc = word 1 of current address space
            endif
    	push -1 on stack (an invalid return address)
        else
            ... other possibilities ...
        endif
        return to current thread
    
    The above solution is overkill! One in eight did well here, One in four got no credit, and many either failed to do a context switch to the thread of the object or assumed that the trap service routine could directly call a method of this object.

  8. If each object spawns a new thread on method invocation, the code for each method of an object that may be shared by multiple users will have to directly address questions of mutual exclusion, but methods may allow parallel access to those parts of an object that don't raise interuser conflicts. If the system automatically serializes calls to methods of an object, then users need not write explicit code to deal with mutual exclusion, but users are denied many opportunities to exploit parallelism.

    One in five did well here, while one in six got no credit. Of those who got partial credit, a surprising number misread the question and emphasized the implementation of the semantics that were given instead of emphasizing the impact of this semantic choice on the resulting user code.

  9. -- user code
        state = "want in"
        wait( entry_sem )
        -- critical section
        state = "done"
        signal( done_sem )
    
    -- agent
        repeat
            await token
            if state = "want in"
                signal( entry_sem )
                wait ( done_sem )
            endif
            forward token
        forever
    
    This requires two semaphores and a two-valued variable.

    Half gave essentially the above (or a variation on this theme). One in six got no credit, while as many gave answers that were sufficiently vague that correctness was difficult to evaluate. This problem was lifted almost literally from a homework problem assigned earlier in the semester.

  10. An implementation of atomic transactions on this machine could use the two phase model of transactions, acquiring all locks before making any changes to any shared variables. Thus, the aborting of a user process that created a deadlock would not damage any shared objects. User code would typically package each attempt to perform a transaction as a process, so that it could be aborted without killing the user code, thus allowing the user code to try again.

    The update phase of each transaction could be implemented using pointer assignment. System failures may interrupt the sequence of assignments that mark the commit phase of a transaction, so all changes should be logged before the commit is attempted, and on system restart, the logs must be examined and compared with any data that persists through a failure.

    One in six did very well. One in three failed to address the issue of how to commit a transaction. Less common errors included failing to understand the appropriateness of the two-phase model to this system (typically proposing a client-server model) or premature lock release.