Assignment 11, due Apr 28

Solutions

Part of the homework for 22C:112, Spring 2008
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: See the assignment for MP6 and the code distributed with that assignment.

    Note, in this code that, before each call to copy(), both ends of the pipe are closed, and that Note, in this code that, before each call to copy() copies from stdin to stdout.

    a) Explain exactly what change the program does to the input as it copies it to the output. Feel free to compile and test this code to answer this question. (0.5 points)

    The copy() routine adds a leading underscore to each blank in the file. Since copy() processes each character twice (once in the parent process, once in the child), the net effect is to add two underscores before each blank.

    b) Given that the descriptors returned in creating the pipe are all closed before the call to copy(), and that copy() copies from stdin to stdout, explain how the data can flow through the pipe. (0.5 points)

    In the parent process, the read end of the pipe is made to become standard input, while in the child process, the write end of the pipe is made to become standard outputs. The dup2 kernel call is used to implicitly close a file and then make it become the same file as an already open file.

  2. Background: Our Linux implementation includes a number of semaphore operations, summarized under sem_overview in part 7 of the programmer's manual.

    A Problem: Evaluate the appropriateness of these semaphores with regard to the synchronization requirements of machine problem 6. (1 point)

    First, note that a bounded buffer with a single producer and a single consumer never needs mutual exclusion, since the producer is the only process that manipulates the tail pointer, and the consumer is the only process that manipulates the head pointer.

    Two semaphores could still be useful, one to count the amount of data in the queue (initially zero), one to count the free space in the queue (initially the queue capcity). Unnamed memory-based semaphores are the right primitive for this. Each semaphore can be opened and given its initial value with sem_init(), after which sem_wait() and sem_post() should be used to wait and signal that semaphore. Finally sem_destroy() should be used before the program exits.

    Note, however, that if semaphores prove difficult to use, busy waiting with a call to usleep(10000) once per iteration (a 1/100 second wait) would work quite well.

  3. Background: Dekker's solution to the mutual exclusion problem only solves the problem for two competing processes.

    A problem: How can this be generalized to an arbitrary number of processes? Show that you understand this by explaining how to use it for 5 processes that must compete to enter a critical section. (1 point)

    Whenever you have a binary operator and you need to do an n-ary operation, the usual solution is to form a tree. To add 5 numbers, for example, you can do (a+b)+((c+d)+e). The same goes for using 2-process mutual exclusion mechanisms to arbitrate between 5 processes. Just set up a tournament tree for the processes to enter the critical section. It will take 4 semaphores to arbitrate this tree. Consider the following flow diagram:

    a   b   c   d   e
     \ /     \ /   /
      M       N   /    a: lock(M)      b: lock(M)        c: lock(N)
       \       \ /        lock(P)         lock(P)           lock(O)
        \       O         -- crit --      -- crit --        lock(P)
         \     /          unlock(P,M)     unlock(P,M)       -- crit --
          \   /                                             unlock(P,O,N)
           \ /         d: lock(N)      e: lock(O)
            P             lock(O)         lock(P)
            |             lock(P)         -- crit --
                          -- crit --      unlock(P,O)
                          unlock(P,O,N)