# 2022q1 Project (cpumemory)
contributed by ???

## 目標

- [ ] [閱讀](#閱讀論文) Ulrich Drepper 於 2007 年撰寫的論文《 [What Every Programmer Should Know About Memory]
- [ ] SRAM DRAM 讀取差異
- [ ] Virtual Memory
- [ ] TLB 作用
- [ ] Cache Line Sharing 成本
- [ ] MESI
- [ ] CAS

:::danger
注意書寫:
1. 中英文間以一個半型空白字元或標點符號區隔
2. 使用台灣傳統電腦詞彙
3. 保持書寫風格的一致

:notes: jserv
:::

## SRAM DRAM 讀取差異
### SRAM 介紹

- 圖2.4顯示了一組6個晶體管SRAM單元的結構。M1 ~ M4有兩個穩定的狀態，分別代表0和1，只要Vdd上有電源，該狀態就穩定。如果需要存取記憶單元的狀態，就需要提高自組存取線路(word access line) WL的電位，則記憶單元的狀態就能馬上被兩個 BL 讀取到。若是寫入記憶單元的狀態，要先將兩個BL設定成想要的值，然後再提高 WL 電位。由於外部驅動強過4個晶體管(M1 ~ M4)，這樣使得就狀態能被複寫。

- 最重要的特點是:
1. 維持記憶單元的狀態持續供電。
2. 記憶單元狀態是穩定的，不需要充電週期。

### DRAM 介紹

- 圖2.5顯示出了一個常見的DRAM記憶單元架構，由一個電晶體和一個電容組成。DRAM會將狀態存在電容 C。電晶體 M 用以控制狀態的存取。讀取記憶單元的狀態，需要提高存取線路 AL 的電位，這樣電流會或不會流過資料線路 DL，取決於電容中的**電量**。寫資料進記憶單元要將資料線路 DL 設置好，然後提高 AL 的電位一段時間足以讓電容充電或放電的時間。

- 讀取記憶單元，必須先將電容放電。但是，上述事情不能被重複做，電容必須在某個特定時間點進行充電。

- 由於上述論點，所以每次的讀取完後，都必須重新對電容充電。能透過感測放大器的輸出位回到電容裡頭來自動達成，這樣代表讀取記憶體內容需要額外的電力和時間。

### DRAM SRAM 差異

| | SRAM | DRAM |
| -------- | -------- | -------- |
| 面積 | 大 | 小 |
| 成本 | 高 | 低 |
| 存取速度 | 快 | 慢 (電容充放電時間) |

## Virtual Memory

### Virtual Memory 定義

- 處理器的虛擬記憶體 (VM) 子系統實現提供給每個行程的虛擬地址空間，這使得每個程式都認為它是獨立存在的。

### 為甚麼需要 Virtual Memory [參考](https://medium.com/starbugs/why-do-os-need-virtual-memory-b47d6eeecbce)

### 記憶體碎片化
- 程式被CPU執行之前，都必須把程式的內容載入到**連續的記憶體空間**。
- 當你同時開啟很多程式，實體記憶體就會長下圖
- 之後每當有新啟動的程式，系統就會分配**連續**的空間給這個新程式。反之，程式結束，就將記憶體空間釋放。但這樣做會發生**記憶體碎片化**的問題。
- **記憶體碎片化** : 明明記憶體剩餘總空間足夠容內納程式的大小，但是這個總空間被切割成大大小小的區塊，導致**沒有足夠大**的連續空間可以使用。以下圖來說，剩餘總空間為6G，但是我要開啟一個4G的程式就會因為找不到連續的空間而無法開啟。

### Virtual Memory
- 為了解決記憶體碎片化的問題，處理器會給每個程式一塊獨立的虛擬記憶體，然後再把它映射到可用的實體記憶體。以下圖來說，系統會給firefox 和 chrome 各自一大塊虛擬記憶體，讓程式認為自己拿到的記憶體是連續的。

- 虛擬地址空間是由CPU的記憶體管理單元(MMU)實作的。內部有一個page table紀錄了虛擬/實體地址的對應關係。

### Simple Address Translation

- 圖4.1顯示了如何將virtual address 轉成 physical address。virtual address 前半段的 Directory 是用來選擇分頁目錄(Page Directory)中的一個項目，分頁目錄的項目決定了實體記憶體分頁的位址。再利用實體記憶體分頁及後半段的offset就能算出完整的實體記憶體。

### Multi-Level Page Tables

- 分頁目錄會佔據系統中大量的實體記憶體。(以 4 KiB 分頁而言，虛擬位址的 offset 大小僅有 12 位元，這代表留了20位元當作分頁目錄的選擇器。有著 2^20^ 個項目的表格是不切實際。)

- 解決方法是使用多個層級的分頁表。以圖4.2為例，處理器首先會確定最高層目錄的位址。這個位址通常儲存在一個暫存器中。CPU 接著取出對應到這個目錄的虛擬記憶體的索引部分，並使用這個索引來挑選合適的項目。這個項目是下一個目錄的位址，使用虛擬位址的下一個部分來索引。這個過程持續到抵達第一層目錄，這時目錄項目的值為實體位址的高位部分。加上來自虛擬記憶體的分頁偏移位元便組成了完整的實體位址。這個過程被稱為分頁樹走訪（page tree walking）。

### Virtual memory 優點

- 解決實體記憶體碎片化問題。
- Process 間共享實體記憶體。

## TLB 作用

- 根據上述所提到的利用 Multi-Level Page Tables，要將virtual address 轉成 physical address，需要執行分頁樹走訪。以4 level page table 為例需要走訪4次才能轉換成功，且這些存取沒辦法平行化，因為每次都走訪都依賴上次計算的結果，所以非常的慢。

- 所以就將目錄表的項目快取起來，而是連實體分頁位址的完整計算結果也會被快取。由於虛擬位址的分頁偏移量的部分不會參與到實體分頁位址的計算，僅有虛擬位址的剩餘部分會用來作為快取的標籤。視分頁大小而定，這代表數百或數千條的指令或資料物件會共享相同的標籤，因而共享相同的實體位址前綴（prefix）。

- TLB 用來加速virtual address 轉 physical address 的過程。

## Cache Line Sharing 成本


### Cache coherency

- 在 SMP 系統中，CPU 的快取不能相互獨立工作。所有的處理器都應該在任何時候看到相同的記憶體內容。這種記憶體一致觀點被稱為「快取一致性（cache coherency）」。

- 如果一個處理器只看它自己得快取和主記憶體，他就不會看到其他處理器的髒快取行內容，從一個處理器到另一個處理器快取直接存取會非常昂貴。反之，應該是要讓處理器在另一個處理器要讀取或寫入到某個快取行時察覺到。

- 如果檢測到寫入存取，並且處理器的快去中有一個乾淨的快取行副本，這個快取行就會被標記為無效。未來要在使用需要重新載入這個快取行。如果其他 CPU 要在讀取這個快取行不需要無效化，多個乾淨副本能夠被保存得很好。

- 許多快取一致化的協定隨著時間被逐漸發展出來，最重要的為 MESI。

## MESI

- 提供從一個處理器到另一個處理器的快取直接存取權是不切實際的，連接的速度根本不夠快。實用的替代方法是在需要時將快取的內容轉移到另一個處理器上。

- 問題是，這個快取的轉移何時發生呢?這個問題容易回答，當一個處理器需要讀取或寫入某一個快取行，但在另一個處理器上其快取行是髒的。但是處理器要怎麼判斷這個快取行在另一個處理器上會標記為髒呢?僅僅因為一個快取行被另一個處理器載入就認為是髒的化，這樣的作法頂多是次佳的。大部分的快取存取都是讀取存取所以快取行通常不是髒的。處理器對快取行的操作是很頻繁的，這表示在每次寫入操作之後，都去廣播被改變的快取行的資訊是不切實際的。所以就發展出 MESI 快取一致性協定。

- Modified (M) : 本地處理器已經修改了快取行，這也意味著它是任何快去中的唯一副本。
(只有該 cache line 裡有最新資料，比 main memory 裡的資料還新)

- Exclusive (E) : 快取行沒有被修改，但是這個快取行沒有被加載到其他處理器上。
(只有該 cache line 裡有最新資料，不過和 main memory 一致)

- Shared (S) : 快取行沒有被修改，但是這個快取行有可能加載到其他處理器上。
(有兩個以上的 cache lines 有最新資料，和 main memory 一致)

- Invalid (I) : 快取行是無效的––也就是說，沒有被使用。
(cache line 內的資料已過時，不可使用)

- 藉由處理器的監聽或窺探，狀態的改變不需要太多努力就能完成。一個處理器的某些操作執行會在外部引腳上公布，從而使處理器的快取處理讓外部可見，處理中的快取行位址能在位址匯流排上看到。

- 起初所有快取行都是空的，因此也是無效的。若是資料是為了寫入而載入快取，則改為修改。若是資料是為了讀取而載入，新的狀態則取決於另一個處理器是否也已載入這個快取行。如果是的話，新的狀態為共享，否則為獨占。

- 如果一個修改過的快取行在本地處理器上被讀出或寫入，該指令可以使用當前的快取內容，且狀態不會改變。如果第二個處理器想讀取快取內容，第一個處理器必須將其快去內容發送給第二個處理器，然後將它標記為共享。發送給第二個處理器的資訊會被記憶體控制體接收然後存回記憶體，如果上述情況不發生，就不能標記為共享。如果第二個處理器想寫入到快取行，第一個處理器會發送快取內容，並將該塊去內容在本地端標記為無效。這就是「所有權請求（Request For Ownership，RFO）」操作。在最後一個層級的快取中執行這個操作，就像是 I→M 的轉換一樣，相當昂貴。對直寫式快取而言，我們也得加上它將新的快取行內容寫入到更高階快取或主記憶體所花費的時間，進而提高了成本。

- 若是一個快取行處在共享狀態，那麼本地端處理器讀取它不需要改變狀態，讀取請求能夠由這個快取來達成。如果快取行被本地端寫入，快取行也可以被使用，但狀態變為修改，且還要要求所有快取行在其他處理器中的可能副本標記為無效，因此寫入操作必須通過一個 RFO 像其他處理器宣布訊息。如果快取行被第二個處理請求讀取，則不會發生任何事，主要記憶體包含了當前數據，且本地端的狀態早已經是共享了。第二個處理器想要寫入到快取行的情況下（RFO），就直接將快取行標為無效。不需要匯流排操作。

- 獨享狀態與共享狀態基本相同，有一個重要的區 : 本地寫入操作不需要在 bus 上宣布，因為已經知道本地快取是唯一一個持有這個獨有的快取行的了。這是一個巨大的優勢，所以處理器會盡可能多地將快取行保持在獨占而不是共享狀態。後者是在這種時刻，無法取得這個資訊的退而求其次。獨占狀態也能夠在完全不引發功能問題的情況下被省去。唯一會變糟的只有效能，因為 E→M 轉換比 S→M 轉換要快得多了。