Issue
I am learning how fork works with Unix-like operating systems. I want to create exactly 9 child processes with each parent can only create 2 children. So this is a binary fork algorithm.
However I can't manage to limit the correct number of children to create in third recursion call.
Here is the flow of creating children.
Here is the code I have right now.
#include <iostream.h>
#include <sys/wait.h>
#include <unistd.h>
#include <stdlib.h>
using namespace std;
static int CHILD_SIZE = 9;
static int LEVEL = 1;
static int MAX_LEVEL = 3;
void createChildren(int remaining, int level) {
int CURRENT_REMAINING = remaining;
if(CURRENT_REMAINING <= 0 || level > MAX_LEVEL){
return;
}
pid_t firstChild,secondChild;
// Fork the first child
firstChild = fork();
if(firstChild == -1){
cerr << "Fork failed!" << endl;
}
else if (firstChild == 0 && CURRENT_REMAINING > 1)
{
// first child
cout << "First child process (PID: " << getpid() << ") with parent process (PID: " << getppid() << ") at level: " << level << endl;
// calculate how many child needs after this iteration
CURRENT_REMAINING -= (2 * level);
if(CURRENT_REMAINING < 0){
CURRENT_REMAINING = 0;
}
}
else if (firstChild > 0 && CURRENT_REMAINING > 1)
{
// Fork the second child
secondChild = fork();
if(firstChild == -1){
cerr << "Fork failed!" << endl;
}
else if (secondChild == 0) {
// second child
waitpid(firstChild, NULL, 0);
cout << "Second child process (PID: " << getpid() << ") with parent process (PID: " << getppid() << ") at level: " << level << endl;
// calculate how many child needs after this iteration
CURRENT_REMAINING -= (2 * level);
if(CURRENT_REMAINING < 0){
CURRENT_REMAINING = 0;
}
} else if (secondChild > 0){
// Wait for both child processes to complete
waitpid(firstChild, NULL, 0);
waitpid(secondChild, NULL, 0);
}
}
//---------- recursion call-----------//
// upper child recursion call
if(firstChild == 0){
cout << "current remaining in first child is: " << CURRENT_REMAINING << " at level " << level << endl;
createChildren(CURRENT_REMAINING, level + 1);
}
// lower child recursion call
if(secondChild == 0){
cout << "current remaining in second child is: " << CURRENT_REMAINING << " at level " << level << endl;
if(CURRENT_REMAINING > 3){
//cout << "Create two more processes" << endl;
createChildren(CURRENT_REMAINING, level + 1);
}
}
}
int main() {
std::cout << "Parent process " << getpid() << std::endl;
createChildren(CHILD_SIZE, LEVEL);
return 0;
}
Here is the output:
Parent process 8571
First child process (PID: 8573) with parent process (PID: 8571) at level: 1
current remaining in first child is: 7 at level 1
Second child process (PID: 8574) with parent process (PID: 8571) at level: 1
current remaining in second child is: 7 at level 1
First child process (PID: 8575) with parent process (PID: 8573) at level: 2
current remaining in first child is: 3 at level 2
First child process (PID: 8576) with parent process (PID: 8574) at level: 2
current remaining in first child is: 3 at level 2
Second child process (PID: 8577) with parent process (PID: 8573) at level: 2
current remaining in second child is: 3 at level 2
Second child process (PID: 8578) with parent process (PID: 8574) at level: 2
current remaining in second child is: 3 at level 2
First child process (PID: 8579) with parent process (PID: 8575) at level: 3
current remaining in first child is: 0 at level 3
Second child process (PID: 8581) with parent process (PID: 8575) at level: 3
current remaining in second child is: 0 at level 3
First child process (PID: 8580) with parent process (PID: 8576) at level: 3
current remaining in first child is: 0 at level 3
Second child process (PID: 8582) with parent process (PID: 8576) at level: 3
current remaining in second child is: 0 at level 3
the first call makes 2 children the second call makes 4 children and the third call makes 4, but should be 3 instead.
Solution
You want each process to fork() at most twice, so you shouldn’t need any loops, recursion or some such.
Given a command line argument 9, the following program will print 10 times Terminating. and 9 times Waited for: <pid>, which seems to be what your drawing specifies.
#include <errno.h>
#include <sys/wait.h>
#include <unistd.h>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <sstream>
namespace {
struct Process {
Process() : pid{fork()} { if (pid == -1) throw -1; }
bool is_child() const { return pid == 0; }
void disarm() { pid = 0; }
~Process() { if (pid)
std::cout << (std::stringstream{}
<< "Waited for: " << waitpid(pid, nullptr, 0) << '\n') .str(); }
private:
pid_t pid;
};
struct Blah { ~Blah() { std::cout << "Terminating.\n"; } };
} // namespace
int main(int argc, const char *const argv[]) {
Blah blah;
if (argc != 2) return EXIT_FAILURE;
size_t remaining;
if (!(std::stringstream{argv[1]} >> remaining)) return EXIT_FAILURE;
fork_again:
const size_t old_remaining{remaining};
remaining = old_remaining / 2 + old_remaining % 2;
if (!remaining) return EXIT_SUCCESS;
Process firstFork;
if (firstFork.is_child()) {
if (--remaining) goto fork_again; else return EXIT_SUCCESS;
}
remaining = old_remaining - remaining;
if (!remaining) return EXIT_SUCCESS;
const Process secondFork;
if (secondFork.is_child()) {
firstFork.disarm();
if (--remaining) goto fork_again;
}
}
With just the two unconstrained fork()s, it would be an equivalent of this Bash awesomeness:
_()(_&_&);_
To tame the exponential growth in the number of processes, we limit the number of times a process can fork() as we proceed up the fork()ing tree, and that number needs to decrease exponentially if we want a constant total number of fork()s.
The rest is all about getting the details (somewhat) right. The first subtree is granted remaining / 2 + remaining % 2 of fork()s, the second subtree gets the rest. This handles both odd and even cases correctly. Additionally, all processes other than the original (grand)parent must count themselves too, which is why they always start with --remaining.
The use of RAII in this code is controversial when it comes to readability, due to the goto. I’m almost sure there is a way to implement it without a backward-jumping goto statement, but I’m also way too lazy to figure this out.
Answered By - Andrej Podzimek Answer Checked By - Timothy Miller (WPSolving Admin)