操作系統(tǒng)-連續(xù)分配存儲管理方式

4.3連續(xù)分配存儲管理方式

4.3.1單一連續(xù)分配

在單道程序環(huán)境下，當時的存儲器管理方式是把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，它通常是放在內(nèi)存的低址部分。而在用戶區(qū)內(nèi)存中，僅裝有一道用戶程序，即整個內(nèi)存的用戶空間由該程序獨占。這樣的存儲器分配方式被稱為單一連續(xù)分配方式。4.3.2固定分區(qū)分配

1.劃分分區(qū)的方法

可用下述兩種方法將內(nèi)存的用戶空間劃分為若干個固定大小的分區(qū)：

(1)分區(qū)大小相等(指所有的內(nèi)存分區(qū)大小相等)。

(2)分區(qū)大小不等。

2.內(nèi)存分配

為了便于內(nèi)存分配，通常將分區(qū)按其大小進行排隊，并為之建立一張分區(qū)使用表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)(是否已分配)，如圖4-5所示。圖4-5固定分區(qū)使用表4.3.3動態(tài)分區(qū)分配

1.動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)

常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：①空閑分區(qū)表，在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目中包括分區(qū)號、分區(qū)大小和分區(qū)始址等數(shù)據(jù)項，如圖4-6所示。②空閑分區(qū)鏈。為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針，在分區(qū)尾部則設(shè)置一后向指針。通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個雙向鏈，如圖4-7所示。

圖4-6空閑分區(qū)表

圖4-7空閑鏈結(jié)構(gòu)

2.動態(tài)分區(qū)分配算法

為把一個新作業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。由于內(nèi)存分配算法對系統(tǒng)性能有很大的影響，故人們對它進行了較為廣泛而深入的研究，于是產(chǎn)生了許多動態(tài)分區(qū)分配算法。

3.分區(qū)分配操作

1)分配內(nèi)存

系統(tǒng)應利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請求的分區(qū)大小為u.size，表中每個空閑分區(qū)的大小可表示為m.size。圖4-8內(nèi)存分配流程

2)回收內(nèi)存

當進程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應的插入點，此時可能出現(xiàn)以下四種情況之一：

(1)回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰接，見圖4-9(a)。此時應將回收區(qū)與插入點的前一分區(qū)合并，不必為回收分區(qū)分配新表項，而只需修改其前一分區(qū)F1的大小。

(2)回收分區(qū)與插入點的后一空閑分區(qū)F2相鄰接，見圖

4-9(b)。此時也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。

(3)回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接，見圖

4-9(c)。此時將三個分區(qū)合并，使用F1的表項和F1的首址，取消F2的表項，大小為三者之和。

(4)回收區(qū)既不與F1鄰接，又不與F2鄰接。這時應為回收區(qū)單獨建立一個新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當位置。圖4-10示出了內(nèi)存回收時的流程。圖4-9內(nèi)存回收時的情況圖4-10內(nèi)存回收流程4.3.4基于順序搜索的動態(tài)分區(qū)分配算法

1.首次適應(firstfit，F(xiàn)F)算法

我們以空閑分區(qū)鏈為例來說明采用FF算法時的分配情況。FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時，從鏈首開始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈首直至鏈尾都不能找到一個能滿足要求的分區(qū)，則表明系統(tǒng)中已沒有足夠大的內(nèi)存分配給該進程，內(nèi)存分配失敗，返回。

2.循環(huán)首次適應(nextfit，NF)算法

為避免低址部分留下許多很小的空閑分區(qū)，以及減少查找可用空閑分區(qū)的開銷，循環(huán)首次適應算法在為進程分配內(nèi)存空間時，不再是每次都從鏈首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至找到一個能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。

3.最佳適應(bestfit，BF)算法

所謂“最佳”是指，每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。

4.最壞適應(worstfit，WF)算法

由于最壞適應分配算法選擇空閑分區(qū)的策略正好與最佳適應算法相反：它在掃描整個空閑分區(qū)表或鏈表時，總是挑選一個最大的空閑區(qū)，從中分割一部分存儲空間給作業(yè)使用，以至于存儲器中缺乏大的空閑分區(qū)，故把它稱為是最壞適應算法。4.3.5基于索引搜索的動態(tài)分區(qū)分配算法

1.快速適應(quickfit)算法

該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，這樣系統(tǒng)中存在多個空閑分區(qū)鏈表。同時，在內(nèi)存中設(shè)立一張管理索引表，其中的每一個索引表項對應了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。

2.伙伴系統(tǒng)(buddysystem)

該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為整數(shù)，l≤k≤m)。通常2m是整個可分配內(nèi)存的大小(也就是最大分區(qū)的大小)。假設(shè)系統(tǒng)的可利用空間容量為2m

個字，則系統(tǒng)開始運行時，整個內(nèi)存區(qū)是一個大小為2m的空閑分區(qū)。在系統(tǒng)運行過程中，由于不斷地劃分，將會形成若干個不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)按分區(qū)的大小進行分類。對于具有相同大小的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)雙向鏈表，這樣，不同大小的空閑分區(qū)形成了k個空閑分區(qū)鏈表。在伙伴系統(tǒng)中，對于一個大小為2k，地址為x的內(nèi)存塊，其伙伴塊的地址則用buddyk(x)表示，其通式為：

3.哈希算法

在上述的分類搜索算法和伙伴系統(tǒng)算法中，都是將空閑分區(qū)根據(jù)分區(qū)大小進行分類，對于每一類具有相同大小的空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表。在為進程分配空間時，需要在一張管理索引表中查找到所需空間大小所對應的表項，從中得到對應的空閑分區(qū)鏈表表頭指針，從而通過查找得到一個空閑分區(qū)。如果對空閑分區(qū)分類較細，則相應索引表的表項也就較多，因此會顯著地增加搜索索引表的表項的時間開銷。4.3.6動態(tài)可重定位分區(qū)分配

1.緊湊

連續(xù)分配方式的一個重要特點是，一個系統(tǒng)或用戶程序必須被裝入一片連續(xù)的內(nèi)存空間中。當一臺計算機運行了一段時間后，它的內(nèi)存空間將會被分割成許多小的分區(qū)，而缺乏大的空閑空間。即使這些分散的許多小分區(qū)的容量總和大于要裝入的程序，但由于這些分區(qū)不相鄰接，也無法把該程序裝入內(nèi)存。圖4-11緊湊的示意

2.動態(tài)重定位

在4.2.1節(jié)中所介紹的動態(tài)運行時裝入的方式中，作業(yè)裝入內(nèi)存后的所有地址仍然都是相對(邏輯)地址。而將相對地址轉(zhuǎn)換為絕對(物理)地址的工作被推遲到程序指令要真正執(zhí)行時進行。為使地址的轉(zhuǎn)換不會影響到指令的執(zhí)行速度，必須有硬件地址變換機構(gòu)的支持，即須在系統(tǒng)中增設(shè)一個重定位寄存器，用它來存放程序(數(shù)據(jù))在內(nèi)存中的起始地址。程序在執(zhí)行時，真正訪問的內(nèi)存地址是相對地址與重定位寄存器中的地址相加而形成的。圖4-12動態(tài)重定位示意圖

3.動態(tài)重定位分區(qū)分配算法

動態(tài)重定位分區(qū)分配算法與動態(tài)分區(qū)分配算法基本上