OS handout

Question

For following code how many times the '*' will printed?

main()

{

     int i,n ;

     for(i = 1 ; i<=n ; ++i)

     {

         fork();

         printf("*");

     }

}

Comments

https://gateoverflow.in/3707/gate-it-2004-question-64

---

2+4+8+16+...+$2^n$ = 2($2^n$-1)

Answer 1

For each $fork()$ function call, the parent creates one child. So, there are $2$ child nodes for each fork call (i.e. one parent + one child). The above example creates a complete binary tree, where each level from $1$ to $n$ describes a total number of children after a $fork()$ system call. After, $n$ level, the tree is left with one parent + $(n-1)$ child, each of which executes the printf(“*”). For each iteration of the for loop, the print(“*”) will be executed.

$\therefore$ total number of $* =$ (total number of nodes possible for tree with n+1 height) – 1

$=(2^{n+1}-1) – 1$

$=2^{n+1}-2$

ex- for n=2, total number of * will be $2^3-2=6$

Comments

But in the question it's just asked about no.of * printed and here there'll be more than 2^n * printed .

After each fork in the same process one * will be printed and at the end i.e. the leaf will be 2^n .If we calculate all of them it'll be Greater than 2^n 

For example:

F() means fork()

let p(*) means print(*)

n=2 in the loop then

Parent

|F()---------------------|-child 

|P(*).   1               |-P(*) 2

|F()------| ​​​​​​childp.   |-F()--------|child

|P(*)3   |P(*)4       |-P(*)5     |P(*)6

Totally 6 * printed here 

 

 

---

You are right. Thanks for commenting 👍

Answer 2

Since there is a `printf("*");` statement inside the loop and the loop will run `n` times, each process will print '*' `n` times.

For every iteration of the loop, the number of processes doubles because both the parent and child processes will fork again in the next iteration. So,

the total number of '*' printed by all processes combined will be `2^n`, where `n` is the value of `n` in the loop condition.

Comments

we want generalised term in the form of n

---

@Ray Tomlinson  

chatGPt ?

---

It's a just basic concept , if we study in coaching in very first class this formula taught by teachers.🙂

Answer 3

2 + 4 + 8 + 16 + ... + 2^n