經典同步問題與並行程式設計

有限緩衝區(bounded buffer)

有限緩衝區就是生產者-消費者問題核心的那個共享架子:一個容量上限固定的佇列。「有限」是關鍵詞——它最多只能容納 N 個項目,絕不更多。相對的是無限緩衝區,需要多大就長多大。這個上限不是需要道歉的限制,而是一項優點:它保證即使生產者跑得比消費者快,記憶體用量也不會爆掉;它還提供天然的背壓(backpressure)——緩衝區滿時,生產者被迫等待,速度自動降到與消費者一致。

常見的實作是環形(ring)緩衝區:一個 N 格的固定陣列,配兩個索引——in 指向下一個寫入的位置,out 指向下一個讀取的位置,各自以模 N 前進,繞過陣列尾端再回到開頭。當 in 等於 out 時為空;當 in 前進會撞上 out 時為滿(通常另外維護一個計數來判斷)。放入就是寫 buffer[in] = item 並做 in = (in + 1) % N;取出就是讀 buffer[out] 並做 out = (out + 1) % N。沒有任何資料需要搬移,陣列就地重複使用,因此快速且對快取友善。

資料結構本身並非執行緒安全的——它不過是一個陣列加兩個整數。唯有搭配同步,它才成為正確的並行元件:用計數號誌或條件變數在滿/空時阻塞,用互斥鎖讓每次放入與取出成為不可分割的動作。許多系統都提供現成版本(Java 的 ArrayBlockingQueue、Go 的有緩衝通道、音訊驅動程式與網路卡裡的環形緩衝區)。誠實的提醒:上限 N 是個真正的調校決定——太小,生產者會無謂地卡住;太大,既浪費記憶體,又會掩蓋背壓本該暴露的突發行為。

一個 N = 8 格的環形緩衝區:in = 5、out = 2 表示有 3 個項目待處理(索引 2、3、4)。消費者取走一個後:out 變為 3。生產者放入一個後:in 變為 6。

索引以模 N 環繞,陣列因而像繞圈一樣重複使用——沒有任何元素被搬動。

經典的差一錯誤:若用 in == out 同時代表「空」與「滿」,兩者就無法區分。常見的解法是另外維護一個計數,或永遠空出一格(於是滿的緩衝區只放 N − 1 個項目)。

又称
有界緩衝區ring buffercircular buffer環形緩衝區