Homework 2

22C:116, Fall 1997

Due Friday Sept. 5, 1997, in class

1. Write a program on any UNIX system that uses the fork(), exit() and wait primitives to construct the following program structure:

                    A
                   _|_
             parent/ \child
                  B   \
               __/     \
         parent/ \child \
              C   D      E
               \_/      /
                 \     /  
                  F   /
                   \_/
                    |
                    G
   

   Each letter indicates an output operation that should output the corresponging letter, and flow of control is from top to bottom, with no loops. So, your program might, when run, output ABCDEFG, but it could, just as easily, output AEBDCFG. It should not, however, be able to output ABCEFDG.

   Big Hint: See lecture 4 and note the following.

   The parent process in the above diagram outputs ABCFG, while one child outputs D and the other outputs E; the parent will have to selectively wait for thild D to finish before it outputs F, and the parent must not mistake the termination of child D for child E!

   Note that fprintf() output routines in C buffer their output! Therefore, you should either use write() to output each character (avoiding the buffering) or you should use the sequence of fprintf();fflush() (this defeats the buffering).

2. With reference to the discussion of bounded buffers in Lecture 5, note that there are two primary characteristics of a bounded buffer: 1) the size of the items being buffered, and 2) the number of items in the buffer. Unix pipes are a kind of bounded buffer. Propose a series of experiments you could conduct to determine the item size and the number of items in a Unix pipe? (note that pipes are accessed by the read() and write() Unix system calls, and that the use of bytes as the basic unit of data transfer by these calls does not imply that the bounded buffers that implement pipes view each byte as a single item).

3. Section 2.2.4 of Tannenbaum suggests using the primitives sleep and wakeup(p). Sleep causes the caller's process to be suspended (put in the waiting state), and wakeup(p) causes process p to become ready -- wakeup has no effect on a ready process, but it undoes the effect of sleep for a waiting process. Can you use sleep and wakeup to create a working mutual exclusion mechanism that is not based on busy waiting? If not, why not?

4. Priority schedulers generally assign a numerical priority to each process, and when a scheduling decision must be made, they select the highest priority ready process as the next process to be run. In terms of abstract data types, this involves replacing the FIFO ready queue with a non-FIFO priority queue. Refer to the material you have studied in data structures and algorithms, and identify an appropriate and efficient priority queue implementation.

   For this implementation, discuss the problems you would encounter in a large scale shared memory multiprocessor where many CPU's (under the direction of the operating system) were competing to take processes from and add processes to the ready queue.