環形緩衝器

在通信程序中，經常使用環形緩衝器作為數據結構來存放通信中發送和接收的數據。環形緩衝區是一個先進先出的循環緩衝區，可以向通信程序提供對緩衝區的互斥訪問。

圓形緩衝區的一個有用特性是：當一個數據元素被用掉后，其餘數據元素不需要移動其存儲位置。相反，一個非圓形緩衝區（例如一個普通的隊列）在用掉一個數據元素后，其餘數據元素需要向前搬移。換句話說，圓形緩衝區適合實現先進先出緩衝區，而非圓形緩衝區適合後進先出緩衝區。

圓形緩衝區適合於事先明確了緩衝區的最大容量的情形。擴展一個圓形緩衝區的容量，需要搬移其中的數據。因此一個緩衝區如果需要經常調整其容量，用鏈表實現更為合適。

寫操作覆蓋圓形緩衝區中未被處理的數據在某些情況下是允許的。特別是在多媒體處理時。例如，音頻的生產者可以覆蓋掉音效卡尚未來得及處理的音頻數據。

一個圓形緩衝區最初為空並有預定的長度。例如，這是一個具有七個元素空間的圓形緩衝區，其中底部的單線與箭頭表示“頭尾相接”形成一個圓形地址空間：

假定1被寫入緩衝區中部（對於圓形緩衝區來說，最初的寫入位置在哪裡是無關緊要的）：

再寫入2個元素，分別是 — 被追加在1之後：

如果兩個元素被處理，那麼是緩衝區中最老的兩個元素被移除。在本例中，被移除，緩衝區中只剩下3:

如果緩衝區中有7個元素，則是滿的：

如果緩衝區是滿的，又要寫入新的數據，一種策略是覆蓋掉最老的數據。此例中，2個新數據— — 寫入，覆蓋了:

也可以採取其他策略，禁止覆蓋緩衝區的數據，採取返回一個錯誤碼或者拋出異常。最終，如果從緩衝區中移除2個數據，不是 而是 。因為 已經覆蓋了：

由於計算機內存是線性地址空間，因此圓形緩衝區需要特別的設計才可以從邏輯上實現。

一般的，圓形緩衝區需要4個指針：

• 在內存中實際開始位置；

• 在內存中實際結束位置，也可以用緩衝區長度代替；

• 存儲在緩衝區中的有效數據的開始位置（讀指針）；

• 存儲在緩衝區中的有效數據的結尾位置（寫指針）。

讀指針、寫指針可以用整型值來表示。下例為一個未滿的緩衝區的讀寫指針：

下例為一個滿的緩衝區的讀寫指針：

緩衝區是滿、或是空，都有可能出現讀指針與寫指針指向同一位置：

有多種策略用於檢測緩衝區是滿、或是空.

緩衝區中總是有一個存儲單元保持未使用狀態。緩衝區最多存入個數據。如果讀寫指針指向同一位置，則緩衝區為空。如果寫指針位於讀指針的相鄰后一個位置，則緩衝區為滿。這種策略的優點是簡單、魯棒；缺點是語義上實際可存數據量與緩衝區容量不一致，測試緩衝區是否滿需要做取餘數計算。

這種策略不使用顯式的寫指針，而是保持著緩衝區內存儲的數據的計數。因此測試緩衝區是空是滿非常簡單；對性能影響可以忽略。缺點是讀寫操作都需要修改這個存儲數據計數，對於多線程訪問緩衝區需要併發控制。

緩衝區的長度如果是n，邏輯地址空間則為至；那麼，規定至為鏡像邏輯地址空間。本策略規定讀寫指針的地址空間為至，其中低半部分對應於常規的邏輯地址空間，高半部分對應於鏡像邏輯地址空間。當指針值大於等於時，使其折返（wrapped）到。使用一位表示寫指針或讀指針是否進入了虛擬的鏡像存儲區：置位表示進入，不置位表示沒進入還在基本存儲區。

在讀寫指針的值相同情況下，如果二者的指示位相同，說明緩衝區為空；如果二者的指示位不同，說明緩衝區為滿。這種方法優點是測試緩衝區滿/空很簡單；不需要做取餘數操作；讀寫線程可以分別設計專用演演算法策略，能實現精緻的併發控制。缺點是讀寫指針各需要額外的一位作為指示位。

如果緩衝區長度是2的冪，則本方法可以省略鏡像指示位。如果讀寫指針的值相等，則緩衝區為空；如果讀寫指針相差n，則緩衝區為滿，這可以用條件表達式（寫指針 == (讀指針 異或 緩衝區長度)）來判斷。

用兩個有符號整型變數分別保存寫入、讀出緩衝區的數據數量。其差值就是緩衝區中尚未被處理的有效數據的數量。這種方法的優點是讀線程、寫線程互不干擾；缺點是需要額外兩個變數。

使用一位記錄最後一次操作是讀還是寫。讀寫指針值相等情況下，如果最後一次操作為寫入，那麼緩衝區是滿的；如果最後一次操作為讀出，那麼緩衝區是空。這種策略的缺點是讀寫操作共享一個標誌位，多線程時需要併發控制。

在Linux內核文件kfifo.h和kfifo.c中，定義了一個先進先出圓形緩衝區實現。如果只有一個讀線程、一個寫線程，二者沒有共享的被修改的控制變數，那麼可以證明這種情況下不需要併發控制。kfifo就滿足上述條件。kfifo要求緩衝區長度必須為2的冪。讀、寫指針分別是無符號整型變數。把讀寫指針變換為緩衝區內的索引值，僅需要“按位與”操作：（指針值 按位與（緩衝區長度-1））。這避免了計算代價高昂的“求余”操作。且下述關係總是成立：讀指針 + 緩衝區存儲的數據長度 == 寫指針

即使在寫指針達到了無符號整型的上界，上溢出后寫指針的值小於讀指針的值，上述關係仍然保持成立（這是因為無符號整型加法的性質）。 kfifo的寫操作，首先計算緩衝區中當前可寫入存儲空間的數據長度：len = min{待寫入數據長度, 緩衝區長度 - （寫指針 - 讀指針）}然後，分兩段寫入數據。第一段是從寫指針開始向緩衝區末尾方向；第二段是從緩衝區起始處寫入餘下的可寫入數據，這部分可能數據長度為0即並無實際數據寫入。