CODEWITHSUNDEEP
coperating-systemfork
Steven Chou
Steven Chou

Reputation: 2215

How many process are created by a program that calls fork in a loop with N iterations?

#include<stdio.h>
#include<unistd.h>

int main()
{
    int i;
    for(i=0;i<4;i++)
        fork();
    return 0;
}

my question:Include the initial parent process, how many processes created by the program?

I think this answer is 1+4=5, 1 parent process and 4 child process. Am I right?

Upvotes: 3

Views: 63700

Answers (8)

hughyi
hughyi

Reputation: 21

The first call of fork() will create the first out of 4 children of this parent, and each of the first children will have 3 remaining fork() calls. Which means that each will create 3 children, and the first child of each of those 3 will create 2, and so on.
(What the highly upvoted answer on this page left out is the last child on the leftmost leaf.)

4 fork() calls total creation of processes

Upvotes: 2

ggorlen
ggorlen

Reputation: 56955

For the code

for (int i = 0; i < 4; i++) fork();

you can unroll the loop and annotate the steps:

fork(); // 1 process will execute this fork, 2 processes exist afterwards
fork(); // 2 processes will execute this fork, 4 processes exist afterwards
fork(); // 4 processes will execute this fork, 8 processes exist afterwards
fork(); // 8 processes will execute this fork, 16 processes exist afterwards

there will be 15 child processes and 1 parent process, 16 total. The process tree looks like:

a─┬─b─┬─f─┬─l───p
  │   │   └─m
  │   ├─g───n
  │   └─h
  ├─c─┬─i───o
  │   └─j
  ├─d───k
  └─e

The a process spawns 4 children: b, c, d and e. b starts after the first fork() and spawns 3 children, f, g, h. c starts after the second fork() and spawns 2 children. And so on. Each of those children also have fork()s in their execution, so they'll spawn more children "recursively".

The issue with OP's attempt is that it doesn't consider branching--that children spawn more children when they hit fork()s in their execution.

Existing answers provide solutions of varying degrees of usefulness, but I'd like to add a general strategy to work through these sort of problems on paper (assuming homework/exam scenario, where you can't run the code), regardless of the code structure (there may be branches present and other tricks).

Start with 1 process and begin at its main(). Execute the code operation by operation mentally. When you encounter a fork() call, make a copy of the code and continue execution on the child process after the fork() returns. This is hard to keep track of mentally, so you can unroll loops as above, then annotate each fork with the number of children that execute it, taking into account branches and control flow. Writing it down step by step should make it feasible to walk through.

The presence of branches (ifs) will usually reduce the total number of processes and cannot increase it. If there are no branches, then the total number of processes will be a power of 2, including the original root process.

Upvotes: 0

Kalyan Sharma
Kalyan Sharma

Reputation: 1

According to question: n = 4 Total no. of processes can be created = 2^n = 2^4 = 16 .

Upvotes: 0

H Rostami
H Rostami

Reputation: 1

enter image description here

This solution inspired by OS reference books that means the parent process at each level goes to the next branch and the previous branch terminates, because of this we just count leafs.

Upvotes: 0

ALIshhde
ALIshhde

Reputation: 1

its so simple, in this question You just notice that the question said including the initial parent process, so in this case the 2 * 2 * 2 * 2 - 1 is the number of process created and because the question said, including the initial parent, the answer is 16. Goodluck :)

Upvotes: 0

Jaime Montoya
Jaime Montoya

Reputation: 7701

Answer using fork() three times

The answer using fork() four times is: 2 * 2 * 2 * 2 - 1 = 16 - 1 = 15 processes.

Upvotes: 12

Aki008
Aki008

Reputation: 403

for(i=0;i<4;i++)
    fork();

This piece of code is equivalant to:

fork();
fork();
fork();
fork();

Lets say that process start with p0. The process graph will look like:

Process-creation diagram

The above image says it all, when first fork() gets executed it creates a new process and three fork() are left to execute. Now, here exists a parent thread and a child thread to execute three more fork() statments. So, child process p1 will create p5,p6 and p7 and parent process will create p2, p3 and p4. After p2 has been created two more fork() needs to be executed for this child thread p2 which was created after execution of 2nd fork() statment. In this way, this parent-child processes are created.

Upvotes: 8

John Saxton
John Saxton

Reputation: 540

Try adding a sleep statement to the end of your program like so:

#include<stdio.h>
#include<unistd.h>

int main()
{
    int i;
    for(i=0;i<4;i++)
        fork();
    sleep(10000);
    return 0;
}

Next, compile and run your program. Then run pstree to see what the process hierarchy looks like.

Upvotes: 4

Related Questions