Assignment 11, due Nov. 16

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: As originally developed, Unix (and Linux, for that matter) had no semaphore services. These were eventually added, as an afterthought, in two semi-incompatible varieties (Posix versus System V). As with many such afterthoughts, it looks like the designers tried to throw in every idea anyone ever had about the subjectl; in addition, they avoided using the standard names for semaphore operations.

    Use man -k semaphore to find all man pages relating to Linux semaphores. One of the pages is an overview; read it first.

    Now, suppose you have a program that forks into several processes that share a memory segment attached using shmat() prior to forking. The objects allocated in that segment need to incorporate semaphores, perhaps several in some objects.

    a) How would you declare one such semaphore as a component named semf of a C structure, and once an instance obj of that structure is allocated, how would you initialize the obj.semf semaphore to have an initial count of zero. (0.4 points)

    b) Give Linux code to wait on the obj.semf semaphore. (0.3 points)

    c) (0.3 points) Give Linux code to signal on the obj.semf semaphore.

  2. Background: Linux supports Posix threads. See man pthreads for detail.

    A question: Can you figure out whether these are kernel threads or user threads. What information in the man page leads you to this conclusion? (Quoting Dr. Google does not count here, although Google can easily give you an answer, you must locate the reason for that conclusion in the man page.) (0.5 points)

  3. A question: Suppose you use user-level threads, for example, something like the thread library in the course home page. What happens to your application when one of the threads does a read() from the keyboard? (0.5 points)

  4. Background: Consider the following implementation of a priority queue:
    struct item {
            struct item * next; /* makes items queueable */
            int priority;
    };
    
    struct queue {
            struct item * head; /* the head item in the queue */
    };
    
    void enqueue( struct queue * q, struct item * i ) {
            if ((q->head == NULL)
            ||  (i->priority > q->head->priority)) {
                    /* enqueue in empty queue or at queue head */
                    i->next = q->head;
                    q->head = i;
            } else { /* linear search for place in queue */
                    struct item * p = q->head;
                    while ((p->next != NULL)
                    &&     (i->priority <= p->next->priority)) {
                            /* march on down the queue */
                            p = p->next;
                    }
                    i->next = p->next;
                    p->next = i;
            }
    }
    
    struct item * dequeue( struct queue * q ) {
            struct item * i = q->head;
            if (i != NULL) {
                    q->head = i->next;
            }
            return i;
    }
    

    All is well and good if the above code is used by just one process. Now ask, what if the priority queue is in a shared heap and is used by multiple processes (or threads)?

    a) Add a semaphore or semaphores to the above code so that it will work for queues in a shared heap. Note that there are two solutions. One is quite easy, using only one semaphore per queue for mutual exclusion. Give that solution. (0.5 points)

    b) That solution has a serious problem: As the queue grows longer, the time spent in the critical seciton for enqueue grows, limiting potential parallelism. There is a better solution involving multiple semaphores, one per item. Briefly describe it -- do not attempt to write code. (0.5 points)

Machine Problem 6

Due Dec 3

Modify the Minimally Usable Shell from MP3, either your solution or the posted solution, so that it supports one additional feature, shell pipes.

If a line contains the symbols, | (vertical bars), these are command delimiters dividing the line into two or more separate commands. Thus, a b | c | d e f is the command a b followed by c followed by d e f.

You may require spaces around the pipe symbol to avoid having to change the way your parse commands.

In addition, whenever two commands are separated by a pipe symbol, they are run in parallel, in two different processes, and the standard output (file descriptor 1) of the command on the left hand side is piped into standard input (file descriptor 0) of the one on the right hand side.

Turn in your solution following the usual procedures.