概念・定理図鑑 · 発展

線形化可能性:操作が一瞬で起きたように説明できるか

呼び出しと応答の間に線形化点を置き、実時間の前後関係を保つ並行オブジェクトの正しさを考えます。

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

更新日

この記事の目次
  1. 一つの逐次履歴で説明する
  2. 重なる操作と重ならない操作
  3. 線形化点を探す
  4. 保証の範囲と費用
  5. この記事をロゲイアに質問する理解を確かめる

一つの逐次履歴で説明する

線形化可能性は、並行オブジェクトの各操作が、呼び出しから応答までのどこか一瞬で効いたと考えても矛盾しない性質です。その説明はオブジェクトの逐次仕様に従い、ある操作の応答が別操作の呼び出しより先に完了した場合には、その実時間の前後関係も保ちます。実装内部が逐次的である必要はありません。外部から観測した履歴に、条件を満たす説明が存在することが重要です。

重なる操作と重ならない操作

初期値0のレジスタに対し、write(1)が完了した後にreadが始まるなら、他の書き込みがない限りreadが0を返す履歴は説明できません。一方、readとwriteが重なっている場合には、逐次仕様を満たす範囲でreadを先に置く説明が許されます。操作が重なることと、結果が何でもよいことは違います。呼び出し時刻、応答時刻、返り値を併せて記録すると、どの順序が候補になるかを検討できます。

線形化点を探す

ロックで守られた更新なら、保護区間内の特定の更新を線形化点として考えられる場合があります。CASを使うアルゴリズムでは、成功したCASが候補になることがあります。ただし、どんな操作でも機械的に「最初のCAS」と決められるわけではありません。返り値や失敗操作、他の操作からの観測を含めて、逐次仕様との対応を証明する必要があります。操作ごとに線形化点の位置が異なる実装もあります。

保証の範囲と費用

線形化可能であっても、操作が高速であること、必ず短時間で終了すること、障害後にもデータが残ることまでは保証しません。また、個々のオブジェクトが線形化可能でも、複数オブジェクトをまたぐアプリケーションの一連の手続きが自動的に一つの原子的操作になるわけではありません。永続性、可用性、進行性、複数資源の不変条件は別に確認します。仕様に必要な保証を明示すると、実装や分散配置の選択を比較しやすくなります。

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

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

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

学習コースから次を選ぶ