STEMHA

student

China

文章

分类

标签

105

关注我

2020-05-26

算法

11 分钟读完 (大约 1615 个字)

多线程编程-按序打印（leetcode 1114）

题目描述

提供了一个类：

public class Foo {
  public void one() { print("one"); }
  public void two() { print("two"); }
  public void three() { print("three"); }
}

三个不同的线程将会共用一个 Foo 实例。

线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法

请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。

题目解析

多个线程在cpu中执行，运行不同的程序段，但是这些程序之间有先后关系：

one()方法如果不运行完毕啊，就不能运行two()方法。
two()方法如果不运行完毕啊，就不能运行three()方法。

也属于并发的问题：
并发主要为多任务情况设计。但如果应用不当，可能会引发一些漏洞。按照情况不同，可以分为三种：

竞态条件（Race Condition）：由于多进程之间的竞争执行，导致程序未按照期望的顺序输出。
死锁：并发程序等待一些必要资源，导致没有程序可以执行。
资源不足：进程被永久剥夺了运行所需的资源。

竞态条件是指同一个程序多线程访问同一个资源，如果对资源的访问顺序敏感，就称存在竞态条件，代码区成为临界区。
最常见的竞态条件为：先检测后执行。（比如有一个if判断语句，多个线程都通过这个判断时候，下一步的执行可能造成各种奇怪的结果）

竞态条件的解决方案为：需要某些关键部分代码具有排他性，即在给定的时间内，只有一个线程可以进入关键部分代码。(可以将这种机制看做限制关键部分代码访问的锁)

在该机制下，一旦一个线程进入关键部分，它就可以阻止其他线程进入该关键部分。
如果该线程未被授权进入关键代码，可以认为该线程被阻塞或进入睡眠状态。
这种机制还具有唤醒其他等待线程的功能。

总之，为了防止出现并发竞争状态，需要一种具有两种功能的机制：

关键部分的访问控制。
通知阻塞线程。

代码实现

方法1：使用 synchronization

信号量和互斥锁(mutex)的区别：互斥锁只允许一个线程进入临界区，而信号量允许多个线程同时进入临界区。

#include <semaphore.h>  信号量Semaphore头文件

class Foo {
protected:
    sem_t firstJobDone; 信号量的数据类型为结构sem_t，它本质上是一个长整型的数。
    sem_t secondJobDone;

public:

    Foo() {
        sem_init(&firstJobDone, 0, 0);
        sem_init(&secondJobDone, 0, 0);
    }

    void first(function<void()> printFirst) {
        printFirst();
        sem_post(&firstJobDone);
    }

    void second(function<void()> printSecond) {
        sem_wait(&firstJobDone);
        printSecond();
        sem_post(&secondJobDone);
        
    }

    void third(function<void()> printThird) {
        sem_wait(&secondJobDone);
        printThird();
    }
};

semaphore是由操作系统提供的。

LINUX下，一般是＃include<asm/semaphore.h> 或＃include<semaphore.h>
Windows下，一般是windows.h

信号量的数据类型为结构sem_t，它本质上是一个长整型的数。
sem_init：sem_init函数是Posix信号量操作中的函数。sem_init() 初始化一个定位在 sem 的匿名信号量。value 参数指定信号量的初始值。 pshared 参数指明信号量是由进程内线程共享，还是由进程之间共享。如果 pshared 的值为 0，那么信号量将被进程内的线程共享，并且应该放置在这个进程的所有线程都可见的地址上(如全局变量，或者堆上动态分配的变量)。

int sem_init(sem_t *sem, int pshared, unsigned int value);
sem ：指向信号量对象
pshared : 指明信号量的类型。不为0时此信号量在进程间共享，否则只能为当前进程的所有线程共享。
value : 指定信号量值的大小
sem_init() 成功时返回 0；错误时，返回 -1，并把 errno 设置为合适的值。

sem_post：sem_post是给信号量的值加上一个“1”，它是一个“原子操作”－－－即同时对同一个信号量做加“1”操作的两个线程是不会冲突的；

1 2	int sem_post(sem_t *sem); sem_post() 成功时返回 0；错误时，信号量的值没有更改，-1 被返回，并设置 errno 来指明错误

sem_wait: sem_wait是一个函数，也是一个原子操作，它的作用是从信号量的值减去一个“1”，但它永远会先等待该信号量为一个非零值才开始做减法。也就是说，如果你对一个值为2的信号量调用sem_wait()，线程将会继续执行，将信号量的值将减到1。
如果对一个值为0的信号量调用sem_wait()，这个函数就会原地等待直到有其它线程增加了这个值使它不再是0为止。(也就是说是等于0时会阻塞操作)

1	int sem_wait(sem_t *sem)

方法2：使用mutex加锁解锁

class Foo {
public:
    Foo() {
	//构造函数先执行，将mutex变量进行加锁初始化。
        m2.lock();  /首先给second()和third()上锁
        m3.lock(); 
    }

    void first(function<void()> printFirst) {
        printFirst();
        m2.unlock();  /first()运行完了就解开second()的锁
    }
    void second(function<void()> printSecond) {
        m2.lock();    这里是锁的入口，如果已经上锁了，就不能执行了，如果没有，就可以执行下一步，并把锁值0置为1
        printSecond();
        m3.unlock();  //second()运行完了就解开third()的锁
    }
    void third(function<void()> printThird) {
        m3.lock();
        printThird();
        m3.unlock();
    }
private:
    std::mutex m2, m3;
    
};

参考资料

力扣（LeetCode）
C++多线程同步之Semaphore(信号量)
进程间通信方式——信号量（Semaphore）
线程同步之信号量（sem_init,sem_post,sem_wait）

# C++, leetcode, 互斥锁, 信号量, 多线程

目录

链接

分类

标签云

最新文章

归档

标签