Print in Order

leetcode

code (semaphore)

• noted that the semaphore.acquire() will block the thread until the counter is greater than 0, and semaphore.release() will increment the counter and potentially unblock waiting threads.

class Foo {
private:
    std::binary_semaphore sep1{1};
    std::binary_semaphore sep2{0};
    std::binary_semaphore sep3{0};

public:
    void first(function<void()> printFirst) {
        sep1.acquire();
        printFirst();
        sep2.release();
    }

    void second(function<void()> printSecond) {
        sep2.acquire();
        printSecond();
        sep3.release();
    }

    void third(function<void()> printThird) {
        sep3.acquire();
        printThird();
        sep1.release(); //can restart
    }
};

code (mutex + condition variable) what is wrong?

class Foo {
private:
    std::mutex mtx; //this becomes is using lock, only one thread can print at a time
    std::condition_variable cv2;
    std::condition_variable cv3;

public:
    void first(function<void()> printFirst) {
        printFirst();
        cv2.notify_one();
    }

    void second(function<void()> printSecond) {
        unique_lock<mutex> lock(mtx);
        cv2.wait(lock);
        printSecond();
        cv3.notify_one();
    }

    void third(function<void()> printThird) {
        unique_lock<mutex> lock(mtx);
        cv3.wait(lock);
        printThird();
    }
};

this code above can pass the leetcode test case, but there is still a problem: - it is possible that this become a dead lock forever, because there is no initial synchronization for the first thread to start. It does not use the lock, so it can run concurrently with other threads, producing this scenario:

• thread 2 acquire the lock
• thread 2 is going to run the code cv2.wait(lock); - two parts: unlock & sleep
• thread 2 releases the lock
• thread 1 notify that cv2 is ready, but nothing is waiting for cv2, so the notify is lost
• thread 2 is waiting for cv2 to be notified, but it will never be notified because thread 1 has already run and finished, and thread 3 is waiting for cv3 to be notified, but it will never be notified because thread 2 is waiting for cv2 to be notified.

therefore, do not notify a conditional variable when the lock is hold

code - what is wrong again?

class Foo {
private:
    std::mutex mtx; //this becomes is using lock, only one thread can print at a time
    std::condition_variable cv2;
    std::condition_variable cv3;

public:
    void first(function<void()> printFirst) {
        unique_lock<mutex> lock(mtx);
        printFirst();
        cv2.notify_one();
    }

    void second(function<void()> printSecond) {
        unique_lock<mutex> lock(mtx);
        cv2.wait(lock);
        printSecond();
        cv3.notify_one();
    }

    void third(function<void()> printThird) {
        unique_lock<mutex> lock(mtx);
        cv3.wait(lock);
        printThird();
    }
};

This still does NOT work and frequently produce deadlock. think of the following scenario:

1. thread 2 acquires the lock
2. thread 2 wait for cv2 and release lock
3. thread 3 acquires the lock
4. thread 3 wait for cv3 and release lock
5. thread 1 acquires the lock
6. thread 1 print and notify cv2, but thread 2 is waiting for cv2, so it will be notified and acquire the lock
7. thread 3 runs after it is notified by thread 2 while thread 2 still holds the lock, the thread 3 cannot acquire the lock and is waiting for it to be released (now not waiting for cv3 but waiting for the lock, long delay)
8. the thread 2 ends the function and releases the lock
9. thread 3 acquired the free lock and print.

therefore, we should release the lock before notify. the lock is released when out of scope

code - correct version with (2 conditions, 1 lock)

class Foo {
private:
    std::mutex mtx; //this becomes is using lock, only one thread can print at a time
    std::condition_variable cv2;
    std::condition_variable cv3;

public:
    void first(function<void()> printFirst) {
        printFirst();
        cv2.notify_one();
    }

    void second(function<void()> printSecond) {
        { unique_lock<mutex> lock(mtx); cv2.wait(lock); printSecond(); }
        cv3.notify_one();
    }

    void third(function<void()> printThird) {
        unique_lock<mutex> lock(mtx);
        cv3.wait(lock);
        printThird();
    }
};

- this ensures before notify the lock is released, so the waiting thread can acquire the lock and run.