作業系統：選鎖之前先解釋交錯執行
併發推理先列允許發生的事件。本路線分開作業系統抽象、核心實現與真實語言規則。一個軌跡能反駁全稱保證，同步論證則須說明它排除了哪些軌跡。
學習計畫與例題由 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與付費合併便利版不同。
選書前試做
把共享更新拆成讀取、私有計算與寫回，列允許次序。
檢查標準: 先說什麼原子，不能把高階語句自動當原子操作。
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
勾選用於自我記錄，並非成績評定；標記不會傳送給本站。
-
規定機器
建議閱讀範圍: OSTEP併發引言。
要做的練習: 寫共享狀態、私有暫存器、原子事件及各自順序。
檢查標準: 不偷加未說明的語言行為。
-
追一條執行
建議閱讀範圍: 同一閱讀與原題。
要做的練習: 逐次列讀取值與寫回值。
檢查標準: 寫回用先前儲存值，不必是最新共享值。
-
覆蓋全部順序
建議閱讀範圍: 同步閱讀。
要做的練習: 列兩讀前寫約束下的六條順序。
檢查標準: 證明列舉完整而非只舉有趣例子。
-
寫不變式
建議閱讀範圍: xv6鎖及參考討論。
要做的練習: 寫整個更新須共同觀察和釋出的狀態。
檢查標準: 保護範圍由不變式決定，不由程式碼一行長短決定。
-
改變同步
建議閱讀範圍: 變式。
要做的練習: 用同一互斥鎖重算，再額外指定順序。
檢查標準: 互斥與結果確定是兩件事。
-
接真實實現
建議閱讀範圍: 同版xv6路徑或課程題。
要做的練習: 說明語言和核心機制怎樣建立假設順序。
檢查標準: 抽象軌跡正確不認證未審查的生產程式。
原創例題與解析
原創事件機：原子讀取不等於原子更新
共享x初值10。執行緒1讀入r1再寫r1+3，執行緒2讀入r2再寫2r2，事件記R1,W1,R2,W2。列R1先W1、R2先W2的所有順序及末值。
前提假設
各次讀寫不可分，四事件順序一致，讀取最近已寫值或初值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也讀兩次10，最終W1寫13。
- 線上程1兩有序事件的四槽中選二，有choose(4,2)=6種，其餘給執行緒2，上述已全部覆蓋。
- 末值集合{13,20,23,26}。序列得26或23，其餘因儲存的舊讀數覆蓋另一次結果而丟失更新。
答案與解釋
六條合法交錯只產生13、20、23、26，單個事件原子不使複合更新原子。
檢驗結果
每條用四行狀態帳復算；不能推廣給記憶體／競爭語義不同的語言執行。
改變假設，再做一題
改變同步：互斥仍留下順序選擇
僅改同步：同一互斥鎖覆蓋各執行緒整段讀取與寫回，且都完成。剩什麼結果？再額外規定執行緒1整段先於執行緒2的交接。
- 臨界區不能重疊；1先時10→13→26，2先時10→20→23。
- 排除了13與20，仍有23及26，因為加法與翻倍不交換，互斥規則未選順序。
- 額外交接後僅10→13→26。順序要求是新增條件，不能從同鎖推得。
答案與解釋
僅互斥得{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版產品與配套資料不同於其他格式。
這些是本站建議的學習活動，並非大學官方作業，也不代表對每本書逐頁通讀。