第3章存儲(chǔ)管理

第3章存儲(chǔ)管理分區(qū)式存儲(chǔ)管理分頁(yè)式存儲(chǔ)管理分段存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理引言內(nèi)存管理的需求內(nèi)存管理使用的技術(shù)分區(qū)式管理：固定式、可變式分區(qū)、多重分區(qū)頁(yè)式管理、段式管理段頁(yè)式管理OS的存儲(chǔ)管理機(jī)構(gòu)必須解決以下問題內(nèi)存分配存儲(chǔ)保護(hù)地址變換存儲(chǔ)共享存儲(chǔ)擴(kuò)充同時(shí)進(jìn)行多個(gè)任務(wù)編輯文檔運(yùn)行程序網(wǎng)上瀏覽CD音樂欣賞為多個(gè)程序安排內(nèi)存PCB1PCB2PCB3程序1程序2程序3數(shù)據(jù)程序進(jìn)程控制塊PCB采用內(nèi)存分配與管理技術(shù)：實(shí)存管理技術(shù)：分區(qū)式、分頁(yè)式、分段式、段頁(yè)式虛存管理技術(shù)：請(qǐng)求分頁(yè)式、請(qǐng)求分段式、請(qǐng)求段頁(yè)式OS

分配內(nèi)存程序1程序2程序33.1分區(qū)式存儲(chǔ)管理地址重定位靜態(tài)重定位動(dòng)態(tài)重定位固定式分區(qū)可變式分區(qū)多重分區(qū)覆蓋與交換可變分區(qū)分配和釋放算法

3.1地址重定位內(nèi)存儲(chǔ)器一般分為：系統(tǒng)區(qū)和用戶區(qū)程序的名字空間、地址空間及存儲(chǔ)空間符號(hào)源程序目標(biāo)代碼可執(zhí)行代碼匯編編譯連接地址重定位名字空間地址空間存儲(chǔ)空間:x=x+1::R=XR=R+1X=R:0:K

100:100+K:R=XR=R+1X=R:1.靜態(tài)重定位示意圖::LOAD1,300:5678:

01003004001000110013001400::LOAD1,1300:5678:

某程序的地址空間內(nèi)存2.動(dòng)態(tài)重定位示意圖1000110013001400

LOAD1,300

5678

內(nèi)存物理地址空間0100300400

LOAD1,300

5678某程序的邏輯地址空間1000+3.1.2固定分區(qū)和可變分區(qū)區(qū)號(hào)大小起始地址標(biāo)志123416K32K64K124K20K36K68K132K已分配已分配已分配未分配操作系統(tǒng)作業(yè)A作業(yè)C作業(yè)B020K36K68K132K第1分區(qū)第2分區(qū)第3分區(qū)第4分區(qū)(未分配)(b)內(nèi)存分配圖(a)分區(qū)說(shuō)明表1.固定分區(qū)分配2.可變分區(qū)說(shuō)明表序號(hào)P大小起址狀態(tài)18K20K已分配232K28K已分配3——空表目4120K92K已分配5——空表目…………已分配分區(qū)說(shuō)明

序號(hào)F大小起址狀態(tài)132K60K空閑2300K212K空閑3——空表目4——空表目5——空表目…………空閑分區(qū)說(shuō)明表

可變分區(qū)示例3.可變分區(qū)分配和釋放算法分配算法一般有：①最佳適應(yīng)（BestFit）算法，它從全部空閑區(qū)中找出能滿足作業(yè)需求的容量最小的空閑區(qū)分配之，此法的著眼點(diǎn)是使碎片盡量小。②最先適應(yīng)（FirstFit）算法，它按序查找，把最先找到的滿足需求的空閑區(qū)分配之，此法的目的在于盡量減少查找時(shí)間。③*最壞適應(yīng)（WorstFit）算法,此法的目的在于使剩下的空區(qū)最大，減少空區(qū)碎片機(jī)會(huì)。④*下次適應(yīng)算法（NextFit），此法將空閑區(qū)鏈成環(huán)形鏈，每次分配從上次分配的位置開始查找合適的空閑區(qū)。

可變分區(qū)的分配算法F=F+1置空閑區(qū)號(hào)F=1=Loc

F的起始地址置置F的狀態(tài)=空表目置置P的大小=Xk置P的始址=Loc置P的=已分配本次無(wú)法分配=申請(qǐng)分配一個(gè)xk大小的分區(qū)F已超出最大項(xiàng)號(hào)？F的狀態(tài)=空表目？F的大小

Xk?在已分配表中找一個(gè)狀態(tài)=空表目的序號(hào)P返回序號(hào)P否是是否否否大于等于F的大小

Xk=新空閑塊大小Loc+Xk=新起始地址回收示意圖空閑區(qū)F1程序區(qū)回收區(qū)R空閑區(qū)F1

空閑區(qū)F2程序區(qū)回收區(qū)R

空閑區(qū)F2程序程序回收區(qū)R

程序區(qū)程序區(qū)回收區(qū)R

空閑區(qū)F2程序區(qū)程序區(qū)回收區(qū)R可變分區(qū)的回收算法=置新空閑分區(qū)的大小=Size始址=Loc狀態(tài)=空閑在空閑分區(qū)表中置F2為空閑表目分區(qū)R與F1鄰接？分區(qū)R與F1鄰接？在空閑分區(qū)表中找一個(gè)空閑表目分區(qū)R與F2鄰接？Size

Size+F2的大小已分配區(qū)說(shuō)明表中置R的狀態(tài)=空表目Size

分區(qū)R的大小Loc

分區(qū)的起始地址否是是是否否請(qǐng)求回收分區(qū)R置空閑分區(qū)F2的大小=Size+F1的大小置空閑分區(qū)F2的大小=Size始址=Loc返回F13.1.3覆蓋與交換技術(shù)1.覆蓋技術(shù)所謂覆蓋，就是一個(gè)作業(yè)的若干程序段或幾個(gè)作業(yè)的某些部分共享某一段存儲(chǔ)空間覆蓋技術(shù)舉例A20KB50KF30KC30KD20KE40KRAMA20K覆蓋區(qū)050K覆蓋區(qū)140KBCFDE(a)作業(yè)模塊的調(diào)用結(jié)構(gòu)(b)存儲(chǔ)分配及覆蓋結(jié)構(gòu)2.交換技術(shù)所謂交換，就是允許把一個(gè)作業(yè)裝入內(nèi)存之后仍能把它交換出內(nèi)存或再交換入內(nèi)存。3.2分頁(yè)式存儲(chǔ)管理實(shí)存管理分頁(yè)原理頁(yè)表地址變換機(jī)構(gòu)虛存管理頁(yè)表的擴(kuò)充缺頁(yè)中斷處理頁(yè)面淘汰算法快表頁(yè)面共享分頁(yè)原理1、等分內(nèi)存2、建立頁(yè)表3、動(dòng)態(tài)地址轉(zhuǎn)換4、缺頁(yè)處理1、等分內(nèi)存（頁(yè)面和物理塊）將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的區(qū)域，稱為頁(yè)面或頁(yè)。從0開始編號(hào)。內(nèi)存空間也分成與頁(yè)相同大小的若干個(gè)存儲(chǔ)塊，或稱為物理塊或頁(yè)框（frame）,同樣為它們進(jìn)行編號(hào)(如圖4－11左、右兩邊所示)。以塊為單位將進(jìn)程中的若干個(gè)頁(yè)分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁(yè)經(jīng)常裝不滿一塊，而形成不可利用的碎片，稱為“頁(yè)內(nèi)碎片”。在分頁(yè)存儲(chǔ)管理方式中的地址結(jié)構(gòu)如下：位移量W又稱為頁(yè)內(nèi)地址問題：（1）每頁(yè)大小為？（2）地址空間中最多有？頁(yè)二、頁(yè)表

在分頁(yè)系統(tǒng)中，允許將進(jìn)程的每一頁(yè)離散地存儲(chǔ)在內(nèi)存的任一物理塊中，但系統(tǒng)應(yīng)能保證進(jìn)程的正確運(yùn)行，即能在內(nèi)存中找到每個(gè)頁(yè)面所對(duì)應(yīng)的物理塊。為此，系統(tǒng)又為每個(gè)進(jìn)程建立一張頁(yè)面映射表，簡(jiǎn)稱頁(yè)表。

頁(yè)表的作用：實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的映射。表項(xiàng)中常設(shè)有存儲(chǔ)控制字段一位：允許讀/寫只讀兩位：允許讀/寫只讀只執(zhí)行頁(yè)表的作用

頁(yè)表、存儲(chǔ)分塊表及其關(guān)系0000100000000000

頁(yè)內(nèi)地址

頁(yè)號(hào)相對(duì)頁(yè)號(hào)P頁(yè)內(nèi)地值D分頁(yè)原理0000010000000000

頁(yè)內(nèi)地址

頁(yè)號(hào)相對(duì)頁(yè)號(hào)P頁(yè)內(nèi)地值D頁(yè)表項(xiàng)頁(yè)表項(xiàng)區(qū)域PCB區(qū)域OS用戶區(qū)頁(yè)號(hào)物理塊號(hào)1025171220某作業(yè)頁(yè)表有效（虛地址）操作系統(tǒng)物理塊號(hào)特征頁(yè)號(hào)作業(yè)2頁(yè)表4528物理地址物理塊號(hào)頁(yè)表起始地址頁(yè)表長(zhǎng)度頁(yè)表始址寄存器頁(yè)號(hào)頁(yè)內(nèi)相對(duì)位移內(nèi)存8644外存LOAD1,25004522150地址變換過(guò)程請(qǐng)求分頁(yè)頁(yè)表頁(yè)號(hào)特征內(nèi)存塊號(hào)外存塊號(hào)修改位訪問位0 00 11 01 1淘汰優(yōu)先級(jí)01此頁(yè)不在內(nèi)存此頁(yè)在內(nèi)存缺頁(yè)中斷處理頁(yè)面淘汰算法先進(jìn)先出(FIFO)最近最久未使用淘汰算法(LRU)最近不頻繁使用淘汰算法(LFU)最優(yōu)算法(OPT)以上幾種淘汰算法中，F(xiàn)IFO算法最簡(jiǎn)單，但效率不高，有異常現(xiàn)象。LRU的近似算法和LFU是較為實(shí)用的算法，效果較好，實(shí)現(xiàn)也不難。OPT算法是一種最佳算法，但并不實(shí)用，因?yàn)橐櫢黜?yè)面方可預(yù)測(cè)未來(lái)。而這種預(yù)測(cè)往往是很困難的。FIFO異?，F(xiàn)象FIFO異?，F(xiàn)象FIFO異?，F(xiàn)象快表 序號(hào) 相對(duì)頁(yè)號(hào) 物理塊號(hào) 訪問過(guò) 特征位 0

1

2

3

m-1

快表地址映象快表的地址映象操作頁(yè)面共享共享的例程頁(yè)面共享的數(shù)據(jù)頁(yè)面...共享的歷程頁(yè)面作業(yè)1頁(yè)表作業(yè)2頁(yè)表作業(yè)1頁(yè)表作業(yè)2頁(yè)表公共頁(yè)表3.3段式管理段式地址結(jié)構(gòu)段號(hào)s段內(nèi)位移w3.3.1段式系統(tǒng)的特點(diǎn)3.3.2段式地址變換段號(hào)段內(nèi)地址sw長(zhǎng)度基址段表第s段b+wlb程序地址段式地址變換的步驟：1）取出程序地址(S,W)。2）用S檢索段表。3）如W<0或W>1則內(nèi)存越界。4)(b+w)即為所需內(nèi)存地址3.3.3擴(kuò)充段表功能段頁(yè)式管理作業(yè)地址空間和地址結(jié)構(gòu)主程序段子程序段數(shù)據(jù)段04K8K12K