樊利軍 田柏林 彭淑梅

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

0 引言

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

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

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

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

環(huán)形緩沖區(qū)是一種首尾相連、先入先出（First In First Out，F(xiàn)IFO）的數(shù)據(jù)隊列結(jié)構(gòu)，數(shù)據(jù)組織簡單，判斷緩沖區(qū)狀態(tài)和讀寫數(shù)據(jù)操作簡單［5］。常用的數(shù)組形式環(huán)形緩沖區(qū)示意圖如圖1所示，先利用數(shù)組定義在內(nèi)存中開辟所需的空間，再定義一個隊頭指針變量（head）指向緩沖區(qū)讀取數(shù)據(jù)的第一個數(shù)據(jù)地址，最后定義一個隊尾指針變量（tail）指向緩沖區(qū)寫數(shù)據(jù)的第一個數(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ù)長度存放在變量size。緩沖區(qū)初始化時隊頭指針變量、隊尾指針變量都指向緩沖區(qū)首地址。讀寫數(shù)據(jù)開始，先判斷緩沖區(qū)的狀態(tài)，如果緩沖區(qū)滿或空則返回相應(yīng)狀態(tài)；讀寫操作后，隊頭、隊尾指針值加1并對N取模修改指針值，然后再判斷緩沖區(qū)狀態(tài)，緩沖區(qū)滿tag＝1，緩沖區(qū)空tag＝0；通過隊頭、隊尾指針差值加上N，再對N取模計算緩沖區(qū)數(shù)據(jù)長度。常用環(huán)形緩沖區(qū)的讀寫數(shù)據(jù)流程如圖2所示。

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

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

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

2.1 修改隊頭、隊尾指針分析

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

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

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

（3）當(dāng)x＞M時，x＝20＋21＋…＋2n，n≥4的部分，采用位與邏輯運算后的值為0；n＜4部分運算結(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的冪時，無論x值為多少，x＆（M－1）＝x%M恒成立，因此快速讀寫環(huán)形緩沖區(qū)大小設(shè)置為M，通過位與邏輯運算修改隊頭、隊尾指針值可得緩沖區(qū)內(nèi)存地址正確的映射。

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

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

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

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

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

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

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

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

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

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

4 實驗與結(jié)果分析

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

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

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

根據(jù)表1、表2中常用環(huán)形緩沖區(qū)和快速讀寫環(huán)形緩沖區(qū)讀寫單字節(jié)平均時間tbav，分別計算兩種緩沖區(qū)讀寫數(shù)據(jù)平均時間差值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é)平均時間和提高效率對比表

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

5 結(jié)論

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