Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1114.html
1114. Print in Order
Level
Easy
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()
.
Example 1:
Input: [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: [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.
Note:
We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seems to imply the ordering. The input format you see is mainly to ensure our tests’ comprehensiveness.
Solution
There are several solutions to this problem. This solution uses semaphores. Create three semaphores semaphore1
, semaphore2
and semaphore3
, which are for method first()
, second()
and third()
, respectively. The three semaphores are defined in the class. Initially, semaphore1
has 1 permit, while semaphore2
and semaphore3
have 0 permits.
For each method first()
, second()
and third()
, there are three steps. The first step is to acquire a permit from the current semaphore. The second step is to call the run()
method for the Runnable
object. The third step is to release a permit back to the next semaphore.
-
class Foo { private Semaphore semaphore1 = new Semaphore(1); private Semaphore semaphore2 = new Semaphore(0); private Semaphore semaphore3 = new Semaphore(0); public Foo() { } public void first(Runnable printFirst) throws InterruptedException { semaphore1.acquire(); // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); semaphore2.release(); } public void second(Runnable printSecond) throws InterruptedException { semaphore2.acquire(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); semaphore3.release(); } public void third(Runnable printThird) throws InterruptedException { semaphore3.acquire(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); semaphore1.release(); } } ############ import java.util.concurrent.CountDownLatch; public class Print_in_Order { class Foo { private final CountDownLatch countDownLatch1; private final CountDownLatch countDownLatch2; public Foo() { countDownLatch1 = new CountDownLatch(1); // count the number of times must be invoked countDownLatch2 = new CountDownLatch(1); } public void first(Runnable printFirst) throws InterruptedException { // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); countDownLatch1.countDown(); } public void second(Runnable printSecond) throws InterruptedException { countDownLatch1.await(); // Causes the current thread to wait until the latch has counted down to zero // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); countDownLatch2.countDown(); } public void third(Runnable printThird) throws InterruptedException { countDownLatch2.await(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } }
-
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()