Assignment 5, due Sept. 21

On every assignment, write your name legibly as it appears on your University ID and on the class list! 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 logic for reading and echoing one line of input, including the processing of backspace '\b' characters meaning erase. Assume reasonable definitions for variables and functions, and assume that the stuff done before and after might be substantial.

   /* 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)

2. Background: The put(ch) routine, as used above, can be connected to an interrupt service routine, or to the poll() routine used above, through a FIFO queue, with the interface enqueue(ch) to put a character in the queue, dequeue() to get a character from the queue, and the test functions full() and empty() to test the state of the queue.

   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)

   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)

3. Background: An archaic approach to overlapping computation and input-output is known as "double-buffered I/O." The idea was largely developed with high-performance sequential devices, where a direct-memory-access coprocessor moved data to or from the device. The idea was to use two buffers. While the CPU was processing data in one buffer, for example, creating output there, the DMA coprocessor was dealing with the other buffer, for example, outputting its contents to the device. Here is an outline of typical code:

   /* 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.

   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)

   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)

Machine Problem III

Due Monday, Oct. 1.

Modify the minimally usable shell to add the following. Each, in isolation, is a relatively small change, but in combination, they make the shell significantly more useful:

• Quotation marks may be used to delimit shell arguments, single or double, but the opening quote must match the closing quote. The quotation marks themselves are not part of the argument.
• Everything on the input line after a pound sign (#), if it is not enclosed in quotes, should be ignored -- that is, treated as a comment.
• Any argument that begins with an unquoted dollar sign should be replaced with the value of the corresponding environment variable. The dollar sign is not part of the variable name.
• Before deciding to interpret a command as a request to launch an application, the line should be inspected for built-in commands. Only if no built-in command is detected should an attempt be made to launch an application. The built-in commands are:
  • no command -- do nothing.
  • exit -- terminate the shell
  • setenv a b -- set environment variable a to the value b
• When launching an application, pass it the current environment.

You will find the following routines in the C standard library useful in this assignment: getenv(), exit(), setenv(). These are all documented in section 3 of the manual (use the man 3 xxx command for documentation). The global variable environ will also be useful; this is documented in section 7 of the manual (use the man 7 environ command for documentation).

Some of these are relatively trivial, but some of them interact with each other. You are responsible for deciding how to add these functions to MUSH. Each feature can best be implemented in one or another part of the existing program, and the decisions you make about where to put the code have a significant effect on correctness.

You are responsible for designing test data, and in fact, you are strongly recommended to design the test data for each feature before you write any code to implement it. (This is part of the so-called "extreme programming" or XP methodology. You might enjoy looking this up on Wikipedia.) It will definitely be easier to implement and test the features required here if you do them one at a time in the right order. Keep backups so you can revert and start over if you find yourself working toward a dead end.

Turn in your code -- not your test data, using the coursework submission tools, in the submission directory mp3. Your source file should be named mp3.c.