プロセッサは、独立した2つの読み書きをどちらの順で実行してもよく、別のコアはその選択の結果を見ることがあります。SPYの価格を公開してからフラグを立てても、フラグを見た読み手が価格0を読むことがあります。書き手と読み手の順序付け4通りのうち、安全なのは1つだけで、書き手のreleaseと読み手のacquireの組み合わせです。
プロセッサは並べ替える
ストアバッファ、キャッシュ、コンパイラは、1つのスレッドからは区別できない限り、後の書き込みや読み出しを先のものより先に終わらせます。別のスレッドからは区別できます。このマシンはそれを直接モデル化します。スレッドは操作のリストで、順序制約を満たす操作ならどれでも任意の順に実行できます。同じアドレスへの操作は常に順序を保ちます。そうしないとスレッドが自分の書き込みを見られなくなるからです。acquireロードは後続すべてを止め、releaseストアはそれ以前のすべてを待ちます。2つの関数がすべてを表します。must_wait は操作が待つものを、eligible は次に実行してよいものを挙げます。
def must_wait(ops, j): waits = [] for i in range(j): same = ops[i][1] == ops[j][1] after_acquire = ops[i][0] == "load" and ops[i][3] == "acquire" release = ops[j][0] == "store" and ops[j][3] == "release" if same or after_acquire or release: waits.append(i) return waitsdef eligible(ops, done): return [j for j in range(len(ops)) if j not in done and all(i in done for i in must_wait(ops, j))]writer = [("store", "data", 1, "relaxed"), ("store", "flag", 1, "release")]reader = [("load", "flag", "r1", "acquire"), ("load", "data", "r2", "relaxed")]print(must_wait(writer, 1), eligible(writer, set()), eligible(writer, {0}))print(must_wait(reader, 1), eligible(reader, set()))print(eligible([("load", "flag", "r1", "relaxed"), ("load", "data", "r2", "relaxed")], set()))
[0] [0] [1] [0] [0] [0, 1]
フラグのreleaseストアは位置0のデータストアを待つので、書き手は操作を順番にしか実行できません。フラグのacquireロードは後ろのデータロードを止めるので、読み手も順番に実行します。通常のロードなら両方が同時に実行可能で、読み手はデータを先に読むことがあります。
すべての順序を実行する
outcomes は、これまでのトピックの探索器をこの新しいマシン向けにしたものです。状態は、各スレッドが終えた操作、メモリ、レジスタです。ある状態から、各スレッドの実行可能な操作をすべて試し、実行するものがなくなったらレジスタが1つの結果になります。多くの順序が同じ状態に至るので、見た状態を覚えておきます。メッセージパッシングのテストは、データ、次にフラグの2つのストアで公開し、フラグ、次にデータの2つのロードで消費します。消費側が r1 == 1（フラグ）かつ r2 == 0（データがまだない）を見たら誤りで、これを reads_stale が確認します。
def outcomes(programs, memory=None): found = set() seen = set() def visit(done, mem, regs): state = (tuple(frozenset(d) for d in done), tuple(sorted(mem.items())), tuple(sorted(regs.items()))) if state in seen: return seen.add(state) moved = False for tid, ops in enumerate(programs): for j in eligible(ops, done[tid]): moved = True kind, address, x, _ = ops[j] mem2, regs2 = dict(mem), dict(regs) if kind == "store": mem2[address] = x else: regs2[x] = mem.get(address, 0) done2 = [set(d) for d in done] done2[tid].add(j) visit(done2, mem2, regs2) if not moved: found.add(tuple(sorted(regs.items()))) visit([set() for _ in programs], dict(memory or {}), {}) return founddef mp_programs(write_order, read_order): return [ [("store", "data", 1, "relaxed"), ("store", "flag", 1, write_order)], [("load", "flag", "r1", read_order), ("load", "data", "r2", "relaxed")], ]def reads_stale(results): return any(dict(outcome).get("r1") == 1 and dict(outcome).get("r2") == 0 for outcome in results)for pair in (("relaxed", "relaxed"), ("release", "acquire")): results = outcomes(mp_programs(*pair)) print(pair, sorted(results), "stale:", reads_stale(results))
('relaxed', 'relaxed') [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 1)), (('r1', 1), ('r2', 0)), (('r1', 1), ('r2', 1))] stale: True
('release', 'acquire') [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 1)), (('r1', 1), ('r2', 1))] stale: Falserelaxed の順序では、消費側は (r1, r2) の4通りすべて、古いデータを読む (1, 0) も含めて取りえます。フラグのストアにrelease、ロードにacquireを付けると3通りだけが残ります。フラグを見た読み手はデータも見ます。どちら側もフラグをまたいで並べ替えられないからです。
releaseとacquireは対で使う
片方だけで足りるでしょうか。4つの組み合わせをすべて試します。書き手だけのreleaseは失敗します。読み手がフラグより先にデータをロードするかもしれません。読み手だけのacquireも失敗します。書き手がデータより先にフラグをストアするかもしれません。組み合わせたときだけ成立し、次の表がそれを示します。これはC++の std::atomic やRustのrelease-acquireの契約で、ロックフリーキューがスロットをインデックスのreleaseストアで公開し、acquireロードで読む理由です。
PAIRS = [("relaxed", "relaxed"), ("release", "relaxed"), ("relaxed", "acquire"), ("release", "acquire")]def ordering_table(): return {pair: reads_stale(outcomes(mp_programs(*pair))) for pair in PAIRS}for pair, stale in ordering_table().items(): print("write", pair[0], "| read", pair[1], "->", "can read stale data" if stale else "safe")
write relaxed | read relaxed -> can read stale data write release | read relaxed -> can read stale data write relaxed | read acquire -> can read stale data write release | read acquire -> safe
同じ変数に対応するacquireのないreleaseは何も守りません。C++の実際のメモリオーダー seq_cst はより強くコストも高く、relaxed は最も安い代わりに順序を何も保証しません。上のテストが通る最も弱い順序を選び、探索器で証明しましょう。
price = int(round(float(load_bars()["close"].iloc[0]) * 100))programs = mp_programs("release", "acquire")programs[0][0] = ("store", "data", price, "relaxed")print(price, sorted(outcomes(programs)))
9369 [(('r1', 0), ('r2', 0)), (('r1', 0), ('r2', 9369)), (('r1', 1), ('r2', 9369))]SPYの最初の終値9,369セントでも、4つの構成のうち3つで、読み手はフラグを見ながら価格0を読むことがあります。この種のバグは、たまたま順序を守るマシンではすべてのテストを通り、別のマシンで現れます。だから安全な組み合わせは、探索器のように許されたすべての順序で証明しなければなりません。
フラグのreleaseストアと、それを読むacquireロード。書き手がreleaseより前に行ったことは、読み手からacquireの後に見えます。フラグでデータを公開することを正しくする、最も安い順序付けです。
これから作るもの
ラボは講義の順に進みます。操作が待つべきもの、次に実行してよい操作、スレッド群のすべての結果、メッセージパッシングのテスト、古いデータの検査、4つの順序付けの表、そして実際のSPY価格を公開する研究です。
- 関数 · 問い前提
- must_wait(ops, j)この操作は何を待つべきか？単純な算術
- eligible(ops, done)次に実行できる操作は？単純な算術
- outcomes(programs, memory)スレッドは何で終われるか？eligible
- mp_programs(write_order, read_order)メッセージパッシングはどんな形か？単純な算術
- reads_stale(results)読み手はデータなしでフラグを見られるか？単純な算術
- ordering_table()どの順序付けの組が安全か？outcomesmp_programs
- study(bars)どの組が実際のSPY価格を守るか？outcomesmp_programs
次のトピック：ロックフリーな構造を作る道具と、それが何を保証するかを表す語彙が揃いました。進行保証では、obstruction-free、lock-free、wait-free の3段階に名前を付け、これまで書いた各カウンタを、最悪のタイミングで永久に止められたスレッドに対して試します。
ラボ：採点される内容
7タスク · 100点- 操作が待つもの15点
- 次に実行できるもの10点
- すべての結果25点
- メッセージパッシングのテスト10点
- 古いデータ5点
- 4つの順序付け10点
- SPYの表での研究25点