CS:3620, Homework 5 Solutions, Spring 2018

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!

Background: In the discussion of queues in the notes for Feb. 7, Figure 10 shows an implementation of a FIFO queue. The implementation given uses the mod operation to increment the queue's head or tail. The code looks like this in C (with SIZE defined differently from size in the original):

typedef struct {
        int head, tail, count; /* all initially zero */
        char buffer[SIZE];
} queue;

void enqueue( queue* q; char ch ) {
        q->count = q->count + 1;
        q->buffer[ q->tail ] = ch;
        q->tail = (q->tail + 1) % SIZE;  /* marked */
}

a) Rewrite the marked line so it just increments the tail and then checks to see if it incremented too far and resets the tail to zero. (0.5 points)

        q->tail = q->tail + 1;
	if (q->tail >= SIZE) q->tail = 0;

b) Suppose SIZE is a power of two. Rewrite the marked line so that it uses the & operator instead of the % (mod) operator. (0.5 points)

        q->tail = (q->tail + 1) & (SIZE - 1);

The above relies on the fact that subtracting one from a power of 2 such as 8 (1000₂) gives all ones in the places below that power of two. For example, 8–1 is 0111₂.

Background: Look at the implementation of put() in Figure 9 of the notes for Feb. 7. Now assume that the I/O driver uses echo path 3 from Figure 14 in the same chapter of the notes. This means that the user code and the input interrupt service routine are competing to put characters in the output queue.

a) Assume the code for put() from Figure 9 is used by the user. Identify the point in this code where the interrupt service routine that echoes input keypresses must not interrupt. Note: The code given does not prevent an interrupt at this point; once you identify this point, you will have identified a critical section in the code. (0.5 points)

procedure put( ch: char );
begin
     { wait for space in queue }
     while full( com1outqueue ) do { nothing };
	--- what if the interrupt service routine interrupts here?
     { put the data }
     enqueue( com1outqueue, ch );

     { enable TBE interrupt -- a critical section }
     disableints;
     stat := inp( COM1IER );
     setbit( stat, IETBE );
     outp( COM1IER, stat );
     enableints;
end { put };

The key to credit here is to identify the risk that an interrupt could fill the queue between the time the user's polling loop found that there was space and the time that the user tries to put data in that space.

b) Give appropriate code for the user-level version of put that can be used to protect this critical section. (0.5 points)

procedure put( ch: char );
begin
     { wait for space in queue }
     disableints;
     while full( com1outqueue ) do begin
          enableints;
          --- allow interrupts here
          disableints;
     end;
     --- interrupts cannot occur here
     { put the data }
     enqueue( com1outqueue, ch );
     enableints;

     --- the rest of the code is unchanged

The specific notation does not matter, what matters is that interrupts are disabled from the time the queue is found to be empty until data is enqueued.

The trick is to do this without locking out all interrupts while waiting for space in the queue, since it is an output interrupt that creates that space. The trick of briefly enabling interrupts during each iteration of the polling loop solves this problem.

Background: The code given in the notes assumes just one COM port. Suppose, instead, that you have multiple identical COM ports — identical except that they have different blocks of 8 consecutive device addresses. Only one of these COM1, uses the block from 3F8₁₆ to 3FF₁₆. Furthermore, assume that all of them use the same interrupt address. That is, assume that there is a single interrupt service routine shared by all of the COM ports.

On the operating system side, we'd like to think of an array of COM ports, call it comport[], with legal index values from zero to COMPORTS. conceptually, each COM port in this array is an object.

a) Describe the (conceptual, since they're likely to be written in C) methods of each COM port that would be called from the interrupt service routine. Your goal here is to put most of the work into these methods. (0.5 points)

There are lots of possible solutions. Here's a solution with just one method:

try(), tests the ready bits of this com port and does either an input, an output, or resets the enable bits, depending on the state of the port's queues.

Here's a solution with multiple methods, but note that there are solutions intermediate between the above and the following:

pollin(), tests the input ready bit of this port, returns true if ready, false if not.

pollout(), tests the output ready bit of this port, returns true if ready, false if not.

inputISR(), does the input, called only if this input port is ready. The body of this is written as if it was an interrupt service routine that would be called directly by hardware if there were only one COM port and it only did input.

outputISR(), does the output, called only if this output port is ready. The body of this is written as if it was an interrupt service routine that would be called directly by hardware if there were only one COM port and it only did output.

b) Give appropriate code (or object-oriented pseudocode) for the COM interrupt service routine. (0.5 points)

/* for the first solution suggested above */
void comportISR() {
    int p; /* a com port number */
    for (p = 0; p < COMPORTS; p++) {
	comport[p].try();
    }
    return;
}

/* for the second solution suggested above */
void comportISR() {
    for (p = 0; p < COMPORTS; p++) {
	if (comports[p].pollin()) comports[p].inputISR();
	if (comports[p].pollout()) comports[p].outputISR();
    }
    return;
}

Obviously, the grading of this part of the problem must take into account the solution to part a.

Assignment 5, due Feb. 16

Solutions