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:

• nums is a permutation of [1, 2, 3].

Submitted Code

from threading import Event

class Foo:
    def __init__(self):
        self.first_done = Event()
        self.second_done = Event()


    def first(self, printFirst: 'Callable[[], None]') -> None:
        printFirst()            # printFirst() outputs "first". Do not change or remove this line.
        self.first_done.set()   # first 끝났다고 알림


    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.first_done.wait()  # first 끝날 때까지 대기
        printSecond()           # printSecond() outputs "second". Do not change or remove this line.
        self.second_done.set()  # second 끝났다고 알림


    def third(self, printThird: 'Callable[[], None]') -> None:
        self.second_done.wait() # second 끝날 때까지 대기
        printThird()            # printThird() outputs "third". Do not change or remove this line.

Runtime: 57 ms | Beats 34.40%
Memory: 17.70 MB | Beats 99.63%

Event를 이용하는 방법으로, 두 번째 스레드는 첫 번째 스레드가 이벤트를 set할 때까지 wait하고, 세 번째 스레드는 두 번째 스레드가 이벤트를 set할 때까지 wait한다.

Other Solutions

1st

from threading import Barrier

class Foo:
    def __init__(self):
        # Barrier(2): 스레드 2개가 해당 barrier의 wait()에 도달해야 통과
        self.first_barrier = Barrier(2)
        self.second_barrier = Barrier(2)
            
    def first(self, printFirst):
        printFirst()
        self.first_barrier.wait()         # second도 wait()에 도착할 때까지 대기
        
    def second(self, printSecond):
        self.first_barrier.wait()         # first가 끝날 때까지 대기
        printSecond()
        self.second_barrier.wait()        # third도 wait()에 도착할 때까지 대기
            
    def third(self, printThird):
        self.second_barrier.wait()        # second가 끝날 때까지 대기
        printThird()

Barrier는 정해진 수의 스레드가 모두 barrier에 도착할 때까지 대기시키고, 마지막 스레드가 도착하는 순간 그 그룹을 동시에 통과시키는 방식이다.

from threading import Lock

class Foo:
    def __init__(self):
        # 두 개의 lock을 준비 후 바로 실행하지 못하도록 미리 잠가 둔다
        self.locks = (Lock(),Lock())
        self.locks[0].acquire()
        self.locks[1].acquire()
        
    def first(self, printFirst):
        printFirst()
        self.locks[0].release()       # first 종료 후 second가 들어갈 수 있도록 잠금 해제
        
    def second(self, printSecond):
        with self.locks[0]:           # 첫 번째 lock이 열릴 때까지 대기
            printSecond()
            self.locks[1].release()   # second 종료 후 third가 들어갈 수 있도록 잠금 해제
            
    def third(self, printThird):
        with self.locks[1]:           # 두 번째 lock이 열릴 때까지 대기
            printThird()

Lock은 원래 임계 구역 보호용이지만, 여기서는 한 번에 한 스레드만 실행할 수 있도록 순서를 강제하는 용도로 사용되었다.

from threading import Semaphore

class Foo:
    def __init__(self):
        # Semaphore(0): 카운터 없음 -> 대기
        self.gates = (Semaphore(0),Semaphore(0))
        
    def first(self, printFirst):
        printFirst()
        self.gates[0].release()       # second용 카운터 +1 -> second 통과 가능
        
    def second(self, printSecond):
        with self.gates[0]:           # first에서 카운팅 될 때까지 대기
            printSecond()
            self.gates[1].release()   # third용 카운터 +1 -> third 통과 가능
            
    def third(self, printThird):
        with self.gates[1]:           # second에서 카운팅 될 때까지 대기
            printThird()

Semaphore는 Event와 비슷하나 카운터 숫자로 순서를 관리할 수 있다.

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:           # order == 1 될 때까지 대기
            self.exec_condition.wait_for(self.first_finish)
            printSecond()
            self.order = 2
            self.exec_condition.notify()

    def third(self, printThird):
        with self.exec_condition:           # order == 2 될 때까지 대기
            self.exec_condition.wait_for(self.second_finish)
            printThird()

Condition은 Lock을 기반으로 조건이 만족될 때까지 wait()하며, 다른 스레드의 notify() 신호에 의해 다시 깨어나 조건을 재검사하는 방식이다.