樊利軍 田柏林 彭淑梅

（1.北京工業(yè)職業(yè)技術(shù)學(xué)院信息工程學(xué)院，北京 100042；2.北京市煤炭礦用機(jī)電設(shè)備技術(shù)開發(fā)公司，北京 100042；3.北京工業(yè)職業(yè)技術(shù)學(xué)院基礎(chǔ)教育學(xué)院，北京 100042）

0 引言

環(huán)形緩沖區(qū)在嵌入式系統(tǒng)軟件設(shè)計(jì)中是一種很重要的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用在數(shù)據(jù)采集、數(shù)字通信中數(shù)據(jù)產(chǎn)生率和數(shù)據(jù)處理率存在差異的場(chǎng)合。在實(shí)時(shí)性要求較高的嵌入式應(yīng)用場(chǎng)合，由于內(nèi)存資源非常有限，如果系統(tǒng)在很短的時(shí)間內(nèi)獲取大量數(shù)據(jù)且不允許數(shù)據(jù)丟失，采用環(huán)形緩沖區(qū)是一種理想的方法［1］。

目前常用的環(huán)形緩沖區(qū)采用鏈表形式和數(shù)組形式實(shí)現(xiàn)。鏈表形式采用動(dòng)態(tài)內(nèi)存管理方式，在讀寫數(shù)據(jù)時(shí)頻繁進(jìn)行內(nèi)存申請(qǐng)和釋放，形成內(nèi)存碎片，內(nèi)存使用效率低；數(shù)組形式采用靜態(tài)內(nèi)存管理方式，在讀寫數(shù)據(jù)以及判斷緩沖區(qū)狀態(tài)時(shí)需要進(jìn)行取模操作，存在代碼運(yùn)行效率低的缺點(diǎn)。丁遠(yuǎn)［2］研究了單鏈表環(huán)形數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)既具有鏈表存儲(chǔ)動(dòng)態(tài)申請(qǐng)內(nèi)存實(shí)現(xiàn)緩沖區(qū)動(dòng)態(tài)擴(kuò)展的優(yōu)點(diǎn)，又避免了頻繁申請(qǐng)釋放內(nèi)存帶來的內(nèi)存碎片。李為民［3］提出通過設(shè)置數(shù)組形式緩沖區(qū)大小為2的冪，可以快速進(jìn)行緩沖區(qū)讀寫操作。楊凱喬［4］提出利用數(shù)組形式緩沖區(qū)讀寫指針之間的關(guān)系，借助讀寫指針的差值作為緩沖區(qū)有效數(shù)據(jù)個(gè)數(shù)實(shí)現(xiàn)緩沖區(qū)狀態(tài)判斷，提高了內(nèi)存利用率和運(yùn)行效率。

本文提出一種基于數(shù)組形式的環(huán)形緩沖區(qū)數(shù)據(jù)快速讀寫方法，通過位與邏輯運(yùn)算修改讀寫指針值，利用讀寫指針的差值作為緩沖區(qū)有效數(shù)據(jù)個(gè)數(shù)來實(shí)現(xiàn)環(huán)形緩沖區(qū)狀態(tài)判斷。此方法突出的優(yōu)點(diǎn)是可以提高系統(tǒng)讀寫緩沖區(qū)代碼的運(yùn)行效率。

1 常用環(huán)形緩沖區(qū)實(shí)現(xiàn)方法

環(huán)形緩沖區(qū)是一種首尾相連、先入先出（First In First Out，F(xiàn)IFO）的數(shù)據(jù)隊(duì)列結(jié)構(gòu)，數(shù)據(jù)組織簡(jiǎn)單，判斷緩沖區(qū)狀態(tài)和讀寫數(shù)據(jù)操作簡(jiǎn)單［5］。常用的數(shù)組形式環(huán)形緩沖區(qū)示意圖如圖1所示，先利用數(shù)組定義在內(nèi)存中開辟所需的空間，再定義一個(gè)隊(duì)頭指針變量（head）指向緩沖區(qū)讀取數(shù)據(jù)的第一個(gè)數(shù)據(jù)地址，最后定義一個(gè)隊(duì)尾指針變量（tail）指向緩沖區(qū)寫數(shù)據(jù)的第一個(gè)數(shù)據(jù)地址。

圖1 數(shù)組形式環(huán)形緩沖區(qū)示意圖

常用環(huán)形緩沖區(qū)設(shè)置緩沖區(qū)的大小為N，緩沖區(qū)存放數(shù)組ring［N］，緩沖區(qū)狀態(tài)標(biāo)記tag，緩沖區(qū)數(shù)據(jù)長(zhǎng)度存放在變量size。緩沖區(qū)初始化時(shí)隊(duì)頭指針變量、隊(duì)尾指針變量都指向緩沖區(qū)首地址。讀寫數(shù)據(jù)開始，先判斷緩沖區(qū)的狀態(tài)，如果緩沖區(qū)滿或空則返回相應(yīng)狀態(tài)；讀寫操作后，隊(duì)頭、隊(duì)尾指針值加1并對(duì)N取模修改指針值，然后再判斷緩沖區(qū)狀態(tài)，緩沖區(qū)滿tag＝1，緩沖區(qū)空tag＝0；通過隊(duì)頭、隊(duì)尾指針差值加上N，再對(duì)N取模計(jì)算緩沖區(qū)數(shù)據(jù)長(zhǎng)度。常用環(huán)形緩沖區(qū)的讀寫數(shù)據(jù)流程如圖2所示。

圖2 常用環(huán)形緩沖區(qū)讀寫數(shù)據(jù)流程圖

2 快速讀寫環(huán)形緩沖區(qū)的設(shè)計(jì)原理

快速讀寫環(huán)形緩沖區(qū)設(shè)計(jì)時(shí)，設(shè)置緩沖區(qū)大小為M，其中M＝2n且2n－1＜N＜2n。修改隊(duì)頭、隊(duì)尾指針時(shí)，通過指針值和M－1進(jìn)行位與邏輯運(yùn)算實(shí)現(xiàn)，以隊(duì)頭、隊(duì)尾指針差值作為緩沖區(qū)數(shù)據(jù)長(zhǎng)度。把常用環(huán)形緩沖區(qū)實(shí)現(xiàn)過程的取模運(yùn)算，用位與邏輯運(yùn)算和差值計(jì)算替代，可以提高程序運(yùn)行效率。

2.1 修改隊(duì)頭、隊(duì)尾指針分析

以M＝16＝24為例，即M－1＝15，設(shè)隊(duì)頭或隊(duì)尾指針值為x，以下分三種情況，通過位與邏輯運(yùn)算和直接取模運(yùn)算結(jié)果對(duì)比，驗(yàn)證位與邏輯運(yùn)算修改緩沖區(qū)隊(duì)頭、隊(duì)尾指針在環(huán)形緩沖區(qū)內(nèi)存映射的正確性。

（1）當(dāng)x＜M時(shí)，x＆（M－1）＝x＆15＝x，x%M＝x%16＝x，即x＆（M－1）＝x%M。

（2）當(dāng)x＝M時(shí)，x＆（M－1）＝x＆15＝0，x%M＝x%16＝0，即x＆（M－1）＝x%M。

（3）當(dāng)x＞M時(shí)，x＝20＋21＋…＋2n，n≥4的部分，采用位與邏輯運(yùn)算后的值為0；n＜4部分運(yùn)算結(jié)果同（1），即x＆（M－1）＝x%M。

假設(shè)x＝39，則x＝1＋2＋4＋32 ＝20＋21＋22＋25，x＆（M－1）＝39＆15＝7，x%M＝39%16＝7，即x＆（M－1）＝x%M。

由上可知，當(dāng)緩沖區(qū)大小M為2的冪時(shí)，無論x值為多少，x＆（M－1）＝x%M恒成立，因此快速讀寫環(huán)形緩沖區(qū)大小設(shè)置為M，通過位與邏輯運(yùn)算修改隊(duì)頭、隊(duì)尾指針值可得緩沖區(qū)內(nèi)存地址正確的映射。

2.2 緩沖區(qū)數(shù)據(jù)長(zhǎng)度計(jì)算分析

在快速讀寫環(huán)形緩沖區(qū)設(shè)計(jì)中需要定義隊(duì)頭、隊(duì)尾指針為無符號(hào)整型。當(dāng)隊(duì)頭或隊(duì)尾指針值為最大值M時(shí)，如果緩沖區(qū)再進(jìn)行讀或?qū)懖僮?，?duì)頭或隊(duì)尾指針值需要加1，會(huì)出現(xiàn)溢出情況，即M＋1＝0。根據(jù)緩沖區(qū)讀寫數(shù)據(jù)的操作，緩沖區(qū)中的數(shù)據(jù)總是維持在［*head，*tail）這個(gè)區(qū)間中，由于溢出可能存在，這個(gè)區(qū)間有三種情況。

（1）*head和*tail值都沒有溢出，緩沖區(qū)中數(shù)據(jù)長(zhǎng)度size＝*tail－*head。

（2）*head值沒溢出，*tail值溢出，數(shù)據(jù)長(zhǎng)度size＝M－*head＋1＋*tail＝*tail－*head＋M＋1＝*tail－*head。

（3）*head值和*tail值都溢出，數(shù)據(jù)長(zhǎng)度size＝*tail－*head。

根據(jù)上述分析，size＝*tail－*head總是表示環(huán)形緩沖區(qū)中數(shù)據(jù)的長(zhǎng)度。

3 快速讀寫環(huán)形緩沖區(qū)實(shí)現(xiàn)方法

在快速讀寫環(huán)形緩沖區(qū)實(shí)現(xiàn)方法中設(shè)置緩沖區(qū)大小為M，緩沖區(qū)存放數(shù)組ring［M］，隊(duì)頭和隊(duì)尾指針值為無符號(hào)整型，其余的定義與常用環(huán)形緩沖區(qū)相同?？焖僮x寫環(huán)形緩沖區(qū)的讀寫數(shù)據(jù)流程如圖3所示。

圖3 快速讀寫環(huán)形緩沖區(qū)讀寫數(shù)據(jù)流程圖

快速讀寫環(huán)形緩沖區(qū)在讀寫數(shù)據(jù)時(shí)，首先判斷緩沖區(qū)的狀態(tài)，緩沖區(qū)滿或空則返回相應(yīng)狀態(tài)；然后讀緩沖區(qū)數(shù)據(jù)到相應(yīng)變量或?qū)憯?shù)據(jù)到緩沖區(qū)中；讀寫操作后，隊(duì)頭、隊(duì)尾指針值加1和M－1進(jìn)行位與邏輯運(yùn)算修改指針值；再次判斷緩沖區(qū)狀態(tài)，緩沖區(qū)滿tag＝1，緩沖區(qū)空tag＝0；通過隊(duì)頭、隊(duì)尾指針差值計(jì)算緩沖區(qū)數(shù)據(jù)長(zhǎng)度。

4 實(shí)驗(yàn)與結(jié)果分析

用C語言編寫常用環(huán)形緩沖區(qū)、快速讀寫環(huán)形緩沖區(qū)兩種方法的單字節(jié)讀寫數(shù)據(jù)程序代碼，分別測(cè)量讀寫緩沖區(qū)數(shù)據(jù)運(yùn)行的時(shí)間。為了避免多字節(jié)連續(xù)寫緩沖區(qū)呈現(xiàn)滿狀態(tài)而使程序終止，在測(cè)試程序中寫緩沖區(qū)采用數(shù)據(jù)覆蓋方式。測(cè)試實(shí)驗(yàn)方案基于STM32F103VE6芯片，采用Keil uVision5.33進(jìn)行代碼編譯，J－Link仿真器的串行調(diào)試（Serial Wire Debug，SWD）模式進(jìn)行仿真調(diào)試運(yùn)行，仿真調(diào)試中CPU運(yùn)行主頻設(shè)置為72 MHz，利用Keil軟件調(diào)試中的時(shí)間計(jì)時(shí)器進(jìn)行程序運(yùn)行時(shí)間測(cè)量。

測(cè)試實(shí)驗(yàn)中常用環(huán)形緩沖區(qū)的大小為200 B，即N＝200；快速讀寫環(huán)形緩沖區(qū)的大小為256 B，即M＝256。兩種環(huán)形緩沖區(qū)分別按150，250，500，1 000，2 000 B讀寫數(shù)據(jù)各5次，記錄5次程序運(yùn)行時(shí)間ti，并計(jì)算平均值tav和讀寫單字節(jié)平均值tbav，如表1、表2所示。

表1 兩種環(huán)形緩沖區(qū)讀數(shù)據(jù)時(shí)間表

表2 兩種環(huán)形緩沖區(qū)寫數(shù)據(jù)時(shí)間表

根據(jù)表1、表2中常用環(huán)形緩沖區(qū)和快速讀寫環(huán)形緩沖區(qū)讀寫單字節(jié)平均時(shí)間tbav，分別計(jì)算兩種緩沖區(qū)讀寫數(shù)據(jù)平均時(shí)間差值tTD和提高效率。如表3、表4所示，快速讀寫環(huán)形緩沖區(qū)在讀數(shù)據(jù)比常用環(huán)形緩沖區(qū)提高效率約22%；在緩沖區(qū)狀態(tài)未滿情況下，寫入數(shù)據(jù)提高效率約14%，在緩沖區(qū)滿且數(shù)據(jù)覆蓋狀態(tài)下，寫入數(shù)據(jù)提高效率約10.5%。

表3 兩種環(huán)形緩沖區(qū)讀單字節(jié)平均時(shí)間和提高效率對(duì)比表

表4 兩種環(huán)形緩沖區(qū)寫單字節(jié)平均時(shí)間和提高效率對(duì)比表

5 結(jié)論

本文在常用環(huán)形緩沖區(qū)實(shí)現(xiàn)方法的基礎(chǔ)上，提出了一種快速讀寫環(huán)形緩沖區(qū)的方法，實(shí)現(xiàn)原理是設(shè)置緩沖區(qū)大小M為2的冪，通過指針值和M－1位與邏輯運(yùn)算修改隊(duì)頭、隊(duì)尾指針，直接利用隊(duì)頭、隊(duì)尾指針差值計(jì)算緩沖區(qū)數(shù)據(jù)長(zhǎng)度和判斷緩沖區(qū)狀態(tài)。把常用環(huán)形緩沖區(qū)實(shí)現(xiàn)過程的取模運(yùn)算，用位與邏輯運(yùn)算和差值計(jì)算替代，通過仿真測(cè)試驗(yàn)證了這種快速讀寫環(huán)形緩沖區(qū)的方法可以顯著提高緩沖區(qū)讀寫效率，可應(yīng)用到需要環(huán)形緩沖區(qū)的各種嵌入式系統(tǒng)中。