Assignment 10, Solutions

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

  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)

    Because the loop forgets the process IDs of each process that has already terminated. Thus, in the example, if processes a and b terminate in the wrong order, the first loop would wait until the second process terminates, discarding the ID of the other process, and then the second loop will never terminate.

    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)

            bdone = FALSE;
            for (;;) {
                    int i = wait(NULL);
                    if (i == b) bdone = TRUE;
                    if (i == a) break;
            }
            code_after_a_terminates();
            if (!bdone) for (;;) {
                    int i = wait(NULL);
                    if (i == b) break;
            }
            code_after_both_a_and_b_terminate();
    

  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)

    void idle() {
    	for (;;) {
    		relinquish();
    		SLEEP;
    	}
    }
    

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

    The least possible priority, so that all other processes have more priority.

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

    As many idle processes as there are processors.

    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 );
    	return item; /* easy to fix error -- this was missing */
    }
    

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

    • The data semaphore has a count of zero.
    • The freespace semaphore has a count of QUEUESIZE.
    • The mutex semaphore has a count of 1 meaning unclaimed.
    • head and tail are equal and set to any value from zero QUEUESIZE-1.

    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)

    head and tail can be protected separately, each with its own mutual-exclusion semaphore. They are called headex and tailex in the following code:

    void enqueue( datatype item ) {
    	wait( freespace );
    	wait( tailex );
    	buffer[ tail++ ] = item;
    	if (tail >= QUEUESIZE) tail = 0;
    	signal( tailex );
    	signal( data );
    }
    
    datatype dequeue() {
    	wait( data );
    	wait( headex );
    	datatype item = buffer[ head++ ];
    	if (head >= QUEUESIZE) head = 0;
    	signal( headex );
    	signal( freespace );
    	return item;
    }
    

    This works because the code to enqueue an item only uses the tail pointer, while the code to dequeue only uses the head pointer. Using two separate semaphores allows the greater potential parallelism because enqueue and dequeue can operate completely independently so long as the queue is neither full nor empty.

    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)

    struct queue {
    	char buffer[QUEUESIZE];
    	int head;
    	int tail;
    	semaphore freespace;
    	semaphore data;
    	semaphore mutex; /* could as easily be headex and tailex */
    };
    
    void enqueue( struct queue * q, datatype item ) {
    	wait( q->freespace );
    	wait( q->mutex ); /* could be tailex */
    	q->buffer[ q->tail ++ ] = item;
    	if (q->tail >= QUEUESIZE) q->tail = 0;
    	signal( q->mutex ); /* could be tailex */
    	signal( q->data );
    }
    
    datatype dequeue( struct queue * q ) {
    	wait( q->data );
    	wait( q->mutex ); /* could be headex */
    	datatype item = q->buffer[ q->head++ ];
    	if (q->head >= QUEUESIZE) q->head = 0;
    	signal( q->mutex );
    	signal( q->freespace );
    	return item;
    }