原子性と順序を別々に確認する
共有データを安全に扱うには、一回の更新が途中で分かれないことだけでなく、別のデータへのアクセスがどの順序関係で結ばれるかも必要です。ここではC++のメモリモデルを使います。複数スレッドが同じ非原子的な領域へ競合するアクセスを行い、少なくとも一つが書き込みで、必要な同期関係がなければデータ競合となります。いつも同じ値が観測できたという実行結果は、言語上の保証の代わりにはなりません。まず共有する変数、書き手、読み手、寿命を列挙し、それぞれの読み書きがどの規則で許されるのかを説明します。
一度だけ公開するデータを考える
生産者が整数dataへ42を書き、その後で原子的なreadyへtrueをrelease storeします。消費者はreadyをacquire loadで読み、対応するtrueを観測してからdataを読みます。この公開と取得の間の同期によって、先行するdataへの書き込みが読み手へ渡ります。ここでreadyは初期値falseから一回だけtrueへ変わるものとします。dataを書き換えるのは生産者の一回だけで、読み取り中に次の更新はありません。例の小ささは欠点ではなく、どの条件が安全性を支えているかを確認するためのものです。
取得した値がどの公開に対応するか
acquireという指定を付けただけで、任意のreleaseと同期するわけではありません。同じ原子的オブジェクトに対する、対応する公開から値を読んだことなど、規格が定める関係が必要です。一度trueになったreadyを次のデータにも使い回すと、読み手が古いtrueを見て新しい書き込みと競合する場合があります。繰り返し通信には世代番号、所有権の受け渡し、キューの空き領域の管理などを含む別の設計が要ります。フラグをfalseへ戻す一行を足せば完成すると考えず、各世代のデータを書ける主体と読める期間を図にして確かめます。
relaxedとvolatileの役割を混ぜない
relaxedな原子的操作でも、その原子的オブジェクト自体の読み書きは原子的です。一方、それだけで別の非原子的データを公開する同期関係ができるわけではありません。独立した統計カウンタならrelaxedが用途に合う場合がありますが、値を合図にして別の構造を読むなら、その読み方を含めた証明が必要です。C++のvolatileも、一般的なスレッド間同期を作る指定ではありません。装置アクセスなどに関する実装上の用途と、スレッド間のメモリ順序を区別します。高速そうな指定を先に選ぶより、必要な関係から指定を決めます。
CASの成功と失敗を処理する
compare-and-swapは、現在値が期待値と一致するときにだけ置き換える原子的操作です。C++のcompare_exchangeでは、失敗すると期待値の変数が観測した値へ更新されるため、再試行で使う新しい値も見直します。weak版は値が一致しても失敗する場合があり、適切なループで使います。成功時と失敗時に許されるメモリ順序にも制約があります。期待する値の比較と交換は一つの操作でも、その周囲で作るノード、例外、割当て、参照先のアクセスまで自動的に原子的になるわけではありません。失敗時に何を捨て、何を再利用するかも実装の一部です。
ロックフリーは全員がすぐ終わる保証ではない
ロックフリーの進行保証は、一般に全体として操作が進むことを求めます。あるスレッドが何度もCASに負けて待たされる可能性は残り、各スレッドの操作が限られたステップで完了するwait-freeの保証とは異なります。さらにatomic型が、対象の型や実装によって内部のロックへ依存する場合もあります。必要ならis_lock_freeなどで対象環境の性質を確認しますが、一つの型がロックフリーであることからアルゴリズム全体の進行保証は導けません。内部で使うメモリ割当てや回収処理が停止し得るかも含めて、何を保証する実装なのかを明記します。
取り外したノードをすぐ解放しない
連結構造からノードを外しても、別の読み手がそのポインタを既に取得している場合があります。先頭ポインタのCASに成功した直後に解放すると、読み手が寿命の終わった領域へアクセスする危険があります。同じアドレスが別のノードへ再利用されれば、ポインタ値だけを見る比較では履歴の変化を見逃すABA問題も考えられます。世代番号を付ける工夫と、安全に解放してよい時点を判定する仕組みは同じではありません。hazard pointerやepochによる方式などを使う場合も、読み手の登録、再確認、停止した読み手、回収の遅延を含めた規則を理解して採用します。
小さな例と検査の限界
最初は一回の公開例をスレッド数二で試し、各アクセスに対応する同期関係をコメントで説明します。検査ツールは見つけたデータ競合の修正に役立ちますが、実行しなかった経路の正しさやロックフリーの進行保証まで証明するものではありません。ストレス試験に通ったことも、まれな順序が不可能である根拠にはなりません。特に回収を伴う構造では、実装を自作する前に検証済みライブラリの契約と適用条件を確認します。性能の比較は正しさを説明した後に行い、スレッド数、競合率、待ち時間、メモリ消費も一緒に測ります。