Thread synchronization with Mutex in Ruby - Time & Space Complexity

Time Complexity: Thread synchronization with Mutex

O(n)

Understanding Time Complexity

When using threads with a mutex, we want to see how the program's speed changes as more work is done.

We ask: How does locking and unlocking affect the time as the input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

require 'thread'

mutex = Mutex.new
counter = 0

threads = 10.times.map do
  Thread.new do
    1000.times do
      mutex.synchronize do
        counter += 1
      end
    end
  end
end

threads.each(&:join)

This code creates 10 threads, each adding 1 to a shared counter 1000 times, using a mutex to avoid conflicts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop runs 1000 times per thread, each time locking and unlocking the mutex to update the counter.
• How many times: 10 threads x 1000 times = 10,000 total synchronized increments.

How Execution Grows With Input

As the number of threads or increments grows, the total locking operations grow proportionally.

Input Size (n)	Approx. Operations
10 threads x 1000 increments	10,000 mutex locks/unlocks
10 threads x 10,000 increments	100,000 mutex locks/unlocks
100 threads x 10,000 increments	1,000,000 mutex locks/unlocks

Pattern observation: The total operations grow directly with the number of threads and increments combined.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the total number of increments across all threads.

Common Mistake

[X] Wrong: "Using a mutex makes the program run in constant time regardless of input size."

[OK] Correct: Each lock and unlock still takes time, so as the number of increments grows, the total time grows too.

Interview Connect

Understanding how mutex locking affects time helps you write safe and efficient multi-threaded programs, a useful skill in many real projects.

Self-Check

"What if we replaced the mutex with a lock-free atomic operation? How would the time complexity change?"

Practice

1. What is the main purpose of using a Mutex in Ruby threads?

easy

A. To create new threads automatically

B. To prevent multiple threads from accessing shared data at the same time

C. To speed up thread execution by running them in parallel

D. To stop threads from running

Solution

1. Step 1: Understand what shared data means in threads

   Shared data is information that multiple threads can access or change.

2. Step 2: Identify the role of Mutex

   Mutex ensures only one thread changes shared data at a time to avoid errors.

3. Final Answer:

   To prevent multiple threads from accessing shared data at the same time -> Option B

4. Quick Check:

   Mutex protects shared data = prevent simultaneous access [OK]

Hint: Mutex locks shared data to avoid conflicts between threads [OK]

Common Mistakes:

• Thinking Mutex speeds up threads
• Believing Mutex creates threads
• Assuming Mutex stops threads completely

2. Which of the following is the correct way to use a Mutex to protect a critical section in Ruby?

easy

A. mutex.synchronize { critical_code }

B. mutex.lock; critical_code

C. mutex.run(critical_code)

D. mutex.start { critical_code }

Solution

1. Step 1: Recall Mutex usage in Ruby

   Ruby's Mutex class provides a synchronize method to wrap critical code safely.

2. Step 2: Compare options

   Only mutex.synchronize { critical_code } is the correct and safe syntax.

3. Final Answer:

   mutex.synchronize { critical_code } -> Option A

4. Quick Check:

   Use synchronize method to protect code [OK]

Hint: Use mutex.synchronize { } to wrap critical code [OK]

Common Mistakes:

• Forgetting to unlock mutex after lock
• Using non-existent methods like run or start
• Not wrapping critical code in a block

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

require 'thread'
mutex = Mutex.new
counter = 0
threads = 3.times.map do
  Thread.new do
    2.times do
      mutex.synchronize { counter += 1 }
    end
  end
end
threads.each(&:join)
puts counter

medium

A. 2

B. 3

C. 6

D. 0

Solution

1. Step 1: Count total increments

   There are 3 threads, each increments counter 2 times, total 3*2=6 increments.

2. Step 2: Understand mutex effect

   Mutex ensures increments happen safely without losing counts, so final counter is 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   3 threads * 2 increments each = 6 [OK]

Hint: Multiply threads by increments inside synchronize block [OK]

Common Mistakes:

• Ignoring mutex and expecting wrong count
• Counting only one thread's increments
• Confusing thread join effect

4. Identify the problem in this Ruby code using Mutex and how to fix it:

require 'thread'
mutex = Mutex.new
counter = 0
threads = 2.times.map do
  Thread.new do
    mutex.lock
    counter += 1
  end
end
threads.each(&:join)
puts counter

medium

A. Threads are not joined properly; fix by joining inside the thread block

B. Mutex is not needed here; remove mutex.lock

C. counter should be initialized inside the thread

D. Missing mutex.unlock causes deadlock; fix by adding mutex.unlock after increment

Solution

1. Step 1: Check mutex usage

   Mutex is locked but never unlocked, causing threads to wait forever (deadlock).

2. Step 2: Fix by unlocking mutex

   After increment, call mutex.unlock or better use mutex.synchronize to auto-handle locking/unlocking.

3. Final Answer:

   Missing mutex.unlock causes deadlock; fix by adding mutex.unlock after increment -> Option D

4. Quick Check:

   Always unlock mutex after lock to avoid deadlock [OK]

Hint: Always unlock mutex or use synchronize block [OK]

Common Mistakes:

• Forgetting to unlock mutex
• Removing mutex when needed
• Initializing shared data inside threads incorrectly

5. You want to safely update a shared hash from multiple threads in Ruby. Which approach correctly uses Mutex to avoid race conditions?

shared_hash = {}
mutex = Mutex.new
threads = 5.times.map do |i|
  Thread.new do
    10.times do |j|
      # What goes here?
    end
  end
end
threads.each(&:join)
puts shared_hash.size

hard

A. mutex.synchronize { shared_hash[i * 10 + j] = "value" }

B. shared_hash[i * 10 + j] = "value"

C. mutex.lock; shared_hash[i * 10 + j] = "value";

D. Thread.pass; shared_hash[i * 10 + j] = "value"

Solution

1. Step 1: Understand thread safety for shared hash

   Multiple threads writing to shared_hash need protection to avoid data corruption.

2. Step 2: Use mutex.synchronize for safe updates

   mutex.synchronize { shared_hash[i * 10 + j] = "value" } wraps the update inside mutex.synchronize, ensuring only one thread writes at a time.

3. Final Answer:

   mutex.synchronize { shared_hash[i * 10 + j] = "value" } -> Option A

4. Quick Check:

   Use synchronize block to protect shared hash updates [OK]

Hint: Wrap shared data updates inside mutex.synchronize { } [OK]

Common Mistakes:

• Updating shared hash without mutex
• Locking mutex without unlocking
• Using Thread.pass instead of mutex