ch4-4.2連續(xù)存儲(chǔ)空間管理

1、第四章 存儲(chǔ)管理,4.2 連續(xù)存儲(chǔ)空間管理,4.2.1 固定分區(qū)存儲(chǔ)管理 4.2.2 可變分區(qū)存儲(chǔ)管理 4.2.3 伙伴系統(tǒng)4.2.4 主存不足的存儲(chǔ)管理技術(shù),4.2.1 固定分區(qū)存儲(chǔ)管理,固定分區(qū)存儲(chǔ)管理是實(shí)現(xiàn)多道程序設(shè)計(jì)的最簡(jiǎn)單的一種存儲(chǔ)管理技術(shù)。基本思想：在作業(yè)未進(jìn)入內(nèi)存之前，就由操作員或操作系統(tǒng)把內(nèi)存可用空間劃分成若干個(gè)固定大小的存儲(chǔ)區(qū)，除操作系統(tǒng)占用一個(gè)區(qū)域外，其余區(qū)域?yàn)橄到y(tǒng)中多個(gè)用戶(hù)共享。在系統(tǒng)運(yùn)行期間，分區(qū)大小

2、、數(shù)目都不變，所以固定式分區(qū)也稱(chēng)為靜態(tài)分區(qū)。,,為了便于管理整個(gè)內(nèi)存，建立一個(gè)表格“主存分配表”來(lái)登記和管理整個(gè)內(nèi)存。在這個(gè)表中登記了每一個(gè)分區(qū)的大小，起始地址和分配狀態(tài)。當(dāng)有作業(yè)裝入時(shí)，系統(tǒng)便可以搜索這個(gè)表，找出一個(gè)大小合適的分區(qū)分配給它。當(dāng)程序運(yùn)行結(jié)束時(shí)，可以把它所占用的空間再釋放回去。,4.2.1 固定分區(qū)存儲(chǔ)管理,大小相等的分區(qū)，使用哪個(gè)分區(qū)都一樣對(duì)大小不等的分區(qū)，有兩種方法：多個(gè)輸入隊(duì)列：將每個(gè)進(jìn)程指定到適應(yīng)它的最小分區(qū)

3、；每個(gè)分區(qū)都需要一個(gè)調(diào)度隊(duì)列，用于保存為這個(gè)分區(qū)換出的進(jìn)程。一個(gè)輸入隊(duì)列: 為所有進(jìn)程提供一個(gè)隊(duì)列，當(dāng)需要把一個(gè)進(jìn)程裝入主存時(shí)，選擇可以保存該進(jìn)程的可用分區(qū)。如果所有分區(qū)都被占用，需要等待。,,4.2.1 固定分區(qū)存儲(chǔ)管理,優(yōu)點(diǎn)可以支持多道程序；實(shí)現(xiàn)簡(jiǎn)單，開(kāi)銷(xiāo)小。缺點(diǎn)作業(yè)必須預(yù)先能夠估計(jì)自己要占用多大的內(nèi)存空間，有時(shí)候這是難以做到的；存在內(nèi)碎片；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序個(gè)數(shù)。,4.2.1 固定分區(qū)存儲(chǔ)管理,4.2.2

4、可變分區(qū)存儲(chǔ)管理,基本思想： 內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程否則令其等待主存空間,,可變分區(qū)主存分配表可由兩張表格組成：“已分配區(qū)表”和“未分配區(qū)表”分區(qū)分配：尋找某個(gè)空閑分區(qū)，其大小需大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)。分區(qū)的先后次序通常是從內(nèi)存低端到高端。分區(qū)釋放：需要將相鄰的空閑分區(qū)合并成一個(gè)

5、空閑分區(qū)，登記到“未分配區(qū)表”中。（可分為4中情況）,4.2.2 可變分區(qū)存儲(chǔ)管理,可變分區(qū)管理分配算法,1）最先適應(yīng)分配算法 2）下次適應(yīng)分配算法3) 最優(yōu)適應(yīng)分配算法 4）最壞適應(yīng)分配算法5) 快速適應(yīng)分配算法,為了將一個(gè)進(jìn)程裝入內(nèi)存，應(yīng)按照一定的分配算法從空閑分區(qū)表（鏈）中選 出一個(gè)滿(mǎn)足進(jìn)程需求的分區(qū)分配給作業(yè)。目前常用分配算法有：,最先適應(yīng)分配算法,算法：空閑分區(qū)（鏈）按地址遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空

6、閑分區(qū)表/鏈?zhǔn)组_(kāi)始順序查找，直到找到第一個(gè)滿(mǎn)足其大小要求的空閑分區(qū)為止。然后再按照進(jìn)程大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。,下次適應(yīng)分配算法,算法要求 又稱(chēng)為循環(huán)首次適應(yīng)算法，由首次適應(yīng)算法演變而來(lái)。在為進(jìn)程分配內(nèi)存空間時(shí)，不再每次從空閑分區(qū)表/鏈?zhǔn)组_(kāi)始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找，直到找到第一個(gè)能滿(mǎn)足其大小要求的空閑分區(qū)為止。然后，再按照

7、進(jìn)程大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑分區(qū)表/鏈中。,最優(yōu)適應(yīng)分配算法,算法要求： 空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的首開(kāi)始順序查找，直到找到第一個(gè)滿(mǎn)足其大小要求的空閑分區(qū)為止。 按這種方式為進(jìn)程分配內(nèi)存，就能把既滿(mǎn)足進(jìn)程要求又與進(jìn)程大小最接近的空閑分區(qū)分配給進(jìn)程。如果該空閑分區(qū)大于進(jìn)程的大小，則與首次適應(yīng)算法相同，

8、將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。較大的空閑分區(qū)可以被保留。,最壞適應(yīng)分配算法,算法要求：空閑分區(qū)表/鏈按容量大小遞減的次序排列。在進(jìn)行內(nèi)存分配時(shí)，取最前面所有空閑區(qū)中最大的一塊，把剩余的塊再變成一個(gè)新的小一點(diǎn)的空閑區(qū)?；静涣粝滦】臻e分區(qū)，但較大的空閑分區(qū)不被保留。,,地址轉(zhuǎn)換固定分區(qū)存儲(chǔ)管理采用靜態(tài)地址重定位可變分區(qū)存儲(chǔ)管理采用動(dòng)態(tài)地址重定位存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)是為了防止一個(gè)作業(yè)有意或無(wú)意地破壞操作系統(tǒng)或其它進(jìn)程。常用的

9、存儲(chǔ)保護(hù)方法有：界限寄存器方法存儲(chǔ)保護(hù)鍵方法,地址轉(zhuǎn)換與存儲(chǔ)保護(hù),1、界限寄存器方法 上下界寄存器方法：用這兩個(gè)寄存器分別存放進(jìn)程的起始地址和結(jié)束地址。在進(jìn)程運(yùn)行過(guò)程中，將每一個(gè)訪問(wèn)內(nèi)存的地址都同這兩個(gè)寄存器的內(nèi)容比較，如超出這個(gè)范圍便產(chǎn)生保護(hù)性中斷?；?、限長(zhǎng)寄存器方法：用這兩個(gè)寄存器分別存放作業(yè)的起始地址和作業(yè)的地址空間長(zhǎng)度。當(dāng)作業(yè)執(zhí)行時(shí)，將每一訪問(wèn)內(nèi)存的相對(duì)地址和限長(zhǎng)寄存器比較，如果超過(guò)了限長(zhǎng)寄存器的值，則發(fā)出越界中斷信號(hào)

10、，并停止作業(yè)的運(yùn)行。,地址轉(zhuǎn)換與存儲(chǔ)保護(hù),2、存儲(chǔ)保護(hù)鍵方法 給每個(gè)存儲(chǔ)塊（大小相同，一個(gè)分區(qū)為整數(shù)倍存儲(chǔ)塊）分配一個(gè)單獨(dú)的保護(hù)鍵，它相當(dāng)于一把鎖。進(jìn)入系統(tǒng)的每個(gè)進(jìn)程也賦予一個(gè)保護(hù)鍵，它相當(dāng)于一把鑰匙。當(dāng)進(jìn)程運(yùn)行時(shí)，檢查鑰匙和鎖是否匹配，如果不匹配，則系統(tǒng)發(fā)出保護(hù)性中斷信號(hào)，停止進(jìn)程運(yùn)行。,地址轉(zhuǎn)換與存儲(chǔ)保護(hù),4.2.4 主存不足的存儲(chǔ)管理技術(shù),,1移動(dòng)技術(shù),內(nèi)碎片：在固定分區(qū)方式中，一個(gè)分區(qū)分配給作業(yè)后，分區(qū)中未

11、使用的空間區(qū)稱(chēng)為內(nèi)碎片，又稱(chēng)內(nèi)零頭。外碎片：主存中的一個(gè)空閑區(qū)域在分配給作業(yè)后，一般總是剩余一個(gè)更小的空閑區(qū)。當(dāng)這樣的小分區(qū)不能再裝入一個(gè)作業(yè)時(shí)，即不能被利用時(shí)，它們也成為主存碎片，這樣的分區(qū)在作用使用的分區(qū)之外，所以稱(chēng)為外碎片。可用移動(dòng)技術(shù)來(lái)解決碎片問(wèn)題。,4.2.4 主存不足的存儲(chǔ)管理技術(shù),,將內(nèi)存中所有作業(yè)移到內(nèi)存一端，使本來(lái)分散的多個(gè)小空閑分區(qū)連成一個(gè)大的空閑區(qū)。,有關(guān)移動(dòng)問(wèn)題討論,移動(dòng)條件空閑區(qū)的總和滿(mǎn)足分配要求移動(dòng)時(shí)

12、機(jī)分區(qū)回收時(shí)當(dāng)找不到足夠大的空閑分區(qū)且總空閑分區(qū)容量可以滿(mǎn)足作業(yè)要求時(shí)移動(dòng)算法作業(yè)在內(nèi)存中的位置發(fā)生了變化，這就必須對(duì)其地址加以修改或變換即稱(chēng)為重定位,2 對(duì)換技術(shù),對(duì)換技術(shù)也是“擴(kuò)充”內(nèi)存容量和提高內(nèi)存利用率的有效措施?，F(xiàn)代OS中廣泛采用。 最早用在MIT的兼容分時(shí)系統(tǒng)CTSS中，任何時(shí)刻系統(tǒng)中只有一個(gè)完整的用戶(hù)作業(yè)，當(dāng)運(yùn)行一段時(shí)間后，因時(shí)間片用完或等待某事件發(fā)生，系統(tǒng)就把它交換到外存上，同時(shí)把另一作業(yè)調(diào)入內(nèi)存讓其運(yùn)行，這樣

13、，可以在內(nèi)存容量不大的小型機(jī)上分時(shí)運(yùn)行，早期的一些分時(shí)系統(tǒng)多數(shù)采用這種交換技術(shù)。,交換技術(shù)：將暫時(shí)不用的某個(gè)進(jìn)程及數(shù)據(jù)（首先是處于阻塞狀態(tài)優(yōu)先級(jí)最低的）部分（或全部）從內(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í)間最久的）內(nèi)存中繼續(xù)執(zhí)行。這種內(nèi)存擴(kuò)充技術(shù)就是對(duì)換技術(shù)。,2 對(duì)換技術(shù),3 覆蓋技術(shù),覆蓋技術(shù)

14、主要用在早期的OS中（內(nèi)存<64KB），可用的存儲(chǔ)空間受限，某些大作業(yè)不能一次全部裝入內(nèi)存，產(chǎn)生了大作業(yè)與小內(nèi)存的矛盾。 例：,,覆蓋：把一個(gè)程序劃分為一系列功能相對(duì)獨(dú)立的程序段（稱(chēng)為覆蓋），讓執(zhí)行時(shí)并不要求同時(shí)裝入內(nèi)存的覆蓋組成一組（稱(chēng)為覆蓋段），共享主存的同一個(gè)區(qū)域，從而解決在小的存儲(chǔ)空間中運(yùn)行大作業(yè)問(wèn)題。這種內(nèi)存擴(kuò)充技術(shù)就是覆蓋。,3 覆蓋技術(shù),對(duì)換與覆蓋技術(shù)的對(duì)比,覆蓋與對(duì)換技術(shù)是在多道程序環(huán)境下用來(lái)擴(kuò)充內(nèi)存的兩種方法

15、。覆蓋技術(shù)主要用在早期的OS中，而對(duì)換技術(shù)則主要用在現(xiàn)代OS中，解決在小的內(nèi)存空間運(yùn)行大作業(yè)的問(wèn)題，是“擴(kuò)充”內(nèi)存容量和提高內(nèi)存利用率的有效措施。對(duì)換技術(shù)不要求程序員給出程序段之間的覆蓋結(jié)構(gòu)，對(duì)換主要在作業(yè)或進(jìn)程之間進(jìn)行。,覆蓋技術(shù)要求程序員必須把一個(gè)程序劃分成不同的程序段，并規(guī)定好它們的執(zhí)行和覆蓋順序，操作系統(tǒng)根據(jù)程序員提供的覆蓋結(jié)構(gòu)來(lái)完成程序段之間的覆蓋。覆蓋技術(shù)主要在同一個(gè)作業(yè)或進(jìn)程中進(jìn)行，同時(shí)覆蓋只能覆蓋與覆蓋程序段無(wú)關(guān)的程