GATE Overflow Test Series | Operating Systems | Test 1 | Question: 15

Question

A process executes the following segment of code :

int foo(int n)
{
    int i;
    for(i=0; i <n; i++)
    {
        for(j = 0; j < n; j++)
        {
            if(j < i)
            {
                fork();
            }
        }
    ​}
    return 0;
}

The total number of child processes created if foo is called with parameter $n = 5$ is _______

Answer 1

fork(), copies the current process image, and creates a child process which starts executing from the next instruction onward. fork() returns the child process id to the parent and $0$ to the child process.
 
 In the given code, $i$ and $j$ loop execute n times. But the if condition will be true for in total $0+1+2+\ldots n-1 = n(n-1)/2$ times. For each of these, the fork() ensures the number of processes doubles.
 
 For $n=5$ we'll have $5*4/2 = 10$ times the if condition gets TRUE and so, the number of processes created will be $2^{10} = 1024.$ But out of this $1$ is the parent process and total number of child processes $=1023.$

Comments

if you think in this way then it would be much simpler to answer

suppose A program

for(i=0 ; i<5, i++)

{

fork();

}
Now this can be written in this way

fork();

fork();

fork();

fork();

fork();

 So there are 5 fork for So , it will create the 2^5-1 which is 31 child process

Now coming to the question

i= 0

j = 0,1,2,3,4
In this execution , all the condition is false
So here,no fork generated.

i=1

j=0,1,2,3,4,5

(0,1) this condition is true
one fork generated (1)

fork();

i=2

j=0,1,2,3,4,5

(0,2) (1,2)  this condition is true
two  fork generated

fork();

fork();

and So On.

Now :

if we open the loop we will get the fork in sequence

n(n-1)/2 which is 10

fork();

fork();

fork();

fork();

fork();

fork();

fork();

fork();

fork();

fork();

So this 2^10-1  so answer is 1023