Problem Breakdown
We need to coordinate two asynchronous threads running on a shared instance of FooBar. Thread A executes foo() and prints “foo”, while Thread B executes bar() and prints “bar”. The critical constraint is that they must alternate strictly: every iteration consists of printing “foo” followed immediately by “bar”, resulting in the string “foobar” repeated n times.
Inputs:
- Integer
n(number of iterations). - Two threads calling methods on a shared object instance.
Outputs:
- A sequence where “foo” and “bar” are printed interleaved perfectly:
"foobar"x n.
Implicit Constraints & Edge Cases:
- Concurrency Safety: Without synchronization, both threads could print simultaneously or out of order (e.g.,
barbefore the firstfoo). We must prevent race conditions on shared state if any existed (though here we only care about output ordering). - Deadlock Prevention: If Thread B calls
bar()and waits for a signal that never comes, it hangs. Initialization of synchronization primitives is crucial to ensure progress regardless of thread scheduling priority at startup. - Zero Iterations (
n=0): The loops should simply not execute; no output required.
Intuition
A brute force approach where we just print inside the loop without coordination will fail because threads run independently and asynchronously. If Thread B runs before Thread A, it might try to print “bar” immediately, violating the order constraint. Even if they are synchronized with a simple lock, checking state (e.g., turn flag) requires careful logic to avoid busy-waiting or deadlocks.
Key Insight:
We can model this as a producer-consumer problem where each thread passes control (“tokens”) to the other after completing its task. Using Semaphores is more idiomatic for “hand-off” synchronization than simple locks with flags, though both work. We initialize one semaphore (for foo) to allow it to run first immediately, and another (for bar) to 0 so that Thread B must wait until signaled by the completion of a previous iteration’s foo.
Optimal Approach: Use two semaphores:
- Initialize
foo_semwith value 1 (allows immediate execution). - Initialize
bar_semwith value 0 (forces waiting initially). - In each method, acquire the corresponding semaphore to ensure it’s your turn, print, then release the other thread’s semaphore to signal completion and allow the next step in the sequence.
Approach
- Setup: Create a
FooBarclass with an__init__method that initializes two semaphores (foo_sem,bar_sem). Setfoo_sem = Semaphore(1)so Thread A can start, andbar_sem = Semaphore(0)to enforce waiting for the first signal. - Method Logic:
- Inside
foo(): Acquirefoo_sem. Print “foo”. Releasebar_sem(signal that it’s Bar’s turn). - Inside
bar(): Acquirebar_sem. Print “bar”. Releasefoo_sem(signal back to Foo for the next iteration).
- Inside
- Looping: Wrap this logic in a loop running from
0ton-1inside each method, ensuring exactly n pairs are printed across both threads combined.
Complexity Analysis
- Time Complexity: . Each of the two methods runs exactly times total (distributed between threads). The synchronization overhead is constant per iteration (), so linear time relative to
n. - Space Complexity: . We use a fixed number of semaphores and variables regardless of input size.
Solution
import threading
class FooBar:
def __init__(self, n):
self.n = n
# Initialize two semaphores to control turn-taking between threads.
# foo_sem starts at 1 so the 'foo' thread can run immediately on first call.
# bar_sem starts at 0 so the 'bar' thread must wait for a signal from 'foo'.
self.foo_semaphore = threading.Semaphore(1)
self.bar_semaphore = threading.Semaphore(0)
def foo(self):
"""Thread A calls this method to print 'foo'."""
for _ in range(self.n):
# Wait until it is our turn (acquire token).
self.foo_semaphore.acquire()
print("foo") # Print "foo" safely
# Signal that we are done, allowing Thread B ('bar') to proceed.
self.bar_semaphore.release()
def bar(self):
"""Thread B calls this method to print 'bar'."""
for _ in range(self.n):
# Wait until signaled by the previous 'foo'.
self.bar_semaphore.acquire()
print("bar") # Print "bar" safely
# Signal back that we are done, allowing Thread A ('foo') to proceed.
self.foo_semaphore.release()