# 作業系統：選鎖之前先解釋交錯執行 — 學習任務單 [學習指南](https://unireadinglist.com/zh-tw/guides/operating-systems/) [課程主題: 作業系統](https://unireadinglist.com/zh-tw/subjects/computer-science/#course-operating-systems) 來源確認日期: 2026-11-04 學習計畫與例題由 University Reading List 編輯整理。 適合掌握C、指標、棧和計算機組成的系統學習者。下題是完整規定的順序一致抽象機；不能把這些規則偷偷套給未同步的C資料競爭。 ## 選擇你的起點 - [ ] 需要講清作業系統概念的免費教材 用OSTEP按虛擬化、併發、持久化推進，先問機制解決什麼，再聯絡不變式。 - [ ] 想看核心機制 掌握C和體系結構後讀固定xv6 RISC-V修訂5，先匹配書與程式碼再追行號。 - [ ] 課程需要綜合參考 用Operating System Concepts建立術語地圖，按課表選程序和同步，不一次讀完所有平臺案例。 ## 三本書如何取捨 ### 作業系統：三個簡單部分 Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau · 1.00 · 2018 免費作業系統教材，結合概念與實驗 什麼情況下適合讀: 能追C指標，想從系統問題理解機制。 什麼情況下選別本: 仍需第一門程式設計，或期待線上正文與所選紙書逐頁一致。 建議閱讀範圍: 讀OSTEP併發引言、鎖和條件變數，必要時先補程序及地址空間。 限制與取捨: 所選2018記錄為1.00，作者線上已1.10；免費分章PDF與付費合併便利版不同。 #### 選書前試做 把共享更新拆成讀取、私有計算與寫回，列允許次序。 檢查標準: 先說什麼原子，不能把高階語句自動當原子操作。 你的筆記: ________________________________ ISBN: 9781985086593 [官方免費閱讀](https://pages.cs.wisc.edu/~remzi/OSTEP/) [書目資訊與取得方式](https://unireadinglist.com/zh-tw/subjects/computer-science/operating-systems-three-easy-pieces/) ### 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說明、新倉庫和舊行號。 #### 選書前試做 選一個鎖保護的不變式，找所有能改狀態的路徑。 檢查標準: 不只報鎖名，須說明為什麼所有相關路徑需要同一把鎖。 你的筆記: ________________________________ [官方免費閱讀](https://pdos.csail.mit.edu/6.1810/2025/xv6.html) [書目資訊與取得方式](https://unireadinglist.com/zh-tw/subjects/computer-science/xv6-cox-kaashoek-morris/) ### Operating System Concepts（作業系統概念） Abraham Silberschatz; Peter Baer Galvin; Greg Gagne · 10 · 2018 商業綜合參考 什麼情況下適合讀: 需要課綱中的程序、同步、記憶體與儲存術語。 什麼情況下選別本: 把公開課件或部分練習解答當作免費全書與全部教師答案。 建議閱讀範圍: 2018第10版按標題選程序／執行緒、同步和所需記憶體管理。 限制與取捨: ISBN 9781119320913為Wiley電子產品，其他套裝及紙本配套編號不同。 #### 選書前試做 比較互斥、順序與進展三類要求。 檢查標準: 互斥可阻止重疊，卻不自動決定誰先，也不規定排程策略。 你的筆記: ________________________________ ISBN: 9781119320913 [書目資訊與取得方式](https://unireadinglist.com/zh-tw/subjects/computer-science/operating-system-concepts/) ## 開始前需要會什麼 ### 交錯是什麼？ 你的筆記: ________________________________ ### 保護多大範圍？ 你的筆記: ________________________________ ### 模型省略什麼？ 你的筆記: ________________________________ ## 六步學習計畫 - [ ] 規定機器 建議閱讀範圍: OSTEP併發引言。 要做的練習: 寫共享狀態、私有暫存器、原子事件及各自順序。 檢查標準: 不偷加未說明的語言行為。 你的筆記: ________________________________ - [ ] 追一條執行 建議閱讀範圍: 同一閱讀與原題。 要做的練習: 逐次列讀取值與寫回值。 檢查標準: 寫回用先前儲存值，不必是最新共享值。 你的筆記: ________________________________ - [ ] 覆蓋全部順序 建議閱讀範圍: 同步閱讀。 要做的練習: 列兩讀前寫約束下的六條順序。 檢查標準: 證明列舉完整而非只舉有趣例子。 你的筆記: ________________________________ - [ ] 寫不變式 建議閱讀範圍: xv6鎖及參考討論。 要做的練習: 寫整個更新須共同觀察和釋出的狀態。 檢查標準: 保護範圍由不變式決定，不由程式碼一行長短決定。 你的筆記: ________________________________ - [ ] 改變同步 建議閱讀範圍: 變式。 要做的練習: 用同一互斥鎖重算，再額外指定順序。 檢查標準: 互斥與結果確定是兩件事。 你的筆記: ________________________________ - [ ] 接真實實現 建議閱讀範圍: 同版xv6路徑或課程題。 要做的練習: 說明語言和核心機制怎樣建立假設順序。 檢查標準: 抽象軌跡正確不認證未審查的生產程式。 你的筆記: ________________________________ ## 原創例題與解析: 原創事件機：原子讀取不等於原子更新 共享x初值10。執行緒1讀入r1再寫r1+3，執行緒2讀入r2再寫2r2，事件記R1,W1,R2,W2。列R1先W1、R2先W2的所有順序及末值。 前提假設: 各次讀寫不可分，四事件順序一致，讀取最近已寫值或初值10。私有計算無共享事件，兩執行緒均完成，無其他訪問。這不是未同步C程式。 你的筆記: ________________________________ ## 改變假設，再做一題: 改變同步：互斥仍留下順序選擇 僅改同步：同一互斥鎖覆蓋各執行緒整段讀取與寫回，且都完成。剩什麼結果？再額外規定執行緒1整段先於執行緒2的交接。 你的筆記: ________________________________ ## 進入下一階段之前 - 能列舉全部順序並復現讀寫值。 - 能說明同步精確排除哪些結果。 - 能分清抽象機與真實語言／核心。 ## 答案與解釋 ### 交錯是什麼？ 保留各執行緒自身先後約束的單個事件順序，結果按該順序實際讀到的值計算。 ### 保護多大範圍？ 若不變式依賴讀改寫組合，應保護整個組合；分別鎖讀取和寫回不讓兩者成為一個更新。 ### 模型省略什麼？ 本題原子讀寫且全域性有序，計算私有；真實語言記憶體、編譯變換、故障與公平性另需說明。 ### 原創事件機：原子讀取不等於原子更新 1. R1,W1,R2,W2依次讀10、寫13、讀13、寫26。R2,W2,R1,W1依次讀10、寫20、讀20、寫23。 2. R1,R2,W1,W2與R2,R1,W1,W2均讀兩次10，最終W2寫20；R1,R2,W2,W1與R2,R1,W2,W1也讀兩次10，最終W1寫13。 3. 線上程1兩有序事件的四槽中選二，有choose(4,2)=6種，其餘給執行緒2，上述已全部覆蓋。 4. 末值集合\{13,20,23,26\}。序列得26或23，其餘因儲存的舊讀數覆蓋另一次結果而丟失更新。 六條合法交錯只產生13、20、23、26，單個事件原子不使複合更新原子。 檢驗結果: 每條用四行狀態帳復算；不能推廣給記憶體／競爭語義不同的語言執行。 ### 改變假設，再做一題: 改變同步：互斥仍留下順序選擇 1. 臨界區不能重疊；1先時10→13→26，2先時10→20→23。 2. 排除了13與20，仍有23及26，因為加法與翻倍不交換，互斥規則未選順序。 3. 額外交接後僅10→13→26。順序要求是新增條件，不能從同鎖推得。 僅互斥得\{23,26\}，加指定交接得\{26\}；原子性與確定順序不同。 檢驗結果: 分別複合兩更新函式；公平、死鎖及真實語言正確性還需實現論證。 ## 常見誤區 ### 假定語句原子 原始碼更新可能包含多個可見事件。 ### 鎖名當證明 所有相關訪問須由同一合適鎖保護完整轉換。 ### 互斥當順序 不交換的序列操作仍可有不同結果。 ## 參考來源與版本 - [OSTEP: free conceptual chapters and current online version](https://pages.cs.wisc.edu/~remzi/OSTEP/) 三部分結構提供概念與免費分章路線。 - [OSTEP: publication and revision history](https://pages.cs.wisc.edu/~remzi/OSTEP/combined.html) 1.00記錄與持續修訂的1.10不同。 - [OSTEP: concurrency introduction](https://pages.cs.wisc.edu/~remzi/OSTEP/threads-intro.pdf) 併發引言支援事件推理，數值與軌跡為原創。 - [MIT: xv 6 RISC-V revision 5, September 2025](https://pdos.csail.mit.edu/6.1810/2025/xv6/book-riscv-rev5.pdf) 固定2025 RISC-V書配可追核心。 - [Wiley: tenth-edition electronic product identity](https://www.wiley.com/en-us/operating-system-concepts-10th-edition-p-9781119320913) 精確第10版產品與配套資料不同於其他格式。 這些是本站建議的學習活動，並非大學官方作業，也不代表對每本書逐頁通讀。 [編輯與選書方法](https://unireadinglist.com/zh-tw/editorial/)