Assignment 7, Solved

	struct queue_element {
		struct queue_element * next;
		char buffer;
	}

	struct queue {
		struct queue_element * head;
		struct queue_element * tail;
	}

	struct queue_element * freelist;

	void enqueue( struct queue * q, char ch )
	{
		struct queue_element * item;

		/* get space for one character */
		item = freelist;
		freelist = item->next;

		/* put the character in the buffer */
		item.buffer = ch;

		/* put the buffer at the tail of the queue */
		item->next = NULL;
		if (q->head = NULL) { /* queue is empty */
			q->head = item;
		} else { /* there exists a tail element of the queue */
			q->tail->next = item;
		}
		q->tail = item;
	}

	char dequeue( struct queue * q )
	{
		struct queue_element * item;

		/* get the item out of the queue */
		item = q->head;
		q->head; = item->next;

		/* return the item to the free list */
		item->next = freelist;
		freelist = item;

		/* return the character from the item */
		return item->buffer;
	}

	boolean full( struct queue * q )
	{
		return freelist == NULL;
	}

	boolean empty( struct queue * q )
	{
		return q->head == NULL;
	}

Part b) Explain the economic problems posed by this implementation in a system that uses a queue of characters for output to a printer, so that an application may enqueue thousands or millions of bytes of data long before the printer finishes printing the first page of the document.

For each character in the queue, we must pay a price of at least one pointer, where pointers are 4 bytes each on most current computers.

Run some time consuming application like make and, while it runs, start typing. You notice that each character you type is output as you type it, mixed into the output of the application.

This implies echo paths 1, 2 or 3, not 4.

But then, when the time consuming application is done, all the stuff you typed is echoed again! That's odd but handy. In fact, the second echo is only being done by the shell! If you write your own application to run instead of the shell, it won't echo things this second time. The shell was trying to be nice because users generally want to see what they typed all neatly displayed (echo path 4), so the shell faked that up.

Whenever the application successfully fills the output queue to its current limit, 1) make the application wait, and 2) decrease the limit for the next time, since it seems that the application is producing data at an average rate higher than the device can consume it, so there's no point in allowing a high queue capacity.

Whenever the I/O driver successfully empties the output queue, increase the application's queue-length limit, since it seems that the application isn't keeping up with the device, on average, so the application should be allowed to get farther ahead when, by chance, it manages to get a burst of CPU time or whatever it takes to allow it to be productive.