体系ガイド · 基礎から応用へ

呼出しと返却の履歴から線形化可能性を確かめる

重なるキュー操作の候補順序を列挙し、実時間の制約、FIFOの返り値、進行や寿命の保証との違いを確認します。

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

更新日

この記事の目次
  1. 操作の途中を、一点の出来事へ説明し直す
  2. 重なる二つのputの順序を選ぶ
  3. 候補順序と逐次仕様を二段階で検査する
  4. 値が存在しても順序で拒否される
  5. 一履歴の成功から実装全体へ飛ばない
  6. 線形化可能でも、進み続けるとは限らない
  7. 値が同じ操作にも識別子を付ける
  8. 見つかった順序を、説明できる証拠へする
  9. 二つの履歴を逐次化する課題
  10. この記事をロゲイアに質問する理解を確かめる

操作の途中を、一点の出来事へ説明し直す

二人が同じキューを使うと、putとgetの実行区間が重なる場合があります。線形化可能性は、それぞれの操作が呼出しから返却までのどこか一瞬で起きたと考え、逐次のキュー仕様へ説明できるかという性質です。実装内部の一命令を見つけたら終わりではありません。その点を選んだとき、他の操作との順番と返った値が仕様へ合う必要があります。まずは完了した少数の操作の履歴から判断します。

ここで使うキューの逐次仕様は、putで末尾へ追加し、getで先頭を取り出すものです。空のgetや途中で止まった操作は今回の小さな検査器では扱いません。一般の線形化可能性には未完了操作の扱いも必要になります。定義の導入記事を前提に、このガイドは具体的な呼出し・返却区間から候補順序を作り、実時間の制約と返り値を同時に照合する手順へ進みます。

重なる二つのputの順序を選ぶ

put(1)が時刻0に始まり3に返り、put(2)が1に始まり2に返ったとします。二つは重なるため、返却の早いput(2)を必ず先に並べる必要はありません。put(1)を先に線形化し、その後put(2)を並べる候補もあります。続いてgetが4に始まり5に1を返したなら、put(1)、put(2)、get→1という逐次順序で説明できます。区間が重なる場合、呼出し順と返却順のどちらかへ機械的に整列するのではありません。

一方、操作Aが返り終わってから操作Bが呼ばれた場合は、AをBより前へ置く必要があります。これが実時間の前後の制約です。今回のgetは二つのputがどちらも完了した後なので、その前へ移せません。重なる操作に残る自由度と、重ならない操作にある制約を区間の図で分けます。自由に並べ替えればどんな履歴でも説明できるという意味ではないことを、返り値と合わせて確かめます。

操作呼出し返却候補の逐次順
put(1)031番目に置ける
put(2)122番目に置ける
get→145両putの後

候補順序と逐次仕様を二段階で検査する

検査器は少数の完了操作の全ての順列を作ります。まず、A.end<B.startならAが前という制約を満たすかを見ます。その後、空キューから順に操作を適用し、getの値が実際の先頭と一致するか確認します。時刻はこの模型の一つの順序軸で、実機の複数時計から測った曖昧な時刻を無条件に入れるものではありません。同時刻境界の扱いも今回の厳密な不等号へ固定します。

候補が一つでも成立すれば、その有限履歴はこの仕様へ説明できます。全候補が失敗すれば、この履歴とモデルの前提の下では説明できません。実装があらゆる入力で正しいと証明する検査ではありません。履歴を集める測定が返却値や操作IDを取り違えていないかも確認します。検査器へ入力した資料の正しさと、その資料に対する順序探索の正しさは別々の条件です。

python
from itertools import permutations
def legal(history):
    for order in permutations(range(len(history))):
        rank={key:i for i,key in enumerate(order)}
        if any(a[2]<b[1] and rank[i]>rank[j] for i,a in enumerate(history) for j,b in enumerate(history)):continue
        queue=[];ok=True
        for i in order:
            operation,start,end,value=history[i]
            if operation=='put':queue.append(value)
            elif not queue or queue.pop(0)!=value:ok=False;break
        if ok:return order
    return None
h=[('put',0,3,1),('put',1,2,2),('get',4,5,1)]
assert legal(h) is not None
bad=h[:2]+[('get',4,5,3)]
assert legal(bad) is None
print('legal order=',legal(h),'impossible returned value rejected')
print('finite completed histories, nonempty get specification only')

値が存在しても順序で拒否される

掲載例のgetが3を返すなら、putは1と2しかないため、どんな順序でも説明できません。さらに、put(1)が完全に終わり、その後put(2)も完全に終わってから最初のgetが2を返した場合も、FIFOの仕様では拒否されます。この場合2は確かに投入されていますが、先頭には1が残っています。所属する値かどうかだけの検査と、オブジェクトの逐次仕様を満たす検査は違います。

逆に、順次の仕様がスタックなら後から入れた2を先に出すのが正しい場合があります。同じ操作名でもデータ構造の仕様が違えば判断は変わります。テストを書く前に、空の取り出し、重複する値、失敗するput、容量の上限などの返り値を決めます。今回の簡単な検査器へ対象外の操作を入れ、Noneが返ったから実装不良と結論しないでください。仕様の対応範囲を明示することが、反例を意味のあるものにします。

一履歴の成功から実装全体へ飛ばない

並行実装の検証では、特定した線形化点が、成功と失敗の全経路でどのように選べるかを考えます。CASが成功する操作、再試行する操作、空と判断する操作などで、同じ行を機械的に選べるとは限りません。別スレッドが操作を助ける方式なら、呼出し元自身の命令だけを見ても説明し切れない場合があります。このガイドの履歴検査は、その証明を考えるための小さな反例探しの道具です。

順列の全探索は操作数に対して急激に増えるため、大きな本番ログへそのまま使うものではありません。小さな履歴へ絞る、部分順序の制約を使う、状態を再利用するなどの工夫が必要になります。検査時間が尽きた場合も、不可能と確定した結果と区別します。可能な候補を見つけた、全候補を調べて見つからなかった、調べ切れていない、という三つの状態を混ぜないようにします。

線形化可能でも、進み続けるとは限らない

ロックを使うキューは逐次仕様へ正しく説明できても、ロックの保持者が止まれば他の操作も待つ場合があります。線形化可能性は主に返り値と操作順の正しさを扱い、lock-freeやwait-freeのような進行の保証とは別です。また、メモリを安全に回収できるかも独立した条件です。値が正しいことだけで、デッドロック、飢餓、解放後参照がないとは言えません。

実装を比較する表では、逐次仕様、順序の保証、進行、寿命管理、測定した性能を別の列へ置きます。最速の一回の測定結果から、線形化可能性を読み取ることもできません。第3段階の分散した読み書きの保証と比べる場合も、対象が同じか、どの操作の呼出しと返却を境界とするかを合わせます。言葉が共通でも、アプリ、DB、メモリ上のオブジェクトの保証範囲は同じではありません。

値が同じ操作にも識別子を付ける

二つのputがどちらも値1を入れると、返ったgetの値1だけから、どちらを取り出したかは区別できません。仕様が値の列だけを扱うなら、この曖昧さを許す候補順序を検査できます。一方、要求ごとの一回限りの処理や個別の応答の対応も確認するなら、操作IDと呼出し・返却の対応を履歴へ持つ必要があります。値が同じことと、操作が同じことを混同しません。

記録する時刻も、トレースの入口と出口の意味を定めます。アプリの関数の前後か、ネットワーク越しの呼出しの前後かで区間は変わります。複数ホストの時計を使う場合は、誤差で重ならないはずの順序を誤って固定していないかを考えます。今回の整数時刻は模型で定めた正確な順序軸です。実サービスの記録へ適用するときは、測定境界と識別情報を仕様へ合わせ、検査器へ入力する前の資料の妥当性も検証します。

列挙が成功したという結果を読むときは、調べた操作の件数と逐次仕様も一緒に見ます。未完了操作や空キューの取出しを加えれば、対象となる履歴と仕様の定義を先に拡張する必要があります。

見つかった順序を、説明できる証拠へする

検査器が順序(0,1,2)を返したら、その番号を元の操作へ戻し、各時点のキュー内容を書きます。空からput1で[1]、put2で[1,2]、get1で[2]です。返った値だけでなく、次の操作へ引き継ぐ状態も一致していることを確認できます。候補が返ったという文字だけで終えず、読者が自分の手で検査できる説明へ変えます。

逆に不成立の場合は、どの実時間制約が順序を固定し、どの返り値が逐次仕様と合わないかを示します。今回の小履歴なら全候補を列挙できますが、大きな履歴の途中で打ち切った場合は同じ結論にしません。実装の修正前後で同じ反例を再検査する場合も、操作数、初期状態、対象仕様を保ちます。反例を短くしたとき、その削除で必要な先行操作まで落としていないかを確認し、再現する問いを失わないようにします。

二つの履歴を逐次化する課題

課題の一つ目は、put(1)が0〜3、put(2)が1〜2、get→1が4〜5です。解答はput(1)、put(2)、get→1という順序が成立します。put(2)が先に返っても二つの投入が重なるため、この候補を許せます。二つ目ではput(1)が0〜1、put(2)が2〜3、get→2が4〜5です。解答はFIFOとして不成立です。実時間で投入順が固定され、1を飛ばして2を出す操作がないためです。

追加課題では、getがまだ返っていない履歴を今回の検査器へ入れてよいかを問います。解答は対象外で、完了させるか除くかなど一般の定義へ対応する拡張が必要です。途中の状態に好きな返り値を足して、実測した履歴として報告しないでください。対象仕様、実時間制約、候補順序、探索の完了条件を分けて答えられれば、並行実装のより深い証明へつなげられます。

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

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

CS基礎を固める · STEP 17

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

AI基盤へ進む · STEP 7

学習コースから次を選ぶ