スレッドと同期

複数スレッドが調整せず共有状態を読み書きすると、結果がスケジューリング順に依存し得る。本課は counter = counter + 1 を、読み取り、スレッド専用コピーへの加算、書き戻しという三つの原子的な教材のステップに分ける。間へ別スレッドが入ると更新を失う。

二スレッドが三回ずつ増やせば期待は 6 だが、既定の無同期実行は 4 になる。六回の store は実行しても、古い値が二つの増分を覆う。次に同じスケジュール文字列をミューテックス付きで実行して 6 とし、二つのロックを逆順に取るとデッドロックする例へ進む。

競合が起きる仕組み

通常のインクリメントは一行だから不可分とは限らない。共有値をスレッド専用の一時変数へ読み、コピーを加算し、書き戻して初めて共有状態を変える。原子的な増分が必要なら、言語の atomic read-modify-write や適切な同期を使う。

単一コアはスレッドを交錯させ、段階間で切り替えられる。レジスター状態は文脈とともに保存されるため、古いコピーも切替後に残る。多コアなら同時実行もある。

T1 が 0 を読んで切り替わり、T2 が 0 を読み、足して 1 を保存する。戻った T1 は古い 0 に 1 を足し、既に 1 の counter へ 1 を書く。個々の教材の命令は正当でも T2 の増分が消える。実言語のデータ競合規則は別に必要で、例えば C/C++ の非 atomic 共有データ競合は未定義動作だ。この順序交錯だけを完全な言語モデルとはしない。

ステップ実行

既定文字列は 1 222 11 222 111 2 111 22。各数字が一つの教材の実行ステップを T1 または T2 へ与える。18 ステップ、切替 7 回で、各スレッドは tmp = counter、tmp = tmp + 1、counter = tmp を三度行う。

1. T1 が共有 0 を読み、tmp₁=0。共有値は不変。
2. T2 へ切り替え、T1 の 0 は保存する。
3. T2 も 0 を読み、tmp₂=0。
4. T2 の専用変数への加算で tmp₂=1。counter はまだ 0。
5. T2 が counter=1 を保存し、一増分を完了する。
6. T1 へ戻る。
7. T1 は現在の counter=1 を使わず、旧コピーで tmp₁=0+1=1 を計算する。
8. T1 が 1 を保存する。store は二回でも共有値は一度だけ増えた。
9. T2 が一組の増分を行い counter=2。
10. T1 が一組を行い counter=3。
11. T2 が 3 を読んだところで中断する。
12. T1 が最後の一組を終え counter=4、T1 は完了。
13. T2 は古い 3 に足して 4 を書き、二度目の更新喪失となる。

この番号は説明や切替も含み、18 個の機械スロット番号とは違う。最終値は六 store で 4。下の帯はスロットをスレッド色で示し、他の増分を消した store に X を付ける。機械ステップ 6 と 18、位置差は 12 だ。重なる read-modify-write が問題であり、すべての切替が必ず失敗するわけではない。

ミューテックスの保証

Mutex でも文字列は同じだが、実行は同一でない。取得・解放が増え、ブロックする試行も一スロットを使うため、文字列を反復して計 35 ステップ、14 切替になる。同じ入力スケジュールでも、切替位置を固定した比較ではない。

ロックには所有者が一人いる。保持中に他方が lock.acquire() へ来ると待機列へ入り、保護された load を実行できない。本モデルはスピンしない。所有者は中断され、無関係のコードも動けるが、同じロックに従うクリティカルセクションは重ならない。

既定の二段目でも T2 へ切替は起きる。ただし T2 は待機させる取得試行しかできず、後で古くなるコピーを読めない。全更新が同じロックで read-modify-write 全体を保護し、仕事が最終的に進めば、各増分が残り結果は 6 になる。

この実行はロックが使えないと知るために 5 スロットを使う。誤上書きを待機へ変えても、切替と競合は残る。必要な不変条件全体を囲みつつ、無関係な長い計算や I/O を外すことが設計上の課題だ。

単独カウンターにはユーザー管理の mutex なしで atomic read-modify-write を使える。ただし一命令か、ロックフリーかは型と環境による。残高と記録、キューと長さなど複数フィールドの関係を守る場合、各フィールドを別々に atomic にするだけでは足りず、共通のクリティカルセクションなどで更新全体を調整する。

二つのロックのデッドロック

Two locks は T1 が lock_a、lock_b を A→B、T2 が B→A の順に取る。

T1 が A を取り、切替後 T2 が B を取る。T2 は A を要求して止まり、戻った T1 は B を要求して止まる。四つの取得試行で互いの解放を待つが、解放は両取得の後なので誰も進めない。counter は 1 にもならない。

待機グラフは T1 → lock_b → T2 → lock_a → T1 の輪になる。この排他ロックの例では循環が停止を表す。全体で取得順を統一し、T2 も A を先にすれば、この種類の循環を防げる。A の競争に負けた側は B を持たず待ち、勝者が B を取って完了・解放できる。

境界ケース

• 111222111222111222 は増分の境界だけで切り替え、無同期でも 6 になる。一度成功しても全順序の正しさではない。
• 一つの旧 store は複数の増分を消せる。122222222211111111 は T1 が 0 を読んだ後 T2 が三増分で 3 にし、T1 の旧 store が 1 へ戻す。最終値は 3。
• ブロックは完全に無料ではない。失敗 acquire は一スロットを使うが、その後ずっと CPU を回してスピンするモデルではない。
• 短い文字列は反復する。12 は交互、1 は T1 を先に終える。完了済み・待機中の指定は他の実行可能側へ回す。
• 二スレッドと一変数だけで再現する。スレッド数が増えても機構は同じで、発生頻度は負荷とスケジューリングによる。

よくある間違い

• counter += 1 が一行なので atomic だと思う。保証は言語、ランタイム、同期 API により、ある CPython/GIL 版で見えた偶然の動作へ依存できない。
• counter = tmp の store だけを保護する。古い値は既に読まれており、読み取りから書き込みまでを囲む必要がある。
• テスト成功で競合がないと結論する。試した順序の証拠でしかなく、共有状態の分析や専用検出器も必要だ。
• タイムアウトだけでデッドロックを直す。失敗を報告しても、安全な解放・巻き戻しと循環依存の解消がなければ原因は残る。ここでは順序を統一する。
• 関数全体を不用意にロックする。保護すべき共有不変条件を囲み、不要な I/O や長計算による直列待機を減らす。

モデルの範囲

単一コアの交錯と原子的な擬似命令を使い、キャッシュや並べ替えはない。実際のメモリモデルは複雑で、C/C++ の volatile だけではスレッドの atomicity や同期を提供しない。mutex は所有者と FIFO 待機列で表し、スピン、futex、列を越えた公平性保証は扱わない。

セマフォと条件変数は表示しない。mutex は所有権を持ち、バイナリーセマフォは通常同じスレッドの解放を要求しない。条件変数はロックと組み合わせて共有述語を待つ。完全に置き換え可能な API ではない。