第3章存儲管理

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

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

3.1地址重定位內(nèi)存儲器一般分為：系統(tǒng)區(qū)和用戶區(qū)程序的名字空間、地址空間及存儲空間符號源程序目標代碼可執(zhí)行代碼匯編編譯連接地址重定位名字空間地址空間存儲空間: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.動態(tài)重定位示意圖1000110013001400

LOAD1,300

5678

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

LOAD1,300

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

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

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

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

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

Xk?在已分配表中找一個狀態(tài)=空表目的序號P返回序號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ū)表中找一個空閑表目分區(qū)R與F2鄰接？Size

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

分區(qū)R的大小Loc

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

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

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

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

頁內(nèi)地址

頁號相對頁號P頁內(nèi)地值D分頁原理0000010000000000

頁內(nèi)地址

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

1

2

3

m-1

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