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);  //消費完數據之后，生產者的信號量++}