单生产者单消费者的环形队列

2018-01-25 10:57:44来源:网络收集作者:管理员人点击

分享
第七城市

[var1]环形队列设计如下:
template
class ring
{
puclic:
    explicit ring(int size): m_maxsize(size), m_rp(0), m_wp(0)
    {   
        if (size < 2)
        {
            throw std::runtime_error("too few elements, size must grater than 1");
        }
        m_array = new T[size+1];
    }
    
    ~ring
    {
        delete [] m_array;
    }
    bool full()const
    {
        return inc(wp) == rp;
    }
    bool empty()const
    {
        return rp == wp;
    }
    int inc(int n)const
    {
        return ++n % (maxsize+1);
    }
    int push_back(const T& v)
    {
       if (full()) 
        {
            return -1;
        }
        m_array[m_wp] = v;
        m_wp = inc(m_wp);
        return 0;
    }
    
    int pop_front(T& v)
    {
        if (empty())
        {
            return -1;
        }
        v = m_array[m_rp];
        m_rp = inc(m_rp);
        return 0;
    }
    
    size_t size()const
    {   
        size_t n = m_wp - m_rp;
        return n > 0 ? n : m_maxsize + n;
    }
    
private:
    T* m_array;
    int m_maxsize;
    int m_rp __attribute__((align(8)));
    int m_wp __attribute__((align(8)));
    
}
考虑如下情况,单生产者,单消费者
1.读线程追赶写线程,但empty()条件rp == wp一直为true,即使不加锁也线程安全
2.写线程追赶读线程,单full()条件wp++ == rp一直
3.极端情况下
rp=wp=m_maxsize
读写线程按如下指令执行:
写线程                      读线程
wp++
                            empty() rp == wp 为false
                            rp++
                            rp = 0   rp翻转
                            empty()为false 可读
wp = 0 wp翻转
                            rp++    rp=1,这个时候读索引已经在写索引前,数据读取异常
                            
4.所以rp,wp的操作必须是原子的,根据Intel手册8.1.1节的介绍:
从Intel486 processor开始,以下的基本内存操作是原子的:
• Reading or writing a byte(一个字节的读写)
• Reading or writing a word aligned on a 16-bit boundary(对齐到16位边界的字的读写)
• Reading or writing a doubleword aligned on a 32-bit boundary(对齐到32位边界的双字的读写)
从Pentium processor开始,除了之前支持的原子操作外又新增了以下原子操作:
• Reading or writing a quadword aligned on a 64-bit boundary(对齐到64位边界的四字的读写)
• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus(未缓存且在32位数据总线范围之内的内存地址的访问)
所以__attribute__((align(8)))可保证索引读写的原子性

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台