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)

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

   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.

   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.

   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)

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)