概念・定理図鑑 · 基礎から応用へ

メモリバリア:複数のアクセスの順序を約束する

アトミック性と順序を分け、公開するデータとフラグの組から同期の条件を確認する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 一回のアクセスと複数アクセスの順序
  2. データを公開してからフラグを立てる
  3. バリアだけでは排他にならない
  4. 証明したい性質を先に決める
  5. 一回限りの公開を手順で追う
  6. デバイスとの順序は別の契約で扱う
  7. この記事をロゲイアに質問する理解を確かめる

一回のアクセスと複数アクセスの順序

メモリバリアは、メモリアクセスの順序に関する制約を表すための仕組みです。一つの変数を破れずに読み書きできることと、別の変数への操作が望んだ順で観測されることは異なります。コンパイラによる変換とCPUの実行や可視性の規則の両方を考える必要があります。言語のアトミック操作、OSカーネルのバリア、デバイスI/Oのバリアは、そのまま交換できる道具ではありません。どのモデルと観測者に対する約束かを明示します。

ここでいう順序は、ソースコードの行が上から下に並んでいるという見た目だけでは決まりません。共有データを受け渡す規約を、言語が許す実行として説明する必要があります。カーネル向けの資料にあるマクロ名を、ユーザー空間のC++へそのまま貼り付けても、標準が要求する同期関係を定義したことにはなりません。実装の命令列を読む前に、まずどの言語・APIの約束で正しさを説明するのかを決めます。

データを公開してからフラグを立てる

送信側がdataを書き、その後readyを公開し、受信側がreadyを見てdataを読む例を考えます。対応するrelease/acquire操作が同期関係を作る条件を満たせば、dataの公開を順序付けられます。readyへ通常の代入をしただけ、または両側でrelaxed操作を使っただけでは、同じ保証を当然には得られません。さらに、受信後に送信側が同じdataを無制御に書き換えるなら別の競合が残ります。一度の公開と、その後の所有権・寿命を分けて設計します。

一度だけ公開する例なら、dataの初期化がrelease storeより前に完了し、読み手のacquire loadがそのstoreから書かれた値を読むことが核心です。単に同じ値1を見たという説明では、別の書き手やフラグの再利用がある場合に、どの公開を読んだかが曖昧になります。何度も同じ領域を使うなら、次の書き換えを始めてよい条件を別に設けます。初期化の公開と、継続的な共有更新は異なる問題です。

バリアだけでは排他にならない

二つのスレッドが同じ残高へ読み取り、加算、書き戻しを行う処理は、途中へバリアを置いただけでは一つの原子的操作になりません。排他ロックや適切なread-modify-write操作などが別に必要です。バリアがすべてのキャッシュを必ず書き戻す、あるいは全CPUを同時に待たせると理解するのも誤りです。要求する順序を実現する最小の動作はアーキテクチャごとに異なり、一部のバリアが命令を生成しない場合もあります。保証と実装を区別します。

例えば二人が残高0を読み、それぞれ1を足して1を書き戻すと、順序制約を加えても結果が2になるとは限りません。二回の更新を一つずつ数えるには、競合するread-modify-writeを適切な原子操作にするか、ロックで区間を保護します。データ競合がないこと、更新を取りこぼさないこと、他のデータを公開することは別々の性質です。必要な性質を分けて確認すると、過剰なバリアを追加しても直らない理由が明確になります。

証明したい性質を先に決める

同期を選ぶときは、誰が書き、誰が読み、どの観測が許されないかを小さな例で記述します。CやC++の通常の共有変数へ競合アクセスがあるなら、後からCPUバリアだけを足して言語上の未定義動作を解消できるとは限りません。標準のアトミック型やロックの規約を使います。負荷試験で一度も失敗しなかったことも、すべての許される実行順で正しい証明にはなりません。対象のメモリモデルの説明と、必要に応じたモデル検査を合わせて確認します。

具体例として、初期値0のアトミック変数xとyを用意し、一方のスレッドがxへ1を書いてyを読み、他方がyへ1を書いてxを読む場合を考えます。すべてrelaxedなら、両方の読み取りが0となる実行を当然に禁止できません。全操作をseq_cstとした同じ小例とは、許される結果が異なります。すべてのアクセスが原子的でも、期待した複数変数の順序が自動で成り立つとは限らないことを示しています。モデル上の許可と実機での出現頻度を分けて確認します。

一回限りの公開を手順で追う

書き手だけがpayloadを初期化し、その後ready.store(true, release)を実行するとします。読み手はready.load(acquire)がtrueを返した後にpayloadを読みます。readyをtrueにするのがこの書き手だけで、観測した値が対応する公開から来ており、payloadをその後変更せず寿命も保つなら、初期化した内容を安全に受け渡す説明ができます。逆に、書き手がtrueを立てた直後にpayloadを次の要求向けへ変更すると、最初の公開が正しくても読み手との競合が生じます。フラグをfalseへ戻すだけでは、書き手が読み手の利用終了を知ったことにはなりません。二回目以降の受け渡しには、確認応答や所有権の移転など別の手順が必要です。どの値を読んだかと、その値をいつまで使えるかを一緒に説明します。

デバイスとの順序は別の契約で扱う

ネットワーク装置へ渡すディスクリプタをメモリに書き、最後にドアベルと呼ぶ通知用レジスタへ書き込む例では、装置が見る順序が問題になります。通常のスレッド間の同期を説明するだけでは、DMAの可視性やMMIOの順序まで十分に説明したことにはなりません。ドライバはカーネルが用意するアクセサーやDMA APIを、対象プラットフォームの規約に従って使います。CPUのキャッシュへ書いたこと、装置がその内容を読めること、装置が処理を終えたことは分けて追います。ここでアーキテクチャ固有の命令を一つ選んで全装置に一般化するのは避けます。必要な順序とキャッシュ管理は、メモリの種類、装置との接続、コヒーレンスの条件に依存するためです。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

学習コースから次を選ぶ