Computer Science 322
Operating Systems

Mount Holyoke College
Spring 2008

Lab 1: Process Tree
Due: 10:00 AM, Monday, February 11, 2008

This week's lab consists of a number of programming tasks. You may discuss them with each other, but what you turn in must be your own work. Unless otherwise specified, you should work on the cluster head node.

Practice Using Your fork()

Write the program for SG&G question 3.6. Call your program forkfib.c. Include a Makefile that compiles this program into an executable called forkfib.


Adding POSIX Shared Memory

Write the program for SG&G question 3.10. Call your program forkfibshared.c. Add a rule to your Makefile to compile this program into forkfibshared.

Once your program is working, add a call to sleep(2)2 to your program before you detach and free the shared memory segment. In a separate window, use the ipcs command to see that your shared memory segment is listed, and that it goes away when your program terminates.

A Process Tree

Write a C program that creates a "binary tree" of Unix processes. Call your program proctree.c and add a rule to your Makefile to compile this program into proctree.

Your program should take a single command-line parameter which specifies the number of levels in the binary process tree. Each process should be assigned a number corresponding to its position in a level-order traversal of the tree.

Given a height of 3, the tree can be thought of as this binary tree, where the parent-child links are not explicitly stored by your program but are part of the Unix process hierarchy. The tree should look something like this:

You won't draw a graphical representation, but your program's processes should print out the information about the tree, as follows:

-> ./proctree 3
 [1] pid 81142, ppid 48569
 [1] pid 81142 created left child with pid 81143
 [1] pid 81142 created right child with pid 81144
  [2] pid 81143, ppid 81142
  [3] pid 81144, ppid 81142
  [2] pid 81143 created left child with pid 81145
  [3] pid 81144 created left child with pid 81146
  [3] pid 81144 created right child with pid 81147
   [4] pid 81145, ppid 81143
  [2] pid 81143 created right child with pid 81148
   [6] pid 81146, ppid 81144
   [7] pid 81147, ppid 81144
   [5] pid 81148, ppid 81143
  [3] right child 81147 of 81144 exited with status 7
  [3] left child 81146 of 81144 exited with status 6
  [2] right child 81148 of 81143 exited with status 5
  [2] left child 81145 of 81143 exited with status 4
 [1] right child 81144 of 81142 exited with status 3
 [1] left child 81143 of 81142 exited with status 2

Note that each line of output is indented according to the depth of the node in the process tree and begins by printing the traversal position of the process that prints it.

Your program's processes should produce output in the following situations:

To be able to see what's happening and to reduce the chances that the output of your processes will be interleaved, you should put in calls to sleep(3).

You need not use shared memory for this program. In fact, it will probably confuse things if you try.

This program, as you are developing it, has a good chance of becoming a "fork bomb," a program that keep spawning new processes which can render a Unix system nearly useless. To reduce the chances that this happens, you should check the return value of your fork() calls and stop if it returns -1, which indicates that you were unable to spawn a process. You should also limit your trees to small heights when debugging. Feel free to try larger tree sizes once you're confident that your program is working to see how large a tree you can get before you run out of processes. Try it at least on a cluster FreeBSD machine (joba), a Solaris server (bullpen), and a Linux system in the Unix lab. To connect to bullpen and joba, you should first ssh to mhccluster, then to bullpen or joba. Please remember that the CS Cluster systems have a separate home directory structure. If you have a chance, find a Mac and try it there as well.

Submission and Evaluation

Submit using the turnin utility on the cluster. Please include your C source files and Makefile, but not your compiled executables. Make sure your name is in each file.

This lab will be graded out of 20 points. forkfib is worth 6 points, forkfibshared is worth 4 points, and proctree is worth 10 points. Programs will be evaulated based on correctness, documentation (have a comment describing the entire program and comments pointing out key parts of the code), and efficiency.