Homework 3 Solutions

22C:116, Spring 2002

Douglas W. Jones
  1. Background: Look at the user-level thread package found in:
    http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/

    Part A: Consider writing a program that contains multiple processes all running the same code. Each process can have local variables on its stack, but you need some place to put the static data of the process. Explain how to use the tool provided by the thread manager for solving this problem.

    What we need to do is allocate a block of static variables for each thread and then pass a pointer to this block to the function that holds the code for the thread. When this function calls other cooperating functions that need to access this block of variables, it must pass this pointer as a parameter. The block can be statically allocated, or it can be on the heap. The problem is, the thread package can't anticipate the type of this block, and therefore, we must use casting to cast the block pointer to the form that we can pass through the thread launch function. Thread launch takes an int as a parameter, so we end up casting the pointer to int in order to pass it to the main function of the thread. (For this purpose, the parameter passed to the thread vie thread-launch should probably have been type void*.)

    Alternatively, we could allocate all of the static variables of each thread globally, and pass an integer to the thread that it uses to determine which global variables it looks at. For example, we might have a global array of thread statics, indexed by thread number. When a thread needs to look at some static variable associated with that thread, it uses the integer it was passed as an index into this global array. Again, if multiple functions cooperate to implement the code of the thread, the integer must be passed back and forth between these functions.

    Part B: Look at the C code for the thread manager, specifically at the code to for the thread_launch function. Give a very short description of the key items that must be done to launch a new thread.

    1. A stack for the new thread must be allocated, along with the necessary fields to link this stack into queues of threads and space for the thread state.
    2. The initial state of the thread should be stored in the stack so that the thread can be started.
    3. The activation record of the thread-launch function must be copied onto the thread's stack, so that this code can call the function holding the thread's code when it finally gains control.
    4. Because the initial state was saved using setjmp, it contains values that refer to the activation record of thread-launch on the stack of the thread that called thread-launch. We need to modify these pointers to point into the stack of the new thread, to the copy of the activation record we moved there. The particular fields that need changing are recorded in a data structure called probe_rec.

    Part C: Compare the implementation of the thread_wait operation with the generic description of how the wait operation on a semaphore is implemented, for example, in the notes for lecture 5, and explain the reasons for the significant differences.

    First, thread-wait checks for an empty ready list, and raises a thread_death exception if the ready list is empty. The version in the notes assumed that the ready list would never be empty.

    Second, thread_wait uses longjmp and setjmp for its control transfers. The version in the notes did nothing of the sort. This is because we are confined to the tools of C for this thread implementation instead of being able to save and restore the state the way we would in assembly or machine language.

    Third, this code does not concern itself with interrupts becuase there is no preemption in this thread manager. If we wanted to add preemption, we would have to turn off the interrupts that could preempt a thread during all critical sections in this code.

  2. Problems from the Text: Do problems 12 and 20 on page 154.
    • 12) The overhead of thread management makes a single-threaded server better whenever the rate of client requests makes it unlikely that a client request will ever arrive at the server while another request is still being serviced.

    • 20) The mechanism in Figure 2-20 works perfectly on a multiprocessor. The shortcoming of this mechanism lies not in a failure of mutual exclusion, but rather, it lies in the fact that this mechanism not only assures mutual exclusion, but also forces the two processes to take identical numbers of turns; that is, it forces them to strictly alternate in their use of the critical section. Many parallel applications need more flexibility.

    Do problem 27 on page 155.

    If kernel threads use a kernel semaphore, everything works fine. If a user-level thread blocks on a kernel semaphore, all user-level threads in that process will be blocked, so if it is waiting for a signal from another thread in the same process, the signal will never arrive.