Problem Description

You have a class Foo with three methods: first(), second(), and third(). Each method prints its respective name ("first", "second", or "third").

The challenge is that the same instance of Foo will be shared among three different threads:

• Thread A will call first()
• Thread B will call second()
• Thread C will call third()

Your task is to design a synchronization mechanism to ensure that these methods are always executed in the correct order, regardless of how the operating system schedules the threads. Specifically:

1. second() must execute only after first() has completed
2. third() must execute only after second() has completed

The solution uses two locks (l2 and l3) that are initially acquired in the constructor. The first() method can run immediately and releases l2 when done, allowing second() to proceed. The second() method waits to acquire l2, then releases l3 when done, allowing third() to proceed. The third() method waits to acquire l3 before executing.

This ensures the output is always "first" → "second" → "third", even if the threads are scheduled to run in any order by the operating system.

Intuition

The key insight is that we need to create dependencies between the threads - each thread should wait for the previous one to complete before it can proceed. Think of it like a relay race where each runner can only start when they receive the baton from the previous runner.

Since we don't control when threads are scheduled by the operating system, we need synchronization primitives to enforce ordering. The natural choice is to use locks or semaphores as "gates" that control when each method can execute.

The pattern we're looking for is:

• first() should run immediately (no waiting)
• second() should wait until first() signals it's done
• third() should wait until second() signals it's done

This suggests we need two synchronization points - one between first() and second(), and another between second() and third(). We can implement this with two locks that act as barriers:

1. Lock l2 blocks second() from running until first() releases it
2. Lock l3 blocks third() from running until second() releases it

By acquiring both locks in the constructor, we ensure that second() and third() will block when they try to acquire their respective locks. Then each method releases the lock for the next method in sequence, creating a chain of execution: first() → releases l2 → second() can run → releases l3 → third() can run.

This elegant solution uses the lock's mutual exclusion property not for protecting shared data, but as a signaling mechanism to coordinate thread execution order.

Solution Approach

The solution uses a lock-based synchronization mechanism to enforce the execution order of the three methods. Let's walk through the implementation step by step:

Initialization:

def __init__(self):
    self.l2 = threading.Lock()
    self.l3 = threading.Lock()
    self.l2.acquire()
    self.l3.acquire()

We create two locks (l2 and l3) and immediately acquire them. This is crucial - by acquiring these locks in the constructor, we're setting up barriers that will block second() and third() from executing until the appropriate locks are released.

Method Execution Flow:

1. first() method:

   def first(self, printFirst: 'Callable[[], None]') -> None:
       printFirst()
       self.l2.release()

   • Executes immediately without any blocking (no lock acquisition needed)
   • After printing "first", it releases lock l2
   • This signals that second() can now proceed

2. second() method:

   def second(self, printSecond: 'Callable[[], None]') -> None:
       self.l2.acquire()
       printSecond()
       self.l3.release()

   • Attempts to acquire lock l2 (will block until first() releases it)
   • Once acquired, prints "second"
   • Releases lock l3 to allow third() to proceed

3. third() method:

   def third(self, printThird: 'Callable[[], None]') -> None:
       self.l3.acquire()
       printThird()

   • Attempts to acquire lock l3 (will block until second() releases it)
   • Once acquired, prints "third"

Why This Works:

The pattern creates a dependency chain through lock acquisition and release:

• l2 acts as a gate between first() and second()
• l3 acts as a gate between second() and third()

No matter which order the threads are scheduled by the operating system, the locks ensure the correct execution sequence. For example, if Thread C (calling third()) starts first, it will immediately block on l3.acquire() and wait until Thread B releases that lock, which in turn can only happen after Thread A releases l2.

Alternative Approach with Semaphores:

As mentioned in the reference, we could also use semaphores with initial counts:

• Semaphore a with count 1 (allows first() to run immediately)
• Semaphore b with count 0 (blocks second() initially)
• Semaphore c with count 0 (blocks third() initially)

The semaphore approach follows the same signaling pattern but uses counting semaphores instead of binary locks, providing essentially the same synchronization behavior.

Example Walkthrough

Let's walk through a concrete example where three threads are scheduled in the worst-case order to demonstrate how the lock mechanism ensures correct execution.

Scenario: Threads scheduled in reverse order (C → B → A)

Initial State:

• l2 is acquired (locked)
• l3 is acquired (locked)
• OS schedules threads: Thread C starts first, then B, then A

Step 1: Thread C starts and calls third()

Thread C: third() → tries to acquire l3 → BLOCKED (l3 is locked)
Thread C waits...

Step 2: Thread B starts and calls second()

Thread B: second() → tries to acquire l2 → BLOCKED (l2 is locked)
Thread B waits...
Thread C still waiting...

Step 3: Thread A starts and calls first()

Thread A: first() → executes printFirst() immediately → prints "first"
Thread A: releases l2
Thread B: wakes up! Acquires l2 successfully
Thread C still waiting...

Step 4: Thread B continues

Thread B: now has l2 → executes printSecond() → prints "second"
Thread B: releases l3
Thread C: wakes up! Acquires l3 successfully

Step 5: Thread C continues

Thread C: now has l3 → executes printThird() → prints "third"

Final Output: "first" → "second" → "third"

Even though the OS scheduled the threads in completely reverse order (C, B, A), the lock mechanism enforced the correct execution sequence. Thread C and B had to wait at their respective lock acquisition points until the previous methods in the sequence completed and released the appropriate locks. This demonstrates how the solution handles any possible thread scheduling order.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) and the space complexity is O(1).

Time Complexity Analysis:

• The __init__ method performs a constant number of operations: creating two locks and acquiring them, which are all O(1) operations.
• The first method executes printFirst() and releases a lock, both O(1) operations.
• The second method acquires a lock, executes printSecond(), and releases another lock, all O(1) operations.
• The third method acquires a lock and executes printThird(), both O(1) operations.
• Each method performs a fixed number of operations regardless of input size, resulting in O(1) time complexity.

Space Complexity Analysis:

• The class uses exactly two threading.Lock objects (self.l2 and self.l3), which occupy a constant amount of memory.
• No additional data structures are created that scale with input size.
• The space usage remains constant regardless of how many times the methods are called, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Lock Not Released on Exception

One critical pitfall in this implementation is that if an exception occurs in printFirst() or printSecond(), the subsequent locks won't be released, causing permanent deadlock for the waiting threads.

Problem Example:

def first(self, printFirst: Callable[[], None]) -> None:
    printFirst()  # If this throws an exception...
    self.lock_for_second.release()  # This never executes!

Solution: Use try-finally blocks to ensure locks are always released:

def first(self, printFirst: Callable[[], None]) -> None:
    try:
        printFirst()
    finally:
        self.lock_for_second.release()

def second(self, printSecond: Callable[[], None]) -> None:
    self.lock_for_second.acquire()
    try:
        printSecond()
    finally:
        self.lock_for_third.release()

2. Reusability Issue

The current implementation can only be used once. After all three methods execute, the locks remain in their final state (both released), so subsequent calls won't maintain the ordering constraint.

Problem Scenario:

foo = Foo()
# First round works fine
foo.first(lambda: print("first"))
foo.second(lambda: print("second"))
foo.third(lambda: print("third"))

# Second round - all methods can run immediately!
foo.third(lambda: print("third"))  # Runs without waiting
foo.first(lambda: print("first"))  # Order is broken

Solution: Reset the locks after each complete cycle or use a different synchronization primitive like barriers or condition variables that can be reset:

class ReusableFoo:
    def __init__(self):
        self.first_done = threading.Event()
        self.second_done = threading.Event()
      
    def first(self, printFirst):
        printFirst()
        self.first_done.set()
      
    def second(self, printSecond):
        self.first_done.wait()
        printSecond()
        self.second_done.set()
      
    def third(self, printThird):
        self.second_done.wait()
        printThird()
        # Reset for next round
        self.first_done.clear()
        self.second_done.clear()

3. Resource Leak with Acquired but Unreleased Locks

If the Foo object is destroyed or goes out of scope while threads are still waiting on locks, those threads may hang indefinitely.

Solution: Implement proper cleanup in a destructor or context manager:

def __del__(self):
    # Ensure locks are released if object is destroyed
    try:
        self.lock_for_second.release()
    except:
        pass
    try:
        self.lock_for_third.release()
    except:
        pass

4. Confusing Lock Names

The original variable names l2 and l3 are unclear and can lead to maintenance issues. Using descriptive names like lock_for_second and lock_for_third makes the code's intent clearer and reduces the chance of errors during modifications.