Homework 4

22C:116, Fall 2001

Due Friday Sep 21, 2001, in class

Douglas W. Jones

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

  1. Background There is an example thread manager in http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/

    This thread manager includes a very rudimentary deadlock detection scheme.

    Part A: What deadlock model applies to applications written to run under the example thread manager?

    Part B: Would it be practical to add a general purpose deadlock detection mechanism to the example thread manager, so that it would detect and report (with an error message) all deadlocked applications running under the thread manager. If so, explain what detection algorithm you would use. If not, explain why.

  2. A Problem; Do problem 5 on page 264 of the text.

  3. Background: See problem 9 on page 264 of the text. In the early 1980's, HP came out with the HP9826U workstation; this used a Motorola 68000 CPU and supported one of the early versions of HPUX, a version of UNIX. The Motorola 68000 had no MMU, so they had to build a simple MMU, but there was an additional problem. Under the 68000 architecture, many instructions had side effects, for example, incrementing the program counter or one of the operand registers, that were completed prior to the final instruction issue by that CPU. As a result, when the memory management unit requested a trap, reconstructing the state of the CPU prior to the instruction that caused the trap was difficult.

    Fortunately, the CPU did put out some useful signals with every address. The MMU could determine if an address was an operand address, the address of the first byte of an instruction, or the address of some later byte. Assume you were the chief operating system programmer in charge of writing the page fault handler on this early HP workstation.

    Part A: What data would you ask the MMU designers to collect whenever there is a page-fault in order to allow you to reconstruct the CPU state prior to the fault? Remember, you can't change the CPU, but you can assume that MMU has yet to be designed!

    Part B: How would you use this data?