LeetCode多线程练习

分别⽤原⼦操作，semaphore，condition variable三种⽅式实现题库中的题目。

1114. 按序打印

atomic operation

#include <atomic>
class Foo {
private:
    atomic_bool a = false, b = false;
public:
    Foo() {}

    void first(function<void()> printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        a = true;
    }

    void second(function<void()> printSecond) {
        while(!a) this_thread::sleep_for(chrono::milliseconds(1));
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        b = true;
    }

    void third(function<void()> printThird) {
        while(!b) this_thread::sleep_for(chrono::milliseconds(1));
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
    }
};

初识原子操作。

semaphore

#include <semaphore.h>
class Foo {
private:
    sem_t sem_1, sem_2;
public:
    Foo() {
        sem_init(&sem_1, 0, 0);
        sem_init(&sem_2, 0, 0);
    }

    void first(function<void()> printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        sem_post(&sem_1);
    }

    void second(function<void()> printSecond) {
        sem_wait(&sem_1);
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        sem_post(&sem_2);
    }

    void third(function<void()> printThird) {
        sem_wait(&sem_2);
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
    }
};

condition variable

条件变量（Condition Variable）的一般用法是：线程 A 等待某个条件并挂起，直到线程 B 设置了这个条件，并通知条件变量，然后线程 A 被唤醒。这里等待的线程可以是多个，通知线程可以选择一次通知一个（notify_one）或一次通知所有（notify_all）。

加锁主要有两方面的作用：

1. 保护pred资源，避免多线程同时读写该资源
2. 保证等待线程中pred的读操作和wait操作的原子性

cv.wait(lock, [] { return ready;}); 相当于：while (!ready) { cv.wait(lock);}。

当ready==false的时候，while语句执行到wait这里，然后就堵塞到这行，等到通知信号来唤醒它，同时解锁互斥量，不影响其他线程获取锁。当 cv.notify_all(); 时，通知所有线程，等待唤醒的线程收到了信号就被唤醒开始干活，首先就是不断的尝试重新获取并加锁互斥量。若获取不到锁，就卡在这里，反复尝试加锁，若获取到了锁才往下执行。

没有locker.unlock();，因为局部变量在函数体中执行完后自动释放。

class Foo {
    condition_variable cv;
    mutex mtx;
    int flag = 0;
public:
    Foo() {
    }
    void first(function<void()> printFirst) {
        printFirst();
        flag = 1;
        cv.notify_all();
    }
    void second(function<void()> printSecond) {
        unique_lock<mutex>locker(mtx);
        cv.wait(locker,[this]{return flag == 1;});
        printSecond();
        flag = 2;
        cv.notify_one();
    }
    void third(function<void()> printThird) {
        unique_lock<mutex>locker(mtx);
        cv.wait(locker,[this]{return flag == 2;});
        printThird();
    }
};

1115. 交替打印 FooBar

atomic operation

#include<atomic>
class FooBar {
private:
    int n;
    atomic_bool foo_done = false;
public:
    FooBar(int n) {
        this->n = n;
    }

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            while(foo_done) this_thread::yield();
        	// printFoo() outputs "foo". Do not change or remove this line.
        	printFoo();
            foo_done = true;
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            while(!foo_done) this_thread::yield();
        	// printBar() outputs "bar". Do not change or remove this line.
        	printBar();
            foo_done = false;
        }
    }
};

这里阻塞进程用了yield()，而不是像1114题一样使用sleep_for()。使用sleep_for()始终超时，使用yield()的效率却和使用信号量的效率相当。而在1114题中，使用sleep_for()的耗时仅为使用yield()的一半。

semaphore

#include<semaphore.h>
class FooBar {
private:
    int n;
    sem_t foo_done, bar_done;
public:
    FooBar(int n) {
        this->n = n;
        sem_init(&foo_done, 0 , 0);
        sem_init(&bar_done, 0 , 1);
    }

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            sem_wait(&bar_done);
        	// printFoo() outputs "foo". Do not change or remove this line.
        	printFoo();
            sem_post(&foo_done);
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            sem_wait(&foo_done);
        	// printBar() outputs "bar". Do not change or remove this line.
        	printBar();
            sem_post(&bar_done);
        }
    }
};

condition variable

class FooBar {
private:
    int n;
    mutex mtx;
    condition_variable cv;
    bool foo_done = false;
public:
    FooBar(int n) {
        this->n = n;
    }

    void foo(function<void()> printFoo) {
        unique_lock<mutex>locker(mtx);
        for (int i = 0; i < n; i++) {
            cv.wait(locker, [this] {return !foo_done;});
        	// printFoo() outputs "foo". Do not change or remove this line.
        	printFoo();
            foo_done = true;
            cv.notify_one();
        }
    }

    void bar(function<void()> printBar) {
        unique_lock<mutex>locker(mtx);
        for (int i = 0; i < n; i++) {
            cv.wait(locker, [this] {return foo_done;});
        	// printBar() outputs "bar". Do not change or remove this line.
        	printBar();
            foo_done = false;
            cv.notify_one();
        }
    }
};

1116. 打印零与奇偶数

atomic operation

#include <atomic>
class ZeroEvenOdd {
private:
    int n;
    atomic_int flag = 0;
public:
    ZeroEvenOdd(int n) {
        this->n = n;
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i++){
            while(flag) this_thread::yield();
            printNumber(0);
            if(i % 2 == 1){
                flag = 1;
            }
            else{
                flag = 2;
            }
        }
    }

    void even(function<void(int)> printNumber) {
        for(int i = 2; i <= n; i += 2){
            while(flag != 2) this_thread::yield();
            printNumber(i);
            flag = 0;
         }
    }

    void odd(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i += 2){
            while(flag != 1) this_thread::yield();
            printNumber(i);
            flag = 0;
        }
    }
};

很快。

semaphore

#include <semaphore.h>
class ZeroEvenOdd {
private:
    int n;
    sem_t s0, s1, s2;
public:
    ZeroEvenOdd(int n) {
        this->n = n;
        sem_init(&s0, 0, 1);
        sem_init(&s1, 0, 0);
        sem_init(&s2, 0, 0);
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i++){
            sem_wait(&s0);
            printNumber(0);
            if(i % 2 == 1){
                sem_post(&s1);
            }
            else{
                sem_post(&s2);
            }
        }
    }

    void even(function<void(int)> printNumber) {
        for(int i = 2; i <= n; i += 2){
            sem_wait(&s2);
            printNumber(i);
            sem_post(&s0);
         }
    }

    void odd(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i += 2){
            sem_wait(&s1);
            printNumber(i);
            sem_post(&s0);
        }
    }
};

condition variable

class ZeroEvenOdd {
private:
    int n;
    mutex mtx;
    condition_variable cv;
    int flag = 0;
public:
    ZeroEvenOdd(int n) {
        this->n = n;
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        unique_lock<mutex> locker(mtx);
        for(int i = 1; i <= n; i++){
            cv.wait(locker, [this] {return flag == 0;});
            printNumber(0);
            if(i % 2){
                flag = 1;
            }
            else{
                flag = 2;
            }
            cv.notify_all();
        }
    }

    void even(function<void(int)> printNumber) {
        unique_lock<mutex> locker(mtx);
        for(int i = 2; i <= n; i+=2){
            cv.wait(locker, [this] {return flag == 2;});
            printNumber(i);
            flag = 0;
            cv.notify_all();
        }
    }

    void odd(function<void(int)> printNumber) {
        unique_lock<mutex> locker(mtx);
        for(int i = 1; i <= n; i+=2){
            cv.wait(locker, [this] {return flag == 1;});
            printNumber(i);
            flag = 0;
            cv.notify_all();
        }
    }
};

1117. H2O 生成

atomic operation

#include<atomic>
class H2O {
private:
    atomic_int H_cnt = 0;
public:
    H2O() {
    }
    void hydrogen(function<void()> releaseHydrogen) {
        while(H_cnt == 2) this_thread::yield();
        releaseHydrogen();
        H_cnt++;
    }
    void oxygen(function<void()> releaseOxygen) {
        while(H_cnt != 2) this_thread::yield();
        releaseOxygen();
        H_cnt = 0;
    }
};

很简洁，但比信号量慢点。

semaphore

#include<semaphore.h>
class H2O {
private:
    sem_t H_done,O_done;
    int H_cnt = 0;
public:
    H2O() {
        sem_init(&H_done,0,0);
        sem_init(&O_done,0,2);
    }
    void hydrogen(function<void()> releaseHydrogen) {
        sem_wait(&O_done);
        releaseHydrogen();
        H_cnt++;
        if(H_cnt == 2){
            sem_post(&H_done);
        }
    }
    void oxygen(function<void()> releaseOxygen) {
        sem_wait(&H_done);
        releaseOxygen();
        H_cnt = 0;
        sem_post(&O_done);
        sem_post(&O_done);
    }
};

比1114更复杂，需要变量记录当前已释放的H原子个数，达到2个才能放O原子。

condition variable

class H2O {
    mutex mtx;
    condition_variable cv;
    int H_cnt = 0;
public:
    H2O() {
    }

    void hydrogen(function<void()> releaseHydrogen) {
        unique_lock<mutex>locker(mtx);
        cv.wait(locker, [this] {return H_cnt < 2;});
        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        H_cnt++;
        cv.notify_all();
    }

    void oxygen(function<void()> releaseOxygen) {
        unique_lock<mutex>locker(mtx);
        cv.wait(locker, [this] {return H_cnt == 2;});
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        H_cnt = 0;
        cv.notify_all();
    }
};

1195. 交替打印字符串

atomic operation

#include <atomic>
class FizzBuzz {
private:
    int n;
    atomic_int flag = 0;
public:
    FizzBuzz(int n) {
        this->n = n;
    }

    // printFizz() outputs "fizz".
    void fizz(function<void()> printFizz) {
        for(int i = 3; i <= n; i += 3){
            if(i % 5 != 0){
                while(flag != 1) this_thread::yield();
                printFizz();
                flag = 0;
            }
        }
    }

    // printBuzz() outputs "buzz".
    void buzz(function<void()> printBuzz) {
        for(int i = 5; i <= n; i += 5){
            if(i % 3 != 0){
                while(flag != 2) this_thread::yield();
                printBuzz();
                flag = 0;
            }
        }
    }

    // printFizzBuzz() outputs "fizzbuzz".
	void fizzbuzz(function<void()> printFizzBuzz) {
        for(int i = 1; i <= n; i++){
            if(i % 5 == 0 && i % 3 == 0){
                while(flag != 3) this_thread::yield();
                printFizzBuzz();
                flag = 0;
            }
        }
    }

    // printNumber(x) outputs "x", where x is an integer.
    void number(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i++){
            while(flag) this_thread::yield();
            if(i % 5 != 0 && i % 3 != 0){
                printNumber(i);
            }
            else if(i % 5 != 0 && i % 3 == 0){
                flag = 1;
            }
            else if(i % 5 == 0 && i % 3 != 0){
                flag = 2;
            }
            else{
                flag = 3;
            }
        }
    }
};

semaphore

#include <semaphore.h>
class FizzBuzz {
private:
    int n;
    sem_t numPrint, fizzPrint, buzzPrint, fzbzPrint;
public:
    FizzBuzz(int n) {
        this->n = n;
        sem_init(&numPrint, 0, 1);
        sem_init(&fizzPrint, 0, 0);
        sem_init(&buzzPrint, 0, 0);
        sem_init(&fzbzPrint, 0, 0);
    }

    // printFizz() outputs "fizz".
    void fizz(function<void()> printFizz) {
        for(int i = 1; i <= n; i++){
            if(i % 3 == 0 && i % 5 != 0){
                sem_wait(&fizzPrint);
                printFizz();
                sem_post(&numPrint);
            }
        }
    }

    // printBuzz() outputs "buzz".
    void buzz(function<void()> printBuzz) {
        for(int i = 1; i <= n; i++){
            if(i % 3 != 0 && i % 5 == 0){
                sem_wait(&buzzPrint);
                printBuzz();
                sem_post(&numPrint);
            }
        }
    }

    // printFizzBuzz() outputs "fizzbuzz".
	void fizzbuzz(function<void()> printFizzBuzz) {
        for(int i = 1; i <= n; i++){
            if(i % 3 == 0 && i % 5 == 0){
                sem_wait(&fzbzPrint);
                printFizzBuzz();
                sem_post(&numPrint);
            }
        }
    }

    // printNumber(x) outputs "x", where x is an integer.
    void number(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i++){
            sem_wait(&numPrint);
            if(i % 3 != 0 && i % 5 != 0){
                printNumber(i);
                sem_post(&numPrint);
            }
            else if(i % 3 == 0 && i % 5 != 0){
                sem_post(&fizzPrint);
            }
            else if(i % 3 != 0 && i % 5 == 0){
                sem_post(&buzzPrint);
            }
            else{
                sem_post(&fzbzPrint);
            }
        }
    }
};

依然是基础的变式。

condition variable

class FizzBuzz {
private:
    int n, flag = 0;
    mutex mtx;
    condition_variable cv;
public:
    FizzBuzz(int n) {
        this->n = n;
    }

    // printFizz() outputs "fizz".
    void fizz(function<void()> printFizz) {
        unique_lock<mutex>locker(mtx);
        for(int i = 3; i <= n; i += 3){
            if(i % 5 != 0){
                cv.wait(locker, [this] {return flag == 1;});
                printFizz();
                flag = 0;
                cv.notify_all();
            }
        }
    }

    // printBuzz() outputs "buzz".
    void buzz(function<void()> printBuzz) {
        unique_lock<mutex>locker(mtx);
        for(int i = 5; i <= n; i += 5){
            if(i % 3 != 0){
                cv.wait(locker, [this] {return flag == 2;});
                printBuzz();
                flag = 0;
                cv.notify_all();
            }
        }
    }

    // printFizzBuzz() outputs "fizzbuzz".
	void fizzbuzz(function<void()> printFizzBuzz) {
        unique_lock<mutex>locker(mtx);
        for(int i = 1; i <= n; i++){
            if(i % 5 == 0 && i % 3 == 0){
                cv.wait(locker, [this] {return flag == 3;});
                printFizzBuzz();
                flag = 0;
                cv.notify_all();
            }
        }
    }

    // printNumber(x) outputs "x", where x is an integer.
    void number(function<void(int)> printNumber) {
        unique_lock<mutex>locker(mtx);
        for(int i = 1; i <= n; i++){
            cv.wait(locker, [this] {return flag == 0;});
            if(i % 5 != 0 && i % 3 != 0){
                printNumber(i);
            }
            else if(i % 5 != 0 && i % 3 == 0){
                flag = 1;
                cv.notify_all();
            }
            else if(i % 5 == 0 && i % 3 != 0){
                flag = 2;
                cv.notify_all();
            }
            else{
                flag = 3;
                cv.notify_all();
            }
        }
    }
};

1226. 哲学家进餐

atomic operation

#include <atomic>
class DiningPhilosophers {
private:
    atomic_bool forks[5];
public:
    DiningPhilosophers() {
        for(int i = 0; i < 5; i++){
            forks[i] = true;
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
		int L = philosopher, R = (philosopher + 1) % 5;
        if(philosopher % 2){
            while(!forks[L]) this_thread::yield();
            forks[L] = false;
            while(!forks[R]) this_thread::yield();
            forks[R] = false;
        }
        else{
            while(!forks[R]) this_thread::yield();
            forks[R] = false;
            while(!forks[L]) this_thread::yield();
            forks[L] = false;
        }
        pickLeftFork();
        pickRightFork();
        eat();
        putLeftFork();
        putRightFork();
        forks[L] = true;
        forks[R] = true;
    }
};

思路和semaphore相同。但是对原子操作的使用不太熟练，尝试在声明forks[]时就初始化，出错了，遂改为在constructor中初始化。另一方面，上述代码能通过测试，但似乎并不是原子操作。如下图，经测试，在while()阻塞之后设置延时，就出现了bug。暂未实现真正的原子操作。

semaphore

奇数的哲学家先拿左边叉子，偶数的先拿右边叉子，不会出现循环等待。

#include <semaphore.h>
class DiningPhilosophers {
private:
    sem_t forks[5];
public:
    DiningPhilosophers() {
        for(int i = 0; i < 5; i++){
            sem_init(&forks[i], 0, 1);
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
		int L = philosopher, R = (philosopher + 1) % 5;
        if(philosopher % 2){
            sem_wait(&forks[L]);
            sem_wait(&forks[R]);
        }
        else{
            sem_wait(&forks[R]);
            sem_wait(&forks[L]);
        }
        pickLeftFork();
        pickRightFork();
        eat();
        putLeftFork();
        putRightFork();
        sem_post(&forks[L]);
        sem_post(&forks[R]);
    }
};

condition variable

class DiningPhilosophers {
private:
    mutex mtx;
    condition_variable cv;
    bool forks[5];
public:
    DiningPhilosophers() { 
        for(int i = 0; i < 5; i++){
            forks[i] = true;
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
		int L = philosopher, R = (philosopher + 1) % 5;
        unique_lock<mutex> locker(mtx);
        cv.wait(locker, [this, L, R] {return forks[L] && forks[R];});
        forks[L] = false;
        forks[R] = false;
        locker.unlock();
        pickLeftFork();
        pickRightFork();
        eat();
        putLeftFork();
        putRightFork();
        locker.lock();
        forks[L] = true;
        forks[R] = true;
        locker.unlock();
        cv.notify_all();
    }
};

要么同时拿两个餐具，要么都不拿。和原子操作不同的是，在发现左右叉子都可用后，马上加锁了，不会有其他哲学家发现叉子可用。