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

happens-before:時計ではなく因果と同期の順序

同じ実行内の順序、通信・同期、推移性から作る部分順序を使い、単なる時刻の比較との違いを学びます。

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

更新日

この記事の目次
  1. 時計の値だけで前後を決めない
  2. メッセージを介した例
  3. 共有メモリでは言語の契約を使う
  4. 一つの順序を付けることとの違い
  5. この記事をロゲイアに質問する理解を確かめる

時計の値だけで前後を決めない

happens-beforeは、どの出来事が別の出来事に先行するかを、因果関係や同期規則に基づいて表す関係です。Lamportの分散システムのモデルでは、一つのプロセス内の順序、メッセージ送信からその受信への順序、それらの推移性から関係を構成します。すべての出来事の組に順序が付くわけではなく、関係で結ばれない出来事は並行と捉えます。別の機械の時計の数値が小さいことだけでは、この関係を証明できません。

メッセージを介した例

プロセスAが値を計算してからメッセージを送信し、Bがそのメッセージを受信した後に結果を記録するとします。Aの計算は送信より前、送信は受信より前、受信はBの記録より前なので、推移性によって計算は記録に先行します。一方、通信も共通の同期もないCの出来事については、この連鎖だけで前後を決められません。「順番が不明」と「同時刻に起きた」は同じ意味ではありません。

共有メモリでは言語の契約を使う

共有メモリのプログラムでも、happens-beforeはメモリモデルを説明する重要な関係です。ただし、どの操作が同期関係を作るかは言語やライブラリの仕様で決まります。ロックの解放と後続の取得、適切に組み合わせたrelease/acquireなどが関係を作る例です。名前が似ているからといって、分散システムのメッセージ規則をそのままCPU命令列へ移してはいけません。使うAPIの規則に従って、書き込みから読み込みまでの経路を示します。

一つの順序を付けることとの違い

論理時計では、先行関係があるなら時計値も増えるように値を付けられます。しかし、時計値が小さいから必ず先行関係があるという逆向きは一般に成立しません。無関係な出来事へ便宜的に全順序を付けても、新しい因果関係が発生するわけではありません。デバッグでは時刻付きログを並べるだけで安全なデータ共有を証明せず、実際に存在する通信や同期を確認します。出来事を図にして、どの通信や同期が先行関係を作るかを確認すると、根拠を追いやすくなります。

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

コースの順番に沿って学ぶ

CS基礎を固める · STEP 17

サーバーの中で起きていること · STEP 7

AI基盤へ進む · STEP 7

学習コースから次を選ぶ