Why is the output of a fork() in a particular order?

Question

I am doing some Operating System 101 homework and digging through some C code.

I am new to C and Linux so i have this maybe unusual question. I had to examine a C program to figure out, how many processes it starts. So I read a lot and tinkered with the original code to answer the all the questions.

#include <unistd.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>

int main (void)
{
   printf("Start ID %d\n\n", getpid());

   printf("1.fork() from ");   
   printf("ID: %d\n", getpid());
   fflush(stdout);
   fork();

   printf("2.fork() from ");
   printf("ID: %d my parent is ID %d\n", getpid(), getppid());   
   fflush(stdout);
   fork();

   printf("3.fork() from ");
   printf("ID: %d my parent is ID %d\n", getpid(), getppid());  
   fflush(stdout);
   fork();

   sleep(2);   
   printf("%d finished. Good Night!\n", getpid());
   return EXIT_SUCCESS;
}

There is one thing I don't understand. Why are the outputs of printf() before the forks in this order:

1.fork() from ID: 3124
2.fork() from ID: 3124 my parent is ID 2215
3.fork() from ID: 3124 my parent is ID 2215
3.fork() from ID: 3126 my parent is ID 3124
2.fork() from ID: 3125 my parent is ID 3124
3.fork() from ID: 3125 my parent is ID 3124
3.fork() from ID: 3129 my parent is ID 3125

I would expect

1.fork() from ID: 3124
2.fork() from ID: 3124 my parent is ID 2215
3.fork() from ID: 3124 my parent is ID 2215
2.fork() from ID: 3125 my parent is ID 3124
3.fork() from ID: 3125 my parent is ID 3124
3.fork() from ID: 3126 my parent is ID 3124 
3.fork() from ID: 3125 my parent is ID 3124
3.fork() from ID: 3129 my parent is ID 3125

because PID 3124 starts PID 3125 with the first fork(), both another two child processes with the second and so on. Does the CPU not execute the processes in the order the have been created? This is not part of my homework, but I am still curious about it.

Answer 1

You can't really determine which process will be executed first. Like HackerBoss stated the printf can also influence this order.

Imagine your main program pid (3124) generates child 3125. After generating the child the following instruction needs to be invoked by both father and child:

printf("2.fork() from ");

At this point there are two directions:

1. Fater 3124 invokes the printf
2. Child 3125 invokes the printf

Since the printf requires I/O scheduling it depends on the process priority and on the resource state (there could be another process already already using the resource, making it a busy resource).

So it looks like in your program the father 3124 gets access to the resource first and continues executing up to the next fork, where child 3126 gets generated.

At this point there is the same question: in which direction shall I go? The next instruction is:

printf("3.fork() from ");

Directions are:

1. Fater 3124 invokes the printf
2. Child 3126 invokes the printf

From your program it looks like the first process to invoke it is child 3126.

So actually the printf does not assure you the process generation order. Since it is transparent how the I/O scheduling works, a better way would be to store a value in a specific address different for each process, by wrapping the fork in a if statement:

pid=fork();
if (pid == 0) {
    //child process
} else {
    //father process
}

This way you can have a better idea on what the process scheduler is doing, since it could actually be the process scheduler that starts a child before another, there are a lot of scheduling algorithms. At this point the OS you are running also influences the process execution order, depending on the used algorithm.