1 环形队列

环形队列采用数组来模拟，用取模运算来模拟环状特性。

1.如何判断环形队列为空或者为满?

• 当环形队列为空时，头和尾都指向同一个位置。
• 当环形队列为满时，头和尾也都指向同一个位置。

因此， 可以通过加计数器或者标记位来判满或者空，也可以预留一个空的位置，作为满的状态

1.1 生产者消费者中的环形队列

2.生产者和消费者什么时候会访问同一个位置?

1.环形队列为空的时候，生产者和消费者会访问同一个位置。

环形队列中，如果队列为空，那么队首和队尾的指针是指向同一个位置的。所以，生产者和消费者也会指向同一个位置。

2.环形队列为满的时候，生产者和消费者会访问同一个位置。

环形队列中，如果队列为满，那么队首和队尾的指针是指向同一个位置的。所以，生产者和消费者也会指向同一个位置。

其他任何时候，生产者和消费者访问的都是不同的区域。。

3.环形队列中的数据需要注意什么?

1.消费者不能超过生产者。

也就是： 不能没有数据了还继续消费
。

2.生产者不能将消费者套圈。

也就是： 不能没有空间了还继续生产
。

2 设计信号量

生产者最在意的是空闲的空间个数
消费者最在意的是数据的个数

所以生产者每次在访问临界资源之前，需要先申请空间资源的信号量，申请成功就可以进行生产，否则就阻塞等待。

消费者在访问临界资源之前，需要申请数据资源的信号量，申请成功就可以消费数据，否则就阻塞等待。

空间资源信号量的申请由生产者进行，归还(V操作)由消费者进行，表示生产者可以生产数据。

数据资源信号量的申请有消费者进行，归还(V操作)由生产者进行，表示消费者可以进行消费.

4.空间资源信号如何设计？

最开始，生产者没有生产，所以空间资源是队列的大小（满的）

5.数据资源信号如何设计？

最开始，生产者没有生产，所以数据资源为0（空的）

2.1 生产者伪代码

productor_sem = 环形队列大小;P(productor_sem);//申请空间资源信号量
//申请成功，继续向下运行。
//申请失败，阻塞在申请处。.......//从事生产活动——把数据放入队列中V(comsumer_sem);//归还数据资源信号量

2.2 消费者伪代码

comsumer_sem = 0;P(comsumer_sem);//申请数据资源信号量
//申请成功，继续向下运行。
//申请失败，阻塞在申请处。.......//从事消费活动——从队列中消费数据V(proudctor_sem);//归还空间资源信号量

在环形队列中，大部分情况下单生产和单消费是可以并发执行的，只有在满或者空的时候，才会有同步和互斥问题，同步和互斥是通过信号量来实现的。

3 代码

3.1 RingQueue.h

#include <iostream>
#include <vector>
#include <semaphore.h>
#include <pthread.h>//为什么基于阻塞队列的生产者消费者模型只需要一个锁 ， 而基于环形队列的生产者消费者模型需要两个锁？
//1.因为阻塞队列是对同一个队列的同一个位置进行操作，队列是共享资源，需要对整个队列加锁
//2.阻塞队列中，生产者和消费者访问的不是同一个下标，所以两者是互不干扰的，只需要用条件变量来唤醒阻塞
//但是生产者对生产者而言，是需要加锁的。消费者对消费者而言，是需要加锁的。template <class T>
class RingQueue
{static const int defaultnum = 5;
public://p操作，申请信号量，信号量--void p(sem_t& sem){sem_wait(&sem);}//v操作，释放信号量，信号量++void v(sem_t& sem){sem_post(&sem);}void Lock(pthread_mutex_t& mutex){pthread_mutex_lock(&mutex);}void UnLock(pthread_mutex_t& mutex){pthread_mutex_unlock(&mutex);}public:RingQueue(int cap = defaultnum):_ringqueue(cap),_cap(cap),_c_step(0),_p_step(0){//初始化信号量，给消费者初始的信号量为0，给生产者初始的信号量为cap(满)//因为最开始的时候没有商品，无法消费，只能生产sem_init(&_c_data_sem, 0, 0);sem_init(&_p_space_sem, 0, cap);pthread_mutex_init(&_c_mutex, nullptr);pthread_mutex_init(&_p_mutex, nullptr);}//生产商品void push(const T &in){   //1.申请信号量p(_p_space_sem);//2.消费者加锁Lock(_p_mutex);//3.进行生产_ringqueue[_p_step] = in;_p_step++;_p_step %= _cap;  //保证下标一直都在环形队列里面//4.解锁UnLock(_p_mutex);//5.释放信号量v(_c_data_sem);}void pop(T* out){//1.申请信号量p(_c_data_sem);//2.申请锁Lock(_c_mutex);//3.消费数据*out = _ringqueue[_c_step];++_c_step;_c_step %= _cap;//4.解锁UnLock(_c_mutex);//5.生产者信号量++v(_p_space_sem);  //消费完数据之后，生产者的信号量++}
private:std::vector<T> _ringqueue;int _cap;     //capacityint _c_step;  //消费者在环形队列中的下标int _p_step;  //生产者在环形队列中的下标sem_t _c_data_sem;  //消费者关注的数据资源sem_t _p_space_sem; //生产者关注的消费资源pthread_mutex_t _c_mutex;   //消费者锁pthread_mutex_t _p_mutex;   //生产者锁
};

3.1.1 生产商品

//生产商品void push(const T &in){   //1.申请信号量p(_p_space_sem);//2.消费者加锁Lock(_p_mutex);//3.进行生产_ringqueue[_p_step] = in;_p_step++;_p_step %= _cap;  //保证下标一直都在环形队列里面//4.解锁UnLock(_p_mutex);//5.释放信号量v(_c_data_sem);}

6.为什么要按照 申请信号量 → 加锁 → 解锁 → 释放信号量 的顺序来做？

如果先加锁再申请信号量，可能会出现以下这种情况：
加锁之后，发现没有空闲空间了，于是阻塞。而此时该线程还持有锁，就会导致死锁。.
如果先释放信号量再解锁，可能会出现以下这种情况：
释放信号量之后，消费者得知有可以消费的资源，于是开始消费。但是此时并没有解锁，因此生产者可能并没有完全完成生产，但是消费者已经开始消费。就会导致生产消费数据不一致的问题。.

3.1.2 消费商品

void pop(T* out){//1.申请信号量p(_c_data_sem);//2.申请锁Lock(_c_mutex);//3.消费数据*out = _ringqueue[_c_step];++_c_step;_c_step %= _cap;//4.解锁UnLock(_c_mutex);//5.生产者信号量++v(_p_space_sem);  //消费完数据之后，生产者的信号量++}