Introduction
The Collatz conjecture is a conjecture about a sequence of integers constructed by the following rules:
- if the previous term n is even, the next term is n / 2
- if the previous term n is odd, the next term is 3n+1
Lothar Collatz claimed that such a sequence always converges to 1. The following are a few examples:
- 7, 22, 11, 34. 17. 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
- 10, 5, 16, 8, 4, 2, 1
- 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
In this programming assignment, you will compute a Collatz sequence using N processes in a circular arrangement connected by N pipes written in a C (or C++) programs. In addition to these N (child) processes, the parent process interacts with the user, read the first number in the sequence from its stdin and pass it to the first (oldest) child's input pipe. This child then using its output pipe passes the next number to its sibling.
Upon receiving an input, it determines if the input is odd or even, computes the next number, and passes it to the next (younger) sibling. When a child receives a 1, it will not pass the number to the next (younger sibling.)
An example scenario (with 3 children)
The parent process reads 10 from its stdin and passes it to P0:
| Process | Action |
|---|---|
| P0 | computes 10/2, pass 5 to P1 |
| P1 | computes 3*5 + 1, pass 16 to P2 |
| P2 | computes 16/2, pass 8 to P0 |
| P0 | computes 8/2, pass 4 to P1 |
| P1 | computes 4/2, pass 2 to P2 |
| P2 | computes 2/2, pass 1 to P0 |
| P1 | receives a 1 (do not pass to P2) |
Program Requirements
Shut Down Procedure
From the example scenario above it should be clear that each child process has to run in a loop that reads its input from a pipe, and write its output to the next pipe. But how do you tell all the children to break out of that loop?
To stop the entire program, the user will enter 0. The parent process then informs the first child to shutdown, who will then use its pipe to tell its next sibling to shutdown, and so on.
WARNING
Regardless the level option you implemented below, your program must be
- Free of memory leak. Any single case of memory leak reported valgrind (in either parent or child processes) will result in a 2-point penalty.
- Free of orphan processes, otherwise it will result in a 3-point penalty (collectively, not per child).
The grouping of requirements into the C-, B-, and A-levels below is tentative. Items may be moved from one group to another.
C-Level
- The parent runs in a loop that waits for the user to enter the first number in the sequence. This implies, a single run of your program can be used to generate a several Collatz sequences. When the user enters a zero, the entire program executes its shutdown procedure.
- The number of child processes can be hardcoded (minimum 3)
- Use
usleep()delay in the child loop to observe the progress at a slower rate - Each child process prints the input that it receives
- At the beginning of its loop each child print "Child xxxx is ready" (where xxxx is the PID)
- All the child processes shall be able to break the loop gracefully and print a "Child xxxx is done" at the end of its loop
B-Level
In addition to the C-level requirements:
- The number of child processes is supplied from the command line
- Configuring the pipes and child processes shall be done using loop(s)
- Out of 2N pipe descriptors created in your program:
- Only two of them are used by each child process. Add necessary code in each child to close the 2N-2 unused pipes
- Only one of them is used by the parent process. Add necessary code in the parent process to close the 2N-1 unused pipes.
- In addition to printing its input number, each process keeps a tally of odd/even numbers received. When it breaks out of its loop, each child reports (on its stdout) the statistics of its PID, odd/even numbers received when the entire system shuts down.
A-Level
In addition to the B-level requirements:
- Using a different set of pipes, before prompting the user to enter the first number of the first sequence, the parent also waits for a "ready message" from every child before. Note: subsequent sequences do not require this "ready message"
- Instead of the child printing its odd/even statistics, each child shall report these numbers to the parent who will in turn print these numbers (one line per child) together each child PID.
Grading Rubrics
For C-level (28 points)
| Grading Item | Point |
|---|---|
| Setup the program for at least 3 pipes and 3 children | 5 |
| Program design: organize code into function(s) to avoid code duplication | 5 |
| Each child process is connected to the correct input/output pipes | 3 |
| Each child prints its "ready message" at the beginning of its loop | 2 |
| Use delay in child process | 2 |
| Each child prints its incoming number | 2 |
| Each child computes the next number and pass it to the next sibling | 3 |
| Correct handling of child shutdown by the parent | 3 |
| Correct handling of shutdown by the children | 3 |
| Penalty for orphan children | -3 |
| Penalty for memory leak | -2 * N |
For B-level (+6 points)
| Grading Item | Point |
|---|---|
| Handle a variable number of children | 2 |
| Close all unused pipes the parent and children, and all the pipes at shutdown | 2 |
| Each child keeps counter of odd/even input and print them at shutdown | 2 |
For A-level (+6 points)
| Grading Item | Point |
|---|---|
| Create extra pipes for communication from children to parent | 2 |
| Parent reads the first number from user after all children are ready | 2 |
| Children report odd/even counters to parent and parent summarizes the output | 2 |
Deliverables
- Upload the source code of your implementation to Bb
- Be ready for a demo during lab hour