同步工具 → 同步經典題 → 死結 → 主記憶體 → 虛擬記憶體
2026.06.15 ｜OSConcurrencyMemory
Chapter 06 · Synchronization Tools
多個行程/執行緒同時存取共享資料時，若互相交錯執行就會發生race condition（資料不一致）。
關鍵就是「critical section」：同一時間只能讓一個人進去做會改共享狀態的事情。
Mutex lock：最直覺，進入前 lock()、離開後 unlock()。
Semaphore：用 wait(P) / signal(V) 控制資源數量（二元/計數）。
Monitor + condition variable：把互斥與條件等待封裝在高階抽象中。
CAS / atomic：靠硬體原子指令做「無鎖/低鎖」保護，適合某些高競爭情境。
悲觀鎖
Mutex：先鎖起來再做，高競爭時更穩，但有鎖開銷。
樂觀 CAS
CAS：先做再比對，無/少鎖，競爭不高到中等通常更快。
Deadlock（互卡）與 Starvation（一直輪不到）是兩個不同概念。
另外還有priority inversion：低優先序拿著鎖，高優先序等鎖卻被中優先序一直插隊。常見解法：priority inheritance（讓低優先序暫時繼承高優先序）。
Chapter 07 · Synchronization Examples
這三題基本上是拿來「測」同步機制到底會不會出事：緩衝區、讀者寫者、哲學家用餐。
考試重點通常不是背程式，而是能說清楚：要保護什麼共享狀態、用哪個同步原語、怎麼避免死結/飢餓。
Bounded-Buffer：empty/full/mutex
Readers-Writers：readcount + 互斥
Dining Philosophers：避免 cycle
Producer/Consumer：共享 buffer
RW：公平性設計
DP：拿鎖順序
Transactional Memory：把一段記憶體讀寫當成「交易」；成功就 commit，失敗就 rollback。
OpenMP：用 #pragma omp critical 把區塊當成 critical section。
Functional：資料不可變（immutable），減少共享可變狀態，自然降低 data race。
Chapter 08 · Deadlocks
死結不是「很慢」而已，是：四個必要條件同時成立才會卡死。拆掉其中任一條就能避免。
1) Mutual exclusion（資源不可共享）
2) Hold and wait（手上拿著還想再等）
3) No preemption（不能硬搶走）
4) Circular wait（等待形成環）
Ignore
➞
Prevention
➞
Avoidance（Banker）
➞
Detection + Recovery
Prevention：用規則「讓四條件不可能同時成立」（例如固定拿鎖順序打掉 circular wait）。
Avoidance：每次分配前都判斷系統是否仍在safe state（銀行家演算法）。
Detection：允許死結發生後再偵測；接著terminate 或 resource preemption 做恢復。
Chapter 09 · Main Memory
Logical address 是程式看到的；Physical address 是記憶體實際位置。
MMU 負責翻譯：在 paging 系統裡最常見公式是
physical = frame_number × page_size + offset。
Contiguous
first-fit / best-fit / worst-fit；問題是 external fragmentation。
Paging
把記憶體切成 page/frame；避免外部碎裂，但會有page table / TLB成本。
碎裂記住一句：internal 是「分到但用不完」；external 是「有空但不連續」。
經典 swapping：把整個行程暫時換出到 backing store，再換回來；但現代多改成page-in/page-out。
行動裝置通常不做傳統 swapping（快閃寫入次數/吞吐限制），改用要求 App 釋放記憶體或直接終止（並保存狀態）。
Chapter 10 · Virtual Memory
Demand Paging：一次 page fault 會發生什麼
1存取到不在記憶體的 page → 觸發 trap（page fault）。
2OS 檢查位址合法性，不合法就終止；合法就找 free frame。
3排程磁碟 I/O 把 page 載入；更新 page table / TLB。
4重新啟動被中斷的指令，程式「感覺」像一切正常。
FIFO：最簡單，但可能有 Belady anomaly。
OPT：理論最優（需要知道未來），通常用來當比較基準。
LRU：利用 locality 假設「最近用過的還會再用」，實作可用近似法。
Thrashing：一直 fault 就不是你寫爛，是系統在抖
Working set 放不進可用 frames → page fault 爆炸 → CPU 利用率反而下降：這叫 thrashing。
典型對策：增加 frames、降低 multiprogramming、或用 working-set / page-fault frequency 控制記憶體配置。
TLB Reach：(TLB Size) × (Page Size)。理想情況是每個行程的 working set 都能被 TLB 覆蓋。
程式結構也會影響 fault：例如 2D 陣列的存取順序（row-major vs column-major）會讓 page fault 數量差很多。
I/O interlock：某些 I/O 期間頁面必須被pin住，避免被換出。
最後收斂：一張腦內地圖
Concurrency：先處理互斥（CS），再處理公平/活性（starvation、priority inversion）。
Deadlock：四條件 + 四方法（預防/避免/偵測/恢復）。
Memory：主記憶體翻譯（MMU, paging, TLB）→ 虛擬記憶體（demand paging、replacement、thrashing）。