第十一講存儲(chǔ)器管理之連續(xù)分配方式

1、第十一講 存儲(chǔ)器管理之連續(xù)分配方式所謂連續(xù)分配方式：是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。又可把連續(xù)分配方式分為：?jiǎn)我贿B續(xù)分配，固定分區(qū)分配，動(dòng)態(tài)分區(qū)分配，動(dòng)態(tài)重定位分區(qū)分配，四種方式。1 單一連續(xù)分配（單獨(dú)分區(qū)分配）最簡(jiǎn)單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的OS 中。概念： 單一連續(xù)分配就是整個(gè)主存區(qū)域的用戶空間均歸一個(gè)用戶作業(yè)使用。存儲(chǔ)管理方法： 將內(nèi)存分為系統(tǒng)區(qū)（內(nèi)存低端，分配給OS用）和用戶區(qū)（內(nèi)存高端，分配給用戶用）。其中用戶區(qū)是指除了系統(tǒng)區(qū)外的內(nèi)存空間，提供給用戶程序使用。采用靜態(tài)分配方式，即作業(yè)一旦進(jìn)入內(nèi)存，就要等待它運(yùn)行結(jié)束后才能釋放內(nèi)存。主要特點(diǎn) ：管理簡(jiǎn)單，只

2、需小量的軟件和硬件支持，便于用戶了解和使用。但因內(nèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)大，各類資源的利用率也不高。例子： 一個(gè)容量為256KB的內(nèi)存，操作系統(tǒng)占用32KB，剩下 224KB全部分配給用戶作業(yè)，如果一個(gè)作業(yè)僅需64KB，那么就有160KB的存儲(chǔ)空間被浪費(fèi)。2 固定分區(qū)分配分區(qū)分配方式是滿足多道程序設(shè)計(jì)需要的一種最簡(jiǎn)單的存儲(chǔ)管理方法。2.1 思想：將內(nèi)存分成若干個(gè)分區(qū)（大小相等 /不相等），除 OS 占一區(qū)外，其余的每一個(gè)分區(qū)容納一個(gè)用戶程序。這樣來(lái)實(shí)現(xiàn)多道并發(fā)。2.2 分區(qū)劃分方法： 分區(qū)大小相等，分區(qū)大小不等。但事先必須確定，在運(yùn)行時(shí)不能改變。即分區(qū)大小及邊界在運(yùn)行時(shí)不能改變。

3、2.3 內(nèi)存分配：首先：要先建立一張分區(qū)說(shuō)明表或使用表，以記錄分區(qū)號(hào)、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。其次：當(dāng)某個(gè)用戶程序要裝入內(nèi)存時(shí)，由內(nèi)存分配程序檢索分區(qū)說(shuō)明表，從表中找出一個(gè)滿足要求的尚未分配的分區(qū)分配該程序，同時(shí)修改說(shuō)明表中相應(yīng)分區(qū)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕為該程序分配內(nèi)存。第三：當(dāng)程序執(zhí)行完畢，釋放占用的分區(qū)，管理程序?qū)⑿薷恼f(shuō)明表中相應(yīng)分區(qū)的狀態(tài)為未分配，實(shí)現(xiàn)內(nèi)存資源的回收。2.4 特點(diǎn)主要特點(diǎn)： 管理簡(jiǎn)單，但因作業(yè)的大小并不一定與某個(gè)分區(qū)大小相等，從而使一部分存儲(chǔ)空間被浪費(fèi)。所以主存的利用率不高3 動(dòng)態(tài)分區(qū)分配3.1 基本思想 ：根據(jù)進(jìn)程的實(shí)際需要，動(dòng)

4、態(tài)的為其分配內(nèi)存空間。因此分區(qū)大小是動(dòng)態(tài)可變的，分區(qū)的個(gè)數(shù)也是可變的。3.2 主要特點(diǎn)管理簡(jiǎn)單，只需小量的軟件和硬件支持，便于用戶了解和使用。進(jìn)程的大小與某個(gè)分區(qū)大小相等，從而主存的利用率有所提高。3.3 分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)為描述空閑分區(qū)合已分配的分區(qū)，引入如下數(shù)據(jù)結(jié)構(gòu)。空閑分區(qū)表用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，表目重含有分區(qū)序號(hào)，分區(qū)起始地址，分區(qū)大小等數(shù)據(jù)項(xiàng)。如下圖, 則它必然被選中，若不存在與作業(yè)大小一致的空閑, 從而保留了大的空閑分區(qū) , 但空閑區(qū)一般不可能空閑分區(qū)鏈用鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來(lái)，構(gòu)成空閑分區(qū)鏈。每個(gè)空閑分區(qū)的起始部分存放相應(yīng)的控制信息 (

5、如大小 , 指向下一空閑分區(qū)的指針等 ).就是在分區(qū)頭設(shè)置一個(gè)前向指針，分區(qū)尾部設(shè)置一個(gè)后向指針，這樣把所有空閑分區(qū)連起來(lái)。3.4分區(qū)分配算法把一個(gè)新作業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選擇一俄國(guó)分區(qū)分配給該作業(yè)。有下面三種分配算法：首次適應(yīng)算法算法過程：算法要求空閑分區(qū)（鏈）按地址遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí), 從空閑分區(qū)表/鏈?zhǔn)组_始順序查找, 直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一 塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍 留在空閑分區(qū)表（鏈）中。算法的特點(diǎn)優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū), 從而保留了高地址部分的大空

6、閑區(qū)。但由于低地址部分不斷被劃分, 致使低地址端留下許多難以利用的很小的空閑分區(qū)( 碎片或零頭 ), 而每次查找又都是從低地址部分開始, 這無(wú)疑增加了查找可用空閑分區(qū)的開銷。循環(huán)首次適應(yīng)算法算法過程：由首次適應(yīng)算法發(fā)展而來(lái)，每次為進(jìn)程分配內(nèi)存空間時(shí)，不是從鏈?zhǔn)组_始，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到一個(gè)滿足要求的空閑分區(qū)。該算法要設(shè)置一個(gè)起始查尋指針。用于標(biāo)識(shí)下一次起始查尋的空閑分區(qū)。算法特點(diǎn)使存儲(chǔ)空間的利用更加均衡，不致使小的空閑區(qū)集中在存儲(chǔ)區(qū)的一端，但這會(huì)導(dǎo)致缺乏大的空閑分區(qū)。最佳適應(yīng)算法算法過程：算法要求空閑分區(qū)表/ 鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí)，

7、從空閑分區(qū)表/ 鏈的首開始順序查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/ 鏈中。算法特點(diǎn)若存在與作業(yè)大小一致的空閑分區(qū)分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，正好和它申請(qǐng)的內(nèi)存空間大小一樣, 因而將其分割成兩部分時(shí), 往往使剩下的空閑區(qū)非常小 ,從而在存儲(chǔ)器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。3.5分區(qū)分配操作這里所謂的操作是：分配內(nèi)存合回收內(nèi)存。3.5.1分配內(nèi)存操作實(shí)際上是分區(qū)的分割。具體過程如下：設(shè) 請(qǐng) 求

8、的 分 區(qū) 大 小 為 u.size， 空 閑 分 區(qū) 的 大 小 為 m.size, 若 m.size-u.sizesize( size 是事先規(guī)定的不再切割的剩余分區(qū)的大小) ，說(shuō)明多余部分太小，可不再切割，將整個(gè)分區(qū)分配給請(qǐng)求者；否則, 即多余部分超過size ，從該分區(qū)中按請(qǐng)求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表/ 鏈中，然后，將分配區(qū)的首址返回給調(diào)用者。分配流程圖：回收內(nèi)存操作基本過程： 當(dāng)作業(yè)執(zhí)行結(jié)束時(shí)，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個(gè)大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息。

9、回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種：1）回收分區(qū)上鄰接一個(gè)空閑分區(qū), 合并后首地址為空閑分區(qū)的首地址, 大小為二者之和。2）回收分區(qū)下鄰接一個(gè)空閑分區(qū), 合并后首地址為回收分區(qū)的首地址, 大小為二者之和。3）回收分區(qū)上下鄰接空閑分區(qū), 合并后首地址為上空閑分區(qū)的首地址, 大小為三者之和。4）回收分區(qū)不鄰接空閑分區(qū)，這時(shí)在空閑分區(qū)表中新建一表項(xiàng)，并填寫分區(qū)大小等信息，并根據(jù)其首地址插入到空閑鏈的適當(dāng)位置。如下圖：4 可重定位分區(qū)分配4.1動(dòng)態(tài)重定位的引入在連續(xù)分配方式中，我們必須把一個(gè)系統(tǒng)或用戶程序裝入一個(gè)連續(xù)的內(nèi)存空間。但是，如果在系統(tǒng)中只有一些小分區(qū)并且這些分區(qū)不相鄰鏈接，即使它們的

10、相加之后的空間大于要裝入的程序，也不可能把程序裝入這些內(nèi)存中。這些小分區(qū)就叫做“零頭”或“碎片”。處理思路“緊湊”：將內(nèi)存中的所有作業(yè)移動(dòng)到內(nèi)存的另一端，使它們?nèi)肯噜?。這樣，就可以把原來(lái)分散的多個(gè)小分區(qū)拼接成一個(gè)大分區(qū)，這時(shí)就可把作業(yè)裝入了。稱為“緊湊”或“拼接”。出現(xiàn)問題：緊湊后，明顯可以看出內(nèi)存中的數(shù)據(jù)和程度的存放位置發(fā)生了變化，如果不對(duì)程序和數(shù)據(jù)的地址加以更改，則程序不能運(yùn)行，因此我們需要重定位。也就是說(shuō)在每次緊湊之后需要重定位。4.2動(dòng)態(tài)重定位的實(shí)現(xiàn)引入重定位寄存器，程序在執(zhí)行時(shí)，真正訪問的內(nèi)存地址是相對(duì)地址和重定位寄存器中的地址相加后的地址。見課本圖 p111動(dòng)態(tài)重定位：地址變換過

11、程是在程序執(zhí)行期間，隨著對(duì)每條指令或數(shù)據(jù)的訪問時(shí)才進(jìn)行的。因此稱為動(dòng)態(tài)重定位。4.3動(dòng)態(tài)重定位分區(qū)分配算法和動(dòng)態(tài)分區(qū)分配算法基本相同，只是增加了緊湊功能。算法流程如下：5對(duì)換了解多道程序環(huán)境下，會(huì)出現(xiàn)某些進(jìn)程未執(zhí)行而占據(jù)內(nèi)存空間，而大量的作業(yè)在外存而不能進(jìn)入內(nèi)存執(zhí)行。為了充分的利用內(nèi)存空間，我們引入了覆蓋和對(duì)換。覆蓋是早期的操作系統(tǒng)中運(yùn)用，有興趣的同學(xué)了解一下。我們主要說(shuō)一下對(duì)換。對(duì)換： 將暫時(shí)不用的某個(gè)進(jìn)程及數(shù)據(jù)（首先是處于阻塞狀態(tài)優(yōu)先級(jí)最低的，根據(jù)系統(tǒng)的采用算法決定）部分（或全部）從內(nèi)存移到到外存（備份區(qū)或?qū)Q區(qū)，采用連續(xù)分配的動(dòng)態(tài)存儲(chǔ)管理方式）中去，讓出內(nèi)存空間，同時(shí)將某個(gè)需要的進(jìn)程調(diào)入到內(nèi)存中，讓其運(yùn)行。交換到外存的進(jìn)程需要時(shí)可以被再次交換回（選擇換出時(shí)間最久的，也是根據(jù)系統(tǒng)采用的算法決定）內(nèi)存中繼續(xù)執(zhí)行。這種內(nèi)存擴(kuò)充技術(shù)就是交換技術(shù)。6 覆蓋6.1引入：其目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序。常用于多道程序系統(tǒng)，與