1. 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、Slab）
由操作系統或系統管理員預先將內存劃分成若干個分區。在系統運行過程中，分區的邊界不再改變。分配時，找一個空閑且足夠大的分區。如沒有合適的分區：①讓申請者等待。②先換出某分區的內容，再將其分配出去。
為申請者分配指定的分區或任選一個分區。如果沒有空閑分區，可將一個分區的內容換出。可能需要重定位。
會出現內部碎片，無法滿足大內存的需求。
可減少內部碎片。減少對大內存需求的限制。
①固定分配：只分配某種尺寸的特定分區，如分區已被使用，申請者必須等待。
可能出現不公平等待：雖有更大尺寸的空閑分區，卻必須等待。
②最佳適應分配：分配能滿足需要的最小尺寸的空閑分區，只有當所有分區都已用完時，申請者才需要等待。靈活，但可能產生較大的內部碎片。
3、靜態分區：內存利用率低，產生內部碎片；尺寸和分區數量難以確定。
1、不預先確定分區的大小和數量，將分區工作推遲到實際分配內存時進行。 Lazy
初始情況下，把所有的空閑內存看成一個大分區。分配時，按申請的尺寸，找一塊足夠大的空閑內存分區，臨時從中劃出一塊構成新分區。新分區的尺寸與申請的大小相等，不會出現內部碎片。回收時，盡可能與鄰近的空閑分區合並。在內存緊缺時，可將某個選定的分區換出。
2、會產生外部碎片，如下圖（內部碎片是指 eg：要 1M，分了 8M，產生 7M 的碎片）：
移動內存中的進程，將碎片集中起來，重新構成大的內存塊。需要運行時的動態重定位，費時。
（1）緊縮方向：向一頭緊縮，向兩頭緊縮。
（2）緊縮時機：①在釋放分區時，如果不能與空閑分區合並，則立刻進行緊縮。
好處是不存在外部碎片，壞處是費時。
②在內存分配時，如果剩餘的空閑空間總量能滿足要求但沒有一個獨立的空閑塊能滿足要求，則進行緊縮。
好處是減少緊縮次數。Lazy。
①最先適應演算法（First fit）：從頭開始，在滿足要求的第一個空閑塊中分配。
分區集中在內存的前部，大內存留在後面，便於釋放後的合並。
②最佳適應演算法（Best fit）：遍歷空閑塊，在滿足要求的最小空閑塊中分配。
留下的碎片最小，基本無法再用，需要更頻繁地緊縮。
③下一個適應演算法（Next fit）：從上次分配的位置開始，在滿足要求的下一個空閑塊中分配。
對內存的使用較平均，不容易留下大的空閑塊。
④最差適應演算法（Worst Fit）：遍歷空閑塊，在滿足要求的最大空閑塊中分配。
留下的碎片較大，但不會剩餘大內存。
最先適應演算法較優，最佳適應演算法較差。
夥伴演算法：將動態分區的大小限定為 2^k 位元組，分割方式限定為平分，分區就會變得較為規整，分割與合並會更容易，可以減少一些外部碎片。平分後的兩塊互稱夥伴。
1、
分配時可能要多次平分，釋放時可能要多次合並。舉例：
記錄大小不同的空閑頁：
示意圖：
2、
夥伴演算法是靜態分區和動態分區法的折中，比靜態分區法靈活，不受分區尺寸及個數的限制；比動態分區法規范，不易出現外部碎片。會產生內部碎片，但比靜態分區的小。
Linux、Windows、Ucore等都採用夥伴演算法管理物理內存。
一般情況下，將最小尺寸定為 2^12 位元組（1頁，4K=4096B），最大尺寸定為1024頁，11個隊列。
Linux、Windows、Ucore 等都將夥伴的最小尺寸限定為1頁。
ucore 用 page，在內存初始化函數 page_init 中為系統中的每個物理頁建立一個 page 結構。
頁塊（pageblock）是一組連續的物理頁。
5、
（1）判斷夥伴關系/尋找夥伴
最後兩行是指，B1和B2隻有第i位相反。
（2）判斷夥伴是否空閑：
ucore 用 free_area[ ]數組定義空閑頁塊隊列。
（3）確定夥伴是否在 order 隊列中：
7、
（1）解決內部碎片過大問題（eg：申請5頁，分配8頁，浪費3頁）：
ucore 在前部留下需要的頁數，釋放掉尾部各頁。每次釋放1頁，先劃分成頁塊，再逐個釋放。
（2） 解決切分與合並過於頻繁的問題：
用得較多的是單個頁。位於處理器Cache中頁稱為熱頁（hot page），其餘頁稱為冷頁（cold page）。處理器對熱頁的訪問速度要快於冷頁。
可建一個熱頁隊列（per_cpu_page），暫存剛釋放的單個物理頁，將合並工作向後推遲 Lazy。總是試圖從熱頁隊列中分配單個物理頁。分配與釋放都在熱頁隊列的隊頭進行。
（3）解決內存碎化(有足夠多的空閑頁，但是沒有大頁塊)問題：①將頁塊從一個物理位置移動到另一個物理位置，並保持移動前後邏輯地址不變（拷貝頁塊內容）；②邏輯內存管理器。
（4）滿足大內存的需求：
（5）物理內存空間都耗盡的情況：
在任何情況下，都應該預留一部分空閑的物理內存以備急需。定義兩條基準線low和high，當空閑內存量小於low時，應立刻開始回收物理內存，直到空閑內存量大於high。
（6）回收物理內存：
法一：啟動一個守護進程，專門用於回收物理內存。周期性啟動，也可被喚醒。
法二：申請者自己去回收內存。實際是由內存分配程序回收。回收的方法很多，如釋放緩沖區、頁面淘汰等。
1、
夥伴演算法最小分配內存為頁，對於更小的內存的管理 --> Slab 演算法
內和運行過程中經常使用小內存（小於1頁）eg：建立數據結構、緩沖區
內核對小內存的使用極為頻繁、種類繁多、時機和數量難以預估。所以難以預先分配，只能動態地創建和撤銷
2、
Slab 向夥伴演算法申請大頁塊（批發），將其劃分成小對象分配出去（零售）；將回收的小對象組合成大頁塊後還給夥伴演算法。
Slab 採用等尺寸靜態分區法，將頁塊預先劃分成一組大小相等的小塊，稱為內存對象。
具有相同屬性的多個Slab構成一個Cache，一個Cache管理一種類型（一類應該是指一個大小）的內存對象。當需要小內存時，從預建的Cache中申請內存對象，用完之後再將其還給Cache。當Cache中缺少對象時，追加新的Slab；當物理內存緊缺時，回收完全空閑的Slab。
Slab 演算法的管理結構：
① Cache 管理結構：管理Slab，包括Slab的創建和銷毀。
② Slab 管理結構：管理內存對象，包括小對象的分配與釋放。
（Cache結構和Slab結構合作，共同實現內存對象的管理）
3、
（1）描述各個內存對象的使用情況
可以用點陣圖標識空閑的內存對象。也可以將一個Slab中的空閑內存對象組織成隊列，並在slab結構中記錄隊列的隊頭。
早期的Linux在每個內存對象的尾部都加入一個指針，用該指針將空閑的內存對象串聯成一個真正的隊列。（對象變長、不規范，空間浪費）
改進：將指針集中在一個數組中，用數組內部的鏈表模擬內存對象隊列。
再改進：將數組中的指針換成對象序號，利用序號將空閑的內存對象串成隊列。序號數組是動態創建的。
序號數組可以位於 Slab 內部，也可以位於 Slab 外部
（2）一個Cache會管理多個Slab，可以將所有Slab放在一個隊列中。
Ucore為每個Cache准備了兩個slab結構隊列：全滿的和不滿的。Linux為每個Cache准備了三個slab結構隊列：部分滿的、完全滿的和完全空閑的。
Linux允許動態創建Cache，Ucore不許。Ucore預定了對象大小，分別是32、64、128、256、512、1K、2K（4K、8K、16K、32K、64K、128K）。為每一種大小的對象預建了Cache。
（3）Slab是動態創建的，當Cache中沒有空閑的內存對象時，即為其創建一個新的Slab。
Slab所需要的內存來自夥伴演算法，大小是 2^page_order 個連續頁。
4、小對象的尺寸
如按處理器一級緩存中緩存行（Cache Line）的大小（16、32位元組）取齊，可使對象的開始位置都位於緩存行的邊界處。
在將頁塊劃分成內存對象的過程中，通常會剩餘一小部分空間，位於所有內存對象之外，稱為外部碎片。
Slab演算法選用碎片最小的實現方案。
5、
（1）對象分配 kmalloc
① 根據size確定一個Cache。
② 如果Cache的slabs_notfull為空，則為其創建一個新的Slab。
③ 選中slabs_notfull中第一個Slab，將隊頭的小對象分配出去，並調整隊列。
④ 對象的開始地址是：objp = slabp->s_mem + slabp->free * cachep->objsize;
（2）對象釋放 kfree
① 算出對象所在的頁號，找到它的 Page 結構。
② 根據 Page 找到所屬的 Cache 和 Slab。
③ 算出對象序號：objnr = (objp - slabp->s_mem) / cachep->objsize;
④將序號插入Slab的free隊列。
⑤整Slab所屬隊列。
2. 可變分區管理內存分配演算法有那些,各有什麼有缺點
連續分配： 首次適應演算法（較快，簡單，碎片多），最大適應分配演算法（以期不留下小碎片）， 最佳適應分配演算法（慢，復雜，碎片少）。 都需要碎片整理。
離散分配：分段管理（邏輯性好），分頁管理，段頁式管理（最好，當然也復雜）。
3. 存儲器管理的連續分配存儲管理方式有哪些
連續分配方式．它是指為了一個用戶程序分配一個連續的內存空間．可以分為單一連續分配、固定分區分配、動態分區分配以及動態重定位分區分配四種方式。不過今天我們講的是固定分區分配和動態分區分配。
固定分區分配是最簡單的一種可運行多道程序的存儲管理方式。 一、基本思想：在系統中把用戶區預先劃分成若干個固定分區（每個分區首地址固定，每個分區長度是固定），每個分區可供一個用戶程序獨占使用。注意：每個分區大小可以相同，也可以不相同。 二、主存分配與回收：藉助主存分配表。 三、地址轉換（靜態重定位）：物理地址=分區起始地址+邏輯地址。其中劃分分區方法包括分區大小相等和分區大小不等。
動態分區分配是根據進程的實際需要，動態地為之分配內存空間。一、基本思想：按用戶程序需求動態劃分主存供用戶程序使用。（每個分區首地址是動態的，每個分區的長度也是動態的） 二、主存分配與回收-->（1）未分配表（登記未分配出去的分區情況）；（2）已分配表（登記已經分配出去的分區情況）。 三、地址轉換：物理地址=分區起始地址+邏輯地址。 四、分區分配演算法：從空閑分區中選擇分區分www.hbbz08.com 配給用戶程序的策略。 （1）首次適應演算法（最先適應）順序查詢為分配表，從表中找出第一個可以滿足作業申請的分區劃分部分分配給用戶作業。 （2）循環首次適應演算法 （3）最佳適應演算法：從空閑分區中找出一個能滿足用戶作業申請的最小空閑分區劃分給用戶作業使用（有利於大作業執行） （4）最壞適應演算法：從空閑分區中挑最大的分區劃分給用戶程序使用（有利於中、小作業執行）
4. 浠涔堟槸鍩轟簬緔㈠紩鎼滅儲鐨勫姩鎬佸垎鍖哄垎閰嶇畻娉
涓縐嶉珮鏁堢殑鍐呭瓨鍒嗛厤絳栫暐銆
鍩轟簬緔㈠紩鎼滅儲鐨勫姩鎬佸垎鍖哄垎閰嶇畻娉曟槸涓縐嶉珮鏁堢殑鍐呭瓨鍒嗛厤絳栫暐銆傞氳繃寤虹珛緔㈠紩琛ㄦ潵璁板綍絀洪棽鍒嗗尯鐨勭姸鎬佸拰浣嶇疆淇℃伅錛屼粠鑰屽揩閫熷畾浣嶅彲鐢ㄧ殑絀洪棽鍒嗗尯銆