Final Solutions

22C:116, Fall 1998

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

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.
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:
- Replace a page -- the normal page-fault service.
- Force a virtual page-fault trap for the user.
- Force a virtual bus trap for the user.
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).

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.

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.
The study question outlining the design of an object oriented operating system omitted a number of important details, most notably:
- Object creation was not discussed
- Object destruction was not discussed
- Address space creation was not discussed
- Address space (capability list) manipulation was not discussed
- Process or thread management was not discussed
Two did well here, one in three received no credit.
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.

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.

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