Peter Liu：CPU是如何通路記憶體的？
記憶體管理
記憶體是計算機中重要部件之一，是與CPU進行溝通的橋梁。用于暫存CPU中的運算資料、以及與硬碟等外部存儲器交換的資料。
利用和管理計算機記憶體資源。
記憶體管理演變史
早期，程式直接運作在實體記憶體上，直接操作實體記憶體，這種方式存在幾個問題：
- 位址空間不隔離：程式操作相同位址空間會造成互相影響甚至崩潰，而且安全性也得不到保證；
- 使用效率低：沒有特别好的政策保證多個程序對超過實體記憶體大小的記憶體需求的滿足；
- 程式運作位址不确定：程式運作時，都需要配置設定空閑區域，而空閑位置不确定，會帶來一些重定位問題；
記憶體管理主要就是想辦法解決上面三個問題；
虛拟記憶體
計算機系統裡任何問題都可以靠引入一個中間層來解決
，記憶體管理就在程式和實體記憶體之間引入了
虛拟記憶體
的概念；對程序位址和實體位址進行隔離；
記憶體分區（ZONE）
Linux 對記憶體節點進行分區；将節點分為DMA、Normal、High Memory 記憶體區；
- DMA記憶體區：直接記憶體通路區，通常為實體記憶體的起始16M；主要供I/O外設使用，無需CPU參與的外設和記憶體DMA；
- Normal記憶體區：從16M到896M記憶體區；核心可以直接使用
- Hight Memory記憶體區：896M以後的記憶體區；高端記憶體，核心不能直接使用
核心空間和使用者空間
Linux 作業系統，将虛拟記憶體劃分為
核心空間
和
使用者空間
；
使用者程序隻能通路使用者空間的虛拟位址，隻有通過系統調用、外設中斷或異常才能通路核心空間；
核心空間：
Linux核心空間 1G容量，包括：核心鏡像、實體頁面表、驅動程式等；
- 直接映射區：最大896M
- 高端記憶體線性位址空間：共128MB
- 動态記憶體映射區（vmalloc region）：由核心函數vmalloc 配置設定；
- 永久記憶體映射區：alloc_page、 kmap
- 固定映射區：特定用途，如 ACPI_BASE 等
使用者空間：分為5個不同記憶體區域：
- 代碼段：隻讀，存放可執行檔案的操作指令；鏡像；
- 資料段：存放可執行檔案中已初始化全局變量；存放靜态變量和全局變量；
- BSS段：未初始化全局變量
- 堆：存放被動态配置設定的記憶體段；
- 棧：存放臨時建立的局部變量；
記憶體位址映射
CPU生成的位址是邏輯位址，而記憶體單元中的位址為實體位址；
執行時位址綁定方案會生成不同的邏輯位址和實體位址，這時，邏輯位址通常被稱為虛拟位址
虛拟位址空間
實體位址空間是有限的，虛拟位址空間可以是任意大小；
程式可以通過操作虛拟位址，把虛拟位址空間映射到實體位址空間； Linux通過缺頁中斷和swap機制，實作虛拟位址映射；
虛拟位址優點：
- 避免直接通路實體記憶體位址，保護作業系統
- 每個程序都被配置設定4GB虛拟記憶體；可使用比實際實體記憶體更大的位址空間。
分頁和分段
虛拟位址和實體位址，主要通過
分段
和
分頁
技術，進行映射；
程式位址：段号+頁号+頁内偏移；
段和頁的差別：
- 段是資訊的邏輯機關，根據使用者的需要劃分，段對使用者是可見的； 頁時資訊的實體機關，為管理記憶體友善和劃分的，對使用者透明的。
- 段的大小不固定，根據功能覺得；頁的大小固定，由系統覺得；
- 段向使用者提供二維位址空間；頁向使用者提供一維位址空間；
- 段便于存儲保護和資訊共享；頁的保護和共享受到限制；
- 分段和分頁：分頁的粒度更小；
分段：将程式分為代碼段、資料段、堆棧段等； 分頁：将段分成均勻的小塊，通過頁表映射實體記憶體；
GDT：全局描述表，也就是段表，提供段氏存儲機制；存儲分段基址資訊； CPU通路使用邏輯位址； 分段機制，将邏輯位址轉換成線性位址，也就是分頁系統中的虛拟位址； 分頁機制，将虛拟位址轉換為實體位址；
分頁存儲和分段存儲
分段（Segmentation）
分段位址通過段表，轉換成線性位址； 分段位址包括段号和段内位址； 段表，包括短号、段長、基址；
分頁（Page）
分頁機制就是将虛拟位址空間分為大小相等的頁；實體位址空間也分為若幹個實體塊（頁框）；頁和頁框大小相等。實作離散配置設定； 分頁機制的實作需要 MMU 硬體實作；負責分頁位址轉換；
頁大小（粒度）太大浪費；太小，影響配置設定效率
線性位址通過頁表轉換成實體位址； 分頁位址包括頁号P和位偏移量W； 頁表，包括頁号、實體塊号、存取控制； 頁表作用就是實作頁号到實體塊号的位址映射；
多級頁表
記憶體配置設定
使用者程序通常隻能通路使用者空間的虛拟位址，不能通路核心空間的虛拟位址；
記憶體管理問題： 記憶體碎片太小和管理記憶體碎片的效率問題
記憶體碎片
記憶體碎片：回收記憶體時，将記憶體塊放入空閑連結清單中； 因記憶體越分越小，記憶體塊小而多；當需要一塊大記憶體時，盡管此時空閑記憶體綜合可能滿足需求，但過于零散，沒有一個合适的記憶體塊
記憶體碎片産生原因：配置設定記憶體時，不能将相鄰記憶體合并；
解決記憶體碎片的方法：
- 小記憶體單獨配置設定（記憶體池）、大記憶體由作業系統配置設定
- 夥伴系統算法
- slab 算法
如何避免記憶體碎片：
- 少用動态記憶體配置設定函數（盡量使用棧空間）
- 配置設定記憶體和釋放的記憶體盡量在同一個函數中
- 盡量一次性申請較大的記憶體，而不要反複申請小記憶體
- 盡可能申請大塊的2的指數幂大小的記憶體空間
- 外部碎片避免：夥伴系統（Buddy）算法
- 内部碎片避免：slab算法
- 自己進行記憶體管理工作，設計記憶體池
外部碎片
外部碎片，是指還沒有被配置設定出去，但由于太小無法配置設定的記憶體空閑區域；
夥伴系統算法（Buddy System）
為核心提供了一種用于配置設定一組連續的頁而建立的一種高效的配置設定政策，并有效解決了外碎片問題； 配置設定的記憶體區以頁框為基本機關；
Linux 核心使用夥伴系統算法，把所有的空閑頁框分組為11個塊連結清單，每個塊連結清單分别包含大小為1,2,4,8,16,32,64,128,256,512和1024個連續頁框的頁框塊。最大可申請1024個連續頁框，對應4MB大小的連續記憶體。每個頁框塊的第一個頁框的實體位址是該塊大小的整數倍；
SLAB配置設定器
夥伴系統是以頁為機關管理和配置設定記憶體。但顯式需求卻以位元組為機關，使用夥伴系統就會嚴重浪費記憶體（産生内部碎片）。
slab配置設定器專為小記憶體配置設定而生（解決内部碎片）； slab配置設定器配置設定記憶體以Byte為機關； 基于夥伴系統配置設定的大記憶體，進一步細分成小記憶體配置設定；
高速緩存/TLB控制
slab 高速緩存分為兩大類：普通高速緩存和專用高速緩存；
記憶體配置設定函數
https://www.jianshu.com/p/e42f4977fb7e
kmalloc/ vmalloc / malloc
- malloc ：負責配置設定使用者空間記憶體。标準c庫提供了 malloc/free 函數配置設定釋放記憶體，底層由 sark、brk、mmap、munmap系統調用實作。
- kmalloc：負責配置設定核心空間記憶體。用于申請較小、連續的實體記憶體。以位元組為機關進行配置設定， slab；
- vmalloc：負責配置設定核心空間記憶體。用于申請較大的記憶體空間，虛拟記憶體是連續的，以位元組為機關進行配置設定；配置設定速度要慢；
常用函數總結
使用者空間： malloc/calloc/realloc/free alloca mmap/munmap brk/sbrk
核心空間： vmalloc/vfree
核心空間slab： kmalloc/kcalloc/krealloc/kfree kmem_cache_create
核心空間buddy：
get_free_page/get_free_pages alloc_page/alloc_pages/free_pages
頁面置換算法
當發生缺頁中斷時，作業系統必須在記憶體中選擇一個頁面将其換出，以便為即将調入的頁面騰出空間；
常見置換算法有以下四種：
最佳置換算法（OPT）（不可能實作）
淘汰以後永不使用或最長時間内不再被通路的頁面；保證獲得最低的缺頁率。 但作業系統無法知道各個頁面下一次将在什麼時候被通路，是以該算法是無法被實作的；
先進先出（FIFO）置換算法
優先淘汰最早進入記憶體的頁面；實作簡單，但性能差；
Belady異常：FIFO算法會産生當所配置設定的實體塊數增大而頁故障數不減反增的異常現象；
最近最少使用（LRU）置換算法
置換未使用時間最長的頁面； LRU是堆棧類算法，性能較好，但需要寄存器和棧的硬體支援；實作起來困難，且開銷大；
時鐘（CLOCK）置換算法
環形連結清單，也叫NRU算法