樊利軍 田柏林 彭淑梅

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

0 引言

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

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

本文提出一種基于數組形式的環(huán)形緩沖區(qū)數據快速讀寫方法，通過位與邏輯運算修改讀寫指針值，利用讀寫指針的差值作為緩沖區(qū)有效數據個數來實現(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）的數據隊列結構，數據組織簡單，判斷緩沖區(qū)狀態(tài)和讀寫數據操作簡單［5］。常用的數組形式環(huán)形緩沖區(qū)示意圖如圖1所示，先利用數組定義在內存中開辟所需的空間，再定義一個隊頭指針變量（head）指向緩沖區(qū)讀取數據的第一個數據地址，最后定義一個隊尾指針變量（tail）指向緩沖區(qū)寫數據的第一個數據地址。

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

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

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

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

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

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

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

（1）當x＜M時，x＆（M－1）＝x＆15＝x，x%M＝x%16＝x，即x＆（M－1）＝x%M。

（2）當x＝M時，x＆（M－1）＝x＆15＝0，x%M＝x%16＝0，即x＆（M－1）＝x%M。

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

假設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。

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

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

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

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

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

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

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

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

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

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

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

4 實驗與結果分析

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

測試實驗中常用環(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讀寫數據各5次，記錄5次程序運行時間ti，并計算平均值tav和讀寫單字節(jié)平均值tbav，如表1、表2所示。

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

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

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

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

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

5 結論

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