抱佛脚-刷题系列之多线程

抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的多线程问题~
参考链接：leetcode

概述

基本方法

  • 使用信号量
    • #include <semaphore.h>
    • 定义信号量：sem_t x;
    • 初始化：sem_init(&x, 0, 0); // 第一个参数：控制信号量的类型，值为 0 代表该信号量用于多线程间的同步， > 0 时指定了 sem 处于共享内存区域，所以可以在进程间共享该变量；第二个参数：初始值
    • 释放：sem_post(&x);
    • 等待：sem_wait(&x); // 阻塞的函数，测试所指定信号量的值，它的操作是原子的
    • 非阻塞：sem_trywait(&x); // 非阻塞的函数，它会尝试获取获取 sem value 值，如果 sem value = 0，不是阻塞住，而是直接返回一个错误 EAGAIN
    • int sem_getvalue(sem_t *sem, int *sval); // 获取信号量 sem 的当前值，把该值保存在 sval，若有 1 个或者多个线程正在调用 sem_wait 阻塞在该信号量上，该函数返回阻塞在该信号量上进程或线程个数
    • 清理信号量：int sem_destroy(sem_t *sem); // 成功则返回 0，失败返回 -1
  • 使用互斥锁（能用互斥锁的通常都可以用信号量实现）
    • 定义互斥锁：pthread_mutex_t mutex;
    • 初始化：pthread_mutex_init(&mutex, NULL); // NULL表示使用默认的互斥锁属性
    • 加锁：pthread_mutex_lock(&mutex); // 相当于sem_wait，表示尝试加锁，一直到加到锁才可以执行下面的代码
    • 解锁：pthread_mutex_unlock(&mutex);
    • 尝试加锁：pthread_mutex_trylock(&mutex); // 成功返回0
  • 使用wait&notify
    • 定义条件变量：std::condition_variable cond; (std::mutex m;)
    • 加锁：std::unique_lock<std::mutex> lk(m);
    • wait：cond.wait(lk,[this]{return o_count<1;}); // 也可以用普通函数
      1. 如果条件不满足(函数返回false)，wait解锁lk，并将该线程置于阻塞状态，继续等待notify来唤醒它
      2. 如果条件满足(函数返回true)，wait继续锁定lc，执行wait后面的代码
    • notify：cond.notify_all(); // 或者 notify_one()

基本思路

  • 按序打印：lc1114；lc1116；lc1195；lc1115
    1. 每种打印线程都设置一个信号量/互斥锁
    2. 一开始进入的打印线程初始值设为可以访问（如信号量设为1、不加互斥锁）
    3. 每个线程都是：for i in range-if 是自己要打印的数字-等待自己的信号量/锁-打印数字-解开其他某个线程的锁/信号量
  • 不一定按顺序打印：lc1117
    1. 使用wait/notify

按序打印的题目

交替打印FooBar（lc1115）

  • 使用信号量
#include <semaphore.h>
class FooBar {
private:
    int n;
    sem_t sfoo;
    sem_t sbar;

public:
    FooBar(int n) {
        this->n = n;
        sem_init(&sfoo, 0, 1); 
        sem_init(&sbar, 0, 0); 
    }

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

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

按序打印（lc1114）

  • 使用信号量
class Foo {
    public:
    Foo() {
        sem_init(&firstJobDone, 0, 0);
        sem_init(&secondJobDone, 0, 0);
    }

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

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

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

打印零与奇偶数（lc1116）

  • 使用信号量
#include <semaphore.h>
class ZeroEvenOdd {
private:
    int n;
    sem_t zeroSem;
    sem_t oddSem;
    sem_t evenSem;
    
public:
    ZeroEvenOdd(int n) {
        this->n = n;
        sem_init(&zeroSem, 0, 1);
        sem_init(&oddSem, 0, 0);
        sem_init(&evenSem, 0, 0);
    }

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

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

    void odd(function<void(int)> printNumber) {
        for (int i = 1; i <= n; i += 2) {
            sem_wait(&oddSem);
            printNumber(i);
            sem_post(&zeroSem);
        }
    }
};
- 使用互斥锁
```cpp
class ZeroEvenOdd {
private:
    int n;
    pthread_mutex_t mutex0;
    pthread_mutex_t mutex1;
    pthread_mutex_t mutex2;
    
public:
    ZeroEvenOdd(int n) {
        this->n = n;
        pthread_mutex_init(&mutex0, NULL);
        pthread_mutex_init(&mutex1, NULL);
        pthread_mutex_init(&mutex2, NULL);
        pthread_mutex_lock(&mutex1);
        pthread_mutex_lock(&mutex2);
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        for (int i = 0; i < n; ++i) {
            pthread_mutex_lock(&mutex0);
            printNumber(0);
            if (i % 2 == 0) pthread_mutex_unlock(&mutex1);
            else pthread_mutex_unlock(&mutex2);
        }
    }

    void even(function<void(int)> printNumber) {
        for (int i = 2; i <= n; i += 2) {
            pthread_mutex_lock(&mutex2);
            printNumber(i);
            pthread_mutex_unlock(&mutex0);
        }
    }

    void odd(function<void(int)> printNumber) {
        for (int i = 1; i <= n; i += 2) {
            pthread_mutex_lock(&mutex1);
            printNumber(i);
            pthread_mutex_unlock(&mutex0);
        }
    }
};

交替打印字符串（lc1195）

  • 使用信号量
#include <semaphore.h>
class FizzBuzz {
private:
    int n;
    int last = 0;
    sem_t nx, n3, n5, n35;
public:
    FizzBuzz(int n) {
        sem_init(&nx, 0, 1);
        sem_init(&n3, 0, 0);
        sem_init(&n5, 0, 0);
        sem_init(&n35, 0, 0);
        this->n = n;
    }
    
    // printFizz() outputs "fizz".
    void fizz(function<void()> printFizz) {
        for(int i=1; i<=n; ++i) {
            if(i%3==0 && i%5){
                sem_wait(&n3);
                printFizz();
                if ((i+1)%5 == 0) sem_post(&n5);
                else sem_post(&nx);
            }
        }
    }

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

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

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

不一定按序打印的题目

H2O生成（lc1117）

  • 使用wait&notify
class H2O {
public:
    H2O() {
        
    }

    void hydrogen(function<void()> releaseHydrogen) {
        unique_lock<mutex> lk(m);
        cond.wait(lk, [this] {return this->h < 2;});
        releaseHydrogen();
        ++h;
        if (h + o == 3) {
            h = 0;
            o = 0;
        }
        cond.notify_all();
    }

    void oxygen(function<void()> releaseOxygen) {
        unique_lock<mutex> lk(m);
        cond.wait(lk, [this] {return this->o < 1;});
        releaseOxygen();
        ++o;
        if (h + o == 3) {
            h = 0;
            o = 0;
        }
        cond.notify_all();
    }
private:
    mutex m;
    condition_variable cond;
    int o = 0;
    int h = 0;
};
  • 使用信号量
#include<semaphore.h>
class H2O {
public:
    
    sem_t h, o, h_loc;
    int h_out;
    H2O() {
        sem_init(&h, 0, 2);
        sem_init(&o, 0, 0);
        sem_init(&h_loc, 0, 1);
        h_out = 0;
    }

    void hydrogen(function<void()> releaseHydrogen) {
        sem_wait(&h);
        sem_wait(&h_loc);
        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        if(h_out == 1){
            h_out = 0;
            sem_post(&o);
        }else{
            h_out ++;
        }
        sem_post(&h_loc);
    }

    void oxygen(function<void()> releaseOxygen) {
        sem_wait(&o);
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        sem_post(&h);
        sem_post(&h);
    }
};

其他题目

红绿灯路口（lc1279）

  • 使用信号量
#include <semaphore.h>
class TrafficLight {
private:
    int road; // 亮绿灯的路id
    sem_t s;
public:
    TrafficLight() {
        sem_init(&s, 0, 1);
        road = 1;
    }

    void carArrived(
        int carId,                   // ID of the car
        int roadId,                  // ID of the road the car travels on. Can be 1 (road A) or 2 (road B)
        int direction,               // Direction of the car
        function<void()> turnGreen,  // Use turnGreen() to turn light to green on current road
        function<void()> crossCar    // Use crossCar() to make car cross the intersection
    ) {
        sem_wait(&s);
        if (roadId != road) {
            turnGreen();
            road = 3 - road;
        }
        crossCar();
        sem_post(&s);
    }
};

哲学家进餐（lc1226）

class DiningPhilosophers {
private:
    pthread_mutex_t forks[5];
public:
    DiningPhilosophers() {
        for(int i = 0; i < 5; i++) pthread_mutex_init(forks + i, NULL);
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        int left_hand = philosopher, right_hand = (philosopher + 1) % 5;    //左右手序号
        int ret1 = 1, ret2 = 1;
        while(ret1 || ret2) {                                               //尝试同时锁两个直到成功
            if(ret1 == 0) pthread_mutex_unlock(forks + left_hand);          //锁失败锁住的打开
            if(ret2 == 0) pthread_mutex_unlock(forks + right_hand);
            ret1 = pthread_mutex_trylock(forks + left_hand);                //继续尝试 
            ret2 = pthread_mutex_trylock(forks + right_hand);               //pthread_mutex_trylock 成功会返回0
        }
        pickLeftFork();
        pickRightFork();
        eat();
        putLeftFork();
        putRightFork();
        pthread_mutex_unlock(forks + left_hand);                            //全部解锁
        pthread_mutex_unlock(forks + right_hand);
    }
};

生产者消费者问题

  • 使用信号量
#include<queue>
#include<semaphore.h>
class BoundedBlockingQueue {
public:
    
    sem_t p, c, mut;
    queue<int> q;
    
    BoundedBlockingQueue(int capacity) {
        sem_init(&p, 0, capacity); // 生产者
        sem_init(&c, 0, 0); // 消费者
        sem_init(&mut, 0, 1); // 锁
    }
    
    void enqueue(int element) {
        sem_wait(&p);
        sem_wait(&mut);
        q.push(element);
        sem_post(&mut);
        sem_post(&c);
    }
    
    int dequeue() {
        
        sem_wait(&c);
        sem_wait(&mut);
        int ans = q.front();
        q.pop();
        sem_post(&mut);
        sem_post(&p);
        return ans;
        
    }
    
    int size() {
        sem_wait(&mut);
        int ans = q.size();
        sem_post(&mut);
        return ans;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 210,978评论 6赞 490
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 89,954评论 2赞 384
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 156,623评论 0赞 345
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,324评论 1赞 282
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,390评论 5赞 384
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,741评论 1赞 289
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,892评论 3赞 405
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,655评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,104评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,451评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,569评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,254评论 4赞 328
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,834评论 3赞 312
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,725评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,950评论 1赞 264
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,260评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,446评论 2赞 348