本文為清華大學開放式課程上課心得整理。
Swapping
所謂的 swapping 指的是程式進入記憶體開始執行之後，因為 context switch 在硬碟與記憶體之間轉換的行為。硬碟的 swap space 是一個特殊的空間，被作業系統的 midterm scheduling 使用。swap 不一定是以程式為單位，最小可以到 4kb，因此在使用上相當有彈性。
程式的記憶體位置如果是在 compile time 或 load time 時就決定，那在 swap 時就一定要匯到原來執行的位置，只有 execution time 編譯的記憶體位置才能在任意位置 swap，因此 swapping 與 execution time 必須同時使用才能最大化執行效率。
此外，當程式被 swap 的時候，作業系統必須檢查程式是否在 idle 狀態，也就是程式不能在執行 I/O。解決的方法通常有兩個：
・程式進入 I/O 時立旗標，作業系統必須等旗標撤掉再 swap。
・由於程式透過作業系統做 I/O，因此在作業系統裡建立 OS buffers，讓程式將資料搬進作業系統的記憶體中，將程式 swap 掉，等 I/O 結束再載回記憶體，再將 buffer 中的資料複製回程式的記憶體空間內。
由於 swapping 是將記憶體裡的程式搬到硬體中暫存，因此需要考慮搬運速度的問題；此外，如何決定哪支程式要被移出記憶體，將搬移次數最小化，也是另一個要思考的問題。
Contiguous Memory Allocation
連續的記憶體分配有幾種常見的做法：
・Fixed-partition allocation：先將記憶體空間等分切割，分割的數量就是能執行的程式數量（Degree of multi-programming）。
・Variable-size partition：由於每個程式所需的記憶體大小不一，等分切割容易造成記憶體浪費，因此發展出以程式需要的空間做切割的記憶體分配方法。
在這個情況下，為了有效利用空間，會想辦法將剩餘的位置也填滿，棉滿的演算法可以分為 first fit（找到第一個空位就載入）、best fit（找到最佳位置才載入）、worth fit（找到最大的空間載入）三種；由於無法保證效能最佳化，大部分情況下，作業系統會選擇 first fit 來最大化執行速度。
Fragmentation
上述記憶體浪費的狀況，在電腦科學中有一個專有名詞，稱為 Fragmentation。Fragmentation 又可以再分為 external 和 internal 兩種，external 指的是記憶體還有剩餘空間，但空間大小不足以放進其他程式執行，是發生在 Variable-size partition 的狀況；反之，Fixed-partition allocation 則是對應 internal fragmentation，在每個程式執行的記憶體內會出現剩餘空間。
external fragmentation 的解決方法為壓縮（compaction），也就是定期清理記憶體釋出空間，internal fragmentation 則會用 paging 處理。
Non-Contiguous Memory Allocation
與 Contiguous Memory Allocation 相反，程式執行使用的記憶體空間如果不連續，便稱為 Non-Contiguous Memory Allocation。Non-Contiguous Memory Allocation 也有 Fixed-size 與 Variable-size 兩種方法。
Fixed-size non-contiguous
即俗稱的 paging，將 logical 與 physical memory 都做分割，physical 的分割單位稱為 frames，logical 的分割單位則稱為 pages，兩者的概念不互通，但是大小會完全相同，如此作業系統才能將兩者做匹配。
要匹配 logical 與 physical memory，作業系統必須先確認幾件事：
- 有哪些空閑的 frames 可供分配
- 建立 page table，用來儲存記憶體的配對資訊
paging 可以完成記憶體的不連續分配，也因為是 Fixed-size，所以能避免 external fragmentation，並減少 internal fragmentation 發生；同時透過 page table 的設定，也能讓程式共享記憶體 / pages。
CPU 在使用記憶體時是使用所謂的 byte addressing，即是以 byte 為單位作定址方法，為了找到 physical memory 真正的位置，作業系統會將 logical memory 切成兩部分，一個是 Page number（p），用來表示該記錄在程式裡的第幾個 page，另一個是 Page offset（d），用來表示該記錄在該 page 的位置（相對位置）。
轉譯記憶體時，必須非常留意 Page number 以及 Page offset 的長度所代表的意義，Page number 如果是 N bits，就代表該程式最多只能載入 2 的 N 次方個 page 大小的記憶體；Page offset 如果是 N bits，就代表該程式的一個 page 大小最大就是 2 的 N 次方（即 page size），physical memory 即 page base address 加上 page offset 的結果。
Free Frames
除了轉譯，作業系統還必須知道哪些記憶體位置是空閒的，才能載入資料，為了快速找到空閒的記憶體，作業系統會建立一張 free list，當程式需要使用記憶體時，只要從 list 上面 pop up 即可；反之，如果要釋出記憶體，也只要將該程式使用到的記錄釋出到 list 即可。
Page / Frame Size
Page / Frame 的大小由硬體決定，是影響電腦效能的關鍵，通常在設定上會遵循以下幾個原則：
・Typically a power of 2
・Ranging from 512 bytes to 16 MB / page
・4 kb / 8 kb page is commonly used
若 Page 與 Frame 的大小設太大，就容易造成 internal fragmentation；但由於現在的電腦效能很好，若 Page 與 Frame 設定太小，則會導致 page 數量龐大，使得作業系統浪費過多空間儲存這些資訊，程式執行時也必須花很多時間在讀取 page 上，影響效能，因此大部分電腦的 page size 都會設為 4 kb。
Implementation of Page Table
Page table 存在於作業系統的記憶體中，但負責記憶體轉譯的部件（通常是 MMU）存在於硬體中， 因此 MMU 必須先把資料載入硬體才能開始轉譯。
作業系統會將 page 存在一個特別的空間，稱為 PTBR（Page-table base register），PTBR 裡面記錄的是 physical address，其值存在於 Process Control Block（PCB）中，因此 CPU 在執行 context switch 時，也會將記憶體的位置載入 MMU 中。
PTBR 讀取記憶體的次數是二，一次是讀取 page table，將資料載入 MMU 之後，才能真正的將資料讀取出來，因此需要兩倍的時間才能拿到資料，為了解決這個問題，電腦加入了另一個機制：TLB。TLB 其實就是暫存的概念，將讀取過的資訊先記錄下來，如果有紀錄便不需再轉譯，用來節省重複取用的時間。
Associative Memory
在介紹 PTBR 與 TLB 的關係之前，我們先來了解 TLB 是怎麼被實作出來的。TLB 是一個記憶體空間，且為 Associative Memory，Associative Memory 有以下幾個特色：
・快速，是普通記憶體的好幾倍速
・無序，但為了增加效能，可以同時查詢所有的記錄，讓時間複雜度降到O(1)
由於是特殊規格設計，價格會隨著空間大小遞增，所以不可能將整個 page table 的資訊都放進去，這與一般的 cache 的性質是相同的。有別於每個程式都有自己的 page table，存在硬體中的 TLB 只有一組，當 CPU 執行 context switch 時，為了確保資料配對正確，TLB 通常會執行清空（或是在 TLB 多加一個欄位記錄 process id，但常見為直接清空）。
