主存管理 | 分區存儲管理

動態分區分配

在創建進程的過程中，依用戶請求的大小建立和分配分區。

• 分區分配數據結構
• 動態分區的分配
• 動態分區的回收

分區分配數據結構

① 主存資源信息塊 (M_RIB)

② 分區描述器 (PD)

flag：為 0 —— 空閑區 為 1 —— 已分配區 size：分區大小 next：空閑區 ：自由主存隊列中的勾鏈字 已分配區 ：此項為零

③ 空閑區隊列結構

分區分配思路

① 尋找空閑塊

依申請者所要求的主存區的大小，分區分配程序在自由主存隊列中找一個滿足用戶需要的空閑塊；

② 若找到了所需的空閑區，有兩種情況

ⅰ 空閑區與要求的大小相等，將該空閑區分配並從隊列中摘除；

ⅱ 空閑區大於所要求的的大小，將空閑區分為兩部分：一部分成為已分配區，建立已分配區的描述器；剩下部分仍為空閑區。返回所分配區域的首址；

③ 否則，告之不能滿足要求。

動態分區的分配過程

分區回收思路

① 檢查釋放分區 (即為回收分區)在主存中的鄰接情況

若上、下鄰接空閑區，則合併，成為一個連續的空閑區。

三種情況：上鄰空、下鄰空、上下都鄰空。

② 若回收分區不與任何空閑區相鄰接

建立一個新的空閑區，並加入到空閑區隊列中。

動態分區的回收過程

放置策略（分配演算法）

• 選擇空閑區的策略，稱為放置策略。
• 常用的放置策略：
• 首次匹配（首次適應演算法）
• 最佳匹配（最佳適應演算法）
• 最壞匹配（最壞適應演算法）

首次適應演算法

• 是將程序裝入到主存中足夠裝入且地址最低的空閑區中。
• 空閑區按地址由低到高排序
• 盡量利用主存低地址空閑區，盡量在高地址保留大空閑區。

這樣會使的程序儘可能的在低端地址部分進行劃分，但是也會導致低端地址產生很多小的無法利用的空間，也就是碎片。為了使碎片不要過於集中在低端，可以使用循環首次適應演算法。

在循環首次適應演算法中，我們對空閑空間的搜尋，會在搜索成功的下一次分配時不是回到空閑隊列的起始位置進行搜索，而是接著上一次搜索到的位置往後搜索。可以相對比較均勻的使用前後端的空間。

最佳適應演算法

• 是將程序裝入到主存中與其大小最接近的空閑區中。
• 空閑區按大小由小到大排序
• 盡量利用存儲器中小的空閑區，而盡量保存大的空閑區。

這樣的演算法會導致其原有的空閑分區被分配後的剩餘空間很小，從而產生無法再利用的碎片。對於這個問題的解決，我們可以使用 最壞適應演算法。

最壞適應演算法

• 是將程序裝入到主存中與其大小差距最大的空閑區中。
• 空閑區按大小由大到小排序
• 盡量利用存儲器中的大空閑區，使剩餘空閑區較大。

三种放置策略的討論

題例 ：程序A要求18KB；程序B要求25KB；程序C要求30KB。用首次適應演算法、最佳適應演算法、最壞適應演算法來處理程序序列，看哪種演算法合適。主存分布圖如下：

（1）首次適應演算法、最佳適應演算法、最壞適應演算法的隊列結構

（2）首次適應演算法

程序A需要18KB的空間，其中第一個節點30KB就可以滿足，剩餘12KB繼續作為空閑空間。程序B需要25KB空間，所以在隊列中從頭往後搜索，12KB，20KB，5KB，46KB，只有最後的46KB才有足夠的空間存放B。但是程序C已經沒有地方存放了。該演算法不合適。

（3）最佳適應演算法

在按照空閑區大小從小到大排列好的隊列中，最佳適應演算法會將20KB分配給A，30KB分配給B。46KB分配給C。三個程序都可以運行。該演算法是合適的。

（4）最壞適應演算法

按照空閑去從大到小排列後，18KB的A程序分配給46KB，剩餘28KB。B程序分配給30KB，剩餘5KB的空間。此處程序C已經沒有空閑空間可以裝入了。所以該演算法也是不合適的。

碎片問題及拼接技術

碎片問題

在已分配區之間存在著的一些太小而難以利用的空閑區，稱為碎片。碎片影響主存的利用率。

拼接技術

是指移動主存中已分配區，使本來分散的小空閑區連成一個大的空閑區。提高系統的資源利用率，但是這種移動的拼接方法必定是十分耗費系統資源的，所以拼接的時間和代價值得我們的考慮。