Homework 2

22C:116, Spring 1997

Due Friday Feb. 7, 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
                   _|_
                   / \
                  B   C
               __/     \__
               / \     / \
              D   E   F   G
               \_/     \_/
                 \     /  
                  H   I
                   \_/
                    |
                    J
   

   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 ABCDEFGHIJ, but it could, just as easily, output ACBFGIEDHJ. It should not, however, be able to output AHIJBCDEFG.

   Big Hint: See lecture 4 and note the following.

   If we assume that left branches in the above diagram are sequential processes, where the name of each process (for the sake of discussion) is the string of letters it prints, we have the following parent child relationships:

                   ABDHJ
                    / \
                  CFI  E
                   |
                   G
   

   Here, note that ABDHJ creates both CFI and E, and it must be prepared for them to terminate in any order. When forking, therefore, ABDHJ must remember the process IDs usef for both CFI and E, and when the time comes to join with E, if CFI terminates first, that must be remembered so that ABDHJ will not wait again for CFI after printing H.

2. With reference to the discussion of bounded buffers in Lecture 5, describe reasonable data structures and write reasonably detailed pseudocode for the enqueue and dequeue operations on FIFO queues, where the queues are implemented as linked lists of data records. Assume multiple producers and multiple consumers using multiple queues, where all queues contain data records of the same type.

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.