Fizz Buzz Multithreaded

1195. Fizz Buzz Multithreaded

class FizzBuzz {
private:
    int n;
    int c = 1;
    mutex m;
    condition_variable cv;

public:
    FizzBuzz(int n) {
        this->n = n;
    }

    // printFizz() outputs "fizz".
    void fizz(function<void()> printFizz) {
        unique_lock<mutex> lock(m);
        while (c <= n) {
            cv.wait(lock, [this] {return n < c || (c % 3 == 0 && c % 5 != 0);});
            if (c <= n && c % 3 == 0 && c % 5 != 0) {
                printFizz();
                ++c;
            }
            cv.notify_all();
        }
    }

    // printBuzz() outputs "buzz".
    void buzz(function<void()> printBuzz) {
        unique_lock<mutex> lock(m);
        while (c <= n) {
            cv.wait(lock, [this] {return n < c || ( c % 3 != 0 && c % 5 == 0);});
            if (c <= n && c % 3 != 0 && c % 5 == 0) {
                printBuzz();
                ++c;
            }
            cv.notify_all();
        }
    }

    // printFizzBuzz() outputs "fizzbuzz".
	void fizzbuzz(function<void()> printFizzBuzz) {
        unique_lock<mutex> lock(m);
        while (c <= n) {
            cv.wait(lock, [this] {return  n < c || (c % 3 == 0 && c % 5 == 0);});
            if (c <= n && c % 3 == 0 && c % 5 == 0) {
                printFizzBuzz();
                ++c;
            }
            cv.notify_all();
        }
    }

    // printNumber(x) outputs "x", where x is an integer.
    void number(function<void(int)> printNumber) {
        unique_lock<mutex> lock(m);
        while (c <= n) {
            cv.wait(lock, [this] {return  n < c || (c % 3 != 0 && c % 5 != 0);});
            if (c <= n && c % 3 != 0 && c % 5 != 0) {
                printNumber(c);
                ++c;
            }
            cv.notify_all();
        }
    }
};

1부터 n 까지 증가하는 값 c를 둔다.
각 스레드는 c 가 n 이하 일때 무한 루프를 돌면서, 문제의 조건이 아닐때 계속 wait 하고,
조건이 맞을때 lock 을 얻어 callback 을 실행하고 c 를 1 증가 시킨다.

그냥 std::mutex 를 각 함수 callback 실행 조건 if 바로 밖에세 lock 을 잡아줘도 동작은 의도된 대로 된다.
하지만 이렇게 하니 6ms 가 나온다. e.g. fizz()

    void fizz(function<void()> printFizz) {
        while (c <= n) {
            m.lock();
            if(c <= n && c % 3 == 0 && c % 5 != 0) {
                printFizz();
                ++c;
            }
            m.unlock();
        }
    }

그런데 이러면 락이 풀리면 조건에 맞지 않는 다른 스레드의 락이 풀릴수 있고 불필요하게 루프를 한바퀴 돌게 되면서 시간이 낭비 될 수 있다.
1117. Building H2O 를 풀고나서 솔루션에 std::condition_variable 을 사용하는걸 보고 여기도 적용 해 봤다.
wait 의 release 조건으로 c 가 n 을 넘어가거나 callback invoke 조건이 되면 release 한다.
c 가 n 이하 && 조건에 맞으면 callback 실행 후 notify all.

Time: 0ms

• 굳이 따지자면 n 번 만큼의 callback invoke 로 O(n) 일것 같다.
• 실제로는 lock 상태에서 얼마나 빠르게 critical section 으로 들어가는지가 관건일듯.

Space: O(1)