Homework 2

22C:116, Fall 2000

Due Friday Sep 1, 2000, in class

1. Background: Consider the antiquated DEC PDP-8 architecture (introduced 1965 as a discrete transistor machine, discontinuted as a microprocessor in 1990). See http://homepage.cs.uiowa.edu/~dwjones/pdp8/man/ for more detail than you ever wanted about this antique machine. For the purpose of this assignment, assume the PDP-8/E model with memory management unit.

   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. (Do not consider the auto-increment registers to be part of the state! These are allocated to processes as part of the memory resources of that process.)

   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. Note that many of the registers and status bits can be manipulated by several different instructions and delivered to the user packed in several different formats. Based on what you have found, suggest an appropriate layout for a process state record as it would be saved in consecutive memory locations.

   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. Note that this machine has a painfully simple interrupt mechanism, so there is really only one handler!

2. Background: The Quicksort algorithm is a classic; you can find it in just about any algorithms textbook. Each call to Quicksort on an array of size n divides it into two arrays of, typically, size n/2, and then applies Quicksort recursively to sort the new smaller arrays. A trivial way to use parallelism to speed the sorting process is to run these two recursive calls in parallel.

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

   Part B: The naive code you wrote may spawn O(n) parallel processes to sort an array of n items. This is unwise in an environment where there are fewer than n CPUs. For example, the SGI Onyx machine in MacLean hall has 8 very fast CPUs, so applications using more than 8 processes merely force the scheduler to do lots of context switching. 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.

3. 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. Your waitfor() routine may rely on static data to maintain a database of the children that have already terminated, and you may assume that users of waitfor() will never call wait(). Express your answer as nearly syntactically valid code, but if the code relies on well defined abstractions, you need not present the implementations of these abstractions.