1114. Print in Order - cocoder39/coco39_LC GitHub Wiki

1114. Print in Order

Option 1: lock

if the state is locked, a call to acquire() blocks until another thread calls release(). As a result, third() is blocked at the point of constructor building. The lock is released upon the completion of second()

from threading import Lock
class Foo:
    def __init__(self):
        self.locks = (Lock(), Lock())
        self.locks[0].acquire()
        self.locks[1].acquire()

    def first(self, printFirst: 'Callable[[], None]') -> None:
        
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.locks[0].release()


    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self.locks[0]:
            # printSecond() outputs "second". Do not change or remove this line.
            printSecond()
            self.locks[1].release()
        
    def third(self, printThird: 'Callable[[], None]') -> None:
        with self.locks[1]:
            # printThird() outputs "third". Do not change or remove this line.
            printThird()

Option 2: semaphore

A semaphore is based on an internal counter which is decremented each time acquire() is called and incremented each time release() is called. If the counter is equal to 0 then acquire() blocks.

Using a semaphore makes sense when you want to control access to a resource with limited capacity like a server.

from threading import Semaphore

class Foo:
    def __init__(self):
        self.semaphores = (Semaphore(0), Semaphore(0))

    def first(self, printFirst: 'Callable[[], None]') -> None:
        
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.semaphores[0].release()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self.semaphores[0]:
            # printSecond() outputs "second". Do not change or remove this line.
            printSecond()
            self.semaphores[1].release()
        
    def third(self, printThird: 'Callable[[], None]') -> None:
        with self.semaphores[1]:
            # printThird() outputs "third". Do not change or remove this line.
            printThird()

Option 3: barrier

The real-world analog would be the starting gate at a horse race. Ten horses in a race won't arrive at the gate at the same time, but it isn't until all ten of them have entered the gate and are ready to race does the gate open and each horse starts its race. (Starting gates are also called starting barriers because they were barriers rather than gates, which might be where the threading construct got its name.)

An example usage is something like a worker pool where you would want all of your workers to report ready before sending them work. 

from threading import Barrier

class Foo:
    def __init__(self):
        self.first_barrier = Barrier(2)
        self.second_barrier = Barrier(2)

    def first(self, printFirst: 'Callable[[], None]') -> None:
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.first_barrier.wait()
            
    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.first_barrier.wait()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.second_barrier.wait()
        
    def third(self, printThird: 'Callable[[], None]') -> None:
        self.second_barrier.wait()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

Option 4: event An Event manages an internal flag that callers can either set() or clear(). Other threads can wait() for the flag to be set(). Note that the wait() method blocks until the flag is true.

from threading import Event

class Foo:
    def __init__(self):
        self.done = (Event(), Event())

    def first(self, printFirst: 'Callable[[], None]') -> None:
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.done[0].set()
            
    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.done[0].wait()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.done[1].set()
        
    def third(self, printThird: 'Callable[[], None]') -> None:
        self.done[1].wait()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

Option 5: condition

Have all three threads attempt to acquire an RLock via Condition. The first thread can always acquire a lock, while the other two have to wait for the order to be set to the right value. First thread sets the order after printing which signals for the second thread to run. Second thread does the same for the third.

Why no deadlock? EG, second() acquired lock first, would first() waits for second() to release the lock while second() waits to be notified by first():

• The wait() method releases the lock, and then blocks until it is awakened by a notify() or notifyAll() call for the same condition variable in another thread. Once awakened, it re-acquires the lock and returns. It is also possible to specify a timeout.

from threading import Condition

class Foo:
    def __init__(self):
        self.condition = Condition()
        self.order = 0
        
    def first(self, printFirst: 'Callable[[], None]') -> None:
        with self.condition:
            # printFirst() outputs "first". Do not change or remove this line.
            printFirst()
            self.order = 1
            self.condition.notifyAll()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self.condition:
            while self.order != 1:
                self.condition.wait()
            # printSecond() outputs "second". Do not change or remove this line.
            printSecond()
            self.order = 2
            self.condition.notify()
        
    def third(self, printThird: 'Callable[[], None]') -> None:
        with self.condition:
            while self.order != 2:
                self.condition.wait()
            # printThird() outputs "third". Do not change or remove this line.
            printThird()