This article focuses on calculating the total number of proccesses in a code that uses fork(). But first lets describe fork briefly.
In an operating system, particularly in the context of the Unix operating system, the term fork, or the function fork, is an operation where a process creates a copy of itself in order to start the execution of a different process. This copy, known as “child process”, then calls the exec system call to overlay itself with the other program, basically ending execution of former program in favor of the other. The fork operation creates a seperate address space for the child, but the child has an exact copy of all the memory segments of the parent process1. In short, fork allows user procceses to start other proccess while running.
How to Fork?
The fork function is quite simple, here is a “Hello World” of forking.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(void) {
pid_t pid = fork();
if (pid < 0) { // error if forked process returns pid < 0
perror("fork failed"); // no new processes is created
exit(EXIT_FAILURE);
}
// fork is successful, both procceses are executing in main, and must branch based on pid
else if (pid == 0) { // child fork returns pid of 0, handle child process
printf("Hello from the child process!\n"); // can exec other program here
_exit(EXIT_SUCCESS);
}
else { // parent process returns pid > 0
int status;
printf("Hello from parent process");
(void)waitpid(pid, &status, 0);
}
return EXIT_SUCCESS;
}
Calculating how many forks?
These are related problems to calculating exactly how many child processes are created. All of the problems below can use these following libraries to run.
1
2
3
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
Using g++ -o file.o file.cpp, we can run the code locally.
Problem 1
How many times is hello world printed?
1
2
3
4
5
int main () {
fork();
fork();
print("Hello World\n");
}
Four times!
Problem 2
How many child processes are created by fork? Try drawing the relationship between the proccesses.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define LOOP 3
int main() {
int pid;
int i;
for (i = 0; i < LOOP; i++) {
pid = fork();
if (pid < 0) {
printf("Error occured\n");
}
else if (pid == 0) { // handle child proccesses
printf("Child Process i=%d, pid=%d, parent pid=%d\n", i, getpid(), getppid());
}
else {
wait(NULL);
}
}
}
Since fork is called LOOP number of times, there is a total of 2^LOOP proccesses, and 2^LOOP -1 child proccesses. The output of the program (the pid’s will be different every run), is
1
2
3
4
5
6
7
Child Process i=0, pid=13916, parent pid=13915
Child Process i=1, pid=13917, parent pid=13916
Child Process i=2, pid=13918, parent pid=13917
Child Process i=2, pid=13919, parent pid=13916
Child Process i=1, pid=13920, parent pid=13915
Child Process i=2, pid=13921, parent pid=13920
Child Process i=2, pid=13922, parent pid=13915
The child creation “tree” can be described below,
The child creation process can be broken down as such, where the P0 represents the parent process, and with each loop, each child calls fork and creates its own child proccess. As we can see, there a total of 2^LOOP -1 child proccesses
Wait, why add wait(NULL)? This is because the parent process is finished by the time the child asks for its parents pid. When a process is finished, all its children are reassigned as children of the init process, which has a pid of 1. Thus, we must use wait() in the paren’ts code to wait for the child to execute. This type of child process is known as “orphan processes”. If we didn’t use it, we would have gotten something like this
1
2
3
4
5
6
7
Child Process i=0, pid=13546, parent pid=13545
Child Process i=1, pid=13547, parent pid=13545
Child Process i=1, pid=13549, parent pid=13546
Child Process i=2, pid=13551, parent pid=1
Child Process i=2, pid=13552, parent pid=1
Child Process i=2, pid=13550, parent pid=13547
Child Process i=2, pid=13548, parent pid=1
Which was not what we expected to see.
Problem 3
How many child processes are created by fork?
1
2
3
4
5
6
int main() {
if (fork() && fork() || fork() && fork() || fork() && fork() && fork()) {
printf("A\n");
}
return 0;
}
Problem 4
How many child processes are created by fork? Try with print("A") instead, see what happens. Why?
1
2
3
4
5
6
7
int main() {
for (int i = 0; i < 2; i++) {
if (fork() || (fork() && fork()) || !fork()) {
printf("A\n");
}
}
}
Problem 5
How many child process are created by fork?
1
2
3
4
5
6
7
8
9
10
11
12
int main() {
int i = 1;
if (fork()) {
i++;
}
else if (fork()) {
i--;
}
else {
i++;
}
}
Related Sources
Footnotes
This is before good memory management, now, it doesn’t copy the memory, instead, it is simply set on (copy on write) ↩