はじめに
私が組み込みプログラミングを始めたころ(まだインターネットもなく組み込みマイコンもAKI-80とかZ80系主流で遊んでいた時代)に大学の先輩に教えてもらったテクニックです。今どきのCPU向けではないですが、私自身が古典的かつ重要な要素が含まれており、組み込みプログラミングに引き込まれたきっかけの一つでもありますので、当時を思い出しつつ記事にしてみます。
「ロックフリーなアルゴリズム」についてはこちらのWikipediaの記事がわかりやすいです。
これらのアルゴリズムは、割り込み禁止やミューテックスなどのロックを用いずに、割り込みハンドラやマルチタスク／マルチスレッドなどの異なる非同期な実行コンテキスト間で情報を渡すことを目的としており、今回はその応用内でのFIFOバッファの構成例となります。
近年ではArduinoなどの組み込みプログラミングも手軽に行える環境が増えています。またOSやCPUを自作してみようといったチャレンジングな話も増えてきました。
そういった低レイヤの操作に挑戦する場合、例えば「割り込みハンドラからメインタスクに情報渡したいけど、ロックに割り込み禁止を使うとタイミング制約が満たせない」など事象はあり得るの事で、この手のアルゴリズムを知っていると解決につながる場合もあります。
本記事、シンプルな説明とするために、基本的にシングルプロセッサを想定した組み込みプログラミングとして説明します。
(Cortex-A9 MPCore などのマルチプコア環境の組み込みプログラムだと条件が変わるので注意ください。C言語環境へのポーティングの為、条件を限定して古い機能である volatile を用いていますが、マルチプロセッサを含めた安全な記述の為には C++11以降の std::atomic やC11以降の _Atomic などの機能で記述することが望ましいです)。
なお、少し調べたところ有名なBoostにロックフリーキューというものがあるようです。テンプレートでのアルゴリズム提供のようですのでC++が使える環境であればこちらを使うのがよいかもしれません。こちらはマルチプロセッサもケアされているようです。
(むしろ本記事は「C言語しか使えない環境でもシングルコアマイコンなら比較的簡単に似たことをやる手はありますよ」的な内容です)
コード
組み込みでは、使えるコンパイラがプロセッサごとに非常に多彩です。特に組み込みで使うマイコンでは最低限の環境しか提供されないケースもあるため、ANSI-C89(ANSI X3.159-1989) の文法のみでの記述を余儀なくされることも(昔は)多かったです。
下記は基本となる書き込みと読出しのみのコードです。
- 書き込み側は単一のコンテキストから呼び出す
- 読出し側も単一のコンテキストから呼び出す
の前提となります(つまりリそれぞれはリエントラントではありません)。
(なお、概念説明のための記述で、筆者はコンパイル確認等しておりません。実用には実際の環境に応じたカスタマイズが必要と思います。)
#define BUF_SIZE 16 /* FIFOサイズ + 1 */
volatile int buf[BUF_SIZE]; /* バッファ */
volatile int write_index = 0; /* 書き込み位置 */
volatile int read_index = 0; /* 読出し位置 */
/* 書き込み */
int fifo_write(int data)
{
int next_index;
/* 次の書き込み位置を計算 */
next_index = write_index + 1;
if ( next_index >= BUF_SIZE ) {
next_index = 0;
}
/* 読み出し位置に重なるならバッファフルと判定 */
if ( next_index == read_index ) {
return 0; /* バッファフル */
}
/* バッファに格納 */
buf[write_index] = data;
/* マルチプロセッサの場合はここでメモリバリア命令挿入 */
/* (x86などはwriteの追い越しはないものもあるが、省くと危険) */
/* 書き込み位置を進める */
write_index = next_index;
return 1; /* 書き込み成功 */
}
/* 読み出し */
int fifo_read(int *data)
{
int next_index;
/* 書き込み位置に追い付いていたら空と判定 */
if ( read_index == write_index ) {
return 0; /* バッファが空 */
}
/* マルチプロセッサの場合はここでメモリバリア命令挿入 */
/* (アドレス依存しているので入れ替わることはないがマナーとして) */
/* 取り出し */
*data = buf[read_index];
/* 次の読み出し位置計算 */
next_index = read_index + 1;
if ( next_index >= BUF_SIZE ) {
next_index = 0;
}
read_index = next_index;
return 1; /* 読み出し成功 */
}
ポイントとしては、
- write_index、read_indexはそのCPUで一回で書き込めるサイズ(その処理系でatomic性が期待できるサイズ)でvolatileとしておくこと(C++11以降なら std::atomic を使うべき)
- データバッファもvolatileとしておくこと(C++11以降で std::atomic を使うなら不要かも)
- write_indexは書き込み側のコンテキストでしか書き換えない
- read_indexは読出し側のコンテキストでしか書き換えない
- 実際に格納できるサイズは BUF_SIZE-1 となる
- メモリコヒーレンシが保証できるコンテキスト間で使う(C++11以降なら std::atomic をえば保証される)
などです。
上記の条件下では、各変数を書き換えるオーナーが決まっているので、割り込み禁止や、OSのミューテックス機能などを使わなくても、競合することもなく異なる実行コンテキスト間でデータの受け渡しが可能です。
まず、CPUで一回で書き込めるサイズという点は、読出し側で上位バイトが新しく下位バイトが古い値になっているといったような事がないようにするためです(これをatomic性があるという言い方をします)。8051とかR8とかPICとかAVRなどの8bit/16bit級のCPUの場合は実は注意しておく必要がある項目です。CPUが32bitでもバスの途中で16bitに分割されたりするかもしれません。ここはC89では言語保証のない領域なので、プログラマがケアする必要があります。とはいえ、一般に利用するマイコンでは CPUのワード幅である int (8bit CPUで16bit load/store命令を持たない場合は char)を使っておけば、ほぼ問題になることはないでしょう。
atomic性が確保できれば、write_index や read_index の変数の書き換えは同一コンテキスト内に閉じているので(write-write競合は起こらない)、変数そのものがおかしな値になるような不整合を起こすことはありません。
また、volatile指定しておくことで、コンパイラの最適化が抑止できます。近年のコンパイラは自動でinline展開してくれたりなどのケース含めて非常によく最適化してくれますので、volatileがないと、一度メモリから読みだした値は他のスレッドが書き換えたりしない前提で再利用しようとし、無限ループに入るなどの可能性もあるため指定は必須です。
組み込みプログラミングでは volatile はしばしメモリマップドIOへのアクセスで利用され、volatile 指定した変数へのアクセスに限っては、コンパイラが最適化せずに書いたとおりにアクセスする機械語コードが出力される事が期待できます。
なお、volatile は C++11の atomic とは異なり、非volatile 変数との間のメモリバリアは期待できませんので、アルゴリズム上順序保証が必要な変数にはすべてvolatileをつけておく必要があります。
また読み出す側においては、最新の値を読めたり、古い値を読み出してしまったりがあり得ます(read-write競合)。その場合でも、
- 書き込み側においては読出し側の古い値を読み出しても「バッファがまだ空いていない」という判定に倒れるだけなので安全
- 読出し側においては書き込み側の古い値を読み出しても「まだデータが書かれていない」という判定に倒れるだけなので安全
と言うようにどちらに転んでも不整合が出ないようにアルゴリズムでケアします。
これは実際のデータの格納をバッファサイズより1少ない数を上限にして
- 書き込み側はインデックスを「同じ -> 異なる」の遷移はさせるが逆はしない
- 読出し側はインデックスを「異なる -> 同じ」の遷移はさせるが逆はしない
を守っていることで、いわゆるABA問題を回避していることによって成立しています。
最後のメモリコヒーレンシですが、
- 書き込んだデータの変更が必ず読出し側に伝わる
- 書き込み順序が入れ替わらない(同じアドレスに 1-> 2-> 3 の順で書いたのに、読んだら 2 -> 1 -> 3 の順で読めたりしない)
が満たされる必要があります。
シングルコアのCPU(要するに普通のマイコン)であれば当然問題なく満たされますので無視してかまいません。
これはマルチプロセッサでWrite-Writeでメモリオーダー保証が無かったり、キャッシュ間の整合を取る機能が無かったり(キャッシュスヌーピングがないなど)する場合に発生する問題で、そのようなケースではプログラマが明示的に解決する必要があります。
ソースコード中で「マルチプロセッサの場合はここでメモリバリア命令挿入」と書いている個所でケアする必要があります。
アウトオブオーダー実行に対するメモリバリア命令としてはx86だとsfence命令など、ARMだとDMB命令などありますので調べてみてください。
またキャッシュについてもキャッシュフラッシュやキャッシュクリアなどの機構がキャッシュ階層ごとに用意されていたりしますので組み込み用のSoCを使う場合や、自分でマルチコアCPUを作成する場合は意識しておく必要があります。
注意点
「スレッド間通信でvolatile変数でのやり取りをするのは危険、OSや言語標準の同期機能を使うべき」という話を聞いた人もおられるかもしれません。それはもちろん間違っておらず、同期機構やvolatileは、よく理解して使う必要があります。
一方で、OSの無いような組み込み環境でのプログラミングや、OSの機能を使うとボトルネックになってしまいどうしても踏み込んだ最適化が必要なケースなどもあり、このようなアルゴリズムの存在を知っていること自体は有意義です。
なお、本記事はあくまで、ロックフリーなアルゴリズムについての一例を記載しているもので、どのような環境でも正常に機能することを保証するものではありません。コンパイラ、OS、プロセッサ間のメモリコヒーレンシの保証など、実装先に応じてプログラマが考えておくべき制約はいろいろ考えられます。
おわりに
拙作のRealTime-OSの中でもDPC(Deferred Procedure Call)で使っている技法でして、いろいろな組み込み環境へのOS移植性確保を考えると C89 の言語仕様のみ(volatileしかない)で記述可能な方法の検討が必要となります(C++提供の無い組み込みマイコンも多いので)。
また、組み込みソフトウェアはOS等用いずにスクラッチで記述するケースも多いと思いますが、このようなテクニックを使うと割り込み禁止無しでシステムを組むことも可能になります。
優先度の高い割り込み処理の定時応答の保証が必須となるハードリアルタイムシステムなどでは利用価値のある手法となります。
PCプログラミングの世界では、割り込みハンドラを書くようなケースも少なくなってはきましたが、ひょっとするとマルチスレッドプログラミング等でも性能UPに使えるポイントがあるかもしれません。
余談(ハードウェアでの非同期通信)
FPGAなどで論理回路をプログラムする場合、異なるクロックで動いているハードウェアブロック同士の結線はお互いから「いつ、どのタイミングで変更されるか読めない」という点で、volatile性を持ちます。
非同期回路間ではメタステーブル状態という、新しい値と古い値の間で不安定な信号に陥るケースがあり、これをケアするためのハンドシェーク手法がいくつか存在していますが、ソフトウェアでいうロックフリーなアルゴリズムと非常によく似ております（例えばロックフリーアルゴリズムと同様の論理で 2線式ハンドシェイクなどを組んだりします）。
FPGAなどでも非同期FIFOはよく使われますが、今回のコードととてもよく似たプログラミングが利用可能です。その場合サイズを2のべき乗に限定し、インデックスを1bit余分に設けることでメモリサイズ -1 せずにをフルに使い切るなどの論理回路らしいプログラミングテクニックも存在します。