Assignment 4, Solutions

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

  1. Background: There are two natural implementations of FIFO queues: We can use a bounded buffer, with a fixed-size array and a pair of pointers, the head and the tail, or we can use a linked list. Imagine this structure for a list element:
    struct element {
    	struct element * next; /* NULL means this is the tail */
    	char ch;
    };
    
    struct queue {
    	struct element * head; /* NULL means empty queue */
    	struct element * tail; /* NULL means empty queue */
    };
    

    To allocate a new and uninitialized element, use malloc(), to deallocate an element when it is no-longer needed, use free(). There is some advice about malloc() in the programming style guidelines. Full documentation of these is found in the Unix programmer's reference manual (the man command) and in Kernighan and Ritchie.

    A problem: Give code for a linked-list implementation of enqueue() and dequeue() compatible with the bunded buffer version in the notes. Assume that queue_initialize() is not your problem, and ignore the problem of implementing tests for queue full and queue empty. (1 point)

    void enqueue( struct queue * q, char c ) {
            struct element * item = malloc( sizeof( struct element ) );
            element->ch = c;
            element->next = NULL;
            if (q->head == NULL) {
                    q->head = q->tail = item;
            } else (
                    q->tail->next = item;
                    q->tail = item;
            }
    }
    char dequeue( struct queue * q ) {
            char c = q->head->ch;
            struct element * item = q->head;
            q->head = item->next;
            free( element );
            return c;
    }
    

  2. Background: FIFO queues can be implemented as bounded buffers or as linked lists.

    a) Even if we ignore questions of economics and performance, these are not strictly equivalent. What behavioral difference would you expect between a system that used bounded buffers for all of its character sequential input-output and a system that used linked lists of characters. Hint: the differences are concentrated in an area you were told to ignore in problem 1 above. (0.5 points)

    Each bounded buffer may be full independent of other bounded buffers. With linked lists, if one queue is full, all of them are full because they share one pool of free space from which their elements are allocated.

    b) These two implementations of FIFO queues would be expected to have different economic characteristics in normal operation, when the queues are neither full or empty. What is the biggest difference? (0.5 points)

    The operations on bounded buffers will be faster than the operations on linked lists. In addition, it is likely that small bounded buffers will use significantly less memory because a single pointer typically occupies the same space as 4 to 8 characters.

  3. Background: Consider a device driver, consisting of a FIFO queue linking an interrupt service routine to a user-side routine.

    a) The device is an output device. What does the interrupt service routine do if the queue is empty? As a consequence, what does the user-side routine need to do after each enqueue? (0.5 points)

    If the output queue is empty, the interrupt service routine leaves the device interrupt enable bit set to zero when it returns. Each time the user-side routine enqueues a character, it sets the device's interrupt enable bit.

    b) The device is an input device. What does the user side routine do if the queue is empty? As a consequence, does the interrupt service routine need to do anything special after each enqueue? (0.5 points)

    It keeps trying to dequeue. The input interrupt service routine therefore has no need to signal that a character has arrived. This answer changes to a far more complex answer in a multithreaded system.