Assignment 5, Solutions

/* other stuff to be done first */
i = 0;
for (;;){
        ch = get();
        if (ch == '\n') {
                line[i] = NUL;
                put('\n');
                break;
        }
        if (ch != '\b') {
                line[i] = ch;
                put(ch);
                i = i + 1;
        } else if (i > 0) {
                i = i - 1;
                put('\b');
                put(' ');
                put('\b');
        }
}
/* other stuff to be done after */

A problem: Rewrite the above code using the main polling loop approach, with all device interaction packaged in a routine called poll() which is called exactly once per iteration of the main loop. (1.0 point)

First, we need to make some assumptions. poll() handles movement of data between devices and FIFO queues with unspecified capacity, possibly as small as one character. The user end of the input queue is get(), which may only be called if the input queue is not empty(). The user end of the output queue is put(), which may only be called if the output queue is not full().

state = 0;
for (;;) { /* main polling loop */
	poll(); /* called once per iteration */
	switch (state) {
		... /* other stuff to be done first */

		case STARTGETLINE:
			i = 0;
			state = TOPGETLINELOOP;
			break;
		case TOPGETLOOP:
			if (!empty()) {
				ch = get();
				if (ch == '\n') {
					line[i] = NUL;
					state = TRYPUTNL;
				} else if (ch != '\b') {
					line[i] = ch;
					i = i + 1;
					state = TRYPUTCH;
				} else if (i > 0) {
					i = i - 1;
					state = TRYPUTBS;
				} else {
					state = TOPGETLOOP;
				}
			}
			break;
		case TRYPUTNL:
			if (!full()) {
				put('\n');
				state = STUFFTOBEDONEAFTER;
			}
		case TRYPUTCH:
			if (!full()) {
				put(ch);
				state = TOPGETLOOP;
			}
		case TRYPUTBS:
			if (!full()) {
				put('\b');
				state = TRYPUTSP;
			}
		case TRYPUTSP:
			if (!full()) {
				put(' ');
				state = TRYPUTBS1;
			}
		case TRYPUTBS1:
			if (!full()) {
				put('\b');
				state = TOPGETLOOP;
			}
		case STUFFTOBEDONEAFTER:
		... /* other stuff to be done */
        }
}

If you think the above code is awful, you are right. That is the point. This approach always seems to lead to awful code.

Most presentations of FIFO queues have queues with significant capacity, but in fact, a degenerate queue can be constructed with a capacity of one byte. This queue will also require one or more control variables to record the status of the queue, but with only one byte capacity, it does not need head or tail pointers.

a) Give code for a single instance of the queue in C, with appropriate initial values assigned to the global variables used to hold the data and status so that the queue is initially empty. (0.6 points)

#include 
char buffer; /* the bounded buffer with a capacity of one character */
int size = 0; /* the current size of the queue (zero or one) */

bool full(){
	return (size == 1);
}
bool empty(){
	return (size == 0);
}
void enqueue(char ch){
	buffer = ch;
	size = 1;
}
char dequeue(){
	size = 0;
	return buffer;
}

b) If your code above was used by an interrupt handler for input, certain critical sections may be exposed in the get() routine. If your code above was used by an interrupt handler for output, certain critical sections may be exposed in the put() routine. Identify all of the critical sections in your code. (0.4 points)

void enqueue(char ch){
	/* start critical section */
	buffer = ch;
	/* the queue is not marked as full yet, but it is! */
	size = 1;
	/* end critical section */
}
char dequeue(){
	/* start critical section */
	size = 0;
	/* the queue is not really empty yet, but it seems to be! */
	return buffer;
	/* end critical section */
}

/* 2 buffers */
char a[BUFFERSIZE];
char b[BUFFERSIZE];
/* 2 buffer pointers */
char * buff1 = a;
char * buff2 = b;
char * temp;
put_data_in( buff1 ); /* start with buffer 1 full */
for (;;) { /* loop moving data */
        start_DMA_IO( buff1 );
        put_data_in( buff2 );
        wait_for_DMA_done();
        /* swap the pointers after each cycle */
        temp = buff1;
        buff1 = buff2;
        buff2 = temp;
}

This code omits the question of how it terminates, ignore that.

a) The above code is equivalent to code using a FIFO queue of buffers. The queue is a bounded buffer. What is the capacity of the queue? (0.4 points)

Hint: What queue capacity gives the same degree of overlap between processing and I/O. It may help to imagine that the buffer capacity is one byte, so start_DMA_IO() is equivalent to putting the byte in the output data register, and wait_for_DMA_done() is equivalent to waiting for the device's ready bit.

A little bit of logic helps immensely here. There are 2 buffers, therefore, the correct answer cannot be more than two, and it cannot be less than zero. Therefore, the queue capacity must be either 0, 1 or 2 buffers.

The capacity cannot be 2, because this would allow producer to get two buffers ahead of the consumer, and the above code keeps them in lock step. Therefore, a capacity of zero or one makes sense. It is not clear that a queue of capacity zero can be implemented, leaving a capacity of one as the most obvious answer.

b) An I/O system works at maximum efficiency if the CPU is 100% utilized and the data channel to th device is 100% utilized. Assume that the average rate of data production by the CPU is equal to the average rate of data consumption by the device. This allows maximum efficiency but does not guarantee it. Concisely describe a situation where double-buffered I/O would be less than fully efficient despite the average rates being equal. (0.3 points)

An average may be computed over a long time, so the fact that the averages are equal does not imply that the instantaneous rates are equal. If the CPU takes a long time to fill one buffer, while the channel empties a buffer at an above average speed, and then for the next buffer, the CPU fills its buffer very quickly while the channel slows down, the average rates will be the same, but during each cycle, either the CPU or the channel will spend most of its time waiting for the other. The net result (if the rates vary enough) is that both the channel and CPU can be only 50% utilized.

c) Under the circumstances you described in part b) how would efficiency vary if you used a bounded buffer of queues, as a function of queue capacity. (0.3 points)

The larger the buffer, the greater the fluctuation in rate can be tolerated without reducing the efficiency.