Assignment 6, due Oct. 4

On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers 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: Consider this (partial) FIFO queue implementation, with line numbers added for reference. Assume that a variety of input and output streams all share the same queue implementation.

   01  typedef struct {
   02          queue_element * next;
   03          char data;
   04  } queue_element;
   05
   06  typedef struct {
   07          queue_element * head;
   08          queue_element * tail;
   09  } queue;
   10
   11  queue_element * freelist;
   12
   13  void enqueue( queue * q; char ch ) {
   14          queue_element * item;
   15          item = freelist;
   16          freelist = item->next;
   17          item->data = ch;
   18          item->next = NULL;
   19          if (q->head == NULL) {
   20                  q->head = item;
   21          } else {
   22                  q->tail->next = item;
   23          }
   24          q->tail = item;
   25  }
   26
   27  char dequeue( queue * q ) {
   28          queue_element * item;
   29          item = q->head;
   30          q->head = item->next;
   31          if (q->head == NULL) {
   32                  q->tail = NULL;
   33          }
   34          item->next = freelist;
   35          freelist = item;
   36          return item->data;
   37  }
   38
   39  bool empty( queue * q ) {
   40          return ( ---missing code--- );
   41  }
   42
   43  bool full( queue * q ) {
   44          return ( ---missing code--- );
   45  }
   

   a) The queue empty test is missing from line 40 above. Give a correct boolean expression (there are two different correct answers). (0.4 points)

   Answer 1: q->head == NULL
   Answer 2: q->tail == NULL

   The reason this works is that whenever dequeue() sees that q->head is null, it sets q->tail to null. Enqueueing an item always guarantees that both are non-null.

   b) The queue full test is missing from line 43 above. Give the correct boolean expression. (0.4 points)

   freelist == NULL

   This may be non-intuitive. When queues are built with linked lists, there is usually a single global free-list (or in the most general case, a single global heap of free space shared by all dynamic data structures). Thus, the queue-full condition is a global condition and not one that applies to individual queues.

   c) Suppose an interrupt were allowed to occur between lines 15 and 16. Which of the following problems could occur: (0.4 points)

   1. One item could be allocated from the free list twice.
   2. An item placed back on the free list could be lost.
   3. Both of the above.
   4. Neither of the above, but something else could go wrong.
   5. There would be no damage.

   If an interrupt occurs, and the interrupt service routine does an enqueue, the result would be an attempt to use one item from the free list for two different queues (alternative a).

   If an interrupt occurs, and the interrupt service routine does a dequeue, the result would be that the dequeued item would be lost from the free list (alternative b).

   Therefore, the correct answer ia alternative c, both of the above.

   d) Suppose an interrupt were allowed to occur between lines 16 and 17. Which of the following problems could occur: (0.4 points)

   1. One item could be allocated from the free list twice.
   2. An item placed back on the free list could be lost.
   3. Both of the above.
   4. Neither of the above, but something else could go wrong.
   5. There would be no damage.

   Alternative e, there would be no damage. An item from the freelist has been allocated, it is held privately, and no attempt has yet been made to link it to any queue.

   e) Assuming that interrupts only occur between lines of code (a false assumption) there is only one point in the code between lines 29 and 36 where it would be safe to allow an interrupt. Identify the point by giving the line numbers that bracket it. (0.4 points)

   Between lines 32 and 34. (Line 33 does no computation so it really does not enter into this discussion.) At this point, the item has been completely removed from the queue and has not yet been added to the free list.

2. A Subtle Question: Look at the com1receive given in the notes for Sept 23 to Oct 2. Some of the code seems superfluous. Couldn't we write the code like this?

   procedure com1receive;
   var stat: integer;
       data: char;
   begin
        { we know the RxRD status bit is 1 }
        { get the data }
        data := inp( COM1DATA );
        enqueue( com1inqueue, data );
    
        if full( com1inqueue ) then begin
             { disable the RxRD interrupt }
             stat := inp( COM1IER );
             clearbit( stat, RxIE ); 
             outp( COM1IER, stat );
        end;
   end { com1receive };
   

   The above code might work with a bounded buffer input queue, but with the queue implementation given in problem 1, it will fail. Why? (The answer can be quite brief. Excessively long answers will be penalized. Think it through before you write!) (1.0 point)

   This code assumes that the com1receive() interrupt service routine is the only one that can cause com1inqueue to be full, and therefore, it only has to test at the end to see if it filled it, there is no need to test at the beginning to see if the queue is already full. If there are multiple sources of data that can be enqueued in com1inqueue or if there are multiple queues but only one free list, then some other input interrupt could cause the queue full condition without com1receive being aware of it.