Original author: Munehiro Fukuda
Revisions 2019: Morris Bernstein
The purpose of this lab is to familiarize yourself with Unix process management. You will write a program that creates a tree of processes. Each process will simulate doing a random amount of work, then parent processes will wait for their children to terminate and simulate an additional amount of work (presumably combining the results of its children).
You will use the following four system calls. Check their specifications in section 2 of the manual.
fork:
spawns a child process.
exit:
terminates the
process1.
wait:
suspends the process until one of its children terminates.
getpid:
returns the identifier of the calling process.
A skeleton program
lab-01-skel.cc
has been
provided2, 3.
Your job is to fill in the missing pieces identified by comments
containing the string
“TODO(lab)”.
Run your program with both an even and odd number of leaves to ensure that it works for both cases (5 and 6 should be sufficient).
Rename the skeleton file and fill in the missing pieces.
Submit the modified source file,
BUILD
script, and sample output.
The build script can be really simple: just the one-line
g++
command.
Plus, of course, the
shabang
line.
Although you can run
pstree
for definitive system output (see below),
when dealing with data structures, it is often handy to write a
script such as this one to
post-process
output to verify that the correct structure is created.
Most of the work for this lab is reading and understanding the skeleton. There are only a few lines of code to fill in.
The lab will be graded by running a
diff
between the skeleton and your solution.
If you're feeling really ambitious, modify the print statements to include current time so the output log will show the passage of time.
While your program is running, in a separate window, run the command
pstree -p <root_pid>
to see the tree.
You should get output that looks something like this:
lab-01(29207)─┬─lab-01(29208)─┬─lab-01(29210)─┬─lab-01(29215)─┬─lab-01(29222)
│ │ │ └─lab-01(29224)
│ │ └─lab-01(29216)
│ └─lab-01(29212)─┬─lab-01(29217)
│ └─lab-01(29221)
└─lab-01(29209)─┬─lab-01(29213)─┬─lab-01(29218)
│ └─lab-01(29220)
└─lab-01(29214)─┬─lab-01(29219)
└─lab-01(29223)
Your output should look something like this (for
leaves = 9):
Process 29207: leaves: 9; ancestors:
Process 29207: forked children: 29208 29209
Process 29207: interior processing begins
Process 29208: leaves: 5; ancestors: 29207
Process 29209: leaves: 4; ancestors: 29207
Process 29208: forked children: 29210 29212
Process 29208: interior processing begins
Process 29210: leaves: 3; ancestors: 29207 29208
Process 29209: forked children: 29213 29214
Process 29209: interior processing begins
Process 29212: leaves: 2; ancestors: 29207 29208
Process 29213: leaves: 2; ancestors: 29207 29209
Process 29214: leaves: 2; ancestors: 29207 29209
Process 29210: forked children: 29215 29216
Process 29210: interior processing begins
Process 29215: leaves: 2; ancestors: 29207 29208 29210
Process 29216: leaves: 1; ancestors: 29207 29208 29210
Process 29216: leaf processing begins
Process 29218: leaves: 1; ancestors: 29207 29209 29213
Process 29217: leaves: 1; ancestors: 29207 29208 29212
Process 29213: forked children: 29218 29220
Process 29218: leaf processing begins
Process 29217: leaf processing begins
Process 29212: forked children: 29217 29221
Process 29213: interior processing begins
Process 29219: leaves: 1; ancestors: 29207 29209 29214
Process 29212: interior processing begins
Process 29219: leaf processing begins
Process 29220: leaves: 1; ancestors: 29207 29209 29213
Process 29221: leaves: 1; ancestors: 29207 29208 29212
Process 29220: leaf processing begins
Process 29221: leaf processing begins
Process 29214: forked children: 29219 29223
Process 29214: interior processing begins
Process 29222: leaves: 1; ancestors: 29207 29208 29210 29215
Process 29222: leaf processing begins
Process 29223: leaves: 1; ancestors: 29207 29209 29214
Process 29215: forked children: 29222 29224
Process 29223: leaf processing begins
Process 29215: interior processing begins
Process 29224: leaves: 1; ancestors: 29207 29208 29210 29215
Process 29224: leaf processing begins
Process 29207: interior processing ends
Process 29208: interior processing ends
Process 29209: interior processing ends
Process 29210: interior processing ends
Process 29219: leaf processing ends
Process 29217: leaf processing ends
Process 29216: leaf processing ends
Process 29221: leaf processing ends
Process 29214: interior processing ends
Process 29220: leaf processing ends
Process 29215: interior processing ends
Process 29222: leaf processing ends
Process 29212: interior processing ends
Process 29224: leaf processing ends
Process 29218: leaf processing ends
Process 29223: leaf processing ends
Process 29213: interior processing ends
Process 29212: child 29217 terminated status: 0
Process 29212: child 29221 terminated status: 0
Process 29212: combining results from child processes
Process 29213: child 29220 terminated status: 0
Process 29210: child 29216 terminated status: 0
Process 29214: child 29219 terminated status: 0
Process 29213: child 29218 terminated status: 0
Process 29213: combining results from child processes
Process 29215: child 29222 terminated status: 0
Process 29214: child 29223 terminated status: 0
Process 29214: combining results from child processes
Process 29215: child 29224 terminated status: 0
Process 29215: combining results from child processes
Process 29212: complete (terminating EXIT_SUCCESS)
Process 29213: complete (terminating EXIT_SUCCESS)
Process 29214: complete (terminating EXIT_SUCCESS)
Process 29215: complete (terminating EXIT_SUCCESS)
Process 29208: child 29212 terminated status: 0
Process 29209: child 29213 terminated status: 0
Process 29209: child 29214 terminated status: 0
Process 29209: combining results from child processes
Process 29210: child 29215 terminated status: 0
Process 29210: combining results from child processes
Process 29209: complete (terminating EXIT_SUCCESS)
Process 29210: complete (terminating EXIT_SUCCESS)
Process 29207: child 29209 terminated status: 0
Process 29208: child 29210 terminated status: 0
Process 29208: combining results from child processes
Process 29208: complete (terminating EXIT_SUCCESS)
Process 29207: child 29208 terminated status: 0
Process 29207: combining results from child processes
Process 29207: complete (terminating EXIT_SUCCESS)
exit is really a library function that is a thin wrapper around the actual system call, _exit. It makes sure that any output buffered by standard library I/O routines gets written before program termination..cc is just as valid as .cpp for C++ source files. Your instructor happens to prefer the former. Don't get bent out of shape about it.