單生產者和單消費者共同操作同一個環形緩衝區需要加鎖嗎?

01-13

# 問題描述
1. 本問題只針對單個生產者進程和單個消費者進程的問題進行討論。
2. 生產者進程和消費者進程之間通過共享內存的方式進行IPC通信。
3. 環形緩衝區存放在共享內存中，並且環形緩衝區中環形緩衝單元的個數為 `2^N` 個（N為大於1的正整數），環形緩衝區的數據結構定義為：

```c
#define RING_BUFFER_SIZE N
struct RingBuffer{
int w_pos; //環形緩衝區寫入位置值
int r_pos; //環形緩衝區讀取位置值
data_block data[(1&<& }
```
在創建環形緩衝區之後，RingBuffer 結構體中的成員`w_pos`和`r_pos`都被初始化為 0。

4. 判斷環形緩衝區是否為空的偽代碼：
```c
if((w_pos - r_pos) == 0)
//判斷語句為真，RingBuffer 為空
```
5. 判斷環形緩衝區是否為滿的偽代碼：
```c
if((w_pos - r_pos)%(1&<&<(N+1)) == (1&<& //判斷語句為真，RingBuffer 為滿

```
6. 生產者進程中的處理邏輯偽代碼：
```c
while(1)
{
if((w_pos - r_pos)%(1&<&<(N+1)) == (1&<& {
sleep(1);
continue;
}

//否則，則將數據填入到環形緩衝區中空閑的單元中
data[w_pos%(1&<&
w_pos++; //將寫入位置向前移動
}
```
7. 消費者進程中的處理邏輯偽代碼：
```c

while(1)
{
if((w_pos - r_pos) == 0)) //緩衝區為空
{
sleep(1);
continue;
}
//否則，從環形緩衝區中讀取數據出來進行處理
process(data[r_pos%(1&<&

r_pos++; //將讀取位置向前移動
}
```
# 疑惑？
如果按照上面提出的條件和處理邏輯，當生產者進程和消費者進程同時運行時，如果不加`互斥鎖`，上面代碼是否會出現`Bug`，或者不確定的狀態？
而且我想了很多遍生產者和消費者的處理邏輯，他們只會在最後執行語句 `w_pos++` 和 `r_pos++` 時改變兩個進程都共享的值，雖然 `w_pos++` 和 `r_pos++` 的操作不是原子操作的，但是好像是不是原子操作都不會對結果產生影響，我就是在這裡思考不清楚！不知道大家對此有什麼看法呢？能否舉出特殊的栗子來描述一下。

請問，多個線程可以讀一個變數，只有一個線程可以對這個變數進行寫，到底要不要加鎖？ - 陳碩的回答 - 知乎

要，特別是滿了或者空了的時候

單讀單寫的隊列， 2個指針用volatile，移動指針之前mfence 下保證寫進去了。

---------------------------------------------------------

多廢話一句，1vN 的單寫多讀的情況，弄N個隊列搞成N個1v1 就可以利用上述的無鎖行為了。

但是就缺少了讀者競爭的行為了（有時候我們需要利用讀者競爭來實現對部分讀者死亡或者臨時繁忙的容災），而變成寫者分配了。所以最好找一個最空的隊列（這時候還不用mfence，畢竟這已經不是關鍵路徑了）來生產數據。很多時候讀者會把消費結果反饋給寫者，也可以使用反饋的速率來決定把數據生產到某個隊列中。

先說結論：

單生產者，單消費者可以不加鎖。

但是你要保證w_pos, r_pos的原子性。

然而保證原子性，要不關中斷，要不加鎖。。。

-------------------------------------------------------

為什麼要保證w_pos, r_pos 的原子性，什麼叫原子性呢？

也就是要保證對w_pos, r_pos 的操作是互斥的，也就是我執行w_pos++，的時候不能有別的進程運行。

你看上去是一條條的語句，其實編程彙編就變成好幾條了。

對於一個++操作

典型的

1. mov mem eax //從內存裝載到寄存器eax

2. add eax 1 //寄存器eax值加1

3. mov eax mem //從寄存器eax裝載會內存

這裡，你可能已經注意到有什麼可能的問題了，如果++不是原子操作，那麼這三條中間是可以插進其他進程執行的。

例如：

生1. mov w_pos eax 從w_pos內存裝載到寄存器eax

-----------------------------------------------執行了一段消費者的代碼

消1. mov r_pos eax 從r_pos內存裝載到寄存器eax

消2. add eax 1 寄存器eax值加1

----------------------------------------------執行了一段生產者代碼

生2. add eax 1 寄存器eax值加1

生3. mov eax w_pos 從寄存器eax裝載會內存 w_pos

-----------------------------------------------執行了一段消費者代碼

消3 mov eax r_pos 從寄存器eax裝載到內存 r_pos

如果CPU是這樣跑的，那麼w_pos r_pos的值已經都錯了，變成相等的，而且都被rewrite成r_pos+2了。

當然這個例子下不影響你的隊列，還是能進能出，只不過你浪費了一部分空間。

當然cpu還可以各種其他跑。。。

於是其實你的pos 已經是薛定諤的pos了，它可能對，可能不對，你需要實在的觀測才知道到底是怎麼跑的。。。

另外w_pos, r_pos 設成volatile並不能保證操作的原子性。

它只是確保編譯器每次都從內存取值而不是用緩存到寄存器的值。

首先,應該把w_pos, r_pos改成unsigned的, 否則溢出就是ub了.

--------------------------------------------------------------------------------------------------------------------

你並沒有說運行在什麼平台上,所以為了在所有平台上無差錯運行,memory barrier還是得有的,畢竟弱內存模型存在各種亂序.boost的那個實現之所以用了memory order,應該也是為了保證在各個平台上跑都能得到正確的結果.

如果你只在強內存模型上跑,使用msvc環境, 用volatile修飾一下pos變數就可以了,msvc的volatile具體語義請看這裡,volatile (C++), 注意,

A write to a volatile object (also known as volatile write) has Release semantics; that is, a reference to a global or static object that occurs before a write to a volatile object in the instruction sequence will occur before that volatile write in the compiled binary.

A read of a volatile object (also known as volatile read) has Acquire semantics; that is, a reference to a global or static object that occurs after a read of volatile memory in the instruction sequence will occur after that volatile read in the compiled binary.

msvc的volatile,是能保證在編譯好的二進位文件中具有read acquire和write release語義, 但是並不能對cpu執行順序做任何保證,鑒於是強內存模型,只允許store load亂序,你的代碼應該也沒有問題.

但是對於此題我依然有個疑問,就是對於32bit的int來訪問,在不跨越cacheline的情況下,是原子操作,但是這個pos是否跨越了cacheline,我並不確定,也不知道intel手冊上是否有說明,還請聚聚們指點一二

以上都是我的個人猜測,不保證準確性

不匿了,被打臉才能記得牢, (:

考慮要不要加鎖的, 一律加, 直到該處成為性能瓶頸, 再考慮其他.

單生產者和單消費者的情況下可以不要鎖，但是memory barrier還是需要的。

題主認為只有一個寫，其他人讀，好像不應該有錯，但是實際上是會出問題的。

考慮下面一個簡單的情況，初始時，data未初始化，flag=0;

寫者:

data=1;

flag=1;

讀者:

while(!flag){};

read data;

這段代碼意思是讀者等到寫者把flag置上後才去讀data的值，那麼讀到的肯定是正確的結果對吧？

但是現代的CPU做了各種優化，並不保證會按照順序讀寫data和flag的值。

所以可能出現先寫flag，再寫data，或者說先讀了data，再讀flag。這種亂序可以保證在單線程情況下一定不會有問題，但是在多線程情況下，讀者可能讀到未初始化的data，需要加memory barrier來保證正確性。

推薦題主可以去看看這個博客 http://www.chongh.wiki/archives/

單個消費者和單個生產者的話可以實現無鎖。

關鍵詞：kfifo。

題主的場景是內存共享的兩個進程，由於不同進程映射的虛地址可能不同，只要避免絕對地址理論上也能實現。

（看到大家都說要加鎖，做這個回答其實我是有點慌的，如有錯誤還請指正）

比如kernel中底kfifo，但單生產者單消費者，可以不加鎖，但是多核上面需要memory order，memory order是鎖么？很難界定吧？

可以不加鎖，但是w_pos和r_pos需要加volatile，或者定義為atomic變數，注意memory_order的設置。否則可能發生編譯器orCPU亂序，比如編譯器可能看到它們在單個線程沒被修改，優化成永遠從寄存器取數據。

針對單生產者和單消費者，相當於是一個寫，另外一個讀，可以不用加鎖。因為隊列可以引入寫指針和讀指針，生產者用寫指針，消費者用讀指針，兩個變數不存在競爭，不需要引入鎖！隊列需要根據寫指針和讀指針判斷空和滿。大多數隊列加鎖是針對多生產者多消費者的情況，使用力度比較小的原子鎖CAS。可以看看dpdk的ring實現。

需要

這個就是內存隊列disruptor的實現原理，可以參考ifeve上的解釋

要，因為你消費者做了寫操作。