動態分區存儲管理演算法分配與回收實現

⑴ System memory是什麼意思

System memory是系統存儲器的意思。存儲系統是指計算機中由存放程序和數據的各種存儲設備、控制部件及管理信息調度的設備（硬體）和演算法（軟體）所組成的系統。

計算機存儲系統的核心是存儲器，存儲器是計算機中必不可少、用來存儲程序和數據的記憶設備。內部存儲器（簡稱內存）主要存儲計算機當前工作需要的程序和數據，包括高速緩沖存儲器（Cache，簡稱緩存）和主存儲器。目前構成內存的主要是半導體存儲器。

外部存儲器（簡稱外存）主要有磁性存儲器、光存儲器和半導體存儲器三種實現方式，存儲介質有硬磁碟、光碟、磁帶和移動存儲器等。

(1)動態分區存儲管理演算法分配與回收實現擴展閱讀

分配存儲管理

1、單一連續分配

在單道程序環境下，內存分為系統區和用戶區，系統區只留給OS時候，放在低地址部分，用戶區僅裝有一道用戶程序。

2、固定分區分配

將內存的用戶空間劃分為若干個固定大小的分區，，並為之建立一張分區使用表，包含每個分區的起始地址，大小，狀態.

3、動態分區分配

要實現動態分區分配，必須解決分區所用的數據結構，分區分配演算法和分區的分配與回收這三個問題。

⑵ 在分頁存儲管理方式下應怎樣實現主存空間的分配和回收

2.1 模擬包括3部分：
1）實現特定的內存分配演算法
2）實現內存回收模擬
3）每種內存分配策略對應的碎片數統計
2.2 固定分區存儲管理
假設內存容量為120KB，並且分別劃分成8,16,32,64KB大小的塊各一塊。
一個進程所需要的內存為0到100個KB。同時假設一個進程在運行過程中所需內存的大小不變。
模擬五個進程到達請求分配與運行完回收情況,輸出主存分配表.
2.3 動態分區分配存儲管理
採用連續分配方式之動態分區分配存儲管理，使用首次適應演算法、下次適應演算法、最佳適應演算法和最壞適應演算法4種演算法完成設計(任選兩種演算法)。

⑶ 動態分區分配演算法實現報告理解在動態分區分配存儲管理方式下怎樣實現主存

創建程序，用梯形圖編程語言創建一個與模板相連結或與模板無關的程序並存儲用戶管理器設置，用戶管理器用於分配和控制用戶的單個組態和運行系統編輯器的

⑷ 分區存儲管理中常用哪些分配策略

1、固定分區存儲管理
其基本思想是將內存劃分成若干固定大小的分區，每個分區中最多隻能裝入一個作業。當作業申請內存時，系統按一定的演算法為其選擇一個適當的分區，並裝入內存運行。由於分區大小是事先固定的，因而可容納作業的大小受到限制，而且當用戶作業的地址空間小於分區的存儲空間時，造成存儲空間浪費。

一、空間的分配與回收

系統設置一張「分區分配表」來描述各分區的使用情況，登記的內容應包括：分區號、起始地址、長度和佔用標志。其中佔用標志為「0」時，表示目前該分區空閑；否則登記佔用作業名（或作業號）。有了「分區分配表」，空間分配與回收工作是比較簡單的。

二、地址轉換和存儲保護

固定分區管理可以採用靜態重定位方式進行地址映射。

為了實現存儲保護，處理器設置了一對「下限寄存器」和「上限寄存器」。當一個已經被裝入主存儲器的作業能夠得到處理器運行時，進程調度應記錄當前運行作業所在的分區號，且把該分區的下限地址和上限地址分別送入下限寄存器和上限寄存器中。處理器執行該作業的指令時必須核對其要訪問的絕對地址是否越界。

三、多作業隊列的固定分區管理

為避免小作業被分配到大的分區中造成空間的浪費，可採用多作業隊列的方法。即系統按分區數設置多個作業隊列，將作業按其大小排到不同的隊列中，一個隊列對應某一個分區，以提高內存利用率。

2、可變分區存儲管理
可變分區存儲管理不是預先將內存劃分分區，而是在作業裝入內存時建立分區，使分區的大小正好與作業要求的存儲空間相等。這種處理方式使內存分配有較大的靈活性，也提高了內存利用率。但是隨著對內存不斷地分配、釋放操作會引起存儲碎片的產生。

一、空間的分配與回收

採用可變分區存儲管理，系統中的分區個數與分區的大小都在不斷地變化，系統利用「空閑區表」來管理內存中的空閑分區，其中登記空閑區的起始地址、長度和狀態。當有作業要進入內存時，在「空閑區表」中查找狀態為「未分配」且長度大於或等於作業的空閑分區分配給作業，並做適當調整；當一個作業運行完成時，應將該作業佔用的空間作為空閑區歸還給系統。

可以採用首先適應演算法、最佳（優）適應演算法和最壞適應演算法三種分配策略之一進行內存分配。

二、地址轉換和存儲保護

可變分區存儲管理一般採用動態重定位的方式，為實現地址重定位和存儲保護，系統設置相應的硬體：基址/限長寄存器（或上界/下界寄存器）、加法器、比較線路等。

基址寄存器用來存放程序在內存的起始地址，限長寄存器用來存放程序的長度。處理機在執行時，用程序中的相對地址加上基址寄存器中的基地址，形成一個絕對地址，並將相對地址與限長寄存器進行計算比較，檢查是否發生地址越界。

三、存儲碎片與程序的移動

所謂碎片是指內存中出現的一些零散的小空閑區域。由於碎片都很小，無法再利用。如果內存中碎片很多，將會造成嚴重的存儲資源浪費。解決碎片的方法是移動所有的佔用區域，使所有的空閑區合並成一片連續區域，這一技術稱為移動技術（緊湊技術）。移動技術除了可解決碎片問題還使內存中的作業進行擴充。顯然，移動帶來系統開銷加大，並且當一個作業如果正與外設進行I/O時，該作業是無法移動的。

3、頁式存儲管理

基本原理

1．等分內存

頁式存儲管理將內存空間劃分成等長的若干區域，每個區域的大小一般取2的整數冪，稱為一個物理頁面有時稱為塊。內存的所有物理頁面從0開始編號，稱作物理頁號。

2．邏輯地址

系統將程序的邏輯空間按照同樣大小也劃分成若干頁面，稱為邏輯頁面也稱為頁。程序的各個邏輯頁面從0開始依次編號，稱作邏輯頁號或相對頁號。每個頁面內從0開始編址，稱為頁內地址。程序中的邏輯地址由兩部分組成：

邏輯地址
頁號p
頁內地址 d

3．內存分配

系統可用一張「位示圖」來登記內存中各塊的分配情況，存儲分配時以頁面（塊）為單位，並按程序的頁數多少進行分配。相鄰的頁面在內存中不一定相鄰，即分配給程序的內存塊之間不一定連續。

對程序地址空間的分頁是系統自動進行的，即對用戶是透明的。由於頁面尺寸為2的整數次冪，故相對地址中的高位部分即為頁號，低位部分為頁內地址。

3.5.2實現原理

1．頁表

系統為每個進程建立一張頁表，用於記錄進程邏輯頁面與內存物理頁面之間的對應關系。地址空間有多少頁，該頁表裡就登記多少行，且按邏輯頁的順序排列，形如：

邏輯頁號
主存塊號

0
B0

1
B1

2
B2

3
B3

2．地址映射過程

頁式存儲管理採用動態重定位，即在程序的執行過程中完成地址轉換。處理器每執行一條指令，就將指令中的邏輯地址（p,d）取來從中得到邏輯頁號(p)，硬體機構按此頁號查頁表，得到內存的塊號B』，便形成絕對地址（B』,d）,處理器即按此地址訪問主存。

3．頁面的共享與保護

當多個不同進程中需要有相同頁面信息時，可以在主存中只保留一個副本，只要讓這些進程各自的有關項中指向內存同一塊號即可。同時在頁表中設置相應的「存取許可權」，對不同進程的訪問許可權進行各種必要的限制。

4、段式存儲管理

基本原理

1．邏輯地址空間

程序按邏輯上有完整意義的段來劃分，稱為邏輯段。例如主程序、子程序、數據等都可各成一段。將一個程序的所有邏輯段從0開始編號，稱為段號。每一個邏輯段都是從0開始編址，稱為段內地址。

2．邏輯地址

程序中的邏輯地址由段號和段內地址（s,d）兩部分組成。

3．內存分配

系統不進行預先劃分，而是以段為單位進行內存分配，為每一個邏輯段分配一個連續的內存區（物理段）。邏輯上連續的段在內存不一定連續存放。

3．6．2實現方法

1．段表

系統為每個進程建立一張段表，用於記錄進程的邏輯段與內存物理段之間的對應關系，至少應包括邏輯段號、物理段首地址和該段長度三項內容。

2．建立空閑區表

系統中設立一張內存空閑區表，記錄內存中空閑區域情況，用於段的分配和回收內存。

3．地址映射過程

段式存儲管理採用動態重定位，處理器每執行一條指令，就將指令中的邏輯地址（s,d）取來從中得到邏輯段號(s)，硬體機構按此段號查段表，得到該段在內存的首地址S』， 該段在內存的首地址S』加上段內地址d，便形成絕對地址（S』+d），處理器即按此地址訪問主存。

5、段頁式存儲管理

頁式存儲管理的特徵是等分內存，解決了碎片問題；段式存儲管理的特徵是邏輯分段，便於實現共享。為了保持頁式和段式上的優點，結合兩種存儲管理方案，形成了段頁式存儲管理。

段頁式存儲管理的基本思想是：把內存劃分為大小相等的頁面；將程序按其邏輯關系劃分為若干段；再按照頁面的大小，把每一段劃分成若干頁面。程序的邏輯地址由三部分組成，形式如下：

邏輯地址
段號s
頁號p
頁內地址d

內存是以頁為基本單位分配給每個程序的，在邏輯上相鄰的頁面內存不一定相鄰。

系統為每個進程建立一張段表，為進程的每一段各建立一張頁表。地址轉換過程，要經過查段表、頁表後才能得到最終的物理地址。

⑸ 【我的筆記】內存管理（二）分區方法（靜態、動態、夥伴、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所屬隊列。