Homework 2 Solutions

22C:116, Fall 2000

Background:
Part A: Scan the PDP-8 manual pages on registers, memory management and interrupts in order to find all components of the CPU and MMU state that would need to be saved on behalf of one process while another is running. Document this state information, item by item.
The information that needs to be saved includes:
* PC the program counter
* AC the accumulator
* MQ the accumulator
* L the link bit
* IF the current instruction field
* DF the current data field
* GT the greater-than flag (possibly useless)
* U the user-mode (privilege) bit
There are several other bits of CPU state such as IE (interrupt enable) but these seem not to be part of process states. For example, all bits involved with enabling interrupts will always indicate interrupts enabled for ready processes, since a process only disables interrupts durring an interval when it cannot be preempted and must not relinquish.

Part B: Re-scan the first 5 sections of the manual, looking for the tools you would need to use to save and restore the components of the CPU state.
We'll use DCA to store the AC as the first instruction of interrupt service routines, and CLA/TAD to restore it just before return from interrupt. AC will usually not be saved across kernel calls that block a user process; instead, it will be used for parameter passing.
The interrupt or kernel call will save the PC, but then we'll have to use the sequence CLA/TAD/DCA to move the saved PC to an appropriate location in the process description record.
We'll use the sequences CLA/MQA/DCA and CLA/TAD/MQL to save and restore the MQ register.
We'll use the sequences GTF/DCA and CLA/TAD/RTF to save and restore the L, GT, U, IF and DF registers.

Part C: Suggest instruction sequences to be used for saving the process state on entry to the interrupt handler, and for restoring the process state on exit from the interrupt handler.
First, we assume that the interrupt handler has reserved locations in field zero to point to each component of the current process description record. Each component is prefixed with SAV, where the suffix names the component. The skeleton interrupt service routine would be:
```
Location    Value
 0000        -0-           /the return address
 0001        JMP   INTRPT  /goto interrupt service routine

     INTRPT, DCA I SAVAC   /save AC
             GTF
             DCA I SAVF    /save flags (IF,DF,L etc)
             MQA
             DCA I SAVMQ   /save MQ
             TAD   0
             DCA I SAVPC   /save PC

     --- body of interrupt service routine ---

             CLA
             TAD I SAVPC   /get PC (but don't restore)
             DCA   0
             TAD I SAVMQ   /get MQ
             MQL
             TAD I SAVAC   /get AC (but don't restore)
             DCA   TMP
             TAD I SAVF    /get flags
             RTF
             CLA
             TAD   TMP     /restore AC
             ION           /enable interrputs
             JMP I 0       /restores PC
```
This code is a bit tricky! Some instructions clear AC, some don't, and the restore of the flags doesn't change the real IF register; rather, that change only occurs when the JMP is executed. Similarly, the ION instruction doesn't enable interrupts, but rather, this takes place after the immediately following instruction, the JMP.

Part A: Write a naive parallel Quicksort, using the cobegin and coend primitives to parallelize the recursion, and assuming shared memory.

quicksort (int a, int b)
/* given a and b, bounds of the region of array to be sorted */
{
    if (a >= b) return;
    c = partition( a, b );
    cobegin
        quicksort( a, c );
        quicksort( c, b );
    coend;
}

Part B: Write a less naive version of Quicksort that counts the number of processes running and only creates new processes when there are CPUs to spare. When the set of CPUs is exhausted, it should run sequentially.

int processes = 1;

quicksort (int a, int b)
/* given a and b, bounds of the region of array to be sorted */
{
    if (a >= b) return;
    c = partition( a, b );
    if (processes++ < maxprocesses) {  -- atomic!
        cobegin
            quicksort( a, c );
            quicksort( c, b );
        coend;
        processes--;                   -- atomic!
    } else {
        quicksort( a, c );
        quicksort( c, b );
    }
}

In the above, we assumed that the ++ and -- operators are atomic, so that competing processes attempting to increment and decrement processes will not cause unexpected results.

Background: The Unix fork() primitive creates a child process and returns the process ID of the created process to the caller. The Unix wait() primitive waits for any child process to terminate and returns its process ID to the caller. The problem with this primitive is that the caller cannot wait for the termination of a specific child!
The Problem: Design a generalized waitfor(ID) routine that awaits the termination of a particular child.
```
waitfor( int id )
{
    if (is_set_member( id, terminated )) {
        remove_from_set( id, terminated );
        return;
    }
    for (;;) {
        int id1 = wait();
	if (id == id1) return;
        add_to_set( id1, terminated );
    }
}
```
In the above, we assume that we have a good implementation of the set abstraction for arbitrarily sized sets of process IDs. The size of the set terminated will never exceed the number of child processes of this process, but it is illegal to wait for any particular child more than once.