Assignment 10, due Nov. 9

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

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: Unix (and Linux) offer two ways to wait for a child process to terminate:

    If we ignore process groups and the exit status of a process, waitpid(id,NULL,0) has behavior that might appear the same as the following:

            for (;;) {
                    int i = wait(NULL);
                    if (i == id) break;
            }
    

    It is not the same. Consider what happens if a process does waitpid(a,NULL,0) followed by waitpid(b,NULL,0). Regardless of the order in which processes a and b terminate, the two waitpid() calls will work, while if you replaced them with the above for loop, they would fail.

    a) Why is the for loop not equivalent to the call to waitpid()? (0.4 points)

    b) Suppose the Unix/Linux kernel only had wait() and you wanted this logic:

            waitpid(a,NULL,0);
            code_after_a_terminates();
            waitpid(b,NULL,0);
            code_after_both_a_and_b_terminate();
    

    Write code to solve this problem using only wait(). (0.6 points)

  2. Background: In lecture on Monday, we said that there were always more processes than processors, and that if there were no useful processes that needed execution, we would keep the CPUs busy with idle processes, make-work.

    Some CPUs include a special machine instruction with a name like SLEEP. The SLEEP instruction stops the CPU clock (stopping the fetch-execute cycle) until there is an interrupt, at which point, the CPU resumes normal operation. Other than this, SLEEP is a no-op, with no side effects; the benefit of SLEEP is that power consumption is greatly decreased when the clock is stopped.

    Assume your operating system has a scheduler that supports the relinquish() system service as well as semaphores and the usual operations for process creation and destruction.

    a) Give appropriate code for an idle process -- feel free to call any system services and feel free to mix assembly code with high-level language code. (0.4 points)

    b) If the scheduler is a priority scheduler, what priority should your idle process have? (0.3 points)

    c) How many idle processes should be launched at system startup? (0.3 points)

    An aside: Participants in SETI@home and similar efforts install idle processes on their computers that do useful work in their computer's spare time instead of idling doing nothing.

  3. Background: Here is the FIFO queue implementation given in class:
    void enqueue( datatype item ) {
    	wait( freespace );
    	wait( mutex );
    	buffer[ tail ++ ] = item;
    	if (tail >= QUEUESIZE) tail = 0;
    	signal( mutex );
    	signal( data );
    }
    
    datatype dequeue() {
    	wait( data );
    	wait( mutex );
    	datatype item = buffer[ head++ ];
    	if (head >= QUEUESIZE) head = 0;
    	signal( mutex );
    	signal( freespace );
    }
    

    a) What are the initial values of all of the components of the queue object for an empty queue? (0.3 points)

    b) Did the mutex semaphore exclude too much? Should there, perhaps, be two mutual exclusion sempahores protecting different shared variables? Justify your answer by explaining why not or by showing how the code should be changed. (0.3 points)

    c) (0.4 points) Write a C struct queue declaration that allows you to create as many sharable FIFO queues as you want, and rewrite the enqueue() and dequeue() functions so that they take a pointer to the queue object as a parameter and operate on that queue. (0.4 points)