C++线程安全容器stack和queue的使用详细介绍

目录
  • 线程安全的容器栈threadsafe_stack
  • 线程安全的容器队列threadsafe_queue

要构建线程安全的数据结构, 关注几点:

  • 若某线程破坏了数据结构的不变量, 保证其他线程不能看到
  • 提供的操作应该完整,独立, 而非零散的分解步骤避免函数接口固有的条件竞争(比如之前提到的empty和top和pop)

线程安全的容器栈threadsafe_stack

入门(3)里曾介绍过线程安全的stack容器, 这里把代码搬过来再分析

逐项分析, 该代码如何实现线程安全的

template<typename T>
class threadsafe_stack
{
private:
    stack<T> data;
    mutable mutex m;
public:
    threadsafe_stack(){}
    threadsafe_stack(const threadsafe_stack &other)
    {
        lock_guard lock1(other.m);
        data=other.data;
    }
    threadsafe_stack &operator=(const threadsafe_stack &) = delete;
    void push(T new_value)
    {
        lock_guard lock1(m);
        data.push(move(new_value));      //1
    }
    shared_ptr<T> pop()
    {
        lock_guard lock1(m);
        if (data.empty())
        {
            throw empty_stack();        //2
        }
        shared_ptr<T> const
                res(make_shared<T>(move(data.top()))); //3
        data.pop();                                     //4
        return res;
    }
    void pop(T &value)
    {
        lock_guard lock1(m);
        if (data.empty())
        {
            throw empty_stack();
        }
        value = move(data.top());    //5
        data.pop();                 //6
    }
    bool empty() const //7
    {
        lock_guard lock1(m);
        return data.empty();
    }
};

首先, 每个操作都对互斥加锁, 保证基本线程安全

其次, 在多线程下, 对于std::stack容器, empty(), top(), pop()存在接口上的数据竞争(见入门(3)说明), 于是threadsafe_stack把这些调用集合到一个函数pop()里, 以实现线程安全. 其中pop()函数里若与遇栈空, 直接抛出异常

接着分析:

1处data.push()可能抛出异常: 原因是复制/移动时抛出异常或stack容器扩展容量时遇上内存分配不足, 但无论哪种, std::stack<>能保证自身的安全

2处抛出的异常: 没有改动数据, 安全的抛出行为

3处共享指针的创建可能抛出异常: 内存不足或移动/复制相关的构造函数抛出异常,但两种情形c++都能保证不会出现内存泄漏, 并且此时数据还未改动(data.pop()时才改动),

4处data.pop()的实质操作是返回结果, 绝不会抛出异常,结合3, 所以这是异常安全的重载函数pop()

5,6处和3,4处类似, 不同之处是没用创建新共享指针, 但此时数据也没被改动, 也是安全的重载函数pop()

最后7处empty()不改动任何数据, 是异常安全的函数

从内存和数据结构安全方面来说没用问题

然而,这段代码可能造成死锁:

因为在持锁期间, 有可能执行以下用户自定义函数:

用户自定义的复制构造函数(1 3处的res构造), 移动构造函数(3处的make_share), 拷贝赋值操作和移动赋值操作(5处), 用户也可能重载了new和delete.

当在这些函数里, 若是再次调用了同个栈的相关函数, 会再次申请获取锁, 然而之前的锁还没释放, 因此造成死锁

以下是我想到的一种死锁方式(正常情况应该不会这么写, 但是设计时必须要考虑)

class A;
threadsafe_stack<A> s;
class A
{
public:
    A(A&& a)//2->然后这里使用s.pop(),之前锁没释放, 造成了死锁
    {
        s.pop();
    }
    A(){}
};
int main()
{
    s.push(A()); //1->临时对象A()在s.push()里被move进内置data时, 会调用A的移动构造函数
    return 0;
}

向栈添加/移除数据, 不可能不涉及复制行为或内存行为, 于是只能对栈的使用者提出要求: 让使用者来保证避免死锁

栈的各成员函数都有lock_guard保护数据, 因此同时调用的线程没有数量限制.

仅有构造函数和析构函数不是安全行为, 但无论是没构造完成还是销毁到一半, 从而转去调用成员函数, 这在有无并发情况下都是不正确的.

所以, 使用者必须保证: 栈容器未构造完成时不能访问数据, 只有全部线程都停止访问时, 才可销毁容器

线程安全的容器队列threadsafe_queue

自定义一个threadsafe_queue, 并且上面对于线程安全的大多数分析在这也成立

template<typename T>
class threadsafe_queue
{
private:
    queue<T> data;
    mutable mutex m;
    condition_variable condition;
public:
    threadsafe_queue()
    {}
    threadsafe_queue(const threadsafe_queue &other)
    {
        lock_guard lock1(other.m);
        data = other.data;
    }
    threadsafe_queue &operator=(const threadsafe_queue &) = delete;
    void push(T new_value)
    {
        lock_guard lock1(m);
        data.push(move(new_value));
        condition.notify_one();   //1
    }
    void wait_and_pop(T &value)      //2
    {
        lock_guard lock1(m);
        condition.wait(lock1, [this]
        {
            return !data.empty();
        });
        value = move(data.top());
        data.pop();
    }
    shared_ptr<T> wait_and_pop()       //3
    {
        lock_guard lock1(m);
        condition.wait(lock1, [this]
        {
            return !data.empty();
        });
        shared_ptr<T> const
                res(make_shared<T>(move(data.top()))); //4 创建shared_ptr可能出现异常
        data.pop();
        return res;
    }
    shared_ptr<T> try_pop()
    {
        lock_guard lock1(m);
        if (data.empty())
        {
            return shared_ptr<T>();     //5
        }
        shared_ptr<T> const
                res(make_shared<T>(move(data.top())));
        data.pop();
        return res;
    }
    bool try_pop(T &value)
    {
        lock_guard lock1(m);
        if (data.empty())
        {
            return false;
        }
        value = move(data.top());
        data.pop();
    }
    bool empty() const
    {
        lock_guard lock1(m);
        return data.empty();
    }
};

区别:

发现队列通常用于消费者/生产者模型, 因此实现阻塞的取值函数wait_and_pop, 即当调用时队列若空, 阻塞等待, 直到push数据后调用condition.notify_one()

同时也提供了非阻塞的取值函数try_pop

然而这一实现会有问题:

假如有多个线程同时等待, condition.notify_one()只能唤醒其中一个,若该唤醒的线程执行wait_and_pop之后的代码抛出异常(例如4处res的创建), 此时队列里还有数据,却不会有其他任何线程被唤

如果我们因不能接受这种行为方式, 而只是简单的把notify_one改为notify_all,这样每次push数据后都会唤醒所有的等待线程. 由于只push了1个数据, 大多数线程醒来后发现队列还是为空, 还得继续等待, 这将大大增加开销

第二种解决种方法是若wait_and_pop抛出异常则再次调用notify_one

第三种方法是让std::queue存储share_ptr<T>, share_ptr的初始化移动到push的调用处, 从内部复制shared_ptr<>实例则不会抛出异常

这里采用第三种方法, 还会有额外的好处: push里为shared_ptr分配内存操作在加锁之前, 缩短了互斥加锁的时间, 由于分配内存通常是耗时的操作, 因此这样非常有利于增强性能

template<typename T>
class threadsafe_queue
{
private:
    queue<shared_ptr<T>> data;
    mutable mutex m;
    condition_variable condition;
public:
    threadsafe_queue()
    {}
    threadsafe_queue(const threadsafe_queue &other)
    {
        lock_guard lock1(other.m);
        data = other.data;
    }
    threadsafe_queue &operator=(const threadsafe_queue &) = delete;
    void push(T new_value)
    {
        //分配内存在加锁操作之前
        shared_ptr<T> value(make_shared<T>(move(new_value)));
        lock_guard lock1(m);
        data.push(value);
        condition.notify_one();
    }
    void wait_and_pop(T &value)
    {
        lock_guard lock1(m);
        condition.wait(lock1, [this]
        {
            return !data.empty();   //队列空则等待
        });
        value = move(*data.front()); //先取值, 再存入参数value
        data.pop();
    }
    bool try_pop(T &value)
    {
        lock_guard lock1(m);
        if (data.empty())
        {
            return false;       //队列空返回false
        }
        value = move(*data.front()); //先取值, 再存入参数value
        data.pop();
        return true;
    }
    shared_ptr<T> wait_and_pop()
    {
        lock_guard lock1(m);
        condition.wait(lock1, [this]
        {
            return !data.empty();    //队列空则等待
        });
        shared_ptr<T> res = data.front(); //取出结果返回给外部
        data.pop();
        return res;
    }
    shared_ptr<T> try_pop()
    {
        lock_guard lock1(m);
        if (data.empty())
        {
            return shared_ptr<T>();     //队列空返回空shared_ptr
        }
        shared_ptr<T> res = data.front();//取出结果返回给外部
        data.pop();
        return res;
    }
    bool empty() const
    {
        lock_guard lock1(m);
        return data.empty();
    }
};

到此这篇关于C++线程安全容器stack和queue的使用详细介绍的文章就介绍到这了,更多相关C++ stack和queue内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • c++中stack、queue和vector的基本操作示例

    前言 这几天在接触搜索的题目,用bfs时基本都用到队列,就顺便学习了数据结构的栈.队列.本文将详细给大家介绍关于c++中stack.queue和vector的基本操作,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. stack 的基本操作有: 入栈,如例:s.push(x); 出栈,如例:s.pop();注意,出栈操作只是删除栈顶元素,并不返回该元素. 访问栈顶,如例:s.top() 判断栈空,如例:s.empty() ,当栈空时,返回true. 访问栈中的元素个数,如例:s.

  • C++ STL容器stack和queue详解

    stack是一个比较简单的容器,它的使用也很简单,stack是LIFO容器,就是后进先出,最后添加进去的元素,第一个取出来 stack初始化 std::stack<int> first; std::stack<int> second(first); std::stack<int, std;:vector<int>> third; //使用vector初始化stack ### stack常用方法### empty();//判断是否为空 push(Elem e)

  • C++ 详细讲解stack与queue的模拟实现

    目录 容器适配器 双端队列 概念 结构 deque迭代器 优缺点 stack模拟 queue模拟实现 容器适配器 适配器是一种设计模式(设计模式是一套反复使用的.大部分人知道的代码设计经验的总结),该模式试讲一个类的接口转化为用户希望的另一个接口,虽然stack与queue中也可以存放元素,但在STL中并没有将其划分为容器,而是成为容器适配器,这是因为stack与队列只是堆其他容器进行了包装,STL中的stack和queue是使用双端队列进行封装的. 双端队列 概念 它是一种双开口的连续空间数据

  • C++ 超详细讲解stack与queue的使用

    目录 stack 介绍和使用 模拟实现 stack的使用例题 最小栈 栈的弹出压入序列 逆波兰表达式求值 queue 模拟实现 容器适配器 deque简介 priority_queue优先级队列 priority_queue的使用 priority_queue的模拟实现 通过仿函数控制比较方式 stack 介绍和使用 stack文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作. stack是作为容器适配器被实现的,容器适

  • C++中stack、queue、vector的用法详解

    一.栈(stack) 引入头文件 #include<stack> 常用的方法 empty() 堆栈为空则返回真 pop() 移除栈顶元素 push() 在栈顶增加元素 size() 返回栈中元素数目 top() 返回栈顶元素 3.实例代码 #include<iostream> #include<stack> using namespace std; int main(){ //创建栈 s stack<int> s; //将元素压入栈 for(int i=0;

  • C++stack与queue模拟实现详解

    目录 stack与queue模拟实现 stack queue 为什么选择deque作为stack和queue的底层默认容器 总结 stack与queue模拟实现 在stl中,stack(栈)与queue(队列)都是容器适配器. 什么是容器适配器呢? 适配器(adaptor)是标准库中通用的概念,包括容器适配器.迭代器适配器和函数适配器.本质上,适配器是使一事物的行为类似于另一事物的行为的一种机制.容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现.简单来说其实就是利用现有的容

  • C++线程安全容器stack和queue的使用详细介绍

    目录 线程安全的容器栈threadsafe_stack 线程安全的容器队列threadsafe_queue 要构建线程安全的数据结构, 关注几点: 若某线程破坏了数据结构的不变量, 保证其他线程不能看到 提供的操作应该完整,独立, 而非零散的分解步骤避免函数接口固有的条件竞争(比如之前提到的empty和top和pop) 线程安全的容器栈threadsafe_stack 入门(3)里曾介绍过线程安全的stack容器, 这里把代码搬过来再分析 逐项分析, 该代码如何实现线程安全的 template<

  • C++ stack与queue使用方法详细讲解

    目录 Stack的介绍和使用 stack的默认定义的模板 stack的使用 queue的介绍和使用 queue的默认定义的模板 queue的使用 Stack的介绍和使用 stack的文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出. sta

  • Python3 queue队列模块详细介绍

    queue介绍 queue是python中的标准库,俗称队列. 在python中,多个线程之间的数据是共享的,多个线程进行数据交换的时候,不能够保证数据的安全性和一致性,所以当多个线程需要进行数据交换的时候,队列就出现了,队列可以完美解决线程间的数据交换,保证线程间数据的安全性和一致性. 注意: 在python2.x中,模块名为Queue queue模块有三种队列及构造函数 Python queue模块的FIFO队列先进先出. queue.Queue(maxsize) LIFO类似于堆,即先进后

  • 深入线程安全容器的实现方法

    最近写了个小程序用到了C#4.0中的线程安全集合.想起很久以前用C#2.0开发的时候写后台windows服务,为了利用多线程实现生产者和消费者模型,经常要封装一些线程安全的容器,比如泛型队列和字典等等.下面就结合部分MS的源码和自己的开发经验浅显地分析一下如何实现线程安全容器以及实现线程安全容器容易产生的问题. 一.ArrayList 在C#早期版本中已经实现了线程安全的ArrayList,可以通过下面的方式构造线程安全的数组列表: var array = ArrayList.Synchroni

随机推荐