几个多线程题.md

突然发现Leetcode上有几道关于多线程的编程题，本博客用来记录下学习过程。

交替打印FooBar

给你一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例：

线程 A 将会调用 foo() 方法，而

线程 B 将会调用 bar() 方法

请设计修改程序，以确保 “foobar” 被输出 n 次。

• 方法一. 条件变量和互斥量

条件变量一般和互斥量一起使用，条件变量用来控制多线程环境中等待某一个条件达成，互斥量用于多线程对同一数据的访问。

class FooBar {
private:
    int n;
    std::condition_variable cv;
    std::mutex cv_m;
    bool ready = true;
public:
    FooBar(int n) {
        this->n = n;
    }

    void foo(function<void()> printFoo) {
        
        for (int i = 0; i < n; i++) {
            std::unique_lock<std::mutex> lock(cv_m);
            cv.wait(lock, [this]{ return ready;});
            ready = false;
        	// printFoo() outputs "foo". Do not change or remove this line.
        	printFoo();
            cv.notify_one();
        }
    }

    void bar(function<void()> printBar) {
        
        for (int i = 0; i < n; i++) {
            std::unique_lock<std::mutex> lock(cv_m);
            cv.wait(lock, [this]{ return !ready;});
            ready = true;
        	// printBar() outputs "bar". Do not change or remove this line.
        	printBar();
            cv.notify_one();
        }
    }
};

• 方法二. 信号量
  TODO

打印零和奇偶数

现有函数 printNumber 可以用一个整数参数调用，并输出该整数到控制台。

例如，调用 printNumber(7) 将会输出 7 到控制台。

给你类 ZeroEvenOdd 的一个实例，该类中有三个函数：zero、even 和 odd 。ZeroEvenOdd 的相同实例将会传递给三个不同线程：

线程 A：调用 zero() ，只输出 0

线程 B：调用 even() ，只输出偶数

线程 C：调用 odd() ，只输出奇数

修改给出的类，以输出序列 “010203040506…” ，其中序列的长度必须为 2n 。

实现 ZeroEvenOdd 类：

ZeroEvenOdd(int n) 用数字 n 初始化对象，表示需要输出的数。

void zero(printNumber) 调用 printNumber 以输出一个 0 。

void even(printNumber) 调用printNumber 以输出偶数。

void odd(printNumber) 调用 printNumber 以输出奇数。

• 方法一.条件变量和信号量

和第一道题目类似，也是在条件变量的“条件”这里做文章。

注意我们这里使用了while循环，所以要在while内将cur>n作为退出循环的条件。

class ZeroEvenOdd {
private:
    int n;
    std::mutex cv_m;
    std::condition_variable cv;
    bool zr{true};
    int cur{1};
public:
    ZeroEvenOdd(int n) {
        this->n = n;
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        while(1) {
            std::unique_lock<std::mutex> lk(cv_m);
            cv.wait(lk, [this]{ return zr || cur > n;});
            if(cur > n) break;
            printNumber(0);
            zr = false;

            cv.notify_all();
        }
    }

    void even(function<void(int)> printNumber) {
        while(1) {
            if(cur > n) return ;

            std::unique_lock<std::mutex> lk(cv_m);
            cv.wait(lk, [this]{
                return ((cur % 2 == 0) && !zr) || cur > n;
            });
            if(cur > n) break;
            printNumber(cur);
            cur++;
            zr = true;


            cv.notify_all();
        }
    }

    void odd(function<void(int)> printNumber) {
        while(1){
            if(cur > n) return ;
            std::unique_lock<std::mutex> lk(cv_m);
            cv.wait(lk, [this]{
                return ((cur & 1) && !zr) || cur > n;
            });
            if(cur > n) break;
            printNumber(cur);
            cur++;
            zr = true;
            cv.notify_all();
        }
    }
};

• 方法二

H2O生成

现在有两种线程，氧 oxygen 和氢 hydrogen，你的目标是组织这两种线程来产生水分子。

存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。

氢和氧线程会被分别给予 releaseHydrogen 和 releaseOxygen 方法来允许它们突破屏障。

这些线程应该三三成组突破屏障并能立即组合产生一个水分子。

你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。

换句话说:

如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。

如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。

书写满足这些限制条件的氢、氧线程同步代码。

• 方法一. 条件变量 + 互斥锁
  这种方法虽然可以通过评测，实际上不能满足题目的需求

class H2O {
private:
    std::condition_variable cv;
    std::mutex cv_m;
    int H = 2;
    int O = 1;
public:
    H2O() {
        
    }

    void hydrogen(function<void()> releaseHydrogen) {
        std::unique_lock<std::mutex> lk(cv_m);
        cv.wait(lk, [this]{ 
            return H > 0;
        });
        --H;
        if(H == 0) {
            if(O == 0) {
                H = 2;
                O = 1;
            }
        }
        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        cv.notify_all();
    }

    void oxygen(function<void()> releaseOxygen) {
        std::unique_lock<std::mutex> lk(cv_m);
        cv.wait(lk, [this]{ return O == 1;});
        O = 0;
        if(H == 0) {
            H = 2;
            O = 1;
        }
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        cv.notify_all();
    }
};