SME
Operating Systems · Problem type
Processes after n forks
Use this for “A program calls fork() 3 times in a row. How many processes are there at the end, and how many are children?”
This is an example. Type your own values to start a new problem.
N
=
2
C
=
N
−
1
Formulas
N
=
2
n
8
=
2
3
C
=
N
−
1
7 = 8 − 1
Assumptions
•
The program starts as one process, and the fork() calls run one after another with no test around them.
•
Each fork() succeeds and its child goes on from the next line, so it runs the rest of the calls too.
•
No process exits until all the calls are done.
Step-by-step
WE KNOW
n = 3
FIND
processes at the end (N), new processes made (C)
Step 1 · Find processes at the end (N)
Use N = 2ⁿ
Every process alive runs each fork() and becomes two, so each call doubles the count from 1.
N
=
2
3
N
=
8
Step 2 · Find new processes made (C)
Use C = N − 1
Every process but the first one was made by a call to fork().
C
=
8
−
1
C
=
7
Check
Put the numbers back in. Both sides should match.
8
=
2
3
✓
7 = 8 − 1 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Processes and threads
Main lesson
Cost of a context switch
Use this for “The time slice is 10 ms and a context switch takes 0.1 ms. What share of the CPU time does useful work?”
CPU use with I/O waits
Use this for “Each process waits for I/O 80% of the time. With 4 processes in memory, how busy is the CPU?”