作業系統 06–10
同步 × 死結 × 記憶體（手帳皮革本｜新版 PDF）
CH06：critical section、mutex、semaphore、monitor
CH07：經典同步題（buffer / readers-writers / philosophers）
CH08：deadlock 四條件 + 四策略
CH09-10：paging、TLB、virtual memory、thrashing
點擊翻頁開始閱讀 ↓
先問：
誰在改
共享資料？
多行程/多執行緒同時存取共享狀態，若交錯執行就會產生 race condition。核心概念是
critical section：同一時間只允許一條執行路徑進入修改共享資料。
Semaphore
可做二元/計數，控制「資源數」。
Monitor
把互斥 + 條件等待封裝成高階抽象。
一句話記憶
同步不是背 API，是確保「臨界區一次只給一個人」；工具只是實作手段。
1
互斥夠了？
還要
公平與活性
除了互斥，還要看 liveness：
deadlock（互卡）、starvation（永遠輪不到）是不同問題。
Priority inversion（常考概念）
低優先序拿著鎖 → 高優先序等鎖 → 中優先序一直插隊，讓高優先序等更久。常見解：
priority inheritance（持鎖者暫時繼承高優先序）。
CAS vs Mutex（效能直覺）
CAS 常在低到中等競爭更快；但在極高競爭下，傳統鎖機制可能反而更穩。
2
這三題是同步機制的「單元測試」：你要能說清楚共享狀態、需要哪些同步原語、以及如何避免死結/飢餓。
要點速記（只留會考的）
| 問題 |
保護的共享狀態 |
常見技巧 |
| Bounded-Buffer |
buffer 空/滿與索引 |
semaphore：empty / full + mutex |
| Readers-Writers |
readcount + 寫入互斥 |
要注意公平性（避免 writer starvation） |
| Dining Philosophers |
筷子/鎖的取得順序 |
限制同時拿起數量或固定順序破壞 cycle |
另類解法（觀念題）
transactional memory（原子交易）、OpenMP critical、functional 的 immutability，都是降低 data race 的不同路線。
3
四條件
同時成立
才會死結
死結的判斷：四個必要條件同時成立才會卡死。
處理策略（四選一）
ignore（鴕鳥）／prevention（拆條件）／avoidance（Banker，safe state）／detection + recovery（偵測後終止或搶占資源）。
4
位址翻譯核心：logical 是程式看到的，
physical 是實體位置；MMU 負責轉換。
配置方式對比
| 方式 |
優點 |
常見痛點 |
| Contiguous allocation |
概念簡單，直接切一塊連續記憶體 |
external fragmentation（空洞不連續） |
| Paging |
避免外部碎裂，配合 TLB 加速 |
page table 成本 + TLB miss 代價 |
Swapping（現代常見變形）
傳統「整個行程換出/換入」太慢；多改成 page-out / page-in（配合 paging）。行動裝置通常不做傳統 swapping，改以回收/終止策略釋放記憶體。
5
virtual memory 讓程式「看起來」有更大的記憶體；典型做法是 demand paging：用到才載入。
1page fault trap
→
2找 frame / 置換
→
3磁碟載入
→
4重啟指令
Page replacement（最常考）
FIFO（可能有 Belady anomaly）／OPT（理論最優）／LRU（符合 locality，常用近似法）。
Thrashing 與 TLB Reach
working set 放不進 frames → fault 爆炸就是 thrashing。
TLB Reach = (TLB size) × (page size)：想覆蓋 working set，得靠更大頁或多種頁大小。
6