內存劃分與分配技術

1.內存劃分

靜態劃分：劃分預先進行，創建新進程時，在內存中找到一個合適的分區分配給它。
動態劃分：系統初始化時，可以將整個內存的用戶區看作一個分區。創建新進程時，根據進程申請的空間大小，在這個分區中動態地為之劃分一部分空間。

2.靜態劃分

必須事先進行，一旦劃分完畢，分區的大小和數目將不再改變。可以劃分：大小相同/不同的分區，如固定分區和分頁。

2.1固定分區：

根據系統管理員的經驗和一些統計規律，事先將內存空間劃分為若干個固定大小的分區，稱為分區(Partitioning)。當進程申請存儲空間時，系統為之分配一個大小合適的空閑分區。
分頁：特殊的靜態分區，需要事先將內存空間劃分為若干個大小相同的分區，稱為頁框，或幀（frame）（固定分區大小一般要大于分頁）。當進程申請存儲空間時，系統可以為之分配多個空閑頁框。
固定分區：等長原則 所有分區的長度相同。優點：分配簡單，只要進程大小不超過分區大小，就可以裝到任何一個分區中運行。缺點：浪費存儲空間。若進程申請的存儲空間很小，卻需要占用整個分區，分區內存在不可用的浪費空間，稱為內零頭（internal fragmentation）；無法運行超過分區大小的程序；無法精確確定分區的大小（依賴經驗）。
固定分區：異長原則
將內存空間劃分為若干個長度不同的分區，以適合于不同大小的進程需要。優點：既提高存儲空間的利用率、減少浪費，又使長進程能裝入運行。缺點：確定每個分區的大小也是一件十分困難的事情。?
固定分區管理簡單，只需要建立一張分區使用表，登記分區的使用情況（等長分區只需要標明分區狀態是已分配，還是空閑）。
首先，檢索分區使用表，從中找出一個尚未分配的、能滿足大小且內零頭最小的分區。若分區使用表中的分區按從小到大的順序排列，則分配時，從表中的第一個表項開始查找，找到的第一個尚未分配并滿足大小的分區即是最佳的分區。將分區使用表中該分區的狀態修改為已分配。若找不到大小足夠的分區，則系統將拒絕運行該進程，或采用其它技術進行處理，如覆蓋技術等。
固定分配缺點：固定分區存在內零頭，浪費存儲空間：異長分區較等長分區可以一定程度上提高系統的性能，但并不能徹底解決問題。

2.2 分頁式劃分(Paging)

為了提高內存資源的利用率，可以考慮將分區長度縮小，減少內零頭浪費的空間。
但是，這樣做必須有一個前提，即進程可以分配若干不連續的存儲空間。否則，小分區可能使更多的進程無法裝入內存。分頁劃分：系統預先將內存空間劃分為若干較小的、固定大小的頁框。

頁框較小，有效地減少了內零頭的浪費；每個進程平均浪費0.5頁框大小。頁框大小固定，簡化了存儲分配。需要記錄內存頁框的分配和使用情況：位示圖、空閑頁框表或空閑頁框鏈表等。
分頁式劃分：數據結構 位示圖是一個由0、1構成的向量，其中每一位(bit)表示一個頁框的使用狀態。一般規定，0表示頁框空閑，1表示頁框已被分配。假定存儲空間被劃分為n個頁框，所有頁框依次編號為0,1,2,…,n-1，則記錄所有頁框的使用狀態的位示圖形如：000001110111111111110001111…0011111
空閑頁框表：以表格形式記載內存頁框的使用情況。顯然，為每一個空閑頁框設置一個表項是不合理的，這將導致頁框表太大。可以為一組連續的空閑頁框設置一個表項，其中主要包括：首頁框號和頁框個數，如表所示：


位示圖和空閑頁框表都需要占用專門的存儲空間。。。
空閑頁框鏈表：是將內存中所有的空閑頁框通過其內的鏈接指針連成一個鏈表，系統只需要記錄鏈表頭的位置。為進程分配存儲空間時，從鏈表頭開始取所需的頁框，同時更新鏈表頭。回收進程釋放的存儲空間時，將新產生的空閑頁框鏈接到空閑頁框鏈表中。?

3.動態劃分與分配技術

靜態劃分未考慮進程的實際需要。無論是固定分區，還是分頁，都存在不同程度的內零頭。
動態劃分：根據進程的實際需要，動態地劃分內存空間，并分配給進程，徹底解決了內零頭問題(并不意味完全沒有內零頭)。
系統初始化時，內存用戶區就是一個大分區。隨著進程的創建和撤消，內存被動態劃分成若干較小的分區。
例：有一個128MB的內存，其中操作系統自身占用8MB，剩下的120MB空間供用戶進程使用。依次裝入進程P1、P2、P3、P4、P5、P6，剩下一個10MB的空閑分區。一段時間之后，進程P1、P3、P5執行結束，釋放出3個空閑分區。內存中共有4個空閑分區：
利用相應的數據結構記載空閑分區表，例如：
采用動態劃分技術，為進程分配存儲空間的過程較復雜。當系統中有多個滿足進程大小的空閑分區時，如何為進程選擇一個分區合適的分區呢？目前幾種較典型的分區分配方案：

3.1首次適應算法 (FFA：First Fit Algorithm)

基本思想：總是從內存的某一端（一般從低地址端）開始查找，選擇一個超過進程申請大小的空閑分區。為此，可以將空閑分區表中登記的空閑分區按照其起始地址由小到大的次序依次排列。系統查找空閑分區時，從表頭開始查找，取第一個滿足要求的分區分配給進程。若找到的空閑分區恰好與進程申請的存儲空間大小相等，或分配給該進程以后，僅剩下一個非常小的空間（小于系統設置的閾值），則將該分區全部分配給申請進程。否則，系統將該分區劃分為兩個分區，一個分區的長度等于進程申請的空間大小，并將其分配給申請進程。然后，將另一個子分區鏈接到空閑分區鏈表中。 優點：盡量使用低地址空間，因而在高地址的空間可能會保留較大的空閑分區。所以，大進程申請的存儲空間大都能在高地址端得到滿足。
缺點：由于每次只簡單地使用找到的第一個分區，結果可能導致將較大的空閑分區不斷地分割為較小的空閑分區。
3.2 外零頭 動態劃分技術解決了靜態劃分技術的內零頭。可能產生很多較小的分區：外零頭(External Fragment)。緊湊(Compaction)：把內存中的所有空閑分區拼接成一個較大的空閑分區。即把內存中的所有進程移到內存的某一端；所有空閑分區移到另一端
例，將如圖所示的內存空間進行緊湊以后的效果（Windows中的磁盤碎片管理功能）：

3.3下次適應算法 (NFA: Next-Fit Algorithm)?

首次適應算法每次都從低地址端開始查找空閑分區，總是頻繁使用內存的某一端，某些大進程申請的大分區需要很長時間才能在內存的另一端找到。能否均衡使用整個內存空間，加快大分區的查找速度呢？下次適應算法能記住上次分配分區的位置，下一次實施分配時，從上一次的分配位置之后開始查找，選擇一個大小足夠的空閑分區。
該算法常常會導致內存中缺乏大分區，因為它會均衡地利用空閑分區，包括分割較大的空閑分區。從而使得大進程無法裝入內存運行。下次適應算法可能會導致大量的外零頭，需要較頻繁地實施緊湊操作。

3.4最佳適應算法 (BFA：Best Fit Algorithm)?

總是選擇滿足申請要求且長度最小的空閑分區。為了提高查找效率，可以將所有的空閑分區按照長度由小大到的次序依次排列在空閑分區表中。為進程分配存儲空間時，從表頭開始查找，第一個滿足進程申請存儲空間大小的分區就是最適合的分區。?
優點：盡量不分割大的空閑分區
缺點：可能會形成大量較小的、難以再分配的分區 —— 大量的外零頭。
最佳適應算法并非是最好的算法。

3.5最差適應算法 (WFA：Worst Fit Algorithm)

選擇滿足申請要求且長度最大的空閑分區，使分割出來的剩余空閑分區較大。為了提高系統效率，可將系統中所有的空閑分區按照長度由大到小的次序依次排列在空閑分區表中。為進程分配存儲空間時，從表頭開始查找，選擇第一個滿足進程需要的分區。如果第一個空閑分區小于進程申請空間的大小，則不能立即為進程分配存儲空間。
優點：可以避免形成大量較小外零頭，
缺點：總是分割大的空閑分區。當遇到大進程申請大空間時，無法找到一個足夠大的空閑分區。換句話說，在大進程面前，內存中所謂的較大空閑分區也是外零頭了。

3.6例題

當系統進行到如圖所示的情形時，若有一個進程P7申請大小為16MB的存儲空間。分別采用上述4種算法進行分配，如圖所示，分析結果。

4.伙伴系統Buddy System

靜態劃分方案限制了系統中活躍進的數目。并且，只能運行不超過分區大小的進程，如果進程遠遠小于分區大小，則內存空間的利用率非常低。動態劃分方案使存儲管理復雜化，并且需要系統付出緊湊外零頭的額外開銷。
伙伴系統綜合了靜態劃分技術和動態劃分技術的優點。
具體的使用方法過程： 伙伴系統內存的用戶可用空間為2^n 。系統總是為進程分配大小為2^i的一個空閑分區。其中m≤i≤U，2^m是系統允許的最小分區尺寸。如果進程申請的存儲空間大小為k，且2^i-1 ＜k ≤ 2^i,則將整個2i大小的分區分配給它。否則，該分區被分割成大小相等（ 2^i-1 ）的兩個分區。再判斷k是否滿足條件：2^i-2<k≤2^i-1,若滿足條件，則將兩個伙伴中的任何一個分配給進程；否則，將其中一個伙伴又平均分成兩個分區。此過程一直繼續進行，直到產生的分區大于或等于k，將其分配進程。?

4.1伙伴系統的存儲分配

進程申請大小為k的空間，系統為之分配一個2^i的空閑分區，其中，2^i-1 ＜k ≤ 2^i,若k ＞ 2^n，即進程 > 內存空間，失敗；若當前無尺寸為2^i的空閑分區，則：
(1) 將i變為i+1，查找一個尺寸為2^i+1的空閑分區。若存在，轉(2)執行;否則，繼續執行(1)；
(2) 等分2^i+1空閑分區:產生兩個2^i的伙伴分區；
(3) 把其中一個2i的伙伴分區作為空閑分區；
(4) ?另一個2i 空閑分區分配給進程，結束。

4.2伙伴系統存儲空間的回收?

當進程執行完畢，釋放一個尺寸為2^i的分區時，系統用算法回收該分區：如果被回收分區的伙伴分區非空閑，那么保留該分區為一個獨立的空閑分區，否則
[1] ?合并回收分區及其伙伴分區，從而得到一個尺寸為2^i+1的空閑分區；
[2] ?系統再次調用本算法回收上一步得到的尺寸為2^i+1 的空閑分區。?

4.3 例題

有進程P1、P2、P3、P4、P5相繼申請、釋放空間。系統分配、回收（合并）伙伴分區的過程如圖所示：

總結

以上是生活随笔為你收集整理的[OS复习]存储管理2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。