Assignment 3, due Sept 13

Part of the homework for 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background: There is a user-level thread package written in C and callable from C or C++ programs on-line at:
    http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/
    This thread package contains many features typical of the process manager of an operating system, except that they operate at the user level and are coded in machine independent form.

    The Problem: As announced last week, you are to modify this thread package so that the code running in one thread can force the termination of another thread (the thread_kill operator). You will have to add some kind of thread handle to the interface, and the thread_launch operator will return such a handle.

    Note that you may wish to seek a minimum effort path to a solution instead of a computationally optimal solution. If you examine the alternatives to the solution of this problem, you will find that some involve writing more code, or more code disbursed throughout the pre-existing thread package, while others involve less code or code that is concentrated in one part of the package.

    For maximum credit: Your thread handle should be opaque, so that details of the thread implementation are not revealed to the user in the header file that gives the user interface. There are several ways to do this, varying in difficulty.

    What to turn in: Turn in clearly written correct code. This should include the new header file for the thread package, plus those parts of the thread package you changed, with enough context to be easy to read, but without functions that remained unchanged. Your additions to the code should blend comfortably into the style of the existing code, yet should be easy to identify -- this may be done by embedded comments or by highlighting those parts you added or changed. Your code should work, but you'll only be asked to demonstrate this if it isn't obvious that your solution is correct. Note that this problem, in total, is worth 3 of the 5 points for this assignment.

  2. Background: The Berkeley Timesharing System was implemented on the SDS 940 computer, made by Scientific Data Systems, a company that Xerox later bought, renamed Xerox Data Systems, and ran into the ground. The SDS 9x0 family of machines had 24-bit words with an 8-bit opcode, 2 bits of address mode, and 14 bits of physical address. The 940, introduced in 1966, was basically a 930 with an added memory management unit. This took the 14-bit address and broke it into a 3-bit page number and an 11-bit word-in-page field. Note that this machine had no byte addressing. Software could use either 3 8-bit bytes per word or 4 6-bit bytes per word, depending on the character set needed!

    The Berkeley Timesharing System was, incidentally, commercialized by ComShare Inc and by Tymshare Inc. GTE bought the latter, which became the basis of GTE's network division. ComShare is still a thriving company.

    In the notes describing the Berkeley Timesharing System, it is stated that this system allowed each user to have an address space of 64 pages, with any number of threads sharing this address space, where each thread could, at any instant, address only some subset of the user's pages.

    A Problem: Explain why the hardware leads to this constraint! Suggest the data structures appropriate inside the operating system for representing the address space of a user and the address spaces of that user's threads, and suggest how the user might go about specifying the shape of the address space to be used by a thread when that thread is launched. (None of this need be based on the real system as it was actually developed, it need only be plausable.)

  3. A Problem: Do problem 12 on page 154 of the text.