Assignment 2, due Feb. 19

Part of the homework for 22C:112, Spring 2010
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

  1. Background: Applications written to operate under a window manager must take input from two distinct input queues, mouse_queue and keyboard_queue, and create a single stream of events directed to the application. Consider a mouse queue where each mouse event is encoded as one 8-bit byte, of which 6 bits are defined: ab00udlr
    1. a 1 if the left button is being held down.
    2. b 1 if the right button is being held down.
    3. ud up-down, 01, 00 or 11 for mouse moves up, nowhere, or down.
    4. lr left-rignt, 01, 00 or 11 for mouse moves left, nowhere or right.

    Consider a keyboard queue where each keypress event is encoded as one 8-bit character. Both queues support the q.enqueue(d), q.dequeue() and q.empty() (to test-for-empty) operations.

    a) Informally outline code using these primitives to get one byte from whichever queue currently holds data, returning to the caller the data and an indication of which queue produced that data. (0.5 points)

    b) Based on your experience with the previous part of this problem, explain what problems you experienced above can be solved by the Unix select() system service. (For documentation, try man 2 select.) (0.5 points)

    c) Think about the data rates from the mouse and keyboard and the meanings of the data items. Based on this, if neither queue is empty, which queue queue should have priority for the dequeue operation? Support your answer with reasoned argument. (0.5 points)

  2. Background: Suppose the queues used for character sequential input and input are bounded buffers. As such, they support q.enqueue(d), q.dequeue(), q.empty() and q.full() (the latter to test for empty and full queues). Assume an input/output driver that uses interrupts.

    a) What software component checks for input queue full? What does it do in that case? (0.2 points)

    b) What software component checks for input queue empty? What does it do in that case? (0.2 points)

    c) What software component checks for output queue full? What does it do in that case? (0.2 points)

    b) What software component checks for output queue empty? What does it do in that case? (0.2 points)

  3. Background: Consider this code declaring a queue and the enqueue routine for a FIFO queue:
    struct queue {
            char * head;
            char * tail;
            char * marker;
            char buffer[BUFSIZE];
    void enqueue( struct queue * q, char ch ){
            *((q->tail)++) = ch;
    	if (q->tail == q->marker) q->tail = q->buffer;

    a) Given that q points to a newly allocated queue, give a C code fragment that initializes the fields of the queue so that it is empty. (0.4 points)

    b) Give the code for empty(q) to test for an empty queue. (0.3 points)

Machine Problem 2, due Mar. 3

Modify the example shell from MP1 so that it uses the PATH environment variable as a source for the search path. You will probably need to learn about the following functions in the standard C library:

Your goal, of course, is to replace the rather low-quality search path code from MP1 so that it uses the built-in path variable. You need not provide any support for changing the path. Changes to the path will have to be made by the shell that launches your shell.

To submit your work, use the submit command, documented on the web at:
Specifically, your source code should be stored in a file named mp1.c and you should submit it in the course c_112 under the submit directory mp2. The submit command is verbose. Striping out all the verbosity, your dialogue with submit will look something like the following:

[jones@serv16 ~]$ submit
 File/directory name: mp1.c
 File/directory name:
Course (22C:016 would be c_016): c_112
Choice: mp2
* File/directory mp2.c has been
* copied to /group/submit/c_112/mp2/mp2.c.jones.

The above has been verified to work, boldface indicates user input, which is always after a colon.