『壹』 可變分區管理內存分配演算法有那些,各有什麼有缺點
連續分配： 首次適應演算法（較快，簡單，碎片多），最大適應分配演算法（以期不留下小碎片）， 最佳適應分配演算法（慢，復雜，碎片少）。 都需要碎片整理。
離散分配：分段管理（邏輯性好），分頁管理，段頁式管理（最好，當然也復雜）。
『貳』 內存狀態分區管理中最佳適應演算法的空白區是
實驗五 內存分區管理實驗
一、單項選擇題（共5題,每題10分,共50分）
1、最佳適應演算法的空白區是__B__.
A.按大小遞減順序連在一起 B.按大小遞增順序連在一起
C.按地址由小到大排列 D.按地址由大到小排序
2、在固定分區分配中,每個分區的大小是__C__.
A.相同 B.隨作業長度變化
C.可以不同但預先固定 D.可以不同但根據作業長度固定
3、採用__B__不會產生內部碎片.
A.分頁式存儲管理 B.分段式存儲管理
C.固定分區式存儲管理 D.段頁式存儲管理
4、在可變式分區存儲管理中的拼接技術可以_A___.A.集中空閑區 B.增加內存容量
C.縮短訪問周期 D.加速地址轉換
5、採用分段存儲管理的系統中,若地址用24位表示,其中8位表示段號,則允許每段的最大長度是_B___.
二、填空題（共4題,每題5分,共20分）
1、在分區分配演算法中,首次適應演算法傾向於優先利用內存中的_低地址___部分的空閑分區,從而保留了__高地址__部分的大空閑區.
2、在可變分區存儲管理中,分區的保護通常採用_地址越界___和__非法操作__兩種方法.
3、3、採用交換技術獲得的好處是以犧牲_增大系統開銷___為代價的.
4、在採用請求分頁式存儲管理的系統中,地址變換過程可能會因為_缺頁___、_越界___和_訪問許可權錯誤___等原因而產生中斷.
三、 簡答題（共2題,每題15分,共30分） 1、可採用哪幾種方式將程序裝入內存?它們分別適用於何種場合?
a.首先由編譯程序將用戶源代碼編譯成若干目標模塊,再由鏈接程序將編譯後形成的目標模塊和所需的
---庫函數鏈接在一起,組成一個裝入模塊,再由裝入程序將裝入模塊裝入內存；
b.裝入模塊的方式有:絕對裝入方式,可重定位方式和動態運行時裝入方式；
c.絕對裝入方式適用於單道程序環境下；
d.可重定位方式適用於多道程序環境下；
e.動態運行時裝入方式也適用於多道程序環境下.
2、何謂靜態鏈接?何謂裝入時動態鏈接和運行時的動態鏈接?
a.靜態鏈接是指事先進行鏈接形成一個完整的裝入模塊,以後不再拆開的鏈接方---式；
b.裝入時動態鏈接是指目標模塊在裝入內存時,邊裝入邊鏈接的鏈接方式；
c.運行時的動態鏈接是將某些目標模塊的鏈接推遲到執行時才進行.
『叄』 連續分配存儲管理方式
一、單一連續分配
最簡單的一種存儲管理方式，只能用於單用戶、單任務的操作系統中。
優點：易於管理。
缺點：對要求內存空間少的程序，造成內存浪費；程序全部裝入，很少使用的程序部分也佔用內存。
二、固定分區分配
把內存分為一些大小相等或不等的分區(partition)，每個應用進程佔用一個分區。操作系統佔用其中一個分區。支持多個程序並發執行，適用於多道程序系統和分時系統。最早的多道程序存儲管理方式。
缺點：內碎片（一個分區內的剩餘空間）造成浪費；劃分為幾個分區，便只允許幾道作業並發，分區總數固定，限制並發執行的程序數目。
三、動態分區分配
1、分區的大小不固定：在裝入程序時根據進程實際需要，動態分配內存空間，即——需要多少劃分多少。
2、空閑分區表項：從1項到n項：內存會從初始的一個大分區不斷被劃分、回收從而形成內存中的多個分區。
3、優點：並發進程數沒有固定數的限制，不產生內碎片。缺點：有外碎片（分區間無法利用的空間）
4、分區分配演算法
①首次適應演算法FF(first-fit)
空閑分區排序：以地址遞增的次序鏈接。
檢索：分配內存時，從鏈首開始順序查找直至找到一個大小能滿足要求的空閑分區；
分配：從該分區中劃出一塊作業要求大小的內存空間分配給請求者，餘下的空閑分區大小改變仍留在空閑鏈中。
若從頭到尾檢索不到滿足要求的分區則分配失敗
優點：優先利用內存低址部分，保留了高地址部分的大空閑區；
缺點：但低址部分不斷劃分，會產生較多小碎片；而且每次查找從低址部分開始，會逐漸增加查找開銷。
②循環首次適應演算法
空閑分區排序：按地址
檢索：從上次找到的空閑分區的下一個空閑分區開始查找，直到找到一個能滿足要求的空閑分區。為實現演算法，需要設置一個起始查尋指針並採用循環查找方式
分配：分出需要的大小
優點：空閑分區分布均勻，減少查找開銷
缺點：缺乏大的空閑分區
③最佳適應演算法
總是把能滿足要求、又是最小的空閑分區分配給作業，避免「大材小用」。
空閑分區排序：所有空閑分區按容量從小到大排序成空閑分區表或鏈。
檢索：從表或鏈的頭開始，找到的第一個滿足的就分配
分配：分出需要的大小
缺點：每次找到最合適大小的分區割下的空閑區也總是最小，會產生許多難以利用的小空閑區（外碎片）
④最差適應演算法/最壞匹配法
基本不留下小空閑分區，但會出現缺乏較大的空閑分區的情況。
⑤快速適應演算法
根據進程常用空間大小進行劃分，相同大小的串成一個鏈，需管理多個各種不同大小的分區的鏈表。進程需要時，從最接近大小需求的鏈中摘一個分區。
能快速找到合適分區，但鏈表信息會很多；實際上是空間換時間。
5、回收分區
(1)回收區（首址a）與一個分區f1末尾（首址b+大小）鄰接：將回收區與f1合並，修改f1的表項的分區大小
(2)回收區（首址a+大小）與一個分區f2的首址b鄰接：將回收區與f2合並，修改f2的表項的首址、分區大小
(3) （1）（2）兩種情況都有，則將回收區與前後兩個分區F1、F2鄰接：將三個分區合並，使用F1的表項和F1的首址，取消F2的表項，大小為三者之和
(4) 回收區沒有鄰接的分區：為回收區單獨建立新表項，填寫回收區的首址與大小，根據其首址插到空閑鏈中的適當位置
四、動態重定位分區分配——有緊湊功能的動態分區分配
動態重定位分區分配演算法與動態分區分配演算法基本相同，差別在於增加了緊湊的功能。
夥伴系統
分區大小有規定，且分區動態變化
1、無論已分配還是空閑分區，大小都為2的k此冪。若整個可分配空間大小為2m，則1≤k≤m.
2、隨著系統運行，內存被不斷劃分，形成若干不連續的空閑分區。對每一類具有相同大小的空閑分區設置一雙向鏈表，即會有k個鏈表，鏈表中的分區大小都是2m。
3、進程申請n個大小的空間時，計算n= 2i。則找i對應的鏈表。若i大小的鏈表沒有，則找i+1的鏈表。找到的分區對半劃分後，一半用於分配，一半鏈接到較小一級的鏈表裡去。
4、一次分配和回收都可能對應多次的劃分和合並。
五、內存空間管理之對換
當內存空間還是滿足不了需求時，把內存中暫時不能運行、或暫時不用的程序和數據調到外存上，以騰出足夠的內存；把已具備運行條件的進程和進程所需要的程序和數據，調入內存。
整體對換(或進程對換)：以整個進程為單位（連續分配）
頁面對換或分段對換：以頁或段為單位（離散分配）
『肆』 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、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所屬隊列。