嵌入式系統環形緩沖區快速讀寫方法的設計與實現

樊利軍 田柏林 彭淑梅

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

0 引言

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

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

本文提出一種基于數組形式的環形緩沖區數據快速讀寫方法，通過位與邏輯運算修改讀寫指針值，利用讀寫指針的差值作為緩沖區有效數據個數來實現環形緩沖區狀態判斷。此方法突出的優點是可以提高系統讀寫緩沖區代碼的運行效率。

1 常用環形緩沖區實現方法

環形緩沖區是一種首尾相連、先入先出（First In First Out，FIFO）的數據隊列結構，數據組織簡單，判斷緩沖區狀態和讀寫數據操作簡單［5］。常用的數組形式環形緩沖區示意圖如圖1所示，先利用數組定義在內存中開辟所需的空間，再定義一個隊頭指針變量（head）指向緩沖區讀取數據的第一個數據地址，最后定義一個隊尾指針變量（tail）指向緩沖區寫數據的第一個數據地址。

圖1 數組形式環形緩沖區示意圖

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

圖2 常用環形緩沖區讀寫數據流程圖

2 快速讀寫環形緩沖區的設計原理

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

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

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

（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。

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

2.2 緩沖區數據長度計算分析

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

（1）*head和*tail值都沒有溢出，緩沖區中數據長度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總是表示環形緩沖區中數據的長度。

3 快速讀寫環形緩沖區實現方法

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

圖3 快速讀寫環形緩沖區讀寫數據流程圖

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

4 實驗與結果分析

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

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

表1 兩種環形緩沖區讀數據時間表

表2 兩種環形緩沖區寫數據時間表

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

表3 兩種環形緩沖區讀單字節平均時間和提高效率對比表

表4 兩種環形緩沖區寫單字節平均時間和提高效率對比表

5 結論

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