OS：ロックを選ぶ前に交錯実行を説明する
並行性ではまず許されるイベントを定めます。OSの抽象、カーネル実装、実際の言語規則を分け、一つの反例と全実行を制限する同期の議論を区別します。
学習順路・例題の編集責任：University Reading List編集プロジェクト。 編集と選定の方法 · 出典確認日:
このページの目次
対象と編集責任
C、ポインター、スタック、計算機構成の後の学習向け。問題は完全指定の逐次一貫した抽象機械で、同期されていないCプログラムのデータ競合へこの規則をそのまま適用しません。
出発点を選ぶ
三冊を比較する
オペレーティングシステム：三つの基本
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau · 版: 1.00 · 2018
無料の概念・実験主教材
- 選ぶ場面
- C参照を追え、具体的問題から機構を学びたい。
- 別の教材が適する場面
- 初回コーディングが必要、またはオンラインと紙版の同一頁を期待する。
- 読む範囲
- OSTEPの並行性導入、ロック、条件変数。必要ならプロセス・アドレス空間へ戻る。
- 限界と注意点
- 2018年記録は1.00、著者のオンラインは1.10。無料分章PDFと有料一括PDFは別です。
選ぶ前に試す
共有更新を読出し、私的計算、書込みへ分け、順序を列記。
確認すること: 何が原子的かを先に定め、高水準の文を自動で原子的としない。
xv6: a simple, Unix-like teaching operating system
Russ Cox; Frans Kaashoek; Robert Morris · 版: RISC-V revision 5 · 2025
無料の教育カーネル補助
- 選ぶ場面
- プロセス、トラップ、メモリー、ロックを実装で追いたい。
- 別の教材が適する場面
- C／アセンブリが不足、または全実用設計を代表させたい。
- 読む範囲
- 2025年9月2日のRISC-V改訂5。インターフェース・構成からロック・スケジューリングへ。
- 限界と注意点
- 小型設計は追いやすい反面、実用の複雑さを省きます。x86、最新コード、旧行番号を混ぜません。
選ぶ前に試す
一つの保護不変条件と全変更経路を特定する。
確認すること: 同じロックが全経路で必要な理由を説明する。
Operating System Concepts（オペレーティングシステムの概念）
Abraham Silberschatz; Peter Baer Galvin; Greg Gagne · 版: 10 · 2018
商用の総合参考
- 選ぶ場面
- プロセス、同期、メモリー、保存の標準用語が必要。
- 別の教材が適する場面
- スライドや一部解答を本文・教員全解答の無料公開と考える。
- 読む範囲
- 2018年第10版のプロセス／スレッド、同期、必要なメモリー管理を題名で選ぶ。
- 限界と注意点
- ISBN 9781119320913はWileyの電子商品で、紙版補助やバンドルとは別です。
選ぶ前に試す
相互排他、順序、進行を問題で別々に検討。
確認すること: 排他は重複を防いでも、先行操作や調度方針を決めない。
準備を確認する
交錯とは？
各スレッドの必要順序を守る単一イベント列。実際に読んだ値から結果を計算します。
保護範囲は？
組合せに不変条件が依存すれば読出し・変更・書込みの全体を保護。読出しと書込みを別々にロックしても組合せは不可分になりません。
何を省く？
本問は原子的な読出し・書込みと全順序、私的計算。言語メモリー、最適化、故障、公平性は別です。
六つのステップで学ぶ
完了したステップ: 0 / 6
自己記録用のチェックであり、評価ではありません。チェック情報は当サイトに送信されません。
-
機械を規定
読む範囲: 並行性導入。
取り組む課題: 共有状態、レジスター、原子イベント、各順序を書く。
確認すること: 未指定の言語動作を足さない。
-
一実行を追う
読む範囲: 同じ導入と問題。
取り組む課題: 読出しと書込みの値を逐次記録。
確認すること: 保存した旧値を使う点に注意。
-
全順序を覆う
読む範囲: 同期の選読。
取り組む課題: 二つの読前書条件を守る六順序を列記。
確認すること: 例だけでなく完全性を説明。
-
不変条件を書く
読む範囲: xv6のロック。
取り組む課題: 一単位として観測・公開すべき遷移を述べる。
確認すること: 行の見た目で範囲を決めない。
-
同期を変更
読む範囲: 解いた変式。
取り組む課題: 共通mutex、次に指定順序で再計算。
確認すること: 排他と決定性を分ける。
-
実装へつなぐ
読む範囲: 対応xv6経路か授業演習。
取り組む課題: 言語・カーネルが仮定順序をどう実現するか書く。
確認すること: 抽象追跡は実用コードの認証ではない。
解答付きの例題
独自イベント機械：原子読出しと更新は別
共有x=10。スレッド1はr1へ読みr1+3を書く。スレッド2はr2へ読み2r2を書く。R1,W1,R2,W2とし、各Rが自分のWより先の全順序と最終値を求めます。
前提
各読出し・書込みは不可分で全四イベントは逐次一貫。最新の先行書込みか初期10を読み、計算は私的。両者完了、他アクセスなし。同期されていないCコードではない創作機械です。
- R1,W1,R2,W2は10読→13書→13読→26書。R2,W2,R1,W1は10読→20書→20読→23書。
- R1,R2,W1,W2とR2,R1,W1,W2は両方10を読み最終W2=20。R1,R2,W2,W1とR2,R1,W2,W1は最終W1=13。
- 四枠からスレッド1の二枠を選ぶchoose(4,2)=6で全て。残りはスレッド2の順序です。
- 最終集合{13,20,23,26}。直列は26か23、他は保存旧値の上書きで更新が失われます。
解答と解釈
六順序から四最終値13,20,23,26。イベント単位の原子性は更新全体の原子性ではありません。
結果を検証する
各順序に四行の台帳を作り、異なる言語メモリー規則へ一般化しない。
前提を変えて考える
同期変更：排他でも順序は残る
共通mutexで各読出し・書込み更新全体を保護し両方完了する条件へ変更。結果は？さらにスレッド1全体が2より先という受渡しを追加します。
- 保護区間は重複せず、1先なら10→13→26、2先なら10→20→23。
- 13と20は排除されても23と26は残ります。加算と倍増は可換でなく、mutexは順序を選びません。
- 追加の1先行条件なら26のみ。この順序条件はmutexとは別の仮定です。
解答と解釈
mutexのみ{23,26}、指定受渡し込み{26}。原子性と順序決定性は別です。
結果を検証する
二関数を両順で合成。公平性、デッドロック、実言語の正しさには別の実装論証が必要。
よくある誤り
文を原子的と仮定
一文が複数メモリーイベントを含み得ます。
ロック名だけで証明
全関連アクセスの遷移を同じ適切なロックで保護。
排他を順序と誤認
直列化した非可換操作にも二結果があります。
次に進む前に
- 全順序と読出し値と書込み値を再現できる。
- 同期の排除する結果を説明できる。
- 抽象機械と実言語・カーネルを区別できる。
出典と版の確認
出典確認日:
- OSTEP: free conceptual chapters and current online version
三部構成が概念と無料分章の主軸。
- OSTEP: publication and revision history
1.00記録とオンライン1.10を区別。
- OSTEP: concurrency introduction
イベント推論を支え、数値と追跡は独自。
- MIT: xv 6 RISC-V revision 5, September 2025
固定2025年RISC-V冊子でコードを追う。
- Wiley: tenth-edition electronic product identity
正確な第10版商品と他形式を区別。
提案する学習活動であり、公式の課題や全巻通読の主張ではありません。