Assignment 4, due Feb. 18

On every assignment, write your name and the course number legibly. Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!

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)

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)

   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)

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)

   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)