一種新的環形緩沖區設計與實現方法

楊凱喬

摘要：針對環形緩沖區傳統實現中判斷“滿”狀態采用保留緩沖區元素或者引入緩沖區有效數據變量導致的緩沖區空間利用率較低問題，本文提出了一種新的不引入計數變量、不存在內存浪費的緩沖區實現方法，其核心思想是借助于讀寫索引之間的關系，使得讀寫索引一直遞增而不清零，直到遞增溢出后自動清零，該讀寫索引的差值就是緩沖區有效數據的個數。基于以上原理給出了不可覆蓋和可覆蓋環形緩沖區的實現過程，緩沖區“滿”狀態時，內存利用率為100%，并且仿真實驗表明代碼執行效率優于傳統方法。

關鍵詞：環形緩沖區；嵌入式系統；“滿”狀態；讀寫索引

中圖分類號：TP212.9 文獻標識碼：A

文章編號：1009-3044（2019）09-0055-04

Abstract： According to problem involving in the ring buffer in the traditional implementation judgment "full" state with retaining an element without introducing cache data or effective number of variables makes utilization rate of the buffer space lower， a new the realization method of a new buffer is proposed in this paper without counter variables introduced and memory waste. The main ideas is based on the relationship between reading and writing index， the read-write index always increase until automatic reset when overflow. The number of valid data in buffer is read and write index difference. Based on the above principle gives the realization process for the ring buffer override or not override. The method of memory utilization rate is 100% when the buffer is in "full" state. The simulation experiment shows that the code execution efficiency is better than the traditional method.

Key words： Ring Buffer； Embedded Systems； "Full" State； Read and write index

環形緩沖區在嵌入式系統軟件設計中是一種很重要的數據結構[1-4]，也可由硬件實現[5][6]，廣泛應用到數據產生速率和數據處理速率不匹配的場合 [7-10]。在設計上一般采用先入先出（FIFO）的方式，可以采用動態分配內存或預先靜態分配內存的方式，由于嵌入式系統的內存資源非常有限，動態內存管理在多數情況下的運行效率和內存利用率都非常低，特別是頻繁進行小容量內存單元的分配釋放，會造成內存碎片，故多采用靜態分配的方式[11] [12]。

用靜態內存分配實現環形緩沖區的傳統方法存在運行效率低以及內存利用率不高的缺點，本文提出了一種新的利用讀寫索引之間的關系，借助于讀寫索引的差值作為緩沖區有效數據個數來實現環形緩沖區狀態判斷，此方法突出了兩個優點即（1）提高內存利用率；（2）提高運行效率。

1 環形緩沖區基本實現方法及分析

環形緩沖區在實現上可以采用數組形式和鏈表形式，鏈表形式利用動態內存管理動態生成每個入隊出隊的元素，形式靈活、結構簡單，但由于涉及內存申請、釋放效率較低；另外一種就是數組形式，數組在物理存儲上是一維的連續線性結構，一次性分配，訪問效率很高，本文針對數組形式的環形緩沖區。數組型環形緩沖區就是用數組定義在內存中開辟所需要的內存空間，然后定義兩個索引用于對緩沖區元素進行讀取，緩沖區有“空”“滿”“非空非滿”三種狀態，在“空”狀態時，可以寫入新的元素，但讀取元素為空，在“滿”狀態時，可以正確讀取元素，寫入元素時有兩種可以選擇的操作，一種是不執行寫入操作，直接返回，一種是覆蓋寫入，覆蓋最先寫入的數據，兩種方式在不同的場合都有應用。在“非空非滿”狀態可以正確進行讀寫操作。環形緩沖區基本操作如圖1所示：

其中緩沖區使用的數組為Buff[QUEUE_SIZE]，QUEUE_SIZE為緩沖區大小，Wi為寫入索引，指向當前要寫入的單元地址，Ri為讀出索引，指向當前要讀出的單元地址。緩沖區為空時，Ri=Wi；當有數據寫入時，將數據寫入下標為Wi的單元Buff[Wi]，然后將Wi遞增，如果Wi的值等于QUEUE_SIZE，Wi重新賦值為0；當有數據需要讀出時，首先判斷緩沖區是否為空，即Ri是否等于Wi，如果不為空，則返回Buff[Ri]，然后將Ri遞增，如果Ri的值等于QUEUE_SIZE，Ri重新賦值為0。運行中如果寫入的速度大于讀出的速度，Wi和Ri之間的距離越來越大，直到Wi追上Ri即Wi=Ri，此時就是緩沖區寫“滿”的狀態，如果再寫入的話，將覆蓋老數據，并且此時Wi=Ri正好也是緩沖區空的條件，如果不做調整讀出操作將判斷緩沖區為“空”而不能正確操作，因此，環狀緩沖區的關鍵核心就是對緩沖區“滿”狀態的判斷和處理[13]。

常用有兩種方法進行“滿”狀態判斷和處理：

方法一：保持一個元素不用。當Wi差一個等于Ri時，判斷緩沖區為滿，不再增加Wi，如圖2所示。此方法處理雖然簡單，但保留了一個元素空間未能使用，存在內存單元浪費問題，從而導致數據存儲空間利用率不高現象。

方法二：引入一個緩存區有效數據個數的變量QLen。每次入隊、出隊操作時首先根據有效數據個數

判斷隊列的狀態，如果QLen

2 讀寫指針直接計算實現狀態判斷

經過對上述實現方法的分析，本文提出一種新的不引入計數變量不存在內存浪費的實現方法，方法的核心就是利用讀寫索引Wi、Ri之間的關系。不同于上述Wi、Ri遞增到QUEUE_SIZE變0的方法，本方法一直遞增Wi、Ri而不清零，直到遞增溢出后自動清零，這樣Wi和Ri之間的距離就可以通過Wi-Ri直接得到，Wi-Ri就是緩沖區有效數據的個數，如果Wi-Ri=0，則隊列為“空”；如果Wi-Ri=QUEUE_SIZE，則隊列為“滿”，如果Wi-Ri

通過上面Wi、Ri的操作獲取了緩沖區有效數據個數，進而就可以得到緩沖區的“空”、“滿”等狀態。另外，知道了Wi、Ri的值，如果想讀寫緩沖區對應的單元，只需要把Wi、Ri的值用QUEUE_SIZE取模運算，即可得到實際訪問數組的下標值。

3 實現過程

根據上述工作原理，給出環形緩沖區的實現過程。定義環形緩沖區存放數組為Buff；緩沖區大小QUEUE_SIZE；緩沖區有效數據個數N，N為無符號整數；Wi寫索引，Ri讀索引，Wi、Ri均為無符號整數，初始化為0；I為實際讀寫索引，I≤QUEUE_SIZE-1；讀寫數據為Data。不可覆蓋環形緩沖區的寫入過程如圖6所示。可覆蓋環形緩沖區的寫入過程如圖7所示。兩種緩沖區讀取操作相同，如圖8所示。

4 性能分析

4.1 內存利用率

假設緩沖區共M個元素，每個元素長度為S字節，保持一個元素不用的方法（以下簡稱方法A）的“滿”狀態利用率為：

引入有效數據個數變量的方法（以下簡稱方法B）的“滿”狀態利用率為：

其中Q為有效數據個數變量所占的內存，最大值為緩沖區大小QUEUE_SIZE，一般為無符號整數所占的字節數。

本文提出的方法的“滿”狀態利用率為：

圖9為方法A在S=1、S=2、S=4、S=8、S=16，方法B在Q=4，和本文方法在緩沖區為1000字節內的“滿”狀態利用率比較，可以看出本文方法的利用率不論緩沖區大小都為100%，方法B效率次之，方法A最差，并且隨著單個元素所占內存越大效率越差。

4.2 代碼效率測試

分別編寫三種方法的C語言實現代碼，采用不可覆蓋策略，用Keil uVision5.14進行編譯，基于STM32F103ZE芯片進行軟件仿真，編譯器優化級別設為最高（-O3）。本文提出的方法讀寫緩沖區函數為SQueue_Push、SQueue_Pop，方法A讀寫函數為SQueue_Push1、SQueue_Pop1，方法B讀寫函數為SQueue_Push2、SQueue_Pop2，編譯后代碼量如圖10所示。可見三種方法代碼量差不多，但本文的方法少幾條指令。

在主函數中分別進行三種方法的單次寫入讀出，重復10萬次，得到執行效率和代碼覆蓋率如圖11所示。

可見在緩沖區未滿、部分代碼未覆蓋的情況下，本文方法的寫入方法效率最高，讀出方法居中，相差1～2ms。在正常使用中，緩沖區占用容量處于動態調整過程，整個效率決定于讀寫效率最差的操作，這樣三種方法的效率為本文效率>B方法>A方法。

為了使代碼覆蓋率達到100%，分別寫緩沖區2048次，然后讀緩沖區2048次，重復100次，測試結果如圖12所示。

可見在綜合測試中，本文寫緩沖方法只用了80.811ms比其他兩種方法快8～30ms左右，而讀緩沖區方法效率居中，B方法最高，A方法差不多。以緩沖區動態讀寫效率最差計算，本文效率>B方法>A方法。

5 結論

本文在環形緩沖區基本實現方法的基礎上，提出了一種新的不引入計數變量、不存在內存浪費的緩沖區實現方法，其核心思想是利用讀寫索引Wi、Ri之間的關系，讓Wi、Ri一直遞增而不清零，直到遞增溢出后自動清零，Wi和Ri之間的距離Wi-Ri就是緩沖區有效數據的個數，這個同樣適用于Wi