作業系統筆記

SP 提過的或我覺得不重要的會跳過。

下半部分主要參考林忠緯的課程，NTU COOL 連結(雙班是林忠緯)。Youtube 播放清單

Ch1 Overview

Turing Machine

Computation modes

Mode	Description	Metrics	Key Focus
Batch mode	執行後與外界無互動，如：編譯器、ML	CPU utilization、Turnaround time、Throughput，所以不用公平，把資源都集中給正在做的任務。	Efficiency
Online mode	有互動，最常見，如：遊戲、瀏覽器	Waiting Time、Response Time，避免資源都給最花時間的任務，要讓同一個長度的時間內完成的任務數量差不多，所以才要公平分配資源。	Responsiveness
Real-time mode	有互動以外，還有時間限制，如：機器人控制、自駕車	Tardiness（任務超時時間），要盡量避免任務超時。未必要把所有資源給任務，而是需要恰好使需要的資源都準備好。	Predictability

沒有一個系統能同時做好所有模式。

Computing System Architecture

使用者 -> 應用程式 -> 作業系統 -> 硬體

von Neumann Architecture

包含輸入、處理、輸出，處理部分的 Central Processing Unit (含 Central Unit、Arithmetic Logic Unit(ALU)) 會與 Memory Unit 互動。Data 和 Instruction 都放在 Memory Unit 中。
完全符合 Turing Machine。

Havard Architecture

Central Unit 可以獨立存取 Instruction Memory、Data Memory、ALU。與 von Neumann 的差異只有 Instruction 和 Data 放在不同的 Memory 中。

現在的機器主要是 von Neumann Architecture，但有些小元件可能會使用 Havard Architecture，通常會是混合的。

過去的瓶頸主要是 CPU，也是要設計演算法的原因，因此 von Neumann 比較好用，因為不用頻繁存取 Data，bus 主要是設計來存取 Instruction。但比如現在的機器學習往往都是大量的簡單運算，需要頻繁存取 Data，所以或許未來的系統未必會是 von Neumann。

OS 定義

概念上，銜接硬體與應用程式，應用程式分成 system program (ships with OS, not part of kernel)、application program。OS 也稱為 middleware，現在一台電腦可以跑很多系統，比如用 docker、虛擬機，這些也是 middleware。

OS 種類

Stand Alone (Uni-processor) OS

資源管理，讓應用程式更容易實作，而不用管太多硬體問題。
kernel 依架構分類:

• Monolithic (MS-DOS, early Unix): 一個大程式，但功能複雜化之後不太實際。
• Layered: function 只使用較低層的 function，可以用作權限管理。需要 processor 支持，通常從 0(hw) 開始，現在可能有 -1~-3，為 virtual machine 提供虛擬的硬體環境。

第一堂課的 hack 就是改 -2 層的 memory，偷到 superuser 權限

• Microkernel: kernel 通常不能動，因此希望越小越好，只留基本功能，其他給 user module 做。比如想要自訂 process scheduling，一般的 kernel 需要自己把整個重新編譯。Mach 是一個例子，Mac OS X 部分用 Mach。因為 kernel mode 變少，更安全、可靠，但因為要在 user、kernel mode 之間切換，效能較差。
• Modules: Loadable Kernel Module (LKM)，安裝 driver 後不用重開機。

現在通常都是混合，像 Linux 主要是 monolithic，但也有 modular 的成分。

Distributed OS

只要不是 single processor、single core，就是 distributed OS。像 Google 搜尋就可能用幾千台電腦以網路連接。

• Distributed OS(DOS): tightly-coupled(嚴格的主從關係，通常有一個 master OS，其他 processor 只能接受)，processor、core 都差不多的情況(instruction set 一樣)。
• Network OS(NOS): loosely-coupled，每個機器可能不太一樣。
• Middleware: 基於 NOS，因為 loosely-coupled 導致不一定能找到接受 instruction 的機器，所以需要 middleware 來協調。

OS 介面

Application - System call/services - OS - Interrupts - Hardware
System call 大致種類:

• Process Control: fork - Creates a new process.
• File Management: open - Opens a file for reading or writing.
• Device Management: ioctl - Performs device-specific input/output operations. read, write。
• Information Maintenance: time - Returns the current time.
• Communications: pipe - Creates a pipe for inter-process communication (IPC); socket - Creates a socket for network communication.
• Protection: chmod - Changes file permissions (e.g., read, write, execute).

Functional Components

OS 實作 system call 的功能，也是 OS 課程的主要內容，SP 是介紹 application 到 system call 的 interface。

要 Pass 參數給 system call，可以：

• 存放在 register 中，但 register 不大。
• 存放在 memory 中，然後把指標存在 register 中。
• process push 到 stack 中，OS 用完 pop 出來。

功能：

• program execution: process scheduling 等。
• file systems: 提供 I/O 操作的資料結構。
  • Storage Subsystems: 各種裝置有 impedance mismatch(processor、storage 的頻率不同)，所以有各種大小、延遲的 storage，如 SRAM(flip-flop)、DRAM、NAND flash、HDD、tape。分成 primary storage(CPU 可以直接隨機存取，register、cache、main memory。volatile 揮發性，斷電會消失)、secondary storage(需要 I/O controller)。
• I/O operations: Keyboard, mouse 也算。
  • I/O Subsystems: buffering、caching(廣義)、spooling(針對慢速設備，印表機、磁帶機等的排隊系統。使得很多人同時用印表機，不會導致頁面 interleaving)、device drivers。
  • Character Devices: 一次一個字元，如 keyboard。
  • Block Devices: 一次一個 block，如 disk。
• communications: Process 間溝通，IPC、RPC(Remote Procedure Call，透過網路連接不同電腦)都算。
• resource allocation
  • Allocation: 決定 users、processes 各自能使用多少資源。類比: 停車證，可以超過停車位總量，因為不會同時所有車一起停。
  • Assignment: 決定哪些 memory page 等。類比: 停車位。
• accounting: 紀錄使用者使用資源的情況，如 CPU 時間、memory 使用量。
• protection and security
  • Protection: 存取權限設定
  • Security: 防止內在、外在攻擊
• error detection:

Ch3 Process

要求

• Multiplexing by time sharing: 同時執行多個 process，但實際上是在切換執行。
• Isolation: Process 會認為自己在用整個機器，且看不到其他 process 的資料。
• Interaction: Process 之間可以溝通。

先考慮 Uni-processor，一次執行一個 process，因此 Isolation 就簡單達成了，但就要做 scheduling，由 process state 協助。

Process State

admit 代表 OS 決定要不要執行一個 process，即 resource allocation，不夠的話就不給過。或是 real-time mode 時，還會考慮能不能在時間內做完。

Multi-processor

• Multi-Processor: e.g. SMP(Symmetric Multi-Processor system): 每個 processor 都長一樣，共享 memory，以 system bus 連結。
• Multi-core: 每個 processor 裡有多個 core，有 cache(分層，有些共享有些不共享)。

由於 OS 是共享的，有可能一個 processor 進入 kernel mode，也許就會看到其他 process 的資料，很危險，需要重新設計。

SMP 以外，還有:

• AMP(Asymmetric Multi-Processor system)，由一個 master processor 控制其他 processor。
• HMP(Heterogeneous Multi-Processor system)，大小核，如 big.LITTLE，為了省電等。

Process scheduling

找到下個 ready process，並執行。目標是 maximize CPU use、快速的在 process 之間切換、公平分配等。
以 workload 分成 I/O-bound、CPU-bound。通常 CPU-bound 的 process 應該要分配到更久的時間。但 busy waiting(如 spin lock) 會浪費時間。

Context Switch

花時間，要把 state(Register、Program Counter、Memory、I/O 相關資訊等) 存到 PCB，PCB 越大就越花時間。

如果 CPU 有多組 register，也許就不需要保存 register，會快一點。

Ch4 Threads & Concurrency

• Concurrency(共時性): 多個工作同時有進展，在單一 processor 上交替執行也算。

Concurrent Programming

• Single Process on Single Processor
• Multiple Processes on Single Processor: by operating systems，time slice、context switch
• Single Instruction Single Data (SISD)
• Multiple Instruction Multiple Data (MIMD): by hardware architecture (e.g., modern CPU)
  • Multi-core Processor
  • SMT(Simultaneous Multithreading): 一個 core 同時執行多個 thread，利用別的 thread 存取 memory 的時間交替運行，像是 Intel 的 Hyper-Threading。
  • SuperScalar: CPU core 有很多區塊(整數、浮點數等)，一次只用一個區塊有點太浪費，可以讓 core 中的 thread 共用區塊。
• Single Instruction Multiple Data (SIMD): e.g., modern GPU，一大筆資料都是要做一樣的操作。
• Zero Instruction Multiple Data: Computation in Memory by hardware architecture (e.g. SRAM 6T CIM)，instruction 已經在電路做好了，資料存進去再拿出來就好了。為了省電。

估計加速效果

Amdahl's Law

滿直覺、悲觀的一個上界。

$S$: 必須 sequential 執行的程式比例

$N$: core 數量
最好的情況下，把能平行化的部分(比例

$1-S$)給

$N$ 個 core 做。

$$\begin{array}{rl}\frac{\mathrm{加}\mathrm{速}\mathrm{後}\mathrm{所}\mathrm{需}\mathrm{時}\mathrm{間}}{\mathrm{原}\mathrm{來}\mathrm{所}\mathrm{需}\mathrm{時}\mathrm{間}}& \ge S+\frac{1-S}{N}\\ \mathrm{加}\mathrm{速}\mathrm{效}\mathrm{果}& \le \frac{1}{S+\frac{1-S}{N}}\end{array}$$

問題

• 只是一個上界
• 運算的比例
  $S$ 難以估計，可能與資料量有關
• 每個 processor 假設是一樣的，但 CPU、GPU 就有差別，bigLITTLE 架構也不適用

Gustafson's Law

Amdahl's Law 是考慮把 sequential 的程式平行執行，Gustafson's Law 是考慮把平行化的程式 sequential 執行，較樂觀。

假設在平行化時，sequential 部分執行時間

$a$、平行化部分執行時間

$b$，則最差的情況(平行化效果最佳時) sequential 需要執行

$a+bN$ 的時間。也可以順便考慮大小核的問題，比如小核效能是大核一半的話，在

$N$ 個小核平行跑

$t$ 的時間等於在大核 sequential 跑

$Nt/2$ 的時間。

$$\mathrm{加}\mathrm{速}\mathrm{效}\mathrm{果}\le \frac{a+bN}{a+b}$$

Thread 分類

SP 分類成 user level thread (model)、kernel level thread (model) 和 hybrid。而這邊是用不太一樣的等價分類方式，應該是比較貼近現實，把 thread 分成 user thread 和 kernel thread，user thread 代表 program 所使用的 thread，kernel thread 則是指 kernel 實際上排程的 thread。這邊有可能有理解錯，有發現問題的話歡迎更正。

• many-to-one: user level thread model，一個 process 中的 threads 全部對應到一個 kernel thread，代表一次只有一個 thread 在執行，且是由 user 控制的。不能利用多核的優勢，且遇到 blocking call 就會卡住，所以比較難用。
• one-to-one: kernel level thread model，每個 user thread 對應一個 kernel thread，相當於排程是交給 kernel 控制。
• many-to-many(two-level model): hybrid，最理想，但比較難實作。

Thread Libraries

先介紹 threading model 的分類：

• asynchonous: parent 叫出 threads 後，就各自跑各的。像 fork 一樣。
• synchronous: parent 叫出 threads 後，會等所有 threads 都結束後才繼續執行。

以下都是 synchonous threading：

• pthread：因為典型用法會用 pthread_join
• Windows threads
• Java threads

Implicit Threading

CPU 變多核後，多執行緒程式往往有成千上百個 thread，需要解決很多問題：同步、負載平衡、溝通成本、除錯、資源管理與記憶體一致性問題等。

• Thread Pool: 事先建立好 thread，等待任務。
  • 好處：避免建立 thread 的 overhead，預支 resource。
  • 每個 task independent。
• Fork-Join Parallelism: 與分治很像，一個 thread fork 出很多 thread，等待所有 thread 完成後再 join 回來，有可能很多層。pthread 可以說是一種 Fork-join model。
  • 好處：簡單、容易平行化。
  • 上層 depends on 下層。
• OpenMP: 通常是科學運算，用在 task 可以切分的情況。使用方法 #pragma omp <directive> [clause[[,] clause] ...]。
  • 好處：thread 數量不同時，thread 間溝通的方式可能不同。可移植，簡單，GPU 可用。

OpenMP 的例子，向量加法、矩陣等：

#pragma omp parallel for
for (int i = 0; i < N; i++) {
    a[i] = b[i] + c[i];
}

#pragma omp parallel shared (a) private (i,j)
{
  #pragma omp for
  for(i=0; i<N; i++){
    for(j=0; j<N; j++){
      a[i][j]=i+j;
    }
  }
}

矩陣乘法也類似，可參考原始碼

Threading Issues

• fork, exec: SP 說 fork 時是只複製 call fork 的 thread，但其實有的 UNIX 會把所有 thread 都複製。exec 與 SP 講的大致一樣。
• Signal handling: 與 SP 講的大致一樣。
• Thread Cancellation: 與 SP 講的大致一樣。
• Thread-Local Storage(TLS): 每個 thread 各自的 static variable，在 implicit threading 如 thread pool 很有用，比如每一筆交易開一個 thread 處理，則可以在 TLS 放交易序號。概念上是在 thread 開始前宣告一個全域變數，每個 thread 去存取會得到不同的記憶體位置。
  • 比如 pthread 是用 pthread_key_t 作為 key，pthread_key_create(&key, destory_func) 時每個 thread 使用 pthread_setspecific(key, ptr) 設定指標，pthread_getspecific 取得指標。
• Scheduler Activations: LWP? [TODO]

Ch9 Memory Management

Address Binding

program 執行時，需要把 text、data 搬到 memory，並分配 physical memory 給 process。把 program 放到 memory 稱為 Address Binding，有三種時間點:

• Compile Time: 固定 physical address，但已被佔用的話就得等，要改 address 還得重新編譯。
• Load Time: compile 時寫 relocatable code，load 到 memory 時才對應到 physical address，例如 dynamic link library。
• Execution Time: OS 每次執行時，才對應到 physical address，比如用 logical address、virtual memory 達成，但會有 overhead(額外開銷)。

Logical vs Physical Address

• Logical Address: CPU 產生，也稱為 virtual address，program 只看得到 logical address。
• Physical Address: Memory 的實際位置。

透過 MMU(Memory Management Unit) 來對應。

對應方式

Contiguous Memory Allocation

過於簡單的模型，但可以幫助理解。直接分配一段連續的 memory 給每個 process，並把所有 text、data 載入到 memory。會產生 hole，也就是 external fragmentation。

尋找可用的 hole 的方法:

• Best fit: 找到一個最小但夠大的 hole 會是個不錯的方法。
• First fit: 找到第一個夠大的。
• Worst fit: 找到最大的。

Fragmentation

小塊、難以利用的空間

• External: 一些 process 執行、結束後，在目前執行的 process 間產生小塊的 hole。
• Internal: 分配給 process，但不會被實際使用，通常是因為有單位大小，比如 4KB 一個 page/frame。

First fit 分配 N 個 block 則大概會有 N/2 個 block 的 external fragmentation。
可以動 process 來把 hole 集中在一起，因此 address 要是相對的。

Protection(Contiguous)

每個 process 是一個連續的區間，因此檢查是否在

$[\text{base},\text{base}+\text{limit})$ 區間內即可。

Paging

避免 External Fragmentation，把 physical memory 分成固定大小的 frame，把 logical memory 分成固定大小的 page，兩者通常一樣且為 2 的冪次。用 page table 對應。
每個 process 中的 logical address 分成 page number (

$p$)、page offset (

$d$)。若 logical address space 為

$2^m$，每個 page 有

$2^n$ bytes 大，則

$p=m-n,d=n$。
page table 可以簡單的以一個 array 實作，長度為

$2^p$，第

$i$ 格存放第

$i$ 個 page 對應的 frame number。

Internal Fragmentation 的期望值是 page size 的一半，因此 page size 越小則 Internal Fragmentation 越小，但 page table 會變大，因此還是得折衷。

Free frame 可以用一個 list 紀錄，若沒有 free frame list，相當於每次 page fault 後都要先找 victim 再寫入，會浪費時間。

如果 page table 直接放在 main memory，則實際存取記憶體就需要先存取 page table 找到位址，再存取實際內容，會導致 overhead，時間幾乎浪費在存取 memory。
這以 paging 的設計無法避免，但可以用硬體如 translation lookaside buffer(TLB) 來解決，cache page table 的部分。

Page Table Size 計算

• 32-bit: 假設 logical address space: 32-bit，page size: 4KB ，每個 page table entry: 4 bytes=32 bits。
  page size=
  $2^{12}$ bytes，因此 page 數量為
  $2^{32-12}=2^{20}=1M$，page table size=
  $1M\ast 4B=4MB$。
• 64-bit: 假設 logical address space: 64-bit，page size: 4KB ，每個 page table entry: 8 bytes=64 bits。
  page size=
  $2^{12}$ bytes，因此 page 數量為
  $2^{64-12}=2^{52}=4P$，page table size=
  $4P\ast 8B=32PB$。顯然不可能。

實際上 x86-64 只會用 48-bit 的 logical address

Translation Lookaside Buffer

page table 的 cache。
有些 TLB 會儲存 address-space identifiers(ASID)，區分 process 用，TLB 的結構就是 (ASID, page number) 對應到 frame number。
TLB 是用 associative memory 實作，特性是可以平行化的以值找到 key，但成本較高，一般 TLB 只有幾千個以下的 entry。
cache 最近使用的 page table entry，而 replacement policy 就很重要。Wire down 一個 entry 代表使其不能被從 TLB 移除。

Effective Access Time

Hit ratio:

$h$，要找的 entry 已經在 TLB 中的機率，通常會很高，實際上可能有 99%。

$$\text{EAT}=h\times \text{memory access time}+(1-h)\times 2\times \text{memory access time}$$

Protection(Paging)

page table 每個 entry 會有 valid-invalid bit，表示此 page 是否在 memory 中。因為很有可能用不完整個 logical memory，所以未必要建好整個 page table，可以用 length register 來紀錄長度，並把超過長度的存取也視為 invalid。

Shared Page

常用的 library(read only，因此不需要上鎖保護)可以讓所有用到的 process 共用 physical memory，讓 page table 中對應到同一塊就行了。像是 C、compiler、window system、database system 等。
這些 code 需要是 reentrant，因為不同 process 可能會同時交替使用同個 function。

Structure of Page Table

原因: 每次都記下整個 page table 會浪費空間，如 32-bit 可能每個 process 要 4MB，64-bit 更誇張。

Hierarchical Paging

像是 SP 教到的 file system 中的 data block 有 indirect block，用多層的 page table 來解決。因為一層的很多個 page table 可以放在不連續的空間，避免了需要一塊很大的連續記憶體。

但 overhead 變得更大，因為要存取很多次記憶體，64-bit 可能要 7 次，很不實際。

Hashed Page Tables

每個 entry 用一個 linked list 串起許多 (page, frame)。64-bit 系統可能會使用 clustered page tables，把連續的 page 集合起來，可能是 16 個。比如 page

$[16n,16(n+1))$ 共用 page table entry，要存取

$a$ 的位置就計算 a>>4 的 hash，再從 entry 中找到 block 中第 a&1111 個 frame number。可參考原論文

Inverted Page Tables

原本是找到 page，讀取對應到 frame。改成 page table 的大小為 frame 數量，每個 entry 有 (pid, page)，找到後 index 就是 frame number，因此整個系統可以共用一個有一點大的 process table。

有可能需要找整個 page table，因此為了加速，可以用 hash table，輸入 (pid, page)，bucket 中儲存許多 frame，再去 page table 中一一確認。

我的疑問: 是否用 hash table 加速後就變得和 Hashed Page Tables 非常接近？

但有個問題是無法做 shared memory，可以透過把 page table 中的每個 entry 改成一個 linked list 解決，但搜尋的 overhead 就更大了。

Swapping

logical memory 總和大於 physical memory 時，需要把一些 memory(以 process 或 page 為單位)暫存到 secondary storage(如 disk)。

• standard swapping: 整個 process swap in/out，太花時間，很少用。簡稱為 swapping。
• swapping with paging: 現在 paging 幾乎都會 swapping，因此簡稱為 paging。

移動裝置基本上不 swapping，因為 flash memory 寫入次數相當有限，可能會用 compressed memory 代替。

• Android 就會直接清除太久以前的背景程式，但保存 application state，以便快速重啟。
• iOS 會把 read-only(code) 刪掉，但 data 保留，真的不行才全部砍掉。

存取 swap space 會比一般的檔案更快一點，因為會是很大的區塊，而不需要檔案系統多餘的處理。

Ch10 Virtual Memory

因為常常不需要 load 整個 program，所以可以用 demand paging，只有當真的需要時才 load。這樣一次可以跑更多 process，而且比較不用 swapping，載入、運行時間也更快。

OS 在舊的 CPU 上，virtual address 與 logical address 是一樣的，但現在的 CPU 有 segment。

Memory Segmentation

分成 CS(Code)、DS(Data)、SS(Stack)、ES(Extra)，每個 segment 有各自的 base register，支援更大的空間。
切分 segment 可以達到保護的效果，像是 CS 就是 read only。
存取超過 segment 的部分會有 segmentation fault。

Demand Paging

需要的時候才從 disk、swap space (lazy swapper) 載入。使用者不需管這些事情(稱為 transparent)。

此時 valid-invalid bit 代表在 memory 且 legal (屬於這個 process，已 allocate)，這樣若發現 invalid 並不一定是範圍外，有可能只是有 allocate 但沒 swap in，此時是 page fault，OS 會在 physical memory 找一個 free frame 並 swap in，更新 page table。

page fault 後要恢復 process 的狀態，相當於 context switch，比如 register、program counter。如果 page fault 發生在:

• instruction fetch: 重新 fetch instruction 即可。
• operand (運算元): 重新讀取並解碼 instruction，再 fetch 運算元，會稍微比較花時間。

Locality of reference: 如果一個 instruction 需要存取散布在許多 page 的 data，則就會導致一直 page fault，延遲嚴重。但實際上不太可能發生，因為資料往往都不會這樣分布，通常都比較集中，可能是在編譯時整理過。

舉例: 類似 memcpy 或 memmove 的函數，如果簡單實作，遇到 source 或 destination 跨越多個 page 且發生 page fault 的情況，如果 source 與 destination 又有重疊，則這個 instruction 從頭再次執行的話會出錯。簡單的解方是先確定 source 與 destination 都已經 load 進 memory，再進行複製，確保不會被 page fault 打斷。也可以用 register 記下重疊部分。

Free Frame List

在 swap in 或 allocate 新記憶體時，需要找到沒有在使用的 frame(free frame)，紀錄 free frame list。Zero-fill-on-demand: 通常會填 0，確保安全性。

當 free frame 少於一定數量或甚至沒有時，需要 replacement algorithm。

Performance of Demand Paging

swap in 所需的時間比起存取記憶體多很多，所以 EAT 幾乎是正比於 page fault rate。EAT 在計算時，page fault 的 case 要計算 overhead + swap in + swap out，swap out 是指當初 page 被 swap out 的時間，也要計算。

有些老的系統會在開始時就把整個 program 寫入到 swap space，這樣 swap in 比較快，但畢竟現在記憶體很大，不太需要這樣做。
現代的 Linux/Windows 會在開始時 demand paging，而後續 swap out 才寫入 swap space。

Page Replacement

logical memory 大於 physical memory (類似航空公司 overbooking)，則 free frame 可能會滿。以 reference string 來模擬並測試演算法，連續存取同個 page 可以合在一起。正常情況，總 page 數量愈多，page fault rate 會遞減。

需要找到一個 victim page，移到 swap space，並把新 page swap in。另外會用 dirty bit 紀錄是否有修改過，如果沒有則不需要放入 swap，可以直接丟棄，read-only 也是可以直接丟棄。

FIFO(First-In-First-Out)

最早 load 進 memory 的 page 會被 swap out，紀錄一個 queue 即可。 比如 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，frame 數量為 3 時，page fault 的 page 有: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。

Belady's Anomaly

FIFO 有這個現象，frame 數量增加時，page fault rate 反而增加(可能只是局部)

比如 1,2,3,4,1,2,5,1,2,3,4,5，frame 數量為 3 時，page fault 的 page 有: 1,2,3,4,1,2,5,1,2,3,4,5。
frame 數量為 4 時，page fault 的 page 有: 1,2,3,4,1,2,5,1,2,3,4,5。

直觀的看是因為 1,2 雖然近期有使用，但不會因此被保留。看完之後的方法，我們會知道其他方法用的是每個 page 的 priority，而 FIFO 是與 frame 數量有關，因此會有這個問題。

OPT(Optimal Page Replacement)

如果知道未來(完整)的 reference string，則可以找到最佳的 page replacement，也就是讓 swap out 的 page 是未來最晚使用的，但實際不可能，僅當作學術研究的比較。

LRU(Least Recently Used)

類似 Optimal，但變成過去最久沒使用的 page 會被 swap out。
與 optimal 一樣，是用一個 stack(或稱 replacement queue) 來紀錄，越上面是最近使用的 page，因此 victim 是最下面的 page，且 reference 時會把 page 移到最上面。因為是用 doubly-linked list，需要修改 6 個 pointer。

LRU 和 OPT 等都是 stack algorithm，都是用 page 的 priority 判斷。可以發現若有 N 個 frame，則 page frame 中會有最近使用到的 N 個 page，所以 N+1 個 frame 則 page frame 必定包含 N 個時的 page frame，因此不會有 Belady's Anomaly。

LRU Approximation Algorithms

LRU 要在每次存取 page 都更新存取時間，或搬動 stack 內容，沒有硬體支援這樣的操作。類似 LRU 精神的替代方法是記下一個 reference bit，預設 0，有用到就設為 1，但沒辦法知道每個區段內的順序。也許會每一段時間把所有都設為 0。

• Additional reference bits: 比如用一個 8-bit unsigned int，用到時設高位為 1，每個循環(比如 100 毫秒)把所有 page 的 bits 右移一位。victim 找最小的，也就是最久沒用到，有多個的話可能是全部 replace 或 FIFO。
• Second-chance: 改良 FIFO，但如果在準備把隊伍前面的抓去當 victim 時發現它的 reference bit 是 1，則當作新的 page 重新排隊，實作上可以用 circular queue 來實作。也稱為 clock algorithm
• Enhanced second-chance: 合併看 (reference bit, modify(dirty) bit)，順序低到高。優先找沒有用過的 page，都(沒)用過則找沒有修改過的，因為不需寫入 swap，overhead 較小。

Counting-based Algorithms

記錄每個 page 被使用的次數

• least frequently used(LFU): victim 找最少使用的 page。但是若先用到很多次但後面不需要用，則反而會是比較後面被清掉，因此 counter 可能太大。會在每次循環把所有 page 的 counter 右移一位，因此 counter 會 exponential decay。
• most frequently used(MFU): victim 找最多使用的 page。換個思路，少用的 page 也許代表才剛 load 進來，之後更有可能用到。

Page Buffering Algorithms

• 使用 Pool of free frames，保留一些 free frame，replacement 一樣找 victim，但需要的 page 可以從 pool 提早找一個 frame，等到 victim 被寫完再放回 pool，好處是不用等 victim 被寫完。
• Modified page 可以在閒置時先寫入 disk，未必是因為要 swap out，這樣可以提高 clean page 的比例，減少 swap out 時的時間。
• 紀錄 Free frame 原本對應到什麼 page，這樣 page fault 如果還沒真正被清掉，不需要重新讀 disk。

Applications and Page Replacement

Application 可能比 OS 更懂要用哪些記憶體，比如 database 自己更知道 replace 哪些 page 會更好，以及讀取或寫入的 buffer 應該要多大最好。但一般情況還是別管太多讓系統決定比較好。

• Memory 方面，可以用
  • mlock(禁止 swap)
  • madvise(指定區塊是順序、隨機或是不再需要)
  • mmap(直接分配大區塊，2MB or 1GB 等)
• I/O 方面，可以用
  • raw disk，沒有 directory、file 等 FS 提供的功能
  • O_DIRECT 跳過 buffer cache

Allocation of Frames

每個 process 有最低 frame 數量要求，因為

1. frame 太少會導致 page fault rate 太高，影響效能
2. frame 真的太少可能導致一個 instruction 所需的 page 無法完整載入，比如 IBM SS MOVE，instruction 本身 6 bytes，worst case 可能跨越 2 page，而 from、to 也可能各自兩個 page，因此可能需要 6 個 frame。

最高的限制當然就是 physical memory 的大小。

Global vs Local Allocation

• Local: 每個 process 用自己的 set of frames，符合每個 process 的效能，但 Internal Fragmentation 會比較多。較適合 Real-time mode。
• Global: 所有 process 共用一個 set of frames，Internal Fragmentation 會比較少，throughput 較高，因此廣泛使用。較適合 Online mode。

Global 可能發生 logical 總和大於 physical，產生大量 page fault。因此會做 Reclaiming: 盡量保持 free frame 數量在一定範圍內，低於 min 開始 replace、高於 max 停止。

replacement 有沒有分 Global 與 Local？實際上通常會用 Global。好壞處 left as an exercise。

Linux Out-of-Memory Killer(OOM killer)

更極端的狀況，Free memory 真的太低時，會 ternimate 部分 process，在 kernel 必要的以外，試著 kill 用量大的 process 以減少 kill 的 process 數量。

一些細緻(meticulous)的演算法能讓使用者設定哪些 process 可以犧牲，具體是在 /proc/<pid>/oom_score，可以修改 /proc/<pid>/oom_score_adj，越高越容易被 kill。

Fixed Allocation

• Equal allocation: 每個 process 都一樣大小。可能不會把所有 phtsical frame 分完(比如除完的餘數)，使用 free frame pool 在需要時動態額外分配。
• Proportional allocation: 依照 process size 為比例分配，通常是以 text segment、data segment 的大小總和來分配。

Non-Uniform Memory Access(NUMA)

如果有很多 CPU，每個 CPU 有各自的 local memory，則存取其他 CPU 的 memory 會比較慢。會盡量把 process 在上次執行的 CPU 上執行。

這裡指的是在同一張主機板上的 CPU，因為 CPU、記憶體很快，通常不會用網路連接記憶體，除了 DSM。

Linux CFS scheduler: 階層式的 scheduling domain 結構，每個可能包含多個 CPU，讓執行緒盡量在同個或相近的 domain 執行。Solaris也是類似，改叫 lgroups (locality groups)。具體細節要再確認一下。

Thrashing

CPU 使用率太低時，系統會喚醒待命狀態的 process 以增加多工度。但達到一定程度時，記憶體不夠，會一直 page fault，進而一直 page in/out。CPU 沒有實際做事，因此 CPU 使用率又更低，形成惡性循環。
實際上 page fault 時，會有顯性延遲: page in/out 的 I/O 時間，以及隱性延遲: TLB 等 cache miss 增加。

Locality Model

這種現象包括時間區域性(temporal locality)和空間區域性(spatial locality)。畫出橫軸為時間，縱軸為 memory access 的 address，會發現可以分成幾個時段，每個時段活躍的使用同一些 page。如果所有 process 總和大於 physical memory，則會發生 thrashing。

Working-set Model

根據 Locality Model 的觀察，稱一段區間內存取的 page 的集合為 working set。

可以簡單的加總所有 process 的 working set 大小，若太低就多跑一些 process；若超過 physical memory，則把一些 process swap out 並 suspend。

難處就是區間要如何設定，有以下方法：

• 使用每固定數量的 reference 觸發一次的 timer，具體作法像 additional reference bits 那樣。但太大太小都會有問題。
• 根據 Page-Fault Frequency 動態調整: 太高時增加 frame，太低時減少 frame。

結語

然而，最簡單的方法還是暴力的增加更多 physical memory，各種規模的裝置都適用。

Kernel Memory

Kernel memory 比較不能接受被 swap out，因此通常不會用 paging system，會一直保留在 physical memory 中，因此需要更注重 Internal Fragmentation。且有些 memory 需要有連續的 physical memory，所以要用特殊的方式管理。

Buddy System

因為可能需要很大的連續記憶體，合併連續的 frame 作為 segment，管理會更有效率。但又可能需要很小的記憶體，因此把 segment 分成 2 的冪次大小，用 binary tree 管理，節點稱為 buddy。比如需要 31 KB 就拿 256 KB 的 segment 切三次變成 32 KB 的 buddy。

但這樣的 Internal Fragmentation 還是太大，比如 33 KB 就要 64 KB 的 buddy。

Slab Allocation

因為 kernel 是已編譯、固定的，因此可以知道每個 object 的大小，比如 Linux 關於 process 的 task_struct 就是大約 1.7 KB。而系統中會有很多 process，可以把所有 task_struct 放在一起增進效率。

一個 slab 可能橫跨多個 page，而一個 cache 可能包含多個 slab。同大小的 object 通常放在同一個 cache 裡，cache 的 slab 數量是可以擴展的。

優先找未滿的 slab(partial)，否則從空的 slab 分配，再否則創建新的 slab。

SLUB

Linux 中 SLAB 的改良版

• 節省 metadata 儲存開銷，存在 page structure 裡
• 移除 per-CPU queue，在 SMP(對稱多處理系統)表現較好

SLOB

在記憶體很少的情況適用，比如嵌入式系統，分成 small(< 256 bytes)、medium(< 1 KB)、large(< 4 KB) 三種。

Ch12 I/O Systems

系統複雜時需要分工，OS 希望看到的簡單一點，像是管理 Memory 就用 Virtual Memory。I/O 則是會有 Driver 等機制幫忙。

• 硬體軟體變得更標準化
• 但有更多不同的 I/O 裝置

I/O 硬體

概念

• Port：裝置的連接點
• Bus：裝置間的連結
• Daisy Chain：裝置串聯

典型的 Bus 架構

PCIe Bus，許多裝置可能接到各自的 Controller，再接到 PCIe Bus，比如螢幕、儲存、USB 等。

Controller

在硬體端控制硬體。

Memory-mapped I/O

處理器通常是用 register (of device) 把指令或資料給 Controller，因此可以：

• 透過 Bus 修改 register 的值
• 透過 memory-mapped I/O，直接把 register 當作 memory 的一部分，這樣就不用特殊的指令，而且 memory 總是比較快。

register 種類

• Status register: 紀錄裝置狀態，指令是否完成、某個 byte 是否能讀寫、錯誤
• Control register: 控制裝置，啟動指令或更改模式
• Data-in register: 從裝置讀取資料
• Data-out register: 寫入資料到裝置

Polling

command register 可以想成 control register

Handshaking：先看 status register 的 busy bit 是否 on、寫入指令、設 command-ready 為 on、Controller 執行並設為 busy、裝置執行並清空 command-ready、error、busy。

操作時需要一直問是否 ready，造成 busy waiting。因此用 interrupt 來解決。

Interrupt

理解為一條電線伸到 CPU 裡。
若觸發就會執行 handler routine。一台安靜的桌機可能十秒內有 23,000 次 interrupt。
有 Interrupt Vector，紀錄每個 interrupt 的 handler routine 的位址。

Driver 開始 I/O 後，CPU 可能就去做其他事情，等 Controller 做完後會發送 interrupt，CPU 執行 handler routine。

比如 Page Fault 就是一個 Interrupt

特性

• 有差別，有些重要有些不重要，non-maskable、maskable
• vector 可能不夠用，因此一個 interrupt 可能對應一連串的 handler routine，再找出要執行的 routine
• 分得更細，有優先等級：interrupt priority levels
• Trap(Software interrupt)：內部引發，能夠引起 CPU 的注意。

DMA(Direct Memory Access)

希望大量資料傳輸別牽扯到 CPU，CPU 發起指令後，讓 Controller 自己傳輸資料到 memory。

DMA vs memory-mapped I/O: memory-mapped 主要是為了低傳輸量如 control bits，DMA 則是為了高傳輸量。

• Scatter-gather：一個指令就把多個 src 傳輸到多個 dst。
• Double buffering：如果搬到 kernel space 還得要多搬一次，因此希望同時也複製到 user space。需要有 locking 等。
• DMA 要是很快的，需要硬體支持。
• DMA 存取 memory 時，CPU 不該碰這塊記憶體。因為 DMA 速度快，應該不會影響很大。
• DVMA：virtual address 版本。

I/O interfaces

USB、802.11、Mouse、Keyboard 等

• Data-transfer mode: character(terminal)、block(Disk)
• Access method: sequential(Modem 數據機，TCP/IP)、random(CD-ROM)
• Tranfer Schedule: synchronous(磁帶)、asynchronous(鍵盤)，隨時跳出一個指令
• Sharing: dedicated(磁帶)、multiplexed(鍵盤)，能不能給多個 process 用
• Device speed
• I/O Direction: RO WO RW

OS 通常有 back door，比如 UNIX ioctl，繞過 driver

Block and Character Devices

read、write、seek

Block:

• Raw I/O：類似 back door
• Direct I/O：沒有 buffer、lock，像是 O_DIRECT。

Character:

get、put

Network Devices

通常與 Disk 的方式不同，透過 socket 連接

Clocks and Timers

要對時，或是五秒後給一個 interrupt 等。

Nonblocking vs Asynchronous I/O

再複習一次，Nonblocking 是讀到什麼就馬上回傳，而 Asynchronous 像是觸發一個指令，之後某個時間總之會完成。

Vectored I/O

同時做好多個 I/O，比如 readv。

scatter-gather method 比多個個別的 system call 好，省時而且比較不會被干擾（race condition）

Kernel I/O Subsystem

I/O scheduling

同時可能會有很多 threads 要用某 device，所以需要排程，未必要 First come first serve。

Some methods

• Buffering
  在兩個裝置間或裝置與應用程式間，暫存資料
  • 速度有差，Double buffering: producer 與 comsumer 都有各自的 buffer
  • 大小有差: 比如網路，會把大檔案分成多個封包，因此要有個地方暫存封包
  • copy semantics: 希望複製過去的資料是呼叫指令時的資料，因此就把資料先複製到 buffer。
• Caching
  快速的記憶體，暫存一個複製。要找時就先去 cache 找。
  與 Buffer 的差別：buffer 不會是複製一份。
• Spool: 一個 buffer，不應該有穿插的資料，比如印表機。
• Device Reservation: 類似 lock 一個 device，但要注意避免 deadlock。

Error Handling

I/O 可能有很多問題，可能會以回傳值的方式表達，比如 USB 傳輸時突然被拔掉，程式要處理這些事情。

IO Protection

避免 User 亂用，基本上都要透過 system call 執行（trap to kernel）。

Kernel Data Structure

需要紀錄開了哪些檔案，有哪些連線。像 Windows 會把所有指令當作 message，雖然有 overhead 但更方便。

Power Management

邊緣裝置如手機難以散熱，伺服器可能散熱比本身運算還耗電，沒有冷氣很可怕。

Power Collapse: 讓裝置冬眠，只消耗很少的電但仍能反應。
例如 Android 用 Device Tree 了解 Component 間的關係，如果一個 bus 或整個 system 上的裝置都沒在使用，則可以把 bus 關掉或把 system power collapse。

ACPI(Advanced Configuration and Power Interface)

Streams

UNIX 的方法，模組化的設計，每個 stream module 有 read/write queue，可能分很多層。

Performance

I/O 常常使用，且會產生大量 Interrupt、Context Switch，所以要注意。

• 減少 Context Switch
• 減少複製次數
• 減少傳輸
• 盡量 DMA 更同步(比如寫完剛好 CPU 剛剛變得有空)
• 盡量讓 Hardware 做事
• 讓 CPU、Memory、bus、I/O 平衡一點，不要只有一個人做事

Ch5 CPU Scheduling

有些 process 是 CPU Bound(較多長的 CPU Burst)或 I/O Bound(較多短的 CPU Burst)，整體而言長的 CPU Burst 會很少，大部分都是短的。CPU/IO Burst(突發) 代表做事的時間段。

CPU scheduling 就是找 ready 的 process，決定要執行哪個。以下情況需要決定：

1. Running -> Waiting
2. Running -> Ready
3. Waiting -> Ready
4. Terminate

1、4 都是要跑新的 process，2、3 則也許可以選擇繼續執行原本的 process。

Preemptive vs Nonpreemptive

Pre-empt: 搶在…之前說話（或行動）;預先制止

• Nonpreemptive: 2、3 中，不管其他 process 到了 ready，都不影響不會去中斷目前在跑的 process。
• Preemptive: 2、3 中，會考慮要不要中斷目前在跑的 process。

幾乎現代系統都是 Preemptive。

可能有 race condition，比如 shared data 但有一個 process 被 preempt 了，這需要透過同步來解決。

Dispatch

執行下一個 Process，可能要 Context Switch、Mode Switch 等，Dispatch latency 指停下目前的 Process 到下一個 Process 開始執行的時間。

Criteria

不會只看一個指標，會綜合評估

• MAX CPU Utilization
• MAX Throughput: 單位時間執行的 process 數量
• MIN Turnaround time: 單一 process 總共花多久完成
• MIN Waiting time: 在 ready queue 的時間(=Turnaround time - CPU Burst time)
• MIN Response time: request 後第一次執行的時間，通常在 real-time system 會用到

Scheduling Algorithm

First-Come, First-Served (FCFS)

最簡單，就是一個 queue，FIFO。

Convoy effect: 需要執行很久的 Process 卡住其他的 Process。解決方法比如可能會想要讓 I/O-Bound process 先做，等待時間讓 CPU-Bound process 執行。

Shortest-Job-First (SJF) & Shortest-Remaining-Time-First (SRTF)

Nonpreemptive。如果所有 process 同時 ready 且沒有新的 process arrive(變成 ready)，則 SJF 是 Minimize average waiting time 的最佳解。

與 Optimal Page Replacement 一樣，要估計或是問使用者花多少時間，這很難做到。可以用 Exponential averaging: 第

$n$ 個估計為

${\tau }_n$，實際上第

$n$ 個 CPU Burst 為

$t_n$，則

${\tau }_{n+1}=\alpha t_n+(1-\alpha ){\tau }_n$，

$\alpha$ 通常是 0.5。這樣的話，

$\tau$ 會慢慢接近實際的 CPU Burst 時間。需要選

$\alpha ,t_0$。

若 Preemptive 則是 Shortest-Remaining-Time-First(SRTF)。

Shortest-Remaining-Time-First 基本上是 Minimize average waiting time 的最佳解，不管 arrive 時間。

Round-Robin (RR)

輪流做一段小時間(Time Quantum q，大概 10-100ms)，可以減少 response time。

若 q 非常大就變成 FCFS。不考慮 context switch 與 dispatch 的 overhead，肯定是 q 越小越好。實際上一個 context switch 可能會小於 10us，也是差不多能忽略，因此 q=10-100ms是合理的。

通常會讓 80% 的 CPU Burst 小於 q(一個 Quantum 就做完)。

Priority

可以是 Nonpreemptive 或 Preemptive，Priority 設得好可以變成 SJF。

可能有 Starvation 的問題: Priority 低的可能永遠執行不到，可以搭配 Round-Robin，或是用 Aging: 隨著時間增加優先權。

通常數值低的優先權高。

Multilevel Queue

每個 Priority 一個 queue，每個 queue 可以有不同作法。

通常 process 的 priority 是：

1. Real-time
2. System
3. Interactive
4. Batch

Multilevel Feedback Queue

Process 可以移動到別的 queue，Aging 可以藉由此方法達成。

Thread Scheduling

現代實際上是在 Schedule (kernel-level) threads。

• Process Contention Scope(PCS): many-to-many 或 many-to-many，就變得是 user-level threads 在競爭，由 thread library schedule。
• System Contention Scope(SCS): kernel-level threads 在競爭，例如 one-to-one 就都是。

Pthread 可以用 pthread_attr_getscope 來查詢或以 pthread_attr_setscope 來設定，可以是 PTHREAD_SCOPE_PROCESS 或 PTHREAD_SCOPE_SYSTEM。

Multi-Processor Scheduling

• Asymmetric Multiprocessing(AMP): 優點不用太注重 shared data，缺點是 master 可能變成瓶頸。
• Symmetric Multiprocessing(SMP): 可以分成所有 Core 共享 task list，但要用 lock 防止 race condition；每個 core 有一個 task list，需要負載平衡。

Simultaneous Multithreading(SMT)

Intel 稱 hyper-threading。每個 core 會有多個 thread，可以在一個 thread 存取記憶體(memory stall) 時，讓其他 thread 交替執行。

OS 會直接把 thread 當作 core 來用。

這樣需要兩層 scheduling，第一層是決定 kernel-level threads(Software threads) 要在哪些 Hardware threads(CPU threads) 上執行，第二層是決定 Hardware threads 要在執行哪個 Processor Core 執行。兩層未必完全獨立，如果互有認知的話會找到更好的解。

Load Balancing

• Push Migration: 過一段時間檢查分配是否均勻
• Pull Migration: 發呆的 Processor 自己去找工作來做

Processor Affinity

Process(Thread) 會想在之前跑的 processor 上跑，可能是因為 Processor 上有相關的 cache。Load Balancing 時會考慮這個問題，因為若移動到別的 Processor 會需要多餘時間讀資料。

分 Soft、Hard，是否強制跑在同個 Processor 上

NUMA 的話可能會盡量分配與 Processor 鄰近的記憶體給 Process。

Real-Time CPU Scheduling

引進 Deadline，分 Soft、Hard。

Event latency: 事情發生到做出反應。可能被 Interrupt latency(Interrupt 到 ~ Routine 開始做，比如分辨類型、Context Switch)、Dispatch latency 影響。
Event latency 中，可能是由 Interrupt latency、Interrupt routine 執行時間、Dispatch latency(Routine 切換成處理事件的 Process)、處理事件的 Process 組成。

通常會分配某種 Priority，達成 Soft real-time。

Periodic Tasks Model

以下 Real-time scheduling 會考慮一個簡單的 Model：Processing time t、Deadline d、Period p，每 p 時間，會要求在 d 時間內做完要花 t 時間做的事。

$0\le t\le d\le p$，通常

$d=p$。

各種演算法

• Rate-Monotonic Scheduling
  Priority 是固定的，把
  $1/p$ 作為 priority。但可能有辦法都符合結果卻不符合。
• Earliest-Deadline-First(EDF) Scheduling
  Priority 會調整，Deadline 越早的越優先。差不多是最佳解，如果這樣也做不完那其他方法大概也不行。
  雖然看起來很好用，但紀錄、計算 Deadline 還是需要額外時間，有時也會用 Rate-Monotonic。
• Proportional Share Scheduling
  總共有 T 個 share，並保證 Process i 能分到
  $N_i$ share。若又來一個 Process 會導致總共時間超過 T，那就會被 admission controller 拒絕。
  知道分配到多少時間後就能分析 Worst case turnaround time（Arrival 到做完的時間）是否在 Deadline 內。

POSIX Real-Time Scheduling
可以設同 Priority 的要以 FIFO 或 RR，比如 SCHED_FIFO、SCHED_RR

Scheduling Examples

Linux Scheduling

早期是

$O(1)$，但後來想考慮多一點，用 Completely Fair Scheduler(CFS)。以 Scheduling class(Priority) 來 schedule。

Linux Default Scheduling

• Nice value: -20~19，一個 Process nice 大代表它人很好，願意讓別人先做。用來算出 targeted latency，保證一段時間內可以執行一次。
• Virtual run time: 估計一個 task 要跑多久。可以根據 virtual run time 來 schedule。

Linux Real-time Scheduling

POSIX.1b: 把 -20~19 對應到 100~139，0~99 留給 Real-time 的各種 class。

Windows Scheduling

一樣是 Preemptive、priority-based。有分 class(Real-time 等)，之後再分 priority，是一個 multi-level 的設計，但高的 class 低 priority 不一定比低 class 高 priority 優先。

與使用者(前端)相關的程式，會提升 scheduling quantum 到約 3 倍。

Windows 7 支援 User mode scheduling，讓使用很多 thread 的程式自己 schedule。

Algorithm Evaluation

首先還是得決定要注重什麼指標。

• Deterministic Modeling: 自己設一些 task，算出各種指標。
• Queuing Modeling: 把所有參數改成機率分布，用各種 Model 分析。
  • Little's Formula:
    $N=\lambda W$，N 是平均 queue 長度，
    $\lambda$ 是 arrival rate，W 是平均等待時間。
• Simulation: 比如記錄下實際的使用情況，再 Deterministically 測試。
• Implementation：成本、風險高，難以分析。

Real-time 可能需要用 worst case 而不是 average，可能會用悲觀的估計方式。

Ch11 Mass-Storage Systems

Secondary storage，介紹其物理結構、性能特性、I/O scheduling、系統提供的有關服務(比如 RAID)

Overview

HDD

• Platters: 磁碟片，通常有兩面，一個硬碟有很多片
• Tracks: platter 上同心圓的區域
• Sectors: 每個 track 上的區域(512 bytes to 4 KB)
• Cylinders: 不同 platters 同一個 track 上的區域
• Positioning time: 磁頭移動到正確的 track 上的時間，分成 seek time(移動讀寫臂)與 rotational latency(轉到正確的 sector)
• Head Crash: 磁頭與 platter 碰撞，可能會損壞 platter

NVM(Non-volatile Memory)

SSD、Flash Memory。以 page 分區讀寫，但寫入前需要擦除涵蓋多個 page 的整個 block，所以 Controller 會用 Garbage Collection，把需要擦除的 block 裡的資料搬離。

硬碟的每個部分有一定的寫入次數限制，因此 wear leveling 會均勻的寫入到所有記憶體單元。另外，會以 TRIM 來讓硬碟提早填入 0，這樣寫入時就不用先填 0。

Others

通常會視一個硬碟為 logical block 的一維陣列，以 logical block address(LBA) 來存取。

• Constant linear velocity(CLV): 每個 sector 同樣弧長
• Constant angular velocity(CAV): 每個 sector 同樣角度，因此旋轉經過的時間會一樣

HDD scheduling

最小化 access time，最大化 Bandwidth。

讀寫都要經過 system call，以及檔案管理等，而且有 request queue，可以排程。

現代的系統通常不知道 physical 位置，但總之 LBA 越大 physical address 通常也越大，相近的 LBA 通常也相近。

FCFS

浪費時間

SCAN scheduling

磁頭從一端到另一端，然後再回來，像電梯一樣。

問題：假設 request 是均勻分布在 cylinder 上，掃到一邊時，另一邊的 request 密度最高，且等了很久。

C-SCAN scheduling

磁頭從一端到另一端，然後回到起點，這樣的話就不會有一邊的 request 等很久。

如何選擇

以上只是一些簡單的方法，但 SCAN、C-SCAN 就已經不錯了。Linux 會用 deadline scheduling，儲存 read、write 在不同 queue，read 優先，因為 process 通常是因為 read 而 block。

NVM Scheduling

其實不太需要 scheduling，因為沒有物理機械，random access 很快。用 FCFS 就可以了，Linux 還會把鄰近的 request 合併。

Write amplification: write 導致 garbage collection，再導致許多 read/write。

Error Detection

• Parity bits: 以一個 bit 代表一串 bit 的奇偶性。只能檢測一個 bit 的錯誤。
• CRC(Cyclic Redundancy Check): 網路常用。以多項式除法(此時減法改用 XOR)檢查錯誤，資料
  $M$，Generator Polynomial
  $K$，並約定一個位移
  $n$。傳輸者把
  $M$ 左移
  $n$ 位，然後除以
  $K$，把餘數附加到
  $M$ 後面。接收者確認收到的除以
  $K$ 整除。除非錯到 collision，否則都能檢測出來。
• ECC(e.g. Hamming code): 用稍微多一點的多餘位元。比如 [7,4] Hamming code 能夠檢測兩個 bit 的錯誤，或是檢測並修正一個 bit 的錯誤。

Storage Device Management

• Low-level Formatting: 定義 sector 大小等。
• Partitioning: 將硬碟分成多個區域，每個區域可以獨立管理。
• Volume: 將一個或多個 partition 組合成一個邏輯單位。
• Logical Formatting: 定義檔案系統。
• Clustering: 作業系統可能會把多個 sector 當作一個 cluster，這樣可以減少 cluster 的數量，減少 metadata 的開銷。

硬碟中通常會有 bootstrap，放驅動程式等，這會放在 boot blocks 中。
比如 Master boot record(MBR)，存 partition table，也紀錄哪個 partition 是 bootable。

Bad block: 壞掉的 sector。

• Sector sparing: 以好的 sector 取代壞的 sector，要存取壞的 sector 就對應到好的 sector。
• Sector slipping: 平移很多個 sector，比如壞 17，那就用 18 代替 17，19 代替 18…

Swap-Space Management

可以是一個 partition 或一個檔案。會紀錄 swap map，代表一個 page slot 被幾個 process 使用，或沒被使用。

Storage Attachment

• Host-attached: 硬碟直接接到本機，比如 SATA、USB、Fibre channel(FC)。
• Network-attached(NAS): 硬碟接到網路上，比如 iSCSI、Fibre Channel over Ethernet(FCoE)。透過 RPC 等方式存取。
• Cloud Storage: 資料中心，透過 API 存取。
• Storage-Area Networks(SAN): 連接許多 server 與 storage array 的 network，用儲存協議而不是網路協議，動態且彈性的分配 storage。通常是用 FC 來連接。
• Storage Arrays: 專門的儲存設備，可能有 SAN port、網路 port。

Ch13 File-System Interface

與 SP 高度重複，跳過。

Ch14 File-System Implementation

Allocation Methods

• Contiguous Allocation: 連續的區塊，容易存取，但需要預測大小，若空間不夠還需要把資料移到其他地方再寫回來（Compaction）
• Extent-based Systems: 分成多個連續區塊(extent)，每段的最後指向下一段的開頭。
• Linked Allocation: 每個 block 有指向下一個 block 的指標，容易擴展，但需要額外的指標，且隨機存取較慢，萬一中間某個 block 故障就很麻煩。
• File-Allocation Table (FAT): 把 pointer 存在 volume 的最前面，因為是在一個 block 內，可能會更快，但順序讀取要先讀 data 再讀 FAT 往復循環，未必真的比較快。
• Indexed Allocation: 用一個 block 存這個檔案有哪些 block，沒有 fragmentation，也不用 compaction，但需要額外空間。

要考慮 Sequential Access 與 Random Access 的情況。

Free-Space Management

需要知道哪些 block 還沒被使用

• Bit vector: 每個 block 以一個 bit 紀錄，但會需要花一些記憶體紀錄。
• Linked list: 每個 free block 寫下個 free block 的位址。需要一次存取很多 free block 時比較慢，但也能用 FAT 來解決。
• Grouping: n 個 free blocks 的資訊寫在其中某個 free block 中，比一般 linked list 快。
• Counting: 紀錄連續 free blocks 的頭與數量。如果 Allocation 是連續的或有 Clustering，會比較快。

Space Maps

ZFS 為了支援大量檔案、FS，考量了 metadata I/O 的時間。把空間分成多個 metaslab，每個有對應的 space map，是依照時間順序紀錄 log，把操作依時間順序紀錄，需要存取 metadata 時根據 log 模擬一遍。

TRIMing Unused Blocks

SSD 不能直接寫到 disk，而是要先填 0。

FS Performance

影響因素

• Allocation、directory 演算法：UNIX 盡量把 data block 放在 inode block 附近。
• 若存了「上次讀取時間」，就要花很多時間寫 metadata。
• Data Structure 大小是否固定。

Page Cache

把 file data 當作 virtual memory 來管理，效率更高。Mmap I/O 就會用 page cache。

Unified virtual memory: process page 與 file data 都用同樣的 page cache。

Unified Buffer Cache

若有 Buffer cache 又有 Mmap I/O，就會有 page cache + buffer cache 的 double caching 問題。

壞處：

• 浪費記憶體
• 浪費 CPU/IO 時間
• 兩個 cache 可能不一致

若 Mmap I/O 與一般 read/write 都用 Unified Buffer Cache，就能解決。

Free-behind and Read-ahead

Page cache 用 LRU 不太好，因為順序讀取某個檔案時，剛讀完的部分可能接下來反而比較不會再讀一次。

順序讀取的改良方法：

• Free-behind: 要求下個 page 後就把前個 page 釋放。
• Read-ahead: 預先讀取下個 page。

FS Recovery

• Consistency Check: 需要確保 metadata 與 data 一致。
• Log-Structured File System: 每次寫入都先寫到 log，然後再寫到實際的檔案系統。若有 crash，就比較可能從 log 恢復。
• Snapshot: 寫入時暫時寫到新的 block，確保沒問題再釋放舊 block。
• Backup

Ch15 File-System Internals

很多大概算常識，跳過。

Remote - Distributed Information Systems

統一的遠端資訊存取方式。

• DNS(Domain name system): 查詢 IP。
• NIS(Network Information Service): 提供用戶、主機等資訊的查詢。
• Microsoft 的 CIFS(Common Internet File System): 結合網路資訊做驗證。
• LDAP(Lightweight Directory Access Protocol): 也是安全的資訊查詢，用戶、群組等。

Consistency Semantics

要如何實作：多個使用者同時存取一個檔案、一個使用者修改後其他使用者看到的結果。

UNIX Semantics

• 寫入檔案時，會馬上被其他開啟的人看到。
• 另一種模式，所有使用者共用 pointer，會有 interleave 的問題。

Session Semantics

寫入檔案後，要關閉檔案才會被其他人看到變動。就像每次儲存變動都是一個 git commit + push。

Immutable-Shared-Files Semantics

最簡單的方法，Shared file 不能改變。

Ch6 Synchronization Tools

一樣與 SP 高度重複。

Critical Section

Requirements:

• Mutual Exclusion: 同一時間只能有一個 process 在 critical section。
• Progress: 若沒有 process 在 critical section，且有其他 processes 想進入，則在有限時間內選一個 process 進入。
• Bounded Waiting: Request 進入到真正進入時，限制其他 process 的進入次數，避免 Starvation。

Peterson's solution

以 flag 代表要不要做事，以 turn 代表在做事（atomic 的變數）。

// Pi:
while(1){
  flag[i] = true;
  turn = j;
  while(flag[j] && turn == j);
  // critical section
  flag[i] = false;
  // remainder section
}

前兩個明顯符合，重點是第三個，若 Pi 在 while 等的時候，就不會設 turn=j，且 flag[i]=1，因此 Pj 就會被 for 擋住。

不過現代處理器、編譯器可能會把不相依的 load/store 重新排序。Single-thread 沒差，Multi-thread 可能有問題，因為對某 thread 可以 reorder 對其他 thread 可能就不行。

flag 與 turn 順序相反會導致 Peterson's solution 出問題。

Hardware Support for Synchronization

Memory Barriers

不同 Memory Model:

• Strongly ordered: 改變會馬上被其他 processor 看到
• Weakly ordered: 反之，不一定馬上被看到

Memory Barrier 讓其他 processor 強迫看到改變，會等前面的 load/store 完成才繼續執行。像是在 include 間加入註解避免 formatter 亂排序。

Hardware Instructions

現代系統提供以下 atomic operations：

• test_and_set(bool *target): 先紀錄 target 目前的值，設為 1 再回傳原本的值。

while(1){
  while(test_and_set(&lock));
  // critical section
  lock = 0;
  // remainder section
}

• compare_and_swap(bool *target, bool expected, bool new): 如果 target 的值是 expected，就設為 new，並回傳原本的值。

while(1){
  while(compare_and_swap(&lock, 0, 1) != 0);
  // critical section
  lock = 0;
  // remainder section
}

以上兩段程式都沒辦法達到 Bounded Waiting，但加其他操作就可以(比如 critical section 完指定執行下個 thread)。

Atomic Variables

通常以 compare_and_swap 來做其他 Synchronization Tools，比如 atomic variable。

Semaphore

一個只能以兩種操作存取的 int，像是停車場空位數字：

• wait(S): 等到 S 小於 0，把 S 減一。
• signal(S): 把 S 加一。

可以用來限制同時執行的 thread 數量，如果最高只有 1 就可以作為 mutex。若不用先 wait 也能 signal，也可以當成通知機制。

若不要 busy waiting，就可以 suspend，並讓其他 thread 通知，像是 condition variable。

Monitors

signal、wait 可能有人亂用，因此可以用 Monitor 來包裝。

一種 ADT(Abstract Data Type，以一些 function 包裝 data，如各種資料結構。像是網站只提供 API，使用者不用管具體怎麼執行。)，把資料包裝起來，使其在存取時自動進行 lock/unlock 等 synchronize，只有一個 thread 能執行，就不怕使用者亂寫 code。

會提供一些 condition variable 讓 thread 可以等。

Liveness

一些系統必須滿足的性質，使 thread 運作。

Safety: 希望壞事別發生。

Priority Inversion

L M H 三種 priority 的 thread，L 在用某資源，H 在等，但 M 卻可以中斷 L。

解決方法是 Priority Inheritance: L 的 priority 提升到 H 的 priority，等 L 做完後再恢復。