ロックフリーキューの実装
単一プロデューサー・単一コンシューマーのロックフリーキューの設計を順に学びます。
「ロックフリーキューの実装」はCoddyKit上の無料C++ Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC++ Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C++ Academyコースには全4レッスンが含まれています。
ロックフリーキューを使う理由
ミューテックスを使うキューは、高い競合状態ではボトルネックになることがあります。ロックフリーキューを使うと、プロデューサーとコンシューマーを並行して進められます。
SPSC と MPMC
次の2種類があります。
- SPSC — 単一プロデューサー、単一コンシューマー（最も単純で高速）
- MPMC — 複数プロデューサー、複数コンシューマー（最も汎用的）
両端を制御できる場合は、SPSC が自然な選択です。
SPSCリングバッファの概要
2つのインデックスを持つ循環バッファです。head（コンシューマー）とtail（プロデューサー）があり、それぞれが自分のインデックスを更新します。
template <typename T, size_t N>
class SpscQueue {
T buffer_[N];
std::atomic<size_t> head_{0};
std::atomic<size_t> tail_{0};
public:
bool push(const T& v);
bool pop(T& v);
};SPSCへのpush
プロデューサーは空きスロットを確認して書き込み、その後tailを更新して公開します。
bool push(const T& v) {
const size_t t = tail_.load(std::memory_order_relaxed);
const size_t next = (t + 1) % N;
if (next == head_.load(std::memory_order_acquire))
return false; // full
buffer_[t] = v;
tail_.store(next, std::memory_order_release);
return true;
}SPSCからのpop
コンシューマーはデータの有無を確認して読み取り、その後headを更新して公開します。
bool pop(T& v) {
const size_t h = head_.load(std::memory_order_relaxed);
if (h == tail_.load(std::memory_order_acquire))
return false; // empty
v = buffer_[h];
head_.store((h + 1) % N, std::memory_order_release);
return true;
}メモリ順序の組み合わせ
tailへのreleaseストアは、コンシューマー側のtailへのacquireロードと同期します（逆方向も同様です）。適切な順序付けがないと、データへの書き込みがインデックスの更新より後に並べ替えられる可能性があります。
キャッシュラインのパディング
false sharingを避けるには、head_とtail_を別々のキャッシュラインに配置します（通常は64バイト離します）。alignasを使用してください。
alignas(64) std::atomic<size_t> head_{0};
alignas(64) std::atomic<size_t> tail_{0};MPMC：はるかに難しい
複数のプロデューサーまたはコンシューマーがある場合は、通常、共有インデックスに対するCASループなど、追加の調整が必要です。設計には多くの種類があります（Vyukov queue、MS-queue、Hazard-Pointer-basedなど）。
Boost.Lockfree
本番品質のロックフリーキューを実装するのは困難です。独自に実装するのではなく、Boost.LockfreeまたはFollyのProducerConsumerQueueを使用してください。
トレードオフ
ロックフリーキュー：
- 競合時のスループットが高い
- ロックの解放を待たないため、レイテンシが限定される
- 実装とデバッグがはるかに難しい
- メモリ順序のバグは表面化しにくく、発見が困難
ロックフリーコードのテスト
ThreadSanitizer（-fsanitize=thread）を使用してデータ競合を検出します。ランダムなスリープを挿入するストレステストを行い、順序付けのバグを明らかにします。
ミューテックスで十分な場合
ほとんどのアプリケーションでは、ロックフリーキューは必要ありません。まず計測してください。ミューテックスで保護した適切なキューで十分な性能が得られることが多く、特にバッチ処理では効果的です。
確認問題
false sharingとは何ですか。また、なぜhead_とtail_にパディングを追加するのですか？
まとめ
ロックフリーのSPSCキューは、プロデューサーが所有するtailとコンシューマーが所有するheadを持つリングバッファを使用します。acquire/releaseの順序付けを使用し、インデックスをパディングして別々のキャッシュラインに配置してください。MPMCでは、テスト済みのライブラリを優先してください。
よくある質問
「ロックフリーキューの実装」レッスンは無料ですか？
はい。「ロックフリーキューの実装」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C++ Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C++ Academyコースには全4レッスンが含まれています。
「ロックフリーキューの実装」で何を学びますか？
単一プロデューサー・単一コンシューマーのロックフリーキューの設計を順に学びます。 ブラウザで直接実行するハンズオンコードでC++ Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C++ Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC++ Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「ロックフリーキューの実装」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC++ Academyレッスンでコードを書いて実行できますか？
はい。すべてのC++ Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- std::atomicとメモリーオーダー
- 比較交換（CAS）パターン
- ロックフリーキューの実装
- ハザードポインターとABA問題