作業系統原理：從執行緒、虛擬記憶體到檔案系統｜Stanford CS111 課程總覽
CS111 是 Stanford 的作業系統原理課，分並行、記憶體管理、檔案系統三塊，共九份作業。28 份講義、九份作業說明與三年附解答的期中期末考題都公開；起始碼要能登入校內的 myth 機器，錄影在 Canvas。
29 篇文章
Stanford CS111 Operating Systems Principles 導讀
逐講讀 Stanford CS111：程序、執行緒、同步、虛擬記憶體、檔案系統與作業系統設計取捨。
系列導讀
作業系統的歷史、抽象化與三條課程主線｜Stanford CS111 第 1 堂
第 1 講沿 1940 年代共用 I/O 卡片、batch processing、multiprogramming 與個人電腦的演變，解釋 OS 的功能如何隨硬體成本與使用者需求逐層增加。
行程與執行緒的執行抽象、狀態與切換｜Stanford CS111 第 2 堂
第 2 講先定義行程與執行緒的共享／私有狀態，再用 fork、execvp、waitpid 與 thread creation 說明核心如何建立執行單位。
核心執行緒、使用者執行緒、context switch 與 dispatcher｜Stanford CS111 第 3 堂
第 3 講沿 running、blocked、ready 狀態轉移，拆解 PCB、context save/restore 與 dispatcher 如何完成一次 CPU 控制權交接。
交錯執行、race condition、atomicity 與 critical section｜Stanford CS111 第 4 堂
第 4 講逐步拆解 Too Much Milk 的失敗排程，從具體 interleaving 推導 race condition、atomicity、critical section 與正確同步條件。
mutex、condition variable 與 Mesa semantics｜Stanford CS111 第 5 堂
第 5 講用容量為 8 的環形 Pipe 證明：mutex 只提供互斥；condition variable 才能在 predicate 不成立時原子地釋放鎖並阻塞；Mesa semantics 下，wait 返回後必須用 while 重查條件。
關中斷、原子指令、spinlock 與阻塞式 lock 的實作｜Stanford CS111 第 6 堂
第 6 講從單核心關中斷一路修到多核心 v5，追蹤 guard、lock 與 wait queue，說明 atomic exchange、spin、block 與 wakeup 如何避免 race 和 lost wakeup。
Deadlock 的四個必要條件與全域鎖順序｜Stanford CS111 第 7 堂
第 7 講用 request/ownership graph 拆出 deadlock 的四個必要條件，再比較 detection、prevention 與 lock ranking；實務上最常破壞 circular wait，但代價是所有模組必須遵守同一個全域順序。
FIFO、round robin、priority 與多核心排程｜Stanford CS111 第 8 堂
第 8 講從 FIFO、round robin 與不可實作的 SRPT，推到自適應 priority queues、BSD scheduler，再處理多核心 queue contention、core affinity 與 work-conserving 的衝突。
object file、symbol、relocation、static 與 dynamic linking｜Stanford CS111 第 9 堂
第 9 講沿著 source→assembly→object→executable→process，拆解 linker 的三次掃描、symbol relocation，以及 dynamic loader 如何用 jump table 把 shared library 位址延後到啟動時解決。
allocator 介面、free list、fragmentation 與 placement policy｜Stanford CS111 第 10 堂
第 10 講從 stack 的可預測 LIFO，推到 heap 的 free lists、first/best fit 與 slabs，再比較 reference counting 和 mark-and-sweep 如何在 dangling pointers、leaks、cycles、fragmentation 間取捨。
Storage Reclamation、Reference Counting 與 GC｜Stanford CS111 第 11 堂
第 11 講的官方 PDF 與 Lecture 10 逐位元組相同；本文誠實保留此 artifact 缺口，聚焦後半的 reachability、dangling pointers、leaks、reference-count cycles 與 mark/compact GC。
可信任的定義、隔離、驗證與從不信任建立信任｜Stanford CS111 第 12 堂
第 12 講把 trust 定義為自願承受 vulnerability，區分 over-trust 與 untrustworthiness，再用 assumption、inference、substitution 分析 Linux TCB、xz attack 與 AI code policy。
位址空間、relocation、base-and-bound 與保護｜Stanford CS111 第 13 堂
第 13 講從 single-tasking 與 load-time relocation 的失敗出發，以 MMU 的 base/bound 建立 virtual/physical address spaces、透明隔離與 traps，再用 segmentation 解開單一連續區域的限制。
segmentation、共享、稀疏位址空間與配置限制｜Stanford CS111 第 14 堂
Lecture 14 的官方 PDF 與 Lecture 13 逐位元組相同；本文明示此缺口，聚焦 segmentation 如何以多組 base/bound/protection 支援 growth、sharing、compaction，以及 fixed-count、fragmentation、rigid layout 限制。
page、frame、page table、TLB 與多層頁表｜Stanford CS111 第 15 堂
第 15 講以固定大小 pages 消除跨 process external fragmentation，再拆解 x86-64 四層 page-table walk、sharing/aliasing 與 TLB，說明 translation speed、table sparsity、context switch 和 page size 的連動取捨。
Page Fault、Demand Fetching 與 Prefetch｜Stanford CS111 第 16 堂
Demand paging 只在需要時載入頁面；present bit、精確例外與可重啟指令讓核心能從 executable、zero-fill 或 backing store 安全補頁。
從 page fault 到 Clock，記憶體滿了該換掉誰？｜Stanford CS111 第 17 堂
第 17 講把 demand paging 分成 fetching 與 replacement：MIN 無法預知未來，精確 LRU 成本過高，Clock 只靠 reference／dirty bits 找夠舊的 page；active working sets 放不進 RAM 時，1% fault rate 就可能帶來約 1,000 倍 slowdown。
磁碟幾何、Interrupt 與 DMA｜Stanford CS111 第 18 堂
磁碟把機械式 seek 與 rotation 隱藏成線性 block API；現代 I/O 再用 memory-mapped registers、DMA queues 與 interrupts，讓 CPU 只負責下命令和收完成通知。
檔案抽象、配置策略與 FAT｜Stanford CS111 第 19 堂
檔案系統把耐久 byte collection 映射到磁碟 blocks；contiguous、linked 與 FAT 分別交換 locality、成長彈性、random access 與 metadata 成本。
多層 Inode、Index Walk 與磁碟排程｜Stanford CS111 第 20 堂
4.3BSD inode 用 direct、single-indirect 與 double-indirect pointers 讓 lookup depth 隨檔案大小分級；FIFO、SPTF、SCAN 與 CSCAN 則交換 seek cost、公平性與等待時間。
Block Cache、Free Bitmap 與 Delayed Allocation｜Stanford CS111 第 21 堂
Block cache 把熱索引留在 DRAM，bitmap 與保留空間維持配置選擇，fragments 和 delayed allocation 則用較晚、較完整的資訊換取 locality。
Directory Lookup、Hard Link 與 Symbolic Link｜Stanford CS111 第 22 堂
Directory 把文字名稱映射到 file-system-local i-number；hard link 共享 inode 與 reference count，symbolic link 則保存 pathname，換得跨檔案系統能力但可能形成 loop 或 dangling link。
從 fsck、Ordered Writes 到 Write-Ahead Logging｜Stanford CS111 第 23 堂
檔案系統一次操作會改動多個 block，崩潰卻可能發生在任兩次寫入之間；本講比較 fsck、ordered writes 與 write-ahead logging 如何交換復原時間、效能、耐久性與一致性。
Journaling、Transaction 與 Checkpoint｜Stanford CS111 第 24 堂
第 24 講從 WAL 入口往下拆 transaction、idempotent replay 與 checkpoint，說明一致性不等於 durability，journal 也不能取代 fsync 與備份。
Truth, Trust, and Technology——演算法、生成式 AI 與 deepfake 如何改寫信任｜Stanford CS111 第 25 堂
第 25 講把 trust 拆成假設、推論與替代三種建立方式，再檢視社群推薦、生成式 AI 與合成媒體如何放大過度信任；實務答案是保留來源、交叉驗證並協調責任。
Flash Translation Layer、Garbage Collection 與 Wear Leveling｜Stanford CS111 第 26 堂
Flash 只能逐頁 program、整個 erase unit 清除；FTL 以 out-of-place mapping 隱藏不對稱，再用 garbage collection、temperature segregation、wear leveling 與 TRIM 管理放大成本。
Trap-and-Emulate、Virtual I/O 與 Nested Page Tables｜Stanford CS111 第 27 堂
VM 把 process interface 擴成完整硬體介面；hypervisor 讓普通指令直接執行、攔截 privileged operations，並虛擬化 interrupts、I/O 與兩層位址轉譯。
用四個觀念串起並行、記憶體與儲存｜Stanford CS111 第 28 堂
第 28 講把整學期收斂成並行、記憶體、儲存三條主線，再用 virtualization、atomicity、locality、layering 四個觀念解釋作業系統如何管理共享資源。