Welcome to Subscribe On Youtube
1114. Print in Order
Description
Suppose we have a class:
public class Foo {
public void first() { print("first"); }
public void second() { print("second"); }
public void third() { print("third"); }
}
The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().
Note:
We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.
Example 1:
Input: nums = [1,2,3] Output: "firstsecondthird" Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.
Example 2:
Input: nums = [1,3,2] Output: "firstsecondthird" Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.
Constraints:
numsis a permutation of[1, 2, 3].
Solutions
Solution 1: Multithreading + Lock or Semaphore
We can use three semaphores $a$, $b$, and $c$ to control the execution order of the three threads. Initially, the count of semaphore $a$ is $1$, and the counts of $b$ and $c$ are $0$.
When thread $A$ executes the first() method, it first needs to acquire semaphore $a$. After acquiring successfully, it executes the first() method, and then releases semaphore $b$. This allows thread $B$ to acquire semaphore $b$ and execute the second() method.
When thread $B$ executes the second() method, it first needs to acquire semaphore $b$. After acquiring successfully, it executes the second() method, and then releases semaphore $c$. This allows thread $C$ to acquire semaphore $c$ and execute the third() method.
When thread $C$ executes the third() method, it first needs to acquire semaphore $c$. After acquiring successfully, it executes the third() method, and then releases semaphore $a$. This allows thread $A$ to acquire semaphore $a$ and execute the first() method.
The time complexity is $O(1)$, and the space complexity is $O(1)$.
Solution 2: Multithreading + Barrier
In Python, a Barrier is a synchronization primitive that is used in concurrent programming. It allows multiple threads to wait for each other at a certain point in the code, ensuring that all the participating threads have reached this point before any of them can proceed. This is useful in scenarios where a part of the computation in one thread depends on the completion of similar parts in other threads.
Here’s an example using the Barrier from Python’s threading module:
import threading
import time
import random
def task(barrier, name):
print(f'{name} is waiting for the barrier.')
time.sleep(random.randint(1, 5)) # Simulate work
barrier.wait() # Wait for all threads to arrive at this point
print(f'{name} has crossed the barrier.')
# Create a barrier for 3 threads
barrier = threading.Barrier(3)
# Start 3 threads that will wait on the barrier
threads = [threading.Thread(target=task, args=(barrier, f'Thread {i}')) for i in range(1, 4)]
for t in threads:
t.start()
for t in threads:
t.join()
print('All threads have crossed the barrier.')
In this example, three threads are started, and each of them executes the task function. Inside task, each thread first prints a message indicating it’s waiting for the barrier. Then, it simulates some work by sleeping for a random amount of time between 1 and 5 seconds. After the simulated work, the thread calls barrier.wait(), which causes the thread to wait until all three threads have reached this point.
Once all threads have called barrier.wait(), they are all released to proceed past the barrier point. This is indicated by printing that each thread has “crossed the barrier”. Finally, the main thread waits for all threads to complete by joining them and then prints that all threads have crossed the barrier.
This Barrier example demonstrates how to synchronize threads in Python, ensuring that certain parts of your program in different threads run in step with each other.
Solution 3: Multithreading + Event
The Event object from Python’s threading module is a simple synchronization primitive that is used to communicate between threads. One thread signals an event, and other threads can wait for that event to be set. Here’s an example to demonstrate how Event can be used in Python:
from threading import Event, Thread
import time
def waiter(event, name):
print(f'{name} is waiting for the event to be set.')
event.wait() # Block until the event is set.
print(f'{name} has detected the event is set and is proceeding.')
def setter(event, delay):
print('Event setter is sleeping.')
time.sleep(delay) # Simulate doing some work for a while
event.set() # Set the event, all waiting threads are unblocked.
print('Event setter has set the event. Waiting threads are released.')
# Create an Event object
event = Event()
# Start a thread that will wait for the event to be set
waiter_thread1 = Thread(target=waiter, args=(event, 'Waiter 1'))
waiter_thread1.start()
waiter_thread2 = Thread(target=waiter, args=(event, 'Waiter 2'))
waiter_thread2.start()
# Start a thread that will set the event after a delay
setter_thread = Thread(target=setter, args=(event, 3)) # Delay of 3 seconds
setter_thread.start()
# Join all threads to the main thread
waiter_thread1.join()
waiter_thread2.join()
setter_thread.join()
print('All threads have completed.')
In this example, two “waiter” threads are waiting for an event to be set, and a “setter” thread sets the event after a delay of 3 seconds. The event.wait() call in the waiter threads blocks those threads until the event is set by calling event.set() in the setter thread. Once the event is set, all waiting threads are unblocked and proceed with their execution.
This mechanism allows for simple communication between threads, where an event can signal that some condition has been met, a task has been completed, or a certain point in the program flow has been reached.
Solution 4: Multithreading + Condition
In Python, a Condition object from the threading module is a synchronization primitive that allows one or more threads to wait until they are notified by another thread. This can be useful in situations where some threads need to wait for some condition to become true before proceeding. The Condition provides methods for acquiring and releasing a lock, waiting for a condition to become true, and notifying other threads that the condition may be true now.
Here’s an example to demonstrate how to use a Condition:
import threading
import time
# A list to use as the shared resource or condition
items = []
condition = threading.Condition()
class Consumer(threading.Thread):
def __init__(self, name):
threading.Thread.__init__(self)
self.name = name
def run(self):
global items
while True:
with condition:
if not items:
print(f'{self.name} is waiting for items to be added')
condition.wait() # Wait until an item is available
item = items.pop()
print(f'{self.name} consumed an item: {item}')
class Producer(threading.Thread):
def __init__(self, name):
threading.Thread.__init__(self)
self.name = name
def run(self):
global items
for i in range(5):
time.sleep(2) # Simulate time to produce an item
with condition:
item = f'item {i}'
items.append(item)
print(f'{self.name} produced an item: {item}')
condition.notify() # Notify waiting consumers an item is available
# Create and start producer and consumer threads
producer = Producer('Producer')
consumer = Consumer('Consumer')
producer.start()
consumer.start()
producer.join()
consumer.join()
In this example:
- The
Producerthread produces items (in this case, just strings) and adds them to theitemslist. After producing an item, it callscondition.notify()to signal to theConsumerthreads that a new item is available. - The
Consumerthread waits for items to be added to the list by callingcondition.wait(). This call will block theConsumeruntil theProduceradds an item to the list and callscondition.notify(). - Both
ProducerandConsumerusewith condition:to automatically acquire a lock before modifying theitemslist and to release the lock afterward. This ensures that the list is not accessed by multiple threads at the same time, preventing race conditions.
This example demonstrates how Condition objects can be used to synchronize threads in a producer-consumer scenario.
Solution 5: Multithreading + Lock
threading.Lock is a synchronization primitive that is used to enforce limits on access to a resource in a multi-threaded environment. It is one of the simplest locking mechanisms provided by the threading module in Python. A lock can be in one of two states: “locked” or “unlocked”. It has two basic methods: .acquire() (to lock) and .release() (to unlock).
Here is a basic example of using a threading.Lock:
import threading
# Shared resource
counter = 0
# Create a lock
lock = threading.Lock()
# A function to increment global counter
def increment():
global counter
for _ in range(100000):
# Acquire the lock
lock.acquire()
counter += 1
# Release the lock
lock.release()
# Create threads
thread1 = threading.Thread(target=increment)
thread2 = threading.Thread(target=increment)
# Start threads
thread1.start()
thread2.start()
# Wait for both threads to finish
thread1.join()
thread2.join()
print(f"The final counter value is {counter}")
In this example, two threads are incrementing a shared global counter. The lock.acquire() method is used to ensure that only one thread can enter the critical section of code at any time to increment the counter. This prevents race conditions and ensures that the final value of the counter is correct.
Difference Between Lock and Semaphore:
-
Lock: A lock allows only one thread to access the critical section of code at a time. When a thread acquires a lock, any other thread that attempts to acquire it will be blocked until the lock is released by the current owner. Locks are typically binary (either locked or unlocked).
-
Semaphore: A semaphore allows a fixed number of threads to access the critical section. It’s initialized with a given count, which represents the number of threads allowed to access the critical section concurrently. When a thread enters the section, it decrements the count, and when it exits, it increments the count. If the count reaches zero, subsequent threads attempting to enter will block until the count is greater than zero again.
The key difference is in the number of threads allowed to access the critical section: locks restrict access to one thread at a time, whereas semaphores allow multiple threads (up to a fixed limit) to access the shared resource concurrently.
Semaphores can be used for controlling access to a pool of resources, while locks are more suited for situations where access to a single resource must be synchronized among threads.
-
class Foo { private Semaphore a = new Semaphore(1); private Semaphore b = new Semaphore(0); private Semaphore c = new Semaphore(0); public Foo() { } public void first(Runnable printFirst) throws InterruptedException { a.acquire(1); // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); b.release(1); } public void second(Runnable printSecond) throws InterruptedException { b.acquire(1); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); c.release(1); } public void third(Runnable printThird) throws InterruptedException { c.acquire(1); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); a.release(1); } } -
class Foo { private: mutex m2, m3; public: Foo() { m2.lock(); m3.lock(); } void first(function<void()> printFirst) { printFirst(); m2.unlock(); } void second(function<void()> printSecond) { m2.lock(); printSecond(); m3.unlock(); } void third(function<void()> printThird) { m3.lock(); printThird(); } }; -
from threading import Semaphore class Foo: def __init__(self): self.semaphore1 = Semaphore(1) self.semaphore2 = Semaphore(0) self.semaphore3 = Semaphore(0) def first(self, printFirst: 'Callable[[], None]') -> None: self.semaphore1.acquire() # printFirst() outputs "first". Do not change or remove this line. printFirst() self.semaphore2.release() def second(self, printSecond: 'Callable[[], None]') -> None: self.semaphore2.acquire() # printSecond() outputs "second". Do not change or remove this line. printSecond() self.semaphore3.release() def third(self, printThird: 'Callable[[], None]') -> None: self.semaphore3.acquire() # printThird() outputs "third". Do not change or remove this line. printThird() self.semaphore1.release() ############# ''' A Barrier is a synchronization primitive that allows multiple threads to wait until all threads have reached a certain point of execution before continuing. ''' from threading import Barrier class Foo: def __init__(self): self.first_barrier = Barrier(2) self.second_barrier = Barrier(2) ''' first() self.first_barrier.wait(), waits at self.first_barrier, blocking until another thread also reaches that point. Once both threads have reached the barrier, they are released, and execution continues. ''' def first(self, printFirst): printFirst() self.first_barrier.wait() ''' The second method is similar. It takes a function printSecond as a parameter. It first waits at self.first_barrier, ensuring that the first method has completed. Then, it calls printSecond to print the "second" output. Finally, it waits at self.second_barrier, blocking until the third method reaches the same point. ''' def second(self, printSecond): self.first_barrier.wait() printSecond() self.second_barrier.wait() def third(self, printThird): self.second_barrier.wait() printThird() ############ from threading import Event class Foo: def __init__(self): self.done = (Event(),Event()) def first(self, printFirst): printFirst() self.done[0].set() def second(self, printSecond): self.done[0].wait() printSecond() self.done[1].set() def third(self, printThird): self.done[1].wait() printThird() ############ from threading import Semaphore class Foo: def __init__(self): self.gates = (Semaphore(0),Semaphore(0)) def first(self, printFirst): printFirst() self.gates[0].release() def second(self, printSecond): with self.gates[0]: printSecond() self.gates[1].release() def third(self, printThird): with self.gates[1]: printThird() ############ from threading import Condition class Foo: def __init__(self): self.exec_condition = Condition() self.order = 0 self.first_finish = lambda: self.order == 1 self.second_finish = lambda: self.order == 2 def first(self, printFirst): with self.exec_condition: printFirst() self.order = 1 self.exec_condition.notify(2) def second(self, printSecond): with self.exec_condition: self.exec_condition.wait_for(self.first_finish) printSecond() self.order = 2 self.exec_condition.notify() def third(self, printThird): with self.exec_condition: self.exec_condition.wait_for(self.second_finish) printThird() ############ class Foo: def __init__(self): self.l2 = threading.Lock() self.l3 = threading.Lock() self.l2.acquire() self.l3.acquire() def first(self, printFirst: 'Callable[[], None]') -> None: printFirst() self.l2.release() def second(self, printSecond: 'Callable[[], None]') -> None: self.l2.acquire() printSecond() self.l3.release() def third(self, printThird: 'Callable[[], None]') -> None: self.l3.acquire() printThird()