リングバッファー
読み：リングバッファー
外語：ring buffer
バッファーを、(概念上)環状で管理、運用する制御手法。キュー(FIFO)の代表的な実装方法である。
概要
リングバッファーは、ある一定の領域のメモリーを確保しておき、その範囲内を「環」であるように扱うものである。つまり、末尾と先頭が繋がった環状構造とみなした配列である。
キューに格納されたデータは、次の二つの変数で管理する。
- head: キューの先頭要素を指す変数
- tail: キューの末尾要素を指す変数
実装によっては、headをwriteやw、tailをreadやrと、読み書きの動作面から命名する実装もあり、以降は分かり易いように、headを書き込み(W)、tailを読み出し(R)としてこれを説明する。
例えばこれを時計回り(右回り)するものと仮定し、ここに「読み出し用のポインター」と「書き込み用のポインター」を変数として用意する。
リングバッファーに書き込むと、書き込み用のポインターが進む。読み出し用のポインターは、書き込み用のポインターの位置まで読み出すことができる。また書き込み用のポインターは、読み出し用のポインターを通り越すことは出来ない。
特徴
用途
例えば、受信の機能を持った通信プログラムを想定する。
この時、例えばコマンドが一文ずつしか受信できない、つまりコマンドの処理が全て終わるまで次が受信できないのでは、高速処理が実現できない上に不便である。
電文の送信側から見ると、電文を送ったあと、その返信を受けるまで次の電文を送信出来ないことになり、処理が滞る。
理想的には、送受信されたデータは逐一バッファーに格納され、処理ごとに順番にそのバッファーから取り出せることが望ましい。さらに、一度読み出したデータは不要なので破棄され制御的に無効になることが求められ、また当然の要求として制御は高速簡潔でないとならない。
この目的を達成するため、リングバッファーが発案された。
技術
バッファーは固定長で用意され、更に「読み出し用のポインター変数」と「書き込み用のポインター変数」を用意する。
書き込みは、現在の書き込みポインターからバッファーに書きはじめる。まず、書く前に次の書き込みポインターを求める。それが読み出しポインターと一致する場合は、既にバッファーは満タンであるので、書くことができない。一致しない場合はバッファーに余裕があるので、現在のポインターに書いたあと、書き込みポインターを、予め求めて置いた次の書き込みポインターとする。
読み出しは、読み出しポインターから順次読み出す。書き込みポインターと一致した時点で全てを読み終えたとして終了する。
書き込みポインター、読み出しポインター、いずれもバッファーの最後まで至った場合は、先頭のアドレスに戻す。これが、概念的にあたかも環であるかのようにして処理されるゆえんである。
かくして、「実際の領域」と「二つのポインター変数」のみで、決して溢れることの無いバッファー管理が実現できる。処理が簡単であるため、頻繁に利用されている。
再検索