I have a C program, which loops ‘n’ times calling fork each loop. How many child processes do this program create?

First let’s consider a program which loops 2 times:

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#define N 2
int main(){
 int i;
 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: 2^1

Number of children with ‘i’ as 3: 2^2

..

Number of children with ‘i’ as N: 2^(n-1)

Now we know that sum of G.P is \dfrac {a (r^n - 1)}{r - 1}

Hence, total number of child precesses created is: \dfrac {1 (2^n - 1)}{2 - 1}2^n - 1

One thought on “I have a C program, which loops ‘n’ times calling fork each loop. How many child processes do this program create?

  1. Pingback: Quora

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>