Assignment 7, Solutions

Homework

Do problem 4(1.0) from the end of Chapter 10 of the notes.

If the user keeps on typing when no application is interested in reading the data accumulating in the queue, eventually the queue will fill; when this happens, the interrupt service routine will return leaving the RxRD interrupt disabled, so when the next character is received, it will stay in the COM1DATA register, and when the next character arrives, the hardware will have nowhere to put it.

Do problem 7(2.0) from the end of Chapter 10 of the notes.

	/* queue implementation */
	struct queue {
		char buffer;
		char state; /* either FULL or EMPTY */
	}
	#define FULL  0
	#define EMPTY 1

	int full( struct queue * q )
	{
		return (q->state == full);
	}

	int empty( struct queue * q )
	{
		return (q->state == empty);
	}

	void enqueue( struct queue * q, char ch );
	{
		q->buffer = ch;
		q->state = full;
	}

	char dequeue( struct queue * q ); /* dangerous version */
	{
		/* critical section */
		disableints;
		q->state = empty;
		return (q->buffer);
		enableints;
	}

	char dequeue( struct queue * q ); /* safe version */
	{
		char ch = q->buffer;
		q->state = empty;
		return ch;
	}

This implementation assumes that the caller never enqueues in a full queue and never dequeues from an empty queue, as is guaranteed by the code in Figure 10.8.

The full and empty tests are trivially free of critical sections. the situation with enqueue and dequeue is more complex. So long as the queue state is changed after an insertion or deletion, and so long as the caller is careful to check the precondition before calling the queue implementation, all is well. If, however (as in the unsafe version of dequeue shown above) the state change is done first, then if that queue routine is called by a user, and then there is an interrupt between the state change and the user's use of the buffer, the interrupt service routine could respond to the incorrect state! So, the unsafe version shown above has a critical section!

The safe versions of the code shown above are walking on a tightwire when it comes to avoiding critical section problems!

Do problem 9(1.0) from the end of Chapter 10 of the notes.

Comreadline from Figure 9.8 does echoing using software. Therefore, it is not path 1 in Figure 10.14. The echoing is not at the interrupt-service routine level, so it is not paths 2 or 3. That leaves path 4, close to the user code, and on the user side of the queues, but still not quite in the user code.