Homework 4 Solutions

22C:116, Fall 2001

Douglas W. Jones
  1. Part A: When you run this example, it outputs the message "Thread manager terminated, possible deadlock!" Explain the nature of the problem with the example code.
    In the example code, there is no attempt to cleanly terminate any of the threads. When the producer threads have all terminated, the consumers end up all being blocked on the data semaphore. This is not, technically speaking, a deadlock (they are blocked on a semaphore that no thread will ever signal, while a deadlock is defined in terms of a circular wait), but the thread manager cannot distinguish this error situation from a deadlock.

    When the producer threads terminate, they do so by returning to thread-launch instead of calling thread-exit. The design of the thread package anticipates this possibility and does a clean call to thread-exit when this happens. This, therefore, is not an error.

    Part B: Explain why the example code outputs the termination message before it outputs the text produced during the execution of the program prior to termination.

    The error message is output to stderr, while the messages from each thread are output to stdout. These two streams are buffered independantly, and on program termination, the buffers for the two streams are flushed, with stdout being flushed first. In addition, the total text written to both of these streams is less than one buffer full, so none of the output was actually sent to the display screen during the execution of the program. Therefore, the error message occurs before the output from any of the threads.

    Part C: How should the thread manager itself be modified in order to produce its output in the correct order?

    An explicit call to fflush(stdout) should be included before the error message is output.

    Part D: Modify the program so that, in addition to the semaphores, there is a single global queue of integers, with head and tail pointers, where the capacity of the queue is the same as the initial value of the free semaphore.

    Part E: Modify the program so that the producer and consumer threads call your enqueue and dequeue functions. The producers should enqueue the successive values of their loop control variable, and each consumer should count the number of items it consumes and report this.

    -- for part d, insert the following
    
    #define CAPACITY 3
    
    static int head = 0;
    static int tail = 0;
    static int queue[capacity];
    
    void enqueue(int i)
    {
    	thread_wait( &free );
    	queue[tail] = i;
    	tail = (tail + 1) % CAPACITY;
    	thread_signal( &data );
    }
    
    int dequeue()
    {
    	int i;
    	thread_wait( &data );
    	i = queue[head];
    	head = (head + 1) % CAPACITY;
    	thread_signal( &free );
    	return i;
    }
    
    -- for part e, change the producer and consumer to
    
    static int producers = 2;
    
    void producer(int i)
    {
            int j;
            printf( "Enter produce %1d, ", i );
            for (j = 1; j < 6; j++) {
                    printf( "%1d produces %1d, ", i, j );
                    enqueue(j);
            }
    	producers = producers - 1;
    }
    
    void consumer(int i)
    {
    	int j, k;
    	k = 0;
            printf( "Enter consume %1d, ", i );
            while ((producers > 0) && (head != tail)) {
                    j = dequeue();
                    printf( "%1d consumes %1d, ", i, j );
    		k = k + 1;
            }
    	printf( "%1d consumed %1d, ", i, k );
    }
    
    Note that termination detection is the single hardest part of this assignment. In this version, the consumer threads terminate when both the number of producer threads is zero and the queue is empty. It is possible that the queue will be empty occasionally while the producers are waiting and a consumers is running, and it is also possible for there to be a full queue of data waiting to be dequeued after the last producer terminates.

    If we had preemptive scheduling of threads, we would need mutual exclusion around many parts of this code, but because the thread manager is based on a cooperative model of parallelism, the only place context switching can occur in this code is in calls to thread_wait().