開始之前

既然 Load/Store 都寫完了，就來講講 Memory 吧！

相信看到這邊的讀者在學校都有學過或者接觸過計算機相關知識，
課堂描述的角度不一定適合每個人，
網路上很多不同角度切入的文章也很值得參考，
例如這次參加鐵人賽的 ycliang 發的系列文，
可以看到從 OS 角度的切入實際應用案例，
看完之後回頭看教材會更容易理解。

畢業之後斷斷續續的有看過很多公開課程，
猴子推薦 Onur Mutlu 教授的頻道，
我當時是看 CMU 時期的版本，因為疫情的關係，這陣子有上傳很多較近期的課程。
Onur Mutlu 在卡內基美隆大學(CMU)和蘇黎世理工大學(ETH Zürich)任教，
內容清晰而且會帶入很多實際的案例以及參考文獻。
課堂中也有很多很棒的觀念提點，
例如在問同學怎麼做決定的時候，就會說他很喜歡的答案叫做"It depands."，
引導同學更進一步描述情境。
或者在講架構的時候會提到它很喜歡的想法"Do other things."，
分別對應到 CPU 亂序執行的相依性分析，找出等待時可以先做的指令，
以及 GPU 因為運算量夠多，用 fine-grained MT 的方式重疊等待時間等等。

除了上面的 Onur Mutlu 教授之外，還要推薦 Georgia Tech - HPCA 課程，
特色是會把很多題目和運作行為用短影片的方式一步一步帶著做，
觀念的部分我會看 Onur Mutlu 教授，如果是某一部份看不懂就會來這邊查。

記憶體

好了，現在終於來進入正題了，
對大部分的使用者來說，就是一個可以存取的位置。
但是實際上分很多類，
例如 ROM、SRAM、DRAM、Flash、XPoint等等技術，
其中依照斷電後資料是否還在分為 Volitile 和 Non-volitile 等。

嵌入式系統中會需要修改 Linker Script 讓資料放在特定位置，
也有研究者在研究怎麼有效率的使用這些特殊記憶體，
例如國立中正大學的羅習五教授之前在 Facebook 也有提及相關研究。

記憶體特性

最常見的 DRAM 來說，存取步驟有：

• decode row
• drive bit line
• amplify row data
• decode column address & select subset of row
  也可以拆下自己電腦研究一下記憶體時序，上面有標示每個步驟需要的時間，
  通常也會有 Row Cache，讓下次存取不需要再經過前三個步驟。
  另外 jserv 也有提過因為 DRAM 平常就要定時充電的特性，
  有研究者在研究怎麼減少這部分的影響，
  細部可以參考 Onur Mutlu 的課程

記憶體存取特性

因為軟體對記憶體的使用上有特定的規律，
通常會有下面兩個現象：

• Spatial Locality：存取過的位置附近通常會是下一個存取目標，例如 Array。
• Temporal Locality：存取過的位置通常最近會再存取第二次

針對一些軟體也有特殊的規律，
例如：為了不要讓 OS 從記憶體被 Swap Out 到硬碟裡，Linux 可以把特定記憶體 pin 住、
又或者有些特殊的資料要常常存取，可以手動搬到特殊的記憶體位置等等。

Memory Hierarchy

Fast、Cheap、Large Capacity 是我們對記憶體的理想條件，
但是根本不可能同時達成。
為了讓記憶體滿足又大又快又便宜的特性，
我們利用上面提到的特性把記憶體分成多個階層，
就像我們家裏面會把在用的拿在手上，常用的東西放在手邊，
不常用的放在倉庫，想買但暫時不會用到的放在蝦皮購物車然後就會手滑。
記憶體也會這樣分層：

• Register
• Cache
• Memory
• Disk

Cache

收納類的書籍都會這樣說：
只留最重要的東西在桌上。

依照存取特性通常分成兩大類：

• Manualy：就是手動管理，例如 Tightly-Coupled Memory (ARM TCM)
• Automatically：硬體支援自動管理，是最常提到的 Cache 這個考試會考要背起來。

自動管理的 Cache 就是針對上面提到的兩個 Locality 特性設計的，
但因為指令和資料的存取特性不一樣，
比較貴的處理器還會分成 I-Cache 和 D-Cache。

既然是桌子和倉庫之間，資料有事沒事就會搬進搬出，
就要規劃怎麼使用桌上的空間啦！
目前常見空間設計通常都介於 Direct map 和 Fully Set Associative 之間，
N-Way Set Associative 是在 Conflice 和 Access time 取的平衡的設計，

有了桌面空間規畫之後，桌上都是空空的，
東西找不到(Cache Miss)就要進倉庫拿，
但是進倉庫又很花時間，這時候研究規律就很重要：
Cache 裡又叫做 3C (Capacity Miss, Compulsory Miss, Conflict Miss)
Conflict Miss 發生之後，又分成不同的置換方式 (Random, LRU)
也會因為存取特性設計 Prefatch (另一種形式的 Implice Memory Access)

另外資料管理又分成幾個類型，物品的故事掰不下去了就直接寫特性：

• Write-back vs Write-Through：寫入當下更新全部資料，
  或者等被置換掉才寫回去上一層
• Write-allocate vs Write-around：寫入 Miss 時會放一份在 Cache 裡，
  或者直接寫回去上一層(通常是 Memory)

Multi-Processor

在多處理器共用同一塊 Memory 的情況下又比上面更複雜了，
會在 Cache 發生類似 Data Racing 的情況，這時候就需要有仲裁者來管理。
於是偉大的 Bus Snooping Protocal 就出現了！
計算機組織最常介紹的就是 MESI 模型：

• Modify(M)：被改過了，如果原本資料是 Shared 就要做一些處理(例如清除其他 Cache 的資料)
• Exclusive(E)：資料只有我有，寫入的資料被置換掉的時候再寫回去就好
• Shared(S)：有多份資料在不同 Cache 裡
• Invalid(I)：這個 Cache Line 位置是空的，可以直接覆寫資料。

在實際運作的時候也可能有一個 CPU 一直寫入，但其他CPU只是讀取，
結果一直清除(evict)其他 Cache 的情況，
例如 LL-SC 在搶 Lock 的時候，這種情況稱為 False Sharing。

Virtual Memory

從古早時期記憶體就是重要的儲存單位，
但 Compile 後，執行檔中用到的相對位置和絕對位置都會固定下來，
於是不管有沒有用到，每個 Subroutine(Function) 都會被放在 Memory 上。

為了減少占用的的記憶體空間，於是 Overlay 就出現了，
簡單來說就是可以把某段程式從記憶體裡面拿出來，搬到指定的位置取代掉原本的，
這時候就可以在執行 A 工作的時候 Load A 的相關函式，
執行 B 工作的時候 Load B 的相關函式，
再也不用同時把 A 和 B 的所有資料都放在記憶體上了。
但是在使用上有點麻煩，以前用的時候都要先執行 Load Overlay X 的函式，
用到的時候才 Load 對執行速度上也會有影響。

而 Memory Management Unit(MMU) 可以說是 Overlay 的加強版，
讓硬體支援相關操作，使用時只要把虛擬記憶體映射表填好就可以，
如果遇到 Page Fault 就把資料從硬碟搬上來，再更新映射表就好囉！

講到 MMU 就得要說到 Virtual Memory 了，
Segmentation 和 Page Mapping 讓我們從 External Fragmentation 的地獄中解放出來，
但是又帶進 Internal Fragmentation 的問題，
如果需要使用更小的區塊該怎麼辦？
總不能 new 一個 10 byte 的物件就給我 4K 的記憶體吧！

這時候 Slab Allocator 就出現了，
讓我們能把記憶體區塊又繼續往下拆分。
於是小鎮村又恢復了和平...。

不過問題還不只這些，有了虛擬記憶體映射代表 Cache 又有問題了，
如果要存取一個 Virtual Memory Address，到底要直接告訴 Cache (VIVT)呢？
還是要先問 MMU 再給 Cache (PIPT)呢？ 還是兩個都問(VIPT)呢？
細部的說明可以請大家參考 ycliang 的這篇文章

另外 MMU 去 Memory 查表也很花時間，
還要準備一個 Translation Lookaside Buffer(TLB) 來加速這個過程。

結語

總之記憶體的問題很長很複雜，
單處理器還有很多細節沒有函蓋到，
多處理器中的 UMA、NUMA 又是另外的問題了。
雖然對感興趣但是一直都沒有時間研究，
也不是今天看得完的，
就先這樣吧，搭晚安！