Assignment 11, Solutions

Part of the homework for 22C:112, Spring 2009
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  1. Background:

    The file http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/source.txt contains the source code for a thread manager written in C. This is documented in http://homepage.cs.uiowa.edu/~dwjones/opsys/threads/. Note that this is fragile code, not written to be portable and it may not work under the current crop of C compilers. This question does not depend on the code working.

    Note that in c, setjmp(&b) saves the current program counter and activation record pointer in b a jmp_buf (jump buffer), and longjmp(b,v) restores the program counter and activation record pointer from the jump buffer, which means it returns to the return point of the setjmp() call that initialized that jump buffer. When setjmp() returns from its own call, it returns zero. When it returns as a result of call to longjmp(b,v), it returns the value of the parameter v, which should be nonzero.

    Historically, longjmp() and its companions were included in C to allow for jumps to exception handlers.

    a) Explain how thread_relinquish() in the thread package transfers control from one thread to another. (0.5 points)

    The routine _setjmp() is called inside the if statement to save the current state. On return from the initial call, it returns zero, so the body of the if statement is executed. This calls _longjmp() to transfer control to the new thread. Note that _longjmp() does not return to its caller, instead, it returns from the call to _setjmp that saved the state of the destination thread. This is probably called in the context of an if statement very similar to the one in the body of thread_relinquish, and as such, it will skip the body of that if statement and return from whatever thread package interface routine the destination thread was in at the time it was moved from running state to ready state.

    b) Explain why thread_exit() cannot simply say free(current). Instead, it does some elaborate foolishness with mem_to_free and longjmp. (0.5 points)

    If it simply called free() to deallocate the current thread's memory, that means that the current stack would be deallocated. Depending on the nature of the heap manager, this could corrupt the activation record of free() before it tried to return, leading to chaos. Therefore, the stack of the current thread must be abandoned (for example, by longjmp()) before that stack is deallocated.

    c) Suppose you wanted thread_signal() to immediately transfer control to the thread that the signal awakened instead of continuing to run in the calling thread until it relinquishes. Modify thread_signal to do this. (1.0 points)

    void thread_signal( struct thread_semaphore * s )
    /* call this within a thread to signal a semaphore */
    {
            struct thread * t = thread_dequeue( &s->queue );
            if (t == thread_null) {
                    s->count++;
            } else {
                    /* the following code is based on thread_relinquish() */
                    if (_setjmp( current->state ) == 0) {
                            thread_enqueue( current, &readylist );
                            current = t; /* this line has been changed */
                            _longjmp( current->state, 1 );
                    }
                    /* end of code based on thread_relinquish() */
            }
    }
    

  2. Background: Consider a driver for a serial output port. The driver includes an interrupt service routine, a queue of characters to be output, and a user interface routine that enqueues characters in the queue. There may be multiple processes competing to enqueue output to this printer.

    a) When the queue is empty, interrupts are disabled; when a character is enqueued, the user interface routine enables interrupts. When the queue is full, the user interface routine uses a semaphore to wait for space in the queue. Explain this semaphore: What range of values does its counter take on? Exactly where in the driver is the code to wait on this semaphore and where is the code to signal it? (0.5 points)

    This semaphore is zero when the queue is full, and it is equal to the queue capacity when the queue is empty. The call to the wait operation on this semaphore is done immediately before each enqueue in the user-side routine of the driver, and the call to the signal operation is done immediately after each dequeue in the interrupt service routine.

    b) If two or more processes try to output data to the device at the same time, there are potential problems. Explain how a semaphore can be incorporated into the driver to solve this problem. Where is the wait on this semaphore? Where is the signal? What range of values does its counter take on? (0.5 points)

    This is a different semaphore from that in part a. It is used for mutual exclusion, so it has a value ranging from zero (resource in use) to one (resource not in use). The wait operation immediately precedes the enqueue in the user side of the driver, and the signal operation immediately follows the enqueue.