Process creation (fork and exec) in Operating Systems - Time & Space Complexity

Time Complexity: Process creation (fork and exec)

O(n)

Understanding Time Complexity

When a new process is created using fork and exec, it is important to understand how the time taken grows as the system handles more processes.

We want to know how the cost of creating processes changes as the number of processes increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++) {
    pid_t pid = fork();
    if (pid == 0) {
        execve("/bin/program", args, envp);
        exit(0);
    }
}
    

This code creates n child processes by calling fork in a loop, then each child replaces its program image using exec.

Identify Repeating Operations

• Primary operation: The loop runs fork() n times to create n processes.
• How many times: The fork system call is executed once per iteration, so n times.

How Execution Grows With Input

Each new process requires a fork call, which duplicates the current process, and then an exec call to load a new program.

Input Size (n)	Approx. Operations
10	About 10 forks and 10 execs
100	About 100 forks and 100 execs
1000	About 1000 forks and 1000 execs

Pattern observation: The total work grows directly with the number of processes created.

Final Time Complexity

Time Complexity: O(n)

This means the time to create processes grows linearly with the number of processes requested.

Common Mistake

[X] Wrong: "Forking multiple processes happens all at once and takes constant time regardless of n."

[OK] Correct: Each fork call duplicates the process separately, so the total time adds up with each new process created.

Interview Connect

Understanding how process creation scales helps you reason about system performance and resource management in real applications.

Self-Check

"What if we replaced fork with a thread creation call? How would the time complexity change?"

Practice

1. What does the fork() system call do in an operating system?

easy

A. Replaces the current process with a new program

B. Creates a new process by copying the current process

C. Terminates the current process immediately

D. Pauses the current process temporarily

Solution

1. Step 1: Understand the role of fork()

   The fork() call creates a new process by duplicating the current one, including its code and data.

2. Step 2: Differentiate from exec()

   Unlike exec(), which replaces the process, fork() makes a copy, so both processes continue running.

3. Final Answer:

   Creates a new process by copying the current process -> Option B

4. Quick Check:

   fork() = process copy [OK]

Hint: Remember: fork copies, exec replaces [OK]

Common Mistakes:

• Confusing fork() with exec()
• Thinking fork() replaces the process
• Believing fork() pauses the process

2. Which of the following is the correct way to use exec() in a program?

easy

A. exec("ls -l")

B. exec("/bin/ls", "-l")

C. exec("/bin/ls", ["ls", "-l"])

D. exec("ls", "-l")

Solution

1. Step 1: Recall exec() syntax

   The exec() family requires the program path and an argument list, where the first argument is the program name.

2. Step 2: Identify correct argument format

   exec("/bin/ls", ["ls", "-l"]) correctly passes the path and an array with the program name and its argument.

3. Final Answer:

   exec("/bin/ls", ["ls", "-l"]) -> Option C

4. Quick Check:

   exec() needs path + argument list [OK]

Hint: exec() needs program path and argument array [OK]

Common Mistakes:

• Passing arguments as separate strings instead of array
• Using command line string instead of path
• Omitting the program name in argument list

3. Consider this code snippet in a Unix-like system:

pid = fork()
if pid == 0:
    exec("/bin/echo", ["echo", "Hello"])
else:
    print("Parent process")

What will be printed when this code runs?

medium

A. Parent process
Hello

B. Parent process

C. Hello

D. Hello
Parent process

Solution

1. Step 1: Understand fork() behavior

   The fork() creates a child process. The child runs the exec() replacing itself with the echo program.

2. Step 2: Analyze output from parent and child

   The parent (pid > 0) prints "Parent process". The child (pid == 0) calls exec(), loading /bin/echo which prints "Hello". Both outputs appear on stdout, typically with parent first.

3. Final Answer:

   Parent process Hello -> Option A

4. Quick Check:

   fork() + child exec() = both print [OK]

Hint: fork() child exec(): both print, parent first [OK]

Common Mistakes:

• Thinking only parent prints
• Reversing the output order
• Believing exec() prevents child output

4. What is wrong with this code snippet?

pid = fork()
if pid == 0:
    exec("ls", ["ls", "-l"])
else:
    print("Parent")

medium

A. The exec call is missing the full path to the program

B. fork() should be replaced with exec()

C. The parent process should call exec() instead

D. The argument list to exec() should be a string, not a list

Solution

1. Step 1: Check exec() usage

   The exec() call requires the full path to the executable, not just the command name.

2. Step 2: Identify the missing full path

   Using "ls" without "/bin/ls" will cause exec to fail because it won't find the program.

3. Final Answer:

   The exec call is missing the full path to the program -> Option A

4. Quick Check:

   exec() needs full path [OK]

Hint: Always use full path in exec() [OK]

Common Mistakes:

• Using command name without path in exec()
• Confusing fork() and exec() roles
• Passing wrong argument types to exec()

5. A program wants to run another program safely without stopping itself. Which sequence of system calls should it use?

hard

A. Call exec() first, then fork()

B. Call exec() directly to run the new program

C. Call fork() twice, then the parent calls exec()

D. Call fork() to create a child, then the child calls exec()

Solution

1. Step 1: Understand process creation and replacement

   Calling exec() replaces the current process, so calling it directly stops the original program.

2. Step 2: Use fork() then exec() in child

   By calling fork(), the program creates a child process. The child can then call exec() to run the new program, leaving the parent running.

3. Final Answer:

   Call fork() to create a child, then the child calls exec() -> Option D

4. Quick Check:

   fork() then exec() = safe new program run [OK]

Hint: fork first, then exec in child to keep parent alive [OK]

Common Mistakes:

• Calling exec() directly and losing original process
• Calling fork() twice unnecessarily
• Calling exec() before fork()