リングバッファ

バッファの実体はただの配列で、ポインタが末尾に達すると先頭に戻る。メモリ確保もデータの移動も不要で、出し入れは定数時間。そのためファームウェアでは定番の選択肢となっており、UART割り込みが文字を放り込み、メインループが自分のペースでそれを取り出す。

生産者と消費者がちょうど一つずつなら、ロックは要らない。割り込みは書き込み位置だけ、ループは読み出し位置だけを触るからだ。サイズは通常2の冪にして、折り返しを除算ではなく安価なビットマスクで済ませる。残る問題は、満杯と空の区別がつかないという永遠の曖昧さで、どちらもポインタが等しく見える。これは1スロットを犠牲にするか、別にカウンタを持つことで解決される。同じ発想はLinuxのネットワークドライバ、オーディオAPI、io_uringにも使われている。