First let’s consider a program which loops 2 times:
#define N 2
for (i = 1; i <= N; i++) fork();
printf("Hey! from %d\n", getpid());
This program prints “Hey”, 4 times to the console, hence it creates 3 child processes. Let’s figure out how!
Note: The child processes have their local copies of variables, hence any operations on the variables won’t affect the parent’s copy or the other children’s copy.
1) The parent process (P0) runs through the loop 2 times, hence creating 2 child processes (P1 and P2). These child processes get their local copies of ‘i’ which is 1 for the first child and 2 for the second child. Thus, P2 runs through the loop 1 time while the P1 runs through the loop 2 times.
Note: The child always start executing from the instruction immediately after fork, which is i++ in our case.
2) P2 increments i from 2 to 3, followed by the comparison “i <= N” which obviously evaluates to false. Hence, P2 doesn’t create any processes.
3) P1 increments i from 1 to 2, it then executes fork() which creates another child with i as 2, lets call this child “P1_1″. After that it increments i from 2 to 3 and exits out of the loop.
4) P1_1 increments i from 2 to 3, and exits out of the loop.
So, at the end of the loop we have 3 children (P1, P2, P1_1).
Let’s now figure out the number of children for a program which loops ‘N’ times.
Let Pn be the nth child of the parent process, Pn_n be the nth child of the nth child of the parent process and so on.
Children with ‘i’ as 1: 1 (P1)
Children with ‘i’ as 2: 2 (P1_1, P2)
Children with ‘i’ as 3: 4 (P1_2, P2_1, P3, P1_1_1)
Do you notice a pattern in the above written numbers?
Number of children with ‘i’ as 1: 1
Number of children with ‘i’ as 2:
Number of children with ‘i’ as 3:
Number of children with ‘i’ as N:
Now we know that sum of G.P is
Hence, total number of child precesses created is: =