一種新的環(huán)形緩沖區(qū)設(shè)計(jì)與實(shí)現(xiàn)方法

楊凱喬

摘要：針對(duì)環(huán)形緩沖區(qū)傳統(tǒng)實(shí)現(xiàn)中判斷“滿”狀態(tài)采用保留緩沖區(qū)元素或者引入緩沖區(qū)有效數(shù)據(jù)變量導(dǎo)致的緩沖區(qū)空間利用率較低問題，本文提出了一種新的不引入計(jì)數(shù)變量、不存在內(nèi)存浪費(fèi)的緩沖區(qū)實(shí)現(xiàn)方法，其核心思想是借助于讀寫索引之間的關(guān)系，使得讀寫索引一直遞增而不清零，直到遞增溢出后自動(dòng)清零，該讀寫索引的差值就是緩沖區(qū)有效數(shù)據(jù)的個(gè)數(shù)?；谝陨显斫o出了不可覆蓋和可覆蓋環(huán)形緩沖區(qū)的實(shí)現(xiàn)過程，緩沖區(qū)“滿”狀態(tài)時(shí)，內(nèi)存利用率為100%，并且仿真實(shí)驗(yàn)表明代碼執(zhí)行效率優(yōu)于傳統(tǒng)方法。

關(guān)鍵詞：環(huán)形緩沖區(qū)；嵌入式系統(tǒng)；“滿”狀態(tài)；讀寫索引

中圖分類號(hào)：TP212.9 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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

環(huán)形緩沖區(qū)在嵌入式系統(tǒng)軟件設(shè)計(jì)中是一種很重要的數(shù)據(jù)結(jié)構(gòu)[1-4]，也可由硬件實(shí)現(xiàn)[5][6]，廣泛應(yīng)用到數(shù)據(jù)產(chǎn)生速率和數(shù)據(jù)處理速率不匹配的場(chǎng)合 [7-10]。在設(shè)計(jì)上一般采用先入先出（FIFO）的方式，可以采用動(dòng)態(tài)分配內(nèi)存或預(yù)先靜態(tài)分配內(nèi)存的方式，由于嵌入式系統(tǒng)的內(nèi)存資源非常有限，動(dòng)態(tài)內(nèi)存管理在多數(shù)情況下的運(yùn)行效率和內(nèi)存利用率都非常低，特別是頻繁進(jìn)行小容量?jī)?nèi)存單元的分配釋放，會(huì)造成內(nèi)存碎片，故多采用靜態(tài)分配的方式[11] [12]。

用靜態(tài)內(nèi)存分配實(shí)現(xiàn)環(huán)形緩沖區(qū)的傳統(tǒng)方法存在運(yùn)行效率低以及內(nèi)存利用率不高的缺點(diǎn)，本文提出了一種新的利用讀寫索引之間的關(guān)系，借助于讀寫索引的差值作為緩沖區(qū)有效數(shù)據(jù)個(gè)數(shù)來實(shí)現(xiàn)環(huán)形緩沖區(qū)狀態(tài)判斷，此方法突出了兩個(gè)優(yōu)點(diǎn)即（1）提高內(nèi)存利用率；（2）提高運(yùn)行效率。

1 環(huán)形緩沖區(qū)基本實(shí)現(xiàn)方法及分析

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

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

常用有兩種方法進(jìn)行“滿”狀態(tài)判斷和處理：

方法一：保持一個(gè)元素不用。當(dāng)Wi差一個(gè)等于Ri時(shí)，判斷緩沖區(qū)為滿，不再增加Wi，如圖2所示。此方法處理雖然簡(jiǎn)單，但保留了一個(gè)元素空間未能使用，存在內(nèi)存單元浪費(fèi)問題，從而導(dǎo)致數(shù)據(jù)存儲(chǔ)空間利用率不高現(xiàn)象。

方法二：引入一個(gè)緩存區(qū)有效數(shù)據(jù)個(gè)數(shù)的變量QLen。每次入隊(duì)、出隊(duì)操作時(shí)首先根據(jù)有效數(shù)據(jù)個(gè)數(shù)

判斷隊(duì)列的狀態(tài)，如果QLen

2 讀寫指針直接計(jì)算實(shí)現(xiàn)狀態(tài)判斷

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

通過上面Wi、Ri的操作獲取了緩沖區(qū)有效數(shù)據(jù)個(gè)數(shù)，進(jìn)而就可以得到緩沖區(qū)的“空”、“滿”等狀態(tài)。另外，知道了Wi、Ri的值，如果想讀寫緩沖區(qū)對(duì)應(yīng)的單元，只需要把Wi、Ri的值用QUEUE_SIZE取模運(yùn)算，即可得到實(shí)際訪問數(shù)組的下標(biāo)值。

3 實(shí)現(xiàn)過程

根據(jù)上述工作原理，給出環(huán)形緩沖區(qū)的實(shí)現(xiàn)過程。定義環(huán)形緩沖區(qū)存放數(shù)組為Buff；緩沖區(qū)大小QUEUE_SIZE；緩沖區(qū)有效數(shù)據(jù)個(gè)數(shù)N，N為無符號(hào)整數(shù)；Wi寫索引，Ri讀索引，Wi、Ri均為無符號(hào)整數(shù)，初始化為0；I為實(shí)際讀寫索引，I≤QUEUE_SIZE-1；讀寫數(shù)據(jù)為Data。不可覆蓋環(huán)形緩沖區(qū)的寫入過程如圖6所示?？筛采w環(huán)形緩沖區(qū)的寫入過程如圖7所示。兩種緩沖區(qū)讀取操作相同，如圖8所示。

4 性能分析

4.1 內(nèi)存利用率

假設(shè)緩沖區(qū)共M個(gè)元素，每個(gè)元素長(zhǎng)度為S字節(jié)，保持一個(gè)元素不用的方法（以下簡(jiǎn)稱方法A）的“滿”狀態(tài)利用率為：

引入有效數(shù)據(jù)個(gè)數(shù)變量的方法（以下簡(jiǎn)稱方法B）的“滿”狀態(tài)利用率為：

其中Q為有效數(shù)據(jù)個(gè)數(shù)變量所占的內(nèi)存，最大值為緩沖區(qū)大小QUEUE_SIZE，一般為無符號(hào)整數(shù)所占的字節(jié)數(shù)。

本文提出的方法的“滿”狀態(tài)利用率為：

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

4.2 代碼效率測(cè)試

分別編寫三種方法的C語言實(shí)現(xiàn)代碼，采用不可覆蓋策略，用Keil uVision5.14進(jìn)行編譯，基于STM32F103ZE芯片進(jìn)行軟件仿真，編譯器優(yōu)化級(jí)別設(shè)為最高（-O3）。本文提出的方法讀寫緩沖區(qū)函數(shù)為SQueue_Push、SQueue_Pop，方法A讀寫函數(shù)為SQueue_Push1、SQueue_Pop1，方法B讀寫函數(shù)為SQueue_Push2、SQueue_Pop2，編譯后代碼量如圖10所示?？梢娙N方法代碼量差不多，但本文的方法少幾條指令。

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

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

為了使代碼覆蓋率達(dá)到100%，分別寫緩沖區(qū)2048次，然后讀緩沖區(qū)2048次，重復(fù)100次，測(cè)試結(jié)果如圖12所示。

可見在綜合測(cè)試中，本文寫緩沖方法只用了80.811ms比其他兩種方法快8～30ms左右，而讀緩沖區(qū)方法效率居中，B方法最高，A方法差不多。以緩沖區(qū)動(dòng)態(tài)讀寫效率最差計(jì)算，本文效率>B方法>A方法。

5 結(jié)論

本文在環(huán)形緩沖區(qū)基本實(shí)現(xiàn)方法的基礎(chǔ)上，提出了一種新的不引入計(jì)數(shù)變量、不存在內(nèi)存浪費(fèi)的緩沖區(qū)實(shí)現(xiàn)方法，其核心思想是利用讀寫索引Wi、Ri之間的關(guān)系，讓W(xué)i、Ri一直遞增而不清零，直到遞增溢出后自動(dòng)清零，Wi和Ri之間的距離Wi-Ri就是緩沖區(qū)有效數(shù)據(jù)的個(gè)數(shù)，這個(gè)同樣適用于Wi