Leetcode多线程题解及其源码(纯享版)
| 一、按顺序执行一次打印函数 |
【题目链接】1114. 按序打印
我们提供了一个类：
public class Foo {
public void first() { print("first"); }
public void second() { print("second"); }
public void third() { print("third"); }
}
三个不同的线程将会共用一个 Foo 实例。
线程 A 将会调用 first() 方法
线程 B 将会调用 second() 方法
线程 C 将会调用 third() 方法
请设计修改程序，以确保 second() 方法在 first() 方法之后被执行，third() 方法在 second() 方法之后被执行。
【解题思路】
线程之间一等一的情况，建议使用sem信号量，而不是notify和wait。
sem主要有以下几个方法（返回值为0是表示成功）：
int sem_init(sem_t *sem,int pshared,unsigned int value);
int sem_destroy(sem_t *sem);
int sem_wait(sem_t *sem); // 当sem的val>0的时候，会结束等待，并且将val-1
int sem_trywait(sem_t *sem);
int sem_post(sem_t *sem); // 会使得sem的val++
int sem_getvalue(sem_t *sem);
【代码实现】
#include <semaphore.h>
class Foo {
protected:
sem_t sem1;
sem_t sem2;
public:
Foo() {
sem_init(&sem1, 0, 0); // 初始化两个信号量
sem_init(&sem2, 0, 0);
}
void first(function<void()> printFirst) {
printFirst();
sem_post(&sem1);
}
void second(function<void()> printSecond) {
sem_wait(&sem1); // 等待sem1结束
printSecond();
sem_post(&sem2); // 通知sem2可以开始了
}
void third(function<void()> printThird) {
sem_wait(&sem2);
printThird();
}
};
| 二、依次循环输出 |
【题目链接】1115. 交替打印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 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。
请设计修改程序，以确保 "foobar" 被输出 n 次。
【解题思路】
最简单的方法，就是考虑用一个两个mutex来控制。
比如，mtx1为lock状态的时候，无法进入thread1，从而保证只能进入thread2。
参考题解，还可以考虑使用atomic<int>来处理，实现当atomic值不符合预期的时候，直接thread::yield()，从而实现等待
【代码实现】
class FooBar {
private:
int n;
mutex m1,m2;
public:
FooBar(int n) {
this->n = n;
m2.lock();
}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
m1.lock();
printFoo();
m2.unlock();
}
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
m2.lock();
printBar();
m1.unlock();
}
}
};
| 三、间隔打印0和奇偶数字 |
【题目链接】1116. 打印零与奇偶数
假设有这么一个类：
class ZeroEvenOdd {
public ZeroEvenOdd(int n) { ... } // 构造函数
public void zero(printNumber) { ... } // 仅打印出 0
public void even(printNumber) { ... } // 仅打印出 偶数
public void odd(printNumber) { ... } // 仅打印出 奇数
}
相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：
线程 A 将调用 zero()，它只输出 0 。
线程 B 将调用 even()，它只输出偶数。
线程 C 将调用 odd()，它只输出奇数。
每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。
【解题思路】
考虑使用condition_variable来实现线程的控制。
注意学习一下cv.wait(lck, pred)这两个参数的用法：
只有当pred条件为false时调用 wait() 才会阻塞当前线程，并且在收到其他线程的通知后只有当pred为true时才会被解除阻塞。
核心想法是，打印一次0，然后就打印一次信息，然后再打印一次0。
所以用zero_flag来0是否被打印过。然后用odd_flag来标识是否需要打印偶数。
每次打印一个数字之后，zero_flag都会被值为true，从而保证能够进入打印0的线程。
打印0的线程结束之后，通知其他两个线程可以开始，并且根据odd_flag的值，来区分是应该打印奇数还是偶数。
【代码实现】
class ZeroEvenOdd {
private:
int n;
std::mutex mtx;
std::condition_variable cond; // 使用条件变量信息
bool zero_flag = true;
bool odd_flag = true;
public:
ZeroEvenOdd(int n) {
this->n = n;
}
void zero(function<void(int)> printNumber) {
for(int i=0; i<n; ++i)
{
std::unique_lock<std::mutex> lk(mtx);
cond.wait(lk, [this]{return zero_flag;});
printNumber(0);
// 设置false之后，再次进入本函数就会被阻塞
zero_flag = false;
cond.notify_all();
}
}
void even(function<void(int)> printNumber) {
for(int i=2; i<=n; i+=2)
{
std::unique_lock<std::mutex> lk(mtx);
cond.wait(lk, [this]{return !zero_flag && !odd_flag;});
printNumber(i);
zero_flag = true;
odd_flag = true;
cond.notify_all();
}
}
void odd(function<void(int)> printNumber) {
for(int i=1; i<=n; i+=2)
{
std::unique_lock<std::mutex> lk(mtx);
cond.wait(lk, [this]{return !zero_flag && odd_flag;});
printNumber(i);
zero_flag = true;
odd_flag = false;
cond.notify_all();
}
}
};
| 四、按规则交替打印字符串 |
【题目链接】1195. 交替打印字符串
编写一个可以从 1 到 n 输出代表这个数字的字符串的程序，但是：
如果这个数字可以被 3 整除，输出 "fizz"。
如果这个数字可以被 5 整除，输出 "buzz"。
如果这个数字可以同时被 3 和 5 整除，输出 "fizzbuzz"。
例如，当 n = 15，输出： 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz。
假设有这么一个类：
class FizzBuzz {
public FizzBuzz(int n) { ... } // constructor
public void fizz(printFizz) { ... } // only output "fizz"
public void buzz(printBuzz) { ... } // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... } // only output "fizzbuzz"
public void number(printNumber) { ... } // only output the numbers
}
请你实现一个有四个线程的多线程版 FizzBuzz， 同一个 FizzBuzz 实例会被如下四个线程使用：
线程A将调用 fizz() 来判断是否能被 3 整除，如果可以，则输出 fizz。
线程B将调用 buzz() 来判断是否能被 5 整除，如果可以，则输出 buzz。
线程C将调用 fizzbuzz() 来判断是否同时能被 3 和 5 整除，如果可以，则输出 fizzbuzz。
线程D将调用 number() 来实现输出既不能被 3 整除也不能被 5 整除的数字。
【解题思路】
这一题，我的想法是可以通过多个循环，每个循环中设定固定条件，从而保证了仅在符合条件的情况下，才有输出。
但是这样做，优点是代码比较简单；但是缺点是，多个线程在无规律等待，造成了时间消耗比较重，所以运行起来，耗时比较高。
大家可以去网上搜索一下通过信号量的方法，直接sem通知需要打印的线程。这样耗时能明显降低，但是如果有多种情况，代码复杂度较高。
在日常项目开发中，需要根据实际情况，自行选择合适的方法。
【代码实现】
class FizzBuzz {
private:
std::mutex mtx;
int index; // 从1开始，标识当前打到第几个。index<=n
int n;
public:
FizzBuzz(int n) {
this->n = n;
index = 1;
}
void fizz(function<void()> printFizz) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 == index % 3 && 0 != index % 5 && index <= n) {
printFizz();
index++;
}
}
}
void buzz(function<void()> printBuzz) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 == index % 5 && 0 != index % 3 && index <= n){
printBuzz();
index++;
}
}
}
void fizzbuzz(function<void()> printFizzBuzz) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 == index % 15 && index <= n) {
printFizzBuzz();
index++;
}
}
}
void number(function<void(int)> printNumber) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 != index % 3 && 0 != index % 5 && index <= n) {
printNumber(index);
index++;
}
}
}
};
| 五、有屏障打印信息 |
【题目链接】1117. H2O生成
现在有两种线程，氧 oxygen 和氢 hydrogen，你的目标是组织这两种线程来产生水分子。
存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。
氢和氧线程会被分别给予 releaseHydrogen 和 releaseOxygen 方法来允许它们突破屏障。
这些线程应该三三成组突破屏障并能立即组合产生一个水分子。
你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。
换句话说:
如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。
如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。
书写满足这些限制条件的氢、氧线程同步代码。
【解题思路-1】
这一题，主要是理解std::this_thread::yield()，表示的当前线程交出cpu时间片，过一会再来看是否满足条件。
这种方法，明显优于while()循环中，一直轮询等待某个值的方式。
【代码实现-1】
class H2O {
atomic<int> hNum; // 表示有H的个数
public:
H2O() {
hNum = 0;
}
void hydrogen(function<void()> releaseHydrogen) {
while(hNum.load() > 1) {
// 如果已经有2个或者以上的H，则不再输出H信息
std::this_thread::yield();
}
releaseHydrogen();
hNum++;
}
void oxygen(function<void()> releaseOxygen) {
while(hNum.load() != 2) {
// 如果H的个数还不到2个，则不输出O信息
std::this_thread::yield();
}
releaseOxygen();
// 当有2个H之后，才能进入这里，并且将H的个数置0
hNum.store(0);
}
};
【解题思路-2】
这种解法主要思路，还是根据cv.wait(mtx, pred)的属性，当pred值为false的时候才阻塞，并且等pred值为true的时候，才恢复。
用这个特性，确保了H被打印2次的时候，就停止打印了，直到所有次数清0（h_count+o_count==3）后恢复。O的打印思路相同，超过1次则停止打印，直到所有次数清0。
解法2性能，明显优于解法1。
【代码实现-2】
class H2O {
private:
std::mutex mtx;
std::condition_variable cond;
int h_count = 0;
int o_count = 0;
public:
H2O() {
}
void hydrogen(function<void()> releaseHydrogen) {
std::unique_lock<std::mutex> lk(mtx);
// 当H还未打印到2次的时候，不会被锁住
// 当H被打印了2次的时候卡住，并且等h_count清空的时候恢复
cond.wait(lk, [this]{return h_count<2;});
releaseHydrogen();
h_count++;
if(h_count + o_count == 3) {
h_count = 0;
o_count = 0;
}
cond.notify_all();
}
void oxygen(function<void()> releaseOxygen) {
std::unique_lock<std::mutex> lk(mtx);
cond.wait(lk, [this]{return o_count<1;});
releaseOxygen();
o_count++;
if(h_count + o_count == 3) {
h_count = 0;
o_count = 0;
}
cond.notify_all();
}
};
| 六、哲学家进餐问题 |
【题目链接】1226. 哲学家进餐
5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）
所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。
假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。
设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。
【解题思路】
C++17中，提供了std::scoped_lock功能，可以写入两个mutex信息。
功能是使得mtx1和mtx2依次lock()，然后在析构的时候，逆序unlock()。
从而使得philosopher1完成了5个动作之后，philosopher2才开始，依次类推。
并且使得philosopher1和philosopher3或者philosopher4之间的操作，不相互影响，从而实现双优。
【代码实现】
class DiningPhilosophers {
public:
using Func = function<void()>;
void wantsToEat(int philosopher, Func pickLeftFork, Func pickRightFork, Func eat, Func putLeftFork, Func putRightFork) {
// 保证相邻的两个philosopher，不会同时进入对应流程
scoped_lock lock(mutexes_[philosopher], mutexes_[philosopher >= 4 ? 0 : philosopher + 1]);
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork();
}
private:
vector<mutex> mutexes_ = vector<mutex>(5);
};
[2021.01.21 by Chunel]
个人信息
微信: ChunelFeng
邮箱: chunel@foxmail.com
个人网站：www.chunel.cn
github地址: https://github.com/ChunelFeng