OS 心智地圖

OS 心智地圖

作業系統 · 周志遠 10910 期中、11210 期末 Q1、Q6、Q12 · 2026-11-08

這份地圖照故事分章。第 0 章是最簡單的電腦。後面每一章，先寫這台電腦（或前一章的解法）碰到的問題，再寫解決它的模型，最後把從模型推出來的結論寫成問答。

第 0 章

最簡單的電腦

出處：OSC（Silberschatz《Operating System Concepts》10e）§1.2 computer-system organization、§3.1 process concept。

模型

  1. 硬體有三樣：CPU、memory、devices（例：鍵盤、disk、網卡、timer）。
  2. memory 放 instructions 和資料。每個 byte 有一個 physical 位址。
  3. CPU 是執行器：不斷「從 memory 讀 PC（program counter）指的 instruction → 執行 → 更新 PC」。這是你在 Q1 的說法。
  4. CPU 的狀態只有 register：PC 和 registers。registers 裡包含 SP（stack pointer），它存 stack 頂端的位址。
  5. 每個 device 有一個 device controller。CPU 讀寫 device controller 的 register，來控制 device。device 做完事，送 interrupt 通知 CPU。CPU 存下目前的 PC，跳到 kernel 的 handler 執行。硬體怎麼做到，見下面摺疊的段落。
  6. process 是一個執行中的程式。它包含兩部分：memory 裡它的 code、data、heap、stack，以及它的 PC 和 registers。
  7. memory 裡可以同時放好幾個 process。CPU 一次執行一個。一個 process 跑完，才換下一個。
  8. OS（kernel）也只是 memory 裡的一段程式。

這台電腦什麼都沒有保護：任何程式都能執行任何 instruction，也能讀寫任何 physical 位址。

interrupt-request line：device 做完事，用它送 interrupt 給 CPU CPU執行器 讀 PC 指的 instruction → 執行 → 更新 PC PC下一條 instruction 的位址 registers運算中的值 SPstack 頂端的位址 CPU 的狀態只有 register 一次執行一個 process（現在是 U） physical 位址 instruction、資料 Memory每個 byte 有一個 physical 位址 位址 0 kernel（OS） interrupt vector：handler 位址的表 handlers 和其他 kernel code process U執行中 codePC 指在這裡 data heap stack process V等 U 跑完才執行 code、data、heap、stack 空的 位址 最大 Devices 鍵盤 device controller data status control disk device controller data status control 網卡 device controller data status control timer device controller data status control CPU 讀寫 device controller 的 register，來控制 device

沒有 mode bit（第 1 章）、沒有 MMU（memory-management unit，第 3、4 章）：任何程式都能執行任何 instruction、讀寫任何位址。

interrupt、exception、system call 在硬體上怎麼做

出處：OSC §1.2.1 interrupts（圖 1.5 是 Intel 的 event-vector table）；RISC-V 規格書（unprivileged ISA）§1.6。

用詞：本地圖的 trap，指硬體把控制權交給 kernel 的 handler 的那個動作。觸發它的原因有三種：interrupt、exception、system call。這和 RISC-V 規格書的用法一樣。OSC 的 trap（也叫 exception）只指 software 產生的 interrupt：錯誤和 system call。所以讀 OSC 時，看到 trap，要對回本地圖的「exception 或 system call」。

  1. device controller 要通知 CPU 時，會拉起 interrupt-request line。這是 CPU 上的一條線。
  2. CPU 每執行完一條 instruction，就檢查這條線一次。
  3. 線被拉起時，CPU 讀出 interrupt 的編號，用它當 index 去查 interrupt vector。interrupt vector 是 memory 裡的一張表，每一項是一個 handler 的位址。
  4. 硬體把目前的 PC 存到 stack 或專用的 register（看 CPU 而定），再把 PC 設成表裡那一項的位址。之後 CPU 照常「讀 PC → 執行 → 更新 PC」，但執行的已經是 handler。
  5. handler 先存它會改到的 registers，再處理事情，然後恢復 registers。最後它執行 return-from-interrupt，回到原來的程式。
  6. exception 和 system call 也用同一套機制。差別只在誰觸發，以及做完回到哪一條：
原因誰觸發例子handler 做完，回到哪一條
interruptdevice，和目前的 instruction 無關timer、disk 讀完、鍵盤下一條（目前這條已經執行完）
exception目前這條 instruction 執行時出了問題除以零、page fault（要用的頁不在 memory，第 5 章）、在 user mode 執行 privileged instruction出問題的那一條。page fault 處理完會重新執行它；除以零時，kernel 通常直接結束這個 process
system calluser 程式故意執行 trap 指令x86-64 的 syscall、RISC-V 的 ecall、32-bit x86 Linux 的 int 0x80trap 指令的下一條

例：OSC 圖 1.5 是 Intel 的 event-vector table。0 號是除以零，14 號是 page fault，32–255 號給 device 的 interrupt。int 0x80 會故意觸發 128 號。x86-64 的 syscall 指令不查這張表：它直接跳到 kernel 開機時存在一個專用 register 裡的位址。兩種做法效果一樣，目的地都由 kernel 決定。

定理

1.問：interrupt 會在一條 instruction 執行到一半時發生嗎？

答：不會。CPU 每執行完一條 instruction，才檢查 interrupt-request line。

2.問：為什麼 page fault 處理完，要重新執行同一條 instruction，system call 卻回到下一條？

答：page fault 時，那條 instruction 要的資料不在 memory，所以它沒有做完。trap 指令則已經做完了，它要的服務就是 handler 做的事。

3.問：「關 interrupt」關掉的是什麼？

答：CPU 暫時不理 interrupt-request line。exception 和 system call 不受影響，因為它們不是從這條線來的。但 timer interrupt 會被擋住（第 1 章定理 3）。

三類問題

出處：OSC §1.1。這一節從兩個角度看 OS。從 user 看，OS 讓電腦好用。從系統看，OS 有兩個角色：resource allocator（分配 CPU、memory、device）和 control program（控制 user 程式的執行，避免錯誤和不當的使用）。

類問題OSC 的對應
保護一個 process 出錯或惡意，不能影響 OS 和別的 process。control program
效率硬體和時間固定時，做更多有用的事。CPU 時間、memory 空間、device 都是要分配的資源。resource allocator
方便程式不用知道硬體的細節，也不用知道還有別的 process。例：每個 process 的 logical 位址都從 0 開始；同一份 source code，換一台 OS 重新編譯就能跑。user 的角度
  • 有些設計是在兩類之間取捨。例：static linking 換到「帶到哪台機器都能跑」（方便），代價是檔案大、每個程式都多一份 library（效率）。
  • 有些問題，是前一章的解法帶來的。例：第 4 章每次存取都要查 page table，多讀一次 memory。所以第 5 章加了 TLB。

你的原話：「OS 的每個 feature/design 都是爲了解決 naive 的電腦實際上會碰到的問題的。」

第 1 章

mode bit 與 trap

問題（保護）

在第 0 章的電腦裡，任何程式都能執行任何 instruction。一個壞程式可以關掉 interrupt、直接操作 device、改掉 interrupt vector。它也可以一直不讓出 CPU。

模型

出處：OSC §1.4.2 dual-mode operation、§1.4.3 timer、§2.3 system calls。

  1. CPU 多一個 mode bit。mode bit 是 0 時是 kernel mode，是 1 時是 user mode。
  2. 會影響別的 process 或整台機器的 instruction，設成 privileged instruction。privileged instruction 只能在 kernel mode 執行。在 user mode 執行它，CPU 會產生 exception。
  3. 只有 trap 能把 mode bit 從 1 改成 0。trap 就是第 0 章的 interrupt 機制，再多做一步：硬體把 PC 設成 trap 入口的同時，把 mode bit 設成 0。trap 入口就是 interrupt vector 裡的位址，由 kernel 開機時填好，只能在 kernel mode 設定。
  4. system call、interrupt、exception 都經過 trap 進 kernel。kernel 做完以後，用 return-from-interrupt 把 mode bit 設回 1，回到 user 程式。
  5. timer 每隔一段時間送一次 interrupt。所以不管 user 程式做什麼，kernel 都會定期拿回 CPU。
user mode · mode bit = 1 fd（file descriptor）：open 回傳的整數 kernel mode · mode bit = 0 user coderead(fd, buf, n) libc 的 read()syscall 號碼放進 register trap 指令x86-64 的 syscall read() 回傳繼續執行 user code 直接執行 privileged instruction → CPU 產生 exception（第一層檢查） 硬體一次做完：存下 PC、mode bit ← 0、PC ← trap 入口 trap 入口開機時 kernel 填好 syscall table[號碼] → handler sys_read：先驗證 fd、權限、buf 位址（第二層檢查） 再用 privileged instruction 操作 device，把資料複製到 user 的 buf returnprivileged 硬體：mode bit ← 1、PC 回到原處 trap 的其他來源： timer interrupt device interrupt（IO 完成） exception（除以零、page fault）

定理

1.問：怎麼判斷一條 instruction 要不要是 privileged？

答：想一想：讓 user 隨意執行它，會不會搶走 kernel 的控制權，或繞過 kernel 的檢查、存取別人的資源？會，它就要是 privileged。進 kernel 的入口（trap 指令）本身不是 privileged。

例：設定 timer、關 interrupt 會搶走控制權。清除 memory、修改 device-status table（kernel 記錄每個 device 狀態的表）、存取 IO device 會繞過檢查。讀目前的時間、執行 trap 指令都不是 privileged。

2.問：user 程式切到 kernel mode 以後，能執行任意的 privileged instruction 嗎？

答：不能，因為 user 的 code 不會在 kernel mode 執行。mode bit 變成 0 時，PC 已經在 trap 入口，接下來執行的是 kernel 的 code。user 能執行 trap 指令，但選不了 trap 後跳到哪裡。所以 user 要做 privileged 的事，只能用 system call 請 kernel 做。kernel 先驗證，再做。

你的原話：「本質上是，執行 priviledge mode 的 instructions，是作業系統本身，因此保證不是惡意的 instructions。」

3.問：一個 process 進入無窮迴圈，永遠不發 system call。kernel 怎麼拿回 CPU？

答：靠 timer interrupt。所以關 interrupt 的指令一定要是 privileged。不然一個 process 關掉 interrupt 以後，就能一直占著 CPU，別的 process 永遠跑不到。

4.問：既然要保護，為什麼不把 load／store 也設成 privileged？

答：每次進 kernel 都有成本：切 mode bit、存 PC、驗證參數。load／store 是最常用的 instruction。如果它是 privileged，每條 load／store 都要用 system call 進 kernel，程式會慢很多。這是保護和效率的取捨。memory 的保護改用第 4 章的 page table 來做。

5.問：把 IO 指令都設成 privileged，device 就安全了嗎？

答：不一定。CPU 讀寫 device controller 的 register 有兩種方法。PMIO（port-mapped I/O）用 in／out 指令，這種指令可以設成 privileged。MMIO（memory-mapped I/O：device 的 register 對到一段位址）用普通的 load／store，而定理 4 說 load／store 不能是 privileged。所以 MMIO 要靠第 4 章的 page table 來擋。

第 2 章

很多份 PC

問題（效率）

在第 0 章的電腦裡，一個 process 跑完，才換下一個。process 等 IO 時（例：讀 disk 約 10 ms），CPU 只能閒著。

模型

出處：OSC §3.1 的 PCB、§3.2 的 context switch、§4.1 thread 的概念、§4.3 multithreading models。

  1. process 用 system call 請 kernel 做 IO。kernel 啟動 IO 以後，不等它做完：kernel 把這個 process 的 PC 和 registers 存進 memory，再載入另一個 process 的 PC 和 registers。IO 做完時，device 送 interrupt；kernel 之後再把原來的 process 載回來。
  2. 存放 PC 和 registers 的地方，是 kernel 放在 memory 裡的兩種資料結構：
    • PCB（process control block）：kernel 替每個 process 存一個。它記錄 process 的狀態、存下來的 PC 和 registers、memory 管理的資訊（例：page table 在哪），以及開啟的檔案。
    • TCB（thread control block）：kernel 替每條 kernel thread 存一個。它記錄存下來的 PC、registers 和 kernel stack。
  3. thread 是 process 裡的一份 PC 和 registers。一個 process 可以有很多條 thread。同一個 process 的 thread 共用這個 process 的 memory。
  4. kernel 存的那幾份是 TCB，scheduler（kernel 裡決定下一個執行誰的程式）只從 TCB 裡挑。thread library 也可以在 user space 存幾份，這就是 user thread。kernel 看不到 user thread：CPU 的狀態只有 register，thread 只是 memory 裡的資料，而 kernel 沒有記錄 user thread（第 0 章）。
  5. user thread 怎麼對到 kernel thread，有三種模型：one-to-one、many-to-one、many-to-many。
CPU 一次只有一份 PCu2 的下一條指令 registersu2 的值 context switch （要進 kernel） kernel 區 TCB：kernel 看得到的 thread T1 · 屬於 U存好的 PC、registers、kernel stack T2 · 屬於 V存好的 PC、registers、kernel stack T3 · 屬於 W存好的 PC、registers、kernel stack scheduler 挑一個 TCB 載入 CPU N:1 process U 的 user space thread library 的表（kernel 看不到） u1 · 存好的 PC、SP u2 · 正在 T1 上跑 u3 · 存好的 PC、SP library 自己換 PC、SP 不進 kernel、不算 context switch

定理

1.問：為什麼建立 user thread 比建立 kernel thread 快？

答：建立 user thread，只是在 thread library 的表裡加一列，不用 system call。建立 kernel thread，要用 system call 進 kernel 建 TCB。

2.問：在 user thread 之間切換，要 context switch 嗎？

答：不用。context switch 是 kernel 換 TCB：先進 kernel，把 PC、registers 存回 TCB，再載入另一個 TCB。切換 user thread，是 thread library 在 user space 換 PC 和 SP，不進 kernel。

3.問：在 many-to-one 下，一條 user thread 發出會 block 的 system call（例：讀 disk）。同一個 process 的其他 user thread 還能跑嗎？

答：不能。它們共用唯一的一條 kernel thread。那條 kernel thread block 以後，scheduler 不會選它，對到它的 user thread 全部一起停。

4.問：one-to-one 為什麼不能開無限多條 thread？

答：每條 user thread 都要一個 TCB 和一個 kernel stack，它們佔 memory 的 kernel 區。所以 thread 的數量有上限。

5.問：many-to-many 的代價是什麼？

答：要決定哪條 user thread 對到哪條 kernel thread，thread library 和 kernel 都要參與。所以實作複雜，執行時的成本也比較高。

6.問：什麼情況下，many-to-one 的 CPU 使用率比 one-to-one 高？

答：單核、CPU-bound、不做 IO 時。不做 IO，many-to-one 就不會 block。剩下的差別只有切換：many-to-one 切換不進 kernel，one-to-one 切換要進 kernel。一定要單核，是因為 many-to-one 只有一條 kernel thread，一次只能用一個 core；多核時，one-to-one 能讓很多條 thread 同時在不同的 core 上執行。

你的原話（many-to-one 的程式搬到多核會不會變快）：「實際上同個時間點，還是只有一個 user thread 會被執行。」

第 3 章

位址在哪一步定死

問題（方便、效率）

在第 0 章的電腦裡，程式裡的位址就是 physical 位址。這帶來三個問題：

  1. 寫程式時，不知道程式會被放在 memory 的哪裡。兩個程式可能要用同一段位址。（方便）
  2. 每個程式都要用 library（例：libc）。每個 executable 都複製一份，disk 和 memory 都會浪費。（效率）
  3. 程式如果寫死某台 OS 的細節（例：syscall 號碼），換一台 OS 就要重寫。（方便）

模型

出處：OSC §2.5 linkers and loaders、§2.6 why applications are operating-system specific、§9.1.3 address binding。

  1. 程式從 source code 到執行，要經過三步：
    • compiler 把 source code 編譯成 object file。
    • linker 解符號（把函式和全域變數的名字換成位址），再把 object file 和 library 合成 executable。
    • loader 把 executable 從 disk 載入 memory。
  2. 程式裡有三樣東西要定下來：位址、用到的 library、這台 OS 的細節。每一樣都可以早點定死，也可以延後到後面的步驟。越晚定死，越有彈性。代價是後面的步驟要多做事，或者要更多硬體。
  3. 位址有三個時機（address binding）：
    • compile-time binding：compiler 直接寫 physical 位址（absolute code）。起點改了，就要重新編譯。
    • load-time binding：compiler 寫相對於起點的位址（relocatable code）。loader 載入時加上起點。之後位址就不能動。
    • execution-time binding：指令裡留著 logical 位址。MMU（memory-management unit，CPU 裡轉譯位址的硬體）每次存取時，才把它轉成 physical 位址。程式在執行中也能搬動。
  4. library 有兩個時機：
    • static linking：linker 在 build 時，把 library 的 code 複製進 executable。
    • dynamic linking：linking 延後到執行時。executable 裡只留 stub。執行時，dynamic linker 找到 library，把 stub 換成 library 函式的位址。
  5. OS 的細節：source code 只用 POSIX 規定的函式，例：read()。POSIX 是一份 OS 的 API（application programming interface：函式的名字、參數、行為）標準。這台 OS 的 ABI（application binary interface：syscall 號碼、參數放在哪個 register、executable 的格式）到編譯時才定下來。
build time load time run time source.c只用 POSIX 名字 object .osymbol 還沒解 executable放在 disk memory image載入 memory CPU 執行每個位址經 MMU 轉譯 compiler linker loader 執行 static：libc 的 code 複製進來 → 檔案大 dynamic：只留 stub → 檔案小 dynamic linker（執行時） 找 libc.so：memory 有就共用，沒有就載入 這台機器沒有 → library not found 越晚定死 → 越能搬、越需要硬體 compile-time binding compiler 直接寫死 physical 位址 load-time binding loader 載入時加上起點，之後不能動 execution-time binding MMU 每次存取時才轉譯

定理

1.問：POSIX 是什麼？為什麼換一台支援 POSIX 的 OS，程式只要重新編譯，不用重寫？

答：POSIX 是一份 OS 的 API 標準。source code 只依賴 POSIX 的函式名字，這台 OS 的 ABI 到編譯時才定下來。所以換 OS 時，重新編譯就會換成新 OS 的 ABI。

2.問：用 dynamic linking 時，executable 會比用 static linking 時小嗎？

答：會。static linking 把 library 的 code 複製進 executable，dynamic linking 只留 stub。

3.問：用 dynamic linking 時，compiler 要做什麼？OS 在執行時要做什麼？

答：compiler 要放 stub。執行時，OS 要找到 library：library 已經在 memory 裡，就直接用那一份；不在，就先載入 memory，再 link。

4.問：在一台機器上編譯，拿到另一台機器執行。為什麼用 static linking 不會出現「library not found」？

答：static linking 在 build 時，已經把 library 複製進 executable。dynamic linking 要到執行時才找 library。另一台機器沒有那個 library，就找不到。

5.問：系統把 libc 更新到新版。程式要重新編譯，才會用到新版嗎？

答：用 dynamic linking 的不用：下次執行時，dynamic linker 載入的就是新版。用 static linking 的要重新 link，因為舊版已經複製在 executable 裡。

你的原話：「除非是破壞式更新」。新版的 ABI 如果不相容，用 dynamic linking 的程式也要重新編譯。

6.問：什麼情況下，compile-time binding 最好？

答：簡單的系統，不需要動態的 memory 管理（例：共用 page、virtual memory）。這時程式不用搬，compile-time binding 最簡單，執行時也不用轉譯。例：只跑一個固定程式的嵌入式系統。

7.問：dynamic linking 能配合 load-time binding 嗎？

答：不能。library 的位址要到執行時才定下來，但 load-time binding 在載入時就把位址定死了。所以只有 execution-time binding 配合得上。execution-time binding 怎麼做，由第 4 章回答。

第 4 章

paging

問題（保護、效率、方便）

  1. 保護：在第 0 章的電腦裡，程式能讀寫任何 physical 位址，包括 kernel 和別的 process 的 memory。第 1 章的 mode bit 擋不了這件事，因為 load／store 不能是 privileged（第 1 章定理 4）。
  2. 效率：load-time binding 讓程式能放在任何起點，但整個程式要放在連續的 memory。程式來來去去以後，空的 memory 會碎成很多小洞。小洞加起來夠大，卻放不下一個程式。這叫 external fragmentation。
  3. 方便：第 3 章說，dynamic linking 需要 execution-time binding。execution-time binding 要怎麼做？

模型

出處：OSC §9.3 paging。

  1. logical 位址空間切成大小固定的 page。physical memory 切成同樣大小的 frame。
  2. CPU 發出的 logical 位址切成 [p | d]。p（page number）表示第幾個 page，d（offset）表示 page 裡的第幾個 byte。
  3. MMU 每次存取，都用 page table 把 p 換成 f（frame number），再送出 physical 位址 [f | d]。d 不變。
  4. page table 是 p → f 的對應。每個 process 一張，放在 memory 的 kernel 區。
  5. page table 的一項叫 PTE（page table entry），記錄 f 和 valid bit。valid bit 是 0，表示這頁現在不在 memory，或者沒用到。
  6. CPU 裡的 PTBR（page-table base register）存目前這個 process 的 page table 的起點。改 PTBR 是 privileged instruction。
logical 位址 p d MMU用 page table 把 p 換成 f physical 位址 f d d 不變 process U logical 位址 0 → 最大 frames physical memory process V logical 位址 0 → 最大 U 的 page table V 的 page table 0 · code 1 · data沒用到 2 · heap 3 · 沒用到（invalid） 4 · 沒用到（invalid） 5 · libc 6 · 共享區 7 · stack 0 · code 1 · data 2 · heap（在 disk） 3 · 沒用到（invalid） 4 · 沒用到（invalid） 5 · libc 6 · 共享區 7 · stack f0 kernel f1 page tables f2 U code f3 V data f4 libc（共用） f5 U heap f6 共享區 f7 V code f8 空 f9 U data f10 V stack f11 U stack disk：V 的 heap 頁 每條線是一個 PTE。 兩條線指到同一個 frame：共用。 虛線：valid = 0， 這一頁在 disk 上。

定理

1.問：一個 process 為什麼存取不到 kernel、別的 process、MMIO 的 memory？

答：它的 page table 裡，沒有對到那些 frame 的 PTE。MMU 每次存取都查 page table，所以這個 process 發出的任何位址，都到不了那些 frame。page table 放在 kernel 區，改 PTBR 又是 privileged，所以 user 改不了自己的對應。

2.問：paging 怎麼解決 external fragmentation？

答：每一頁都可以放在任何一個空的 frame，不用連續。所以只要空的 frame 數量夠，就放得下。

3.問：為什麼 page size 一定是 2 的次方？

答：MMU 每次存取都要把位址分成 p 和 d。page size 是 2 的次方時，只要取高位和低位的 bits，不用運算。不是 2 的次方，就要做除法和取餘數，而且每次存取都要做，太慢。

你的原話：「如果確保每個 index 和 page 裏面的 bytes 是 1-1 and onto，那麽 page size = 2^s」（s 是 d 的 bits 數）。

4.問：位址的 bits 不變時，page 變大，PTE 的數量和 logical 位址空間會怎麼變？

答：d 在轉譯時不變，所以 page size = 2 的（d 的 bits）次方。page 變大，就是 d 變寬、p 變窄，所以 PTE 變少。總 bits 不變，所以 logical 位址空間不變。

5.問：page 變大，memory 的使用率會怎麼變？

答：下降。每段資料的最後一頁通常用不滿，這塊浪費叫 internal fragmentation。page 越大，浪費越多。

6.問：shared memory 和 message passing，什麼時候要用 system call？資料量大時，哪個比較快？

答：兩張 page table 指到同一個 frame，就是共用。shared memory 在建立時，要用 system call 進 kernel，改兩邊的 page table；之後的讀寫都是普通的 load／store。兩邊要協調讀寫順序時（課本叫 synchronization），也可能要用 system call。message passing 每次 send／recv 都要進 kernel：資料先複製到 kernel buffer，再複製給對方。複製的時間和資料量成正比，所以資料量大時，shared memory 比較快。shared library 在 memory 裡只放一份，也是同樣的道理。

7.問：load-time binding 的系統要支援 virtual memory。一頁被 swap out 以後，再 swap in 時有什麼限制？

答：只能放回原來的 physical 位置，因為 load-time binding 把 physical 位址寫死在指令裡了。execution-time binding 只要改那一個 PTE，這頁就能放到任何 frame。

第 5 章

三條路徑

問題（效率）

  1. 第 4 章的 MMU 每次存取都要查 page table，而 page table 放在 memory 裡。所以每次存取都變成讀兩次 memory：一次讀 PTE，一次讀資料，速度慢了一倍。
  2. 在第 0 章的電腦裡，整個程式都要放進 memory。memory 放不下的程式不能跑，memory 裡也放不了幾個 process。

模型

出處：OSC §9.3.2 hardware support、§10.1–10.2 virtual memory 和 demand paging。「memory 是 disk 的 cache」出自 P&H（Patterson & Hennessy《Computer Organization and Design》）§5.7。

  1. TLB（translation lookaside buffer）是 MMU 裡的一個小 cache，存最近用過的 p → f。也就是說，TLB 是 page table 的 cache。
  2. 只有用到的頁放在 memory，其他頁放在 disk 的 swap 區。PTE 的 valid bit 記錄這一頁在不在 memory。也就是說，memory 是 disk 的 cache。這叫 virtual memory。
  3. 一次 memory 存取，會走三條路徑中的一條。時間用這個量級：查一次 TLB 約 10 ns，讀一次 memory 約 100 ns，處理一次 page fault 約 10 ms（10⁷ ns）。
路徑發生什麼事時間
TLB hit查 TLB 得到 f，讀一次 memory約 10 + 100 ns
TLB miss用 PTBR 讀 memory 裡的 PTE，填回 TLB，再讀資料約 10 + 100 + 100 ns
page faultvalid bit 是 0。CPU 產生 exception，經 trap 進 kernel 的 page fault handler。handler 從 disk 搬一整頁到空的 frame、更新 PTE，再重新執行那條 instruction約 10⁷ ns
  1. EAT（effective access time）是一次存取時間的期望值：每條路徑的時間 × 它發生的機率，全部加起來。

    你的原話：「就是期望值嘛」

CPU core 發出的是 logical 位址 MMU（CPU 裡的硬體） logical p d TLBpage table 的 cache p=8 → f=2 p=3 → f=7 f d physical（d 不變） PTBR page table 起點 Memory kernel 區 page table pfvalid 821 5–0 page fault handler kernel code frames 2 3 4 5 6 空 位址 = f × page size + d Disk swap 區：不在 memory 的頁 一次搬一整頁，約 10 ms 用 p 查 TLB 讀資料 資料回到 CPU TLB hit · 約 110 ns miss 讀 PTE 填回 TLB TLB miss · 約 210 ns trap 從 disk 搬一整頁進空的 frame page fault · 約 10⁷ ns：更新 PTE，重新執行那條 instruction

定理

1.問：page 變大，TLB miss rate 會怎麼變？

答：下降。TLB 的一個 entry 記一整頁的對應，所以 TLB 一次能涵蓋的範圍是「entries 數 × page size」，這叫 TLB reach。page 變大，TLB reach 就變大。程式一段時間內反覆用到的頁（working set，第 7 章），更容易落在 TLB reach 裡。

2.問：page 變大，page fault rate 會怎麼變？

答：下降。一次 page fault 會搬一整頁進來，page 越大，一次帶回的資料越多。程式有 spatial locality（用了一個位址，很快會用附近的位址），所以接下來要用的資料，很可能就在剛搬進來的這一頁。

3.問：page 變大，處理一次 page fault 的時間會怎麼變？

答：變長，因為每次要從 disk 搬更多資料。

4.問：page fault 要多少次存取才發生一次，EAT 才不會變慢超過 10%？

答：先不算 TLB。EAT ≈ 100 ns +（page fault 率）× 10⁷ ns。要讓（page fault 率）× 10⁷ ns < 10 ns，page fault 率就要小於 10⁻⁶，也就是一百萬次存取最多 fault 一次。從這個式子也看得出來：page fault 率減半，和每次 page fault 的時間減半，效果一樣。

5.問：算 EAT 時，一次存取要查幾次 TLB？

答：TLB hit 和 TLB miss 都只查一次：查 TLB →（miss 時讀 PTE）→ 讀資料。page fault 時，handler 做完要重新執行那條 instruction（第 0 章定理 2），所以會從查 TLB 開始再走一次。

6.問：換 process 時，TLB 要怎麼處理？

答：PTBR 要換成新 process 的 page table。TLB 的 entry 如果沒有記 pid（process identifier，每個 process 的編號），舊 process 的 p → f 對新 process 是錯的，所以 TLB 要整個清掉。換 process 以後，前幾次存取都會是 TLB miss。

第 6 章

page table 的結構

問題（效率：空間）

第 4 章的 page table 是一整張陣列，用 p 當 index。第 p 個 PTE 的位址 = PTBR + p × (PTE 的大小)，也就是從陣列取第 p 項。所以：

  1. 每一個可能的 p 都要有一個 PTE，連沒用到的空洞也要有。
  2. 整張表要放在連續的 memory。中間斷開，上面的公式就錯了。

例：32 bits 位址、4 KB page、PTE 4 B。p 的 bits = 位址的 bits − log₂(page size) = 32 − 12 = 20 bits。所以表有 2²⁰ × 4 B = 4 MB，要 1,024 個連續的 frame。64 bits 位址、PTE 8 B 時，表要 2⁵² × 8 B = 32 PB。

模型

出處：OSC §9.4 structure of the page table。

page table 是 p → f 的對應。四種結構只差在用什麼當 index。index 決定兩件事：表有多大，以及 TLB miss 時要讀幾次 memory。

結構用什麼當 index存了哪些TLB miss 時讀幾次 memory（32 bits／64 bits）
一整張p每一個可能的 p1／1
hierarchicalp 切成幾段，一段查一層表。第一層叫 outer page table，下一層叫 inner page table只有用到的區段才建表2／6
hashedhash(p)，沿著串列比對 p只存用到的 p約 1／約 1
inverted反過來用 f。第 f 個 entry 記 (pid, p)每個 frame 一個 entry，全機一張要搜尋整張表
一整張 page table p 直接當 index logical 位址 d · 12 bits frame f一頁 4 KB 第 d 個 byte：要的資料 p · 20 bits：查第幾個 PTE PTBR + p × 4 B PTBR 是表的起點 表要放在連續的 frames： 1024 個 frame 排在一起 TLB miss 時：讀表 1 次 64 bits：2⁵² 個 PTE × 8 B = 32 PB page table一整張，每個 process 一張 0 → f 5 p → f invalid、invalid、invalid ⋯ 沒用到的空洞也要佔 PTE 2²⁰ − 1 → f 11（stack） 2²⁰ 個 PTE × 4 B = 4 MB f
hierarchical page table p 切成幾段，一段查一層 logical 位址 d · 12 bits frame f一頁 4 KB 第 d 個 byte：要的資料 p1 · 10 bits p2 · 10 bits PTBR → 第 p1 個 PTE PTBR 指向 outer page table 每張表剛好 1 頁， 可以放在任何一個 frame TLB miss 時：每一層讀 1 次 64 bits：要 6 層 每頁只放得下 512 個 PTE（9 bits） p 有 52 bits → 切成 6 段 中間還有 4 層，圖上沒畫 outer page table剛好 1 頁，1024 個 PTE 0 → inner 0 1 ⋯ 1022 null：沒用到， 不建 inner page table 1023 → inner 1023 inner 01 頁 0 → f 5 p2 → f ⋯ inner 10231 頁 ⋯ 1023 → f 11
hashed page table 用 hash(p) 找，只存用到的頁 logical 位址 d · 12 bits frame f一頁 4 KB 第 d 個 byte：要的資料 p · 20 bits hash(p) = k CPU 計算，不用讀 memory 沒有碰撞：讀 1 次就拿到 f 每多一個碰撞：多讀 1 次 位址有幾 bits，查法都一樣 buckets 0 k ⋯ 最後一個 p 7 · f 3 · • p · f p 不同：沿 next 走 p 相同：拿到 f 一個元素 = (p, f, next) 表裡只有用到的 page， 空洞完全不佔位置 例子程式用到 300 頁 → 約 300 個元素
inverted page table 反過來用 f 當 index logical 位址 d · 12 bits frame f一頁 4 KB 第 d 個 byte：要的資料 pid p · 20 bits pid 不在位址裡：CPU 知道目前是哪個 process 找 (pid, p) 從第 0 個 entry 往下逐一比對 大小只看 physical memory： 1 GB ÷ 4 KB = 2¹⁸ 個 entry 所有 process 共用這一張 最多要比對 2¹⁸ 個 entry inverted page table全機一張：第 f 個 entry 記 frame f 裡是誰的哪一頁 frame 0 · kernel frame 1 · (V, 5) frame 2 · (U, 0) frame 3 · (W, 2) ⋯ 逐一比對 (pid, p) frame i · (U, p)：相同 ⋯ 一直到 frame 2¹⁸ − 1 f = i

共用的設定：page 4 KB；一個 PTE 在 32 bits 時 4 B、64 bits 時 8 B；physical memory 1 GB。例子程式只用位址空間的最底部（code、data、heap）和最頂部（stack），中間都沒用到。真實的 x86-64 只用 48 bits 位址，所以是 4 層。hierarchical 圖的 inner 0、inner 1023，是 outer page table 第 0 個、第 1023 個 PTE 指到的 inner page table。

定理

1.問：page table 太大時，為什麼要用這些結構？

答：一整張 page table 大到要很多個連續的 frame。paging 已經替程式解決過同樣的問題：page 可以散放在任何 frame（第 4 章定理 2）。現在把同一個方法用在 page table 自己身上：把表切成一頁一頁，散放在任何 frame，再用指標（outer page table、hash 串列）找回每一塊。沒用到的區段就不建。

2.問：程式很小、logical 位址空間很大時，為什麼 hashed 通常比 hierarchical 快？

答：hierarchical 的層數由 p 有幾 bits 決定，和程式大小無關。64 bits 要 6 層，所以每次 TLB miss 要讀 6 次 memory。hashed 只存用到的頁，程式小，串列就短，約讀 1 次。

3.問：為什麼 inverted page table 轉譯比較慢？

答：它用 f 當 index，但轉譯時已知的是 p，要找的是 f。index 的方向反了，只能逐一比對 (pid, p)。

4.問：為什麼 inverted page table 比較省 memory？

答：它每個 frame 一個 entry，全機只有一張，大小只由 physical memory 決定。另外兩種是每個 process 一張，大小和 logical 位址空間或用到的頁數有關。

5.問：一整張 page table 和 inverted page table 各有幾個 entry？

答：一整張：每一個可能的 p 一個，共 2^(p 的 bits) 個。inverted：每個 frame 一個，共（physical memory ÷ page size）個。例：32 bits 位址、4 KB page、512 MB memory 時，一整張有 2²⁰ 個，inverted 有 2²⁹ ÷ 2¹² = 2¹⁷ 個。

6.問：inverted page table 能做 shared memory 嗎？

答：很難。一個 frame 只有一個 entry，只能記一組 (pid, p)。兩個 process 共用一個 frame 時，這個 entry 記不下兩組。

第 7 章

frames 不夠

問題（效率）

第 5 章的 page fault 約要 10⁷ ns，是讀一次 memory 的 10⁵ 倍。發生 page fault 時，如果沒有空的 frame，就要先踢掉一頁。踢錯了，那一頁很快又要搬回來，就多一次 page fault。整台機器也一樣：很多個 process 搶同一批 frames。

模型

出處：OSC §10.4 page replacement、§10.6 thrashing。「排序鍵」是你在 09/25 的說法。

  1. reference string：CPU 依序用到的 page number 排成的串列。程式執行了才有。
  2. 置換演算法把 frame 裡的頁，按一個「排序鍵」排好。發生 page fault 而且沒有空的 frame 時，踢掉排在最後的那一頁。三種演算法只差在排序鍵：
    • FIFO（first-in, first-out）：頁搬進來的時間。最早搬進來的，排在最後。
    • LRU（least recently used）：上次存取的時間。最久沒用的，排在最後。
    • OPT（optimal）：下次存取的時間。最晚才會再用到的，排在最後。
  3. working set：process i 在時間 t 的 working set WSi(t)，是它最近 Δ 次存取用到的頁的集合。Δ 叫 working-set window。t 是 process i 自己的存取次數。t 往前走，WSi(t) 跟著滑動：新用到的頁加進來，Δ 次以內沒再用到的頁離開。WSi(t) 的大小寫成 WSSi（working-set size）。
  4. 整台機器：scheduler 輪流執行 memory 裡的 process，例如 round robin（每個 process 輪流執行一段 time slice）。process i 輪到時，需要 WSi(t) 在 memory 裡。在 global replacement（可以踢任何 process 的頁）下，別的 process 執行時，可能踢掉 i 的頁。i 再輪到時，就要 page fault，把它們搬回來。所以輪流中的 process，working set 加起來（D = Σ WSSi）要放得進總 frames 數 m，才不會一直 fault。

    你的原話（這一點是你提出的模型）：「有 process[1], process[2], process[3], ... 他們各自有各自的 working_set[1][1], working_set[1][2], ... 然後 OS 用 round robin 的方式來并行執行每個 process。那在 round robin 的過程中我就可以模擬，現在 physical memory 有那幾個 working set，踢掉哪幾個 working set。」「working set 對我來説也是一個連續的、而不是一個階段一個階段的」

置換：只有 n 個 frame reference string（LRU 為例） 1 2 3 4 1 2 5 … 排序鍵 FIFO：搬進來的時間 LRU：上次存取的時間 OPT：下次存取的時間 5：page fault 2 1 4 3 最不會被踢 n 個 frame 下一個被踢 踢掉 3 disk（swap 區） U、V、W 輪流執行（round robin） U V W U V W 每個 process 輪流執行一段 time slice 最近 Δ = 4 次存取 U 3 4 1 3 2 1 2 1 WSU(t) = {1, 2} V 6 8 5 8 7 5 6 7 WSV(t) = {5, 6, 7} W 12 9 11 12 10 9 10 10 WSW(t) = {9, 10} t 往前走 → 窗口跟著往右滑 總共 m = 8 個 frame 1 2 5 6 7 9 10 空 D = Σ WSSi = 2 + 3 + 2 = 7 ≤ m = 8 CPU 使用率 degree of multiprogramming（同時在 memory 裡的 process 數） D ≤ m D > m（thrashing）

定理

1.問：為什麼 LRU 實際上的 page fault rate 不錯？

答：程式有 temporal locality：最近用過的頁，很快又會再用。LRU 留下的正是最近用過的頁。

2.問：為什麼 stack algorithm 不會有 Belady's anomaly（frame 變多，page fault 反而變多）？

答：stack algorithm 的定義是：n 個 frame 裡的頁，永遠是 n + 1 個 frame 裡的頁的子集。所以 n 個 frame 時 hit 的存取，n + 1 個 frame 時也一定 hit，fault 次數不會變多。

你在 09/25 推出：排序鍵不依賴 frame 數時（LRU、OPT），n 個 frame 裡的頁，永遠是 n + 1 個 frame 裡排序鍵的前 n 名，所以是 stack algorithm。FIFO 的排序鍵是搬進來的時間。一頁什麼時候搬進來，要看前面哪些存取 fault 了，而這依賴 frame 數。所以 FIFO 不保證。這是充分條件。排序鍵依賴 frame 數時，只能說「沒有保證」。例：FIFO；或是 LFU（least frequently used：踢掉被存取次數最少的頁），而次數從這一頁搬進來時開始數。

3.問：compiler 能分析程式，為什麼還是算不準 OPT 需要的未來 reference string？

答：reference string 要程式執行了才有，compiler 只看得到 code。有三個原因：

  1. 走哪個 branch、迴圈跑幾次，要看執行時的輸入。
  2. malloc 給哪一段位址，要看執行時 heap 的狀態。
  3. 執行時可能發生 exception，例如除以零，會跳進 exception handler。

你的原話（第 2 個原因是獨立的理由）：「就算 n 是常數，這裡應該也是無法確定 reference string」。

4.問：frames 很少時，怎麼改寫迴圈，讓 page fault 最少？

答：讓每段時間用到的頁（working set）放得進 frames。把資料切成一頁一頁的塊，一塊做完所有的工作，再換下一塊（loop blocking）。這樣每一頁只搬進來一次，fault 次數等於下限：用到的頁數。塊的大小要剛好一頁，程式裡用 sysconf(_SC_PAGESIZE) 問 OS 一頁多大。把幾個迴圈合併成一個（loop fusion），會讓每次迴圈同時用到更多頁；frames 不夠時，反而一直 fault。

你的原話（在考卷上寫的）：「對於每一塊 a, 先把 b 前半加過來,結束後再把 b 的後半對應的那一個塊加過來.只是我們不知道 page 多大.」

5.問：一個 process 一直 page fault。把置換演算法換成 OPT，有用嗎？

答：如果分到的 frames 比 working set 少，連 OPT 也會一直 fault。例：3 頁輪流用、只有 2 個 frame 時，LRU 每次存取都 fault，OPT 也約每兩次存取 fault 一次。所以問題不在置換演算法，而在 frames 不夠。這叫 thrashing：process 花在 paging 的時間，比執行的時間還多。

6.問：CPU 使用率很低，負責 paging 的 disk 卻很忙。OS 該增加還是減少 process？

答：減少。這表示 D > m：輪流中的 process，working set 加起來超過了總 frames 數。每個 process 輪到時，都在把被踢掉的頁搬回來，所以 CPU 使用率才低。再加 process，D 只會更大；換更快的 CPU 也沒用。處理方法有三種：

  • working-set model：D 大於 m 時，就 suspend 一個 process：把它整個 swap out，把它的 frames 讓給別人。D 比 m 小很多時，才放新的 process 進來。
  • PFF（page-fault frequency）：替每個 process 的 page fault 率設上界和下界。超過上界，就多給 frames；低於下界，就收回一些。
  • local replacement（每個 process 只能踢自己的頁）：一個 process thrashing 時，別的 process 不會跟著 thrashing。但這個方法不能消除 thrashing。

第 8 章

CPU scheduling

問題（效率）

第 2 章的做法是：一條 kernel thread 等 IO 時，CPU 換給別的 kernel thread。所以 ready 的 kernel thread 常常不只一條，但一個 core 一次只跑一條。scheduler 要決定什麼時候換、換給誰。這決定每條 kernel thread 等多久，也決定 CPU 會不會在還有工作時閒著。

模型

一句話：workload 是固定的，scheduler 只決定每條 kernel thread 什麼時候待在 ready。指標量的是這段 ready 的時間怎麼分；演算法決定怎麼分。

章內順序照 OSC 第 5 章：§5.1 → §5.2 → §5.3 → §5.5。

A. workload 和 state（OSC §3.1.2、§5.1.1）

  1. workload：每條 kernel thread 帶一段 workload，是一串交替的 CPU burst 和 IO burst，從最左邊開始消耗。workload 由程式和輸入決定，不由 scheduler 決定。scheduler 看不到 workload，只能用過去的 CPU burst 預估下一段（OSC §5.3.2）。
  2. state：每一刻，kernel thread 恰好在其中一個 state。
    • running：在 CPU 上，消耗最左邊的 CPU burst。最多 m 條（m 是 core 數）。
    • ready：最左邊是 CPU burst，但不在 CPU 上，排在 ready queue。不消耗 workload。
    • waiting：消耗最左邊的 IO burst。
    • terminated：workload 消耗完。
  3. 換 state：
    • running → waiting（CPU burst 消耗完，下一段是 IO burst）；
    • running → terminated（workload 消耗完）；
    • running → ready（被 preempt，最左邊的 CPU burst 還沒消耗完）；
    • waiting → ready（IO burst 消耗完）；
    • ready → running（只有 scheduler 能做）。

你的原話（A 是你提出的模型）：「核心概念感覺是幾個 pool：waiting, ready, running。在 pool 裏面的是 kernel thread。每個 kernel thread 帶有一段 workload time……放到 running queue 代表正在消耗（workload 的最左側） CPU burst time」

B. 指標：scheduler 只改變 ready 的時間（OSC §5.2、§5.8.2）

  1. 時間的分解：Ci、Oi 是 kernel thread i 的 CPU burst、IO burst 加總，Wi 是 wait time（待在 ready 的時間加總）。由第 2 點，turnaround time Ti = Ci + Wi + Oi。前提：waiting 只在等 IO、IO 不用排隊、不算 context switch 的成本。在這些前提下，Ci、Oi 由 workload 決定；scheduler 只決定 Wi 和它落在時間軸的哪一段。
  2. 五個指標（n 是 kernel thread 數，ai 是進入系統的時刻，L = maxi (ai + Ci + Oi + Wi) − mini ai）：
    指標式子只看 W 的什麼
    wait timeWi平均、最大、p95（95% 的 Wi 不超過的值）
    turnaround timeTi = Ci + Wi + Oi同上，每條加上固定部分 Ci + Oi
    throughputX = n ÷ L每條加上固定部分 ai + Ci + Oi 以後的最大值
    CPU utilizationU = ΣCi ÷ (m × L)同上
    response time每次 request（進入系統，或一段 IO burst 結束）之後，第一段 ready 的長度第一段落在哪裡
    • CPU 忙的總時間正好是 ΣCi，因為 CPU 在忙，就是有 kernel thread 在消耗 CPU burst。
    • 重複：平均 turnaround time 和平均 wait time 只差一個常數；throughput 和 CPU utilization 都只看 L。
    • response time 只在 preemptive 時跟 wait time 不同；non-preemptive 時，每段 CPU burst 只在 ready 等一次。
  3. Little's law：對任何一個 state，平均同時待在這個 state 的 kernel thread 數 = X × 每條待在這個 state 的平均時間。整個系統：平均同時在系統裡的 kernel thread 數 = X × 平均 turnaround time。OSC §5.8.2 說它對任何排程演算法都成立。長時間下來，系統跟得上到達的速度時，X 等於到達率，scheduler 改變不了；排程只剩 W 怎麼分。指標互相衝突，因為同時最多 m 條在 running，所以沒有一個演算法對所有指標都最好。

你的原話（第 4–6 點從這個問題推出）：「既然 model 的底層，kernel thread list 是 [(CPU burst time, wait, IO burst time)...]，那麽這些指標應該可以表示成這些數字？」

C. scheduler 怎麼挑（OSC §5.1.3、§5.3）

  1. scheduler 從 ready queue 挑 priority 最高的 kernel thread。演算法 = priority 怎麼定 ＋ 在哪些時刻重挑。四個時刻：
    • ① running 的 kernel thread 發出 IO request；
    • ② interrupt 到來（例：time slice 用完）；
    • ③ 一條 kernel thread 進入 ready（IO 做完，或剛建立；OSC 只寫 IO 做完，剛建立的情況見第 8 點的 SRTF（shortest-remaining-time-first））；
    • ④ running 的 kernel thread 結束。
    • non-preemptive：scheduler 不換掉 running 的 kernel thread，只在 core 空著時挑：① ④ 讓 core 空出來時；或 core 空著時，有 kernel thread 進入 ready（③）（OSC §5.1.2：CPU 一空下來，就要從 ready queue 挑一條）。
    • preemptive：② ③ 時也可以換掉 running 的 kernel thread。
  2. 基本演算法：
    演算法priority 怎麼定重挑的時刻
    FCFS（first-come, first-served）先進 ready queue 的高① ④
    SJF（shortest-job-first）下一段 CPU burst 短的高① ④
    SRTF（shortest-remaining-time-first，preemptive 的 SJF）剩下的 CPU burst 短的高① ③ ④
    RR（round-robin）跟 FCFS 一樣；被 preempt 的排到 ready queue 尾端① ② ④
    priority 排程任意定non-preemptive：① ④；preemptive：① ③ ④

    表上的時刻，是 core 上有 kernel thread 在 running 時。core 空著時，任何演算法都在有 kernel thread 進入 ready 時就挑。

  3. starvation：kernel thread 一直待在 ready queue，永遠拿不到 CPU。只要一條的 priority 可能永遠比別人低，就會 starvation。aging：在 ready queue 等越久，priority 調得越高（OSC §5.3.4）。

D. 多個 queue：priority 由 queue 決定（OSC §5.3.5、§5.3.6）

  1. MLQ（multilevel queue）：ready queue 分成好幾個 queue；scheduler 先挑 queue，再用那個 queue 的演算法挑 kernel thread。參數 3 個：分類（幾個 queue、每個收哪一類，依據是不會變的屬性，例：類型）、每個 queue 的演算法、queue 之間怎麼挑（固定 priority，可以 preempt；或分配 CPU 時間，例：80%／20%）。kernel thread 每次回到 ready，都進同一個 queue。
  2. MLFQ（multilevel feedback queue）：kernel thread 進哪一個 queue，可以看它執行時的表現。參數 6 個：queue 的數量、每個 queue 的演算法、queue 之間怎麼挑（OSC 的參數表沒列，例子用固定 priority）、降級的規則、升級的規則、要用 CPU 時先進哪一個 queue。MLQ 是 MLFQ 的特例（不升不降、照類型分）。效果取決於參數，寫結論時要寫出參數。
    • OSC 例子的參數：三個 queue，time slice 8 ms、16 ms、最低用 FCFS；queue 之間固定 priority；新的進最高的 queue；用完 time slice 降一級；在低的 queue 等太久升一級。在這組參數下近似 SJF（不用事先知道 workload），aging 防止 starvation。
    • 移動的時機也是參數；常見的設計只在得到新資訊時移動：用完 time slice（running → ready）降級；等太久（待在 ready）升級；IO 做完（waiting → ready）升級，例：Windows（OSC §5.7.2）。

    你的原話（假設 MLQ 每次回到 ready 都重新決定 queue；由此推出 MLQ 是 MLFQ 的特例）：「……MLQ 分類的根據會動態變化，不就變成 MLFQ 嗎？」

    你的原話：「這裏的 MLQ/MLFQ 是一個架構，但是要優化的目標/每個 queue 的演算法我覺得都沒有定義，都可以自己填寫」

E. 多核（OSC §5.5）

  1. 每個 core 通常有自己的 ready queue。kernel thread 在一個 core 上跑過，那個 core 的 cache 裡有它的資料。CPU affinity：讓 kernel thread 留在同一個 core，cache 不用重新填。NUMA（non-uniform memory access）：每個 CPU 有自己的 local memory，存取它比存取別的 CPU 的 memory 快；NUMA-aware 的 OS 把 kernel thread 的 memory 配在它所在 CPU 的 local memory，affinity 讓存取都是 local。affinity 和 load balancing（把 kernel thread 從忙的 core 搬到閒的 core）互相衝突。
CPU burst IO burst 最左邊那一段 決定它在哪個框 長條左邊的數字是 kernel thread 的編號 i， 就是 Ci、Wi、Oi 的 i。 ready queue 不消耗 workload 1 2 3 running 消耗最左邊的 CPU burst core 1 4 core 2 5 最多 m 條（m 是 core 數） waiting 消耗最左邊的 IO burst 6 terminated workload 消耗完 7 scheduler 挑 ② ③ 被 preempt ① 發出 IO request ③ IO 做完 ④ workload 消耗完 一條 kernel thread 的時間軸 ready running waiting ready running waiting ready running terminated scheduler 決定 scheduler 決定 scheduler 決定 turnaround time Ti = Ci + Wi + Oi

定理

1.問：SJF 在什麼條件下讓平均 wait time 最小？

答：所有 kernel thread 同時在 ready queue，而且知道每條的下一段 CPU burst。排第 j 個的 burst bj 讓後面 n − j 條都等它，wait time 總和 = Σ bj × (n − j)，短的放前面最小。不同時到達時，要用 SRTF。

你的原話：「這樣 greedy 是對的，因為swap任何一組逆序都不會更糟。」

2.問：RR 的平均 turnaround time 一定比 FCFS 小嗎？

答：不一定，看 burst 的長度；burst 都一樣長時 RR 比較差。RR 保證的是 response time：ready queue 裡有 r 條時，每條最多等 (r − 1) × time slice 就拿到 CPU。

3.問：什麼情況會 starvation？

答：一條 kernel thread 的 priority 可能永遠比別人低時。例：SJF 在短的一直進來時；MLQ 用固定 priority 時的低 queue。non-preemptive 時，一段永遠不結束的 CPU burst 也會讓其他的 starvation。解法是 aging。

你的原話：「Non-preemptive 可以永遠占據 running。」

4.問：non-preemptive 的 scheduler 在 IO 做完時會重挑嗎？

答：core 上有 kernel thread 在 running 時，不會：IO 做完是時刻 ③，non-preemptive 不換掉 running 的 kernel thread。core 空著時，才會挑剛進 ready 的那一條。

5.問：為什麼 IO-bound 的 kernel thread 常拿到高 priority？

答：CPU burst 短，先跑它近似 SJF，平均 wait time 小；它很快進 waiting，IO 和別人的 CPU burst 同時進行，L 變小。相反的情況是 convoy effect（OSC §5.3.1）：FCFS 時一條 CPU-bound 在 running，IO-bound 的全在 ready queue 等，device 閒著。

6.問：MLFQ 為什麼常比 MLQ 好？

答：MLQ 是 MLFQ 的特例，所以參數選得好的 MLFQ 至少一樣好（不計排程本身的成本）。kernel thread 的表現跟類型不一致，或隨時間改變時，MLFQ 比較好。

7.問：在 NUMA 上，CPU affinity 為什麼讓程式變快？

答：NUMA-aware 的 OS 把 kernel thread 的 memory 配在它所在 CPU 的 local memory；affinity 讓它留在這個 CPU，存取都是 local，cache 也不用重新填。