Process forking for parallelism in Ruby - Time & Space Complexity

Time Complexity: Process forking for parallelism

O(n)

Understanding Time Complexity

When using process forking, we want to see how the program's running time changes as we create more child processes.

We ask: How does splitting work into parallel processes affect the total time spent?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def parallel_work(tasks)
      pids = []
      tasks.each do |task|
        pid = Process.fork do
          task.call
          exit!
        end
        pids << pid
      end
      pids.each { |pid| Process.wait(pid) }
    end
    

This code runs a list of tasks in parallel by creating a new process for each task, then waits for all to finish.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each task to fork a process.
• How many times: Once per task, so as many times as tasks count.
• Secondary operation: Loop to wait for each child process to finish.
• Dominant operation: Forking processes for each task, since it starts parallel work.

How Execution Grows With Input

As the number of tasks grows, the program creates more processes, but they run at the same time.

Input Size (n)	Approx. Operations
10	10 forks + 10 waits, tasks run in parallel
100	100 forks + 100 waits, tasks run in parallel
1000	1000 forks + 1000 waits, tasks run in parallel

Pattern observation: The number of forks and waits grows linearly with tasks, but total time depends on longest task, not sum.

Final Time Complexity

Time Complexity: O(n)

This means the number of operations grows linearly with the number of tasks, but actual runtime can be much faster due to parallel execution.

Common Mistake

[X] Wrong: "Forking many processes always makes the program run n times faster."

[OK] Correct: Creating many processes adds overhead and system limits; also, tasks run in parallel but total time depends on the slowest task, not just number of tasks.

Interview Connect

Understanding how process forking affects time helps you explain parallelism clearly and shows you can think about real program performance beyond just code logic.

Self-Check

"What if we limited the number of child processes running at the same time? How would that change the time complexity?"

Practice

1. What does the fork method do in Ruby?

easy

A. It pauses the current process until a condition is met.

B. It creates a new child process that runs concurrently with the parent.

C. It merges two processes into one.

D. It terminates the current process immediately.

Solution

1. Step 1: Understand the purpose of fork

   The fork method creates a new process, called the child, which runs alongside the original parent process.

2. Step 2: Identify the behavior of the child process

   The child process runs the code block given to fork independently, allowing parallel execution.

3. Final Answer:

   It creates a new child process that runs concurrently with the parent. -> Option B

4. Quick Check:

   fork creates child process = A [OK]

Hint: Fork means start a new process running alongside parent [OK]

Common Mistakes:

• Thinking fork pauses the process
• Confusing fork with process termination
• Assuming fork merges processes

2. Which of the following is the correct syntax to create a child process using fork in Ruby?

easy

A. child_pid = fork puts 'Hello from child'

B. fork = child_pid { puts 'Hello from child' }

C. fork child_pid { puts 'Hello from child' }

D. child_pid = fork { puts 'Hello from child' }

Solution

1. Step 1: Recall the correct fork syntax

   The fork method takes a block with curly braces or do-end to run code in the child process.

2. Step 2: Check each option's syntax

   child_pid = fork { puts 'Hello from child' } correctly assigns the child process ID and uses a block with curly braces. Options A, C, and D have syntax errors or incorrect usage.

3. Final Answer:

   child_pid = fork { puts 'Hello from child' } -> Option D

4. Quick Check:

   Use block with fork = B [OK]

Hint: Fork needs a block with braces or do-end [OK]

Common Mistakes:

• Omitting braces for the block
• Assigning fork incorrectly
• Using wrong order of arguments

3. What will be the output of this Ruby code?

pid = fork do
  puts 'Child process'
end
Process.wait(pid)
puts 'Parent process'

medium

A. Child process
Parent process

B. Child process

C. Parent process
Child process

D. Parent process

Solution

1. Step 1: Understand the fork and wait behavior

   The fork creates a child process that prints 'Child process'. The parent waits for the child to finish using Process.wait(pid).

2. Step 2: Determine output order

   The child prints first, then the parent prints 'Parent process' after the child ends.

3. Final Answer:

   Child process Parent process -> Option A

4. Quick Check:

   Child prints before parent after wait = C [OK]

Hint: Parent waits, so child prints first [OK]

Common Mistakes:

• Assuming parent prints first
• Ignoring Process.wait effect
• Confusing output order

4. Identify the error in this Ruby code using fork:

pid = fork do
  puts 'Child running'
end
puts 'Parent running'
Process.wait

medium

A. Process.wait called without PID argument

B. Missing block for fork

C. fork does not return a PID

D. puts statements are inside the fork block

Solution

1. Step 1: Check usage of Process.wait

   The Process.wait method should be called with the child's PID to wait for that specific process.

2. Step 2: Identify the error

   In the code, Process.wait is called without any argument, which waits for any child process but can cause unexpected behavior or errors if multiple children exist.

3. Final Answer:

   Process.wait called without PID argument -> Option A

4. Quick Check:

   Always pass PID to Process.wait = A [OK]

Hint: Pass child PID to Process.wait to avoid errors [OK]

Common Mistakes:

• Calling Process.wait without PID
• Confusing fork return value
• Misplacing puts statements

5. You want to run two tasks in parallel using fork and wait for both to finish before continuing. Which code correctly achieves this?

hard

A. pids = fork { task1; task2 }
Process.wait(pids)
puts 'Both done'

B. fork { task1 }
fork { task2 }
puts 'Both done'

C. pids = []
pids << fork { task1 }
pids << fork { task2 }
pids.each { |pid| Process.wait(pid) }
puts 'Both done'

D. fork { task1; Process.wait }
fork { task2; Process.wait }
puts 'Both done'

Solution

1. Step 1: Understand how to fork multiple processes

   Each fork creates a child process. To run two tasks in parallel, fork twice and store both child PIDs.

2. Step 2: Wait for both child processes

   Use Process.wait(pid) for each PID to ensure both finish before continuing.

3. Step 3: Analyze options

   pids = [] pids << fork { task1 } pids << fork { task2 } pids.each { |pid| Process.wait(pid) } puts 'Both done' correctly forks twice, stores PIDs, waits for both, then prints. Others either don't wait or misuse fork.

4. Final Answer:

   pids = [] pids << fork { task1 } pids << fork { task2 } pids.each { |pid| Process.wait(pid) } puts 'Both done' -> Option C

5. Quick Check:

   Fork twice, wait both PIDs = D [OK]

Hint: Store PIDs, wait each to sync parallel tasks [OK]

Common Mistakes:

• Not waiting for child processes
• Calling Process.wait inside child
• Forking once for multiple tasks