Homework 2 Solutions

22C:116, Fall 2000

Douglas W. Jones
  1. Part A: Compare the pseudocode for the relinquish operation (or clock interrupt service routine) in the notes for lecture 5 with the implementation of thread_relinquish in the thread package. Certain elements are almost identical to the notes, others are very strange. Explain the function of setjmp and longjmp in this context!
    The setjmp() call is used to save the context, and the longjmp() call is used to restor the context to a context that was previously saved.

    Part B: Compare the pseudocode for the wait (or P) operation in the notes for lecture 5 with the implementation of thread_wait in the thread package. Aside from the strange use of setjmp and longjmp already noted in part A, what other difference is there between the code and the pseudocode. (hint: Was there an error in the pseudocode?) Explain!

    The pseudocode didn't allow for the possibility of an empty ready-list; this could occur, for example, if there was a deadlock. Also, there is no disable-interrupt operation in the thread package; this is because the thread package uses a purely cooperative model of multitasking, while the model in the notes assumes preemption.

    Part C: The thread_lanuch function in the thread package has some odd parameters that don't relate clearly to anything in the notes. Why do we need to specify the size parameter in a practical implementation of a user-level thread manager, when this corresponds to nothing in our abstract programming model.

    In the abstract, programmers never think of the size of the stack allocated to their code. The working assumption is that it is infinite. When there is only one process in the address space, this infinite stack size can be approximated by a huge finite block of the address space. If the address space is shared by an unbounded number of threads, however, where the code within each thread still uses a classical stack model for activation record allocation, the programmer must provide some advice to the system about the expected need of each thread for stack space.

  2. Part A: Explain how the O_NONBLOCK flag can be used (see the documentation for the UNIX fcntl() kernel call) to implement a thread-compatable replacement for read() under the user-level thread manager.
    A read operation on a file with the O_NONBLOCK flag set will return any pending data without blocking and awaiting additional data. This allows the replacement of a blocking read with a polling loop containing a non-blocking read. For each iteration of this loop, we can call thread-relinquish to allow other threads to run.

    Part B: Explain how the select() UNIX system call can be used as an alternative approach to implement a thread-compatable replacement for read() under the user-level thread manager.

    Select tells us, in advance, whether a call to read would block. Therefore, we can preceed each call to read with a polling loop using select to check the file. If it would block, we do a thread-relinquish and try again, so only when the data required is all ready to be read do we finally call the read routine, confident that it will not block.