第四章存儲(chǔ)管理

第4章

存儲(chǔ)管理教學(xué)內(nèi)容:1、程序的裝入和鏈接2、分區(qū)存儲(chǔ)管理方式3、虛擬存儲(chǔ)器的基本概念4、分頁(yè)存儲(chǔ)管理方式5、頁(yè)面置換算法6、分段存儲(chǔ)管理方式7、段頁(yè)存儲(chǔ)管理方式教學(xué)重點(diǎn):1、程序的裝入（地址空間、名字空間、物理空間、地址重定位）2、虛擬存儲(chǔ)器的基本概念3、分頁(yè)存儲(chǔ)管理方式4、頁(yè)面置換算法教學(xué)難點(diǎn):1、地址重定位2、分頁(yè)存儲(chǔ)管理方式3．頁(yè)面置換算法§4.1引言內(nèi)存管理的需求內(nèi)存管理使用的技術(shù)分區(qū)式管理：固定式、可變式分區(qū)、多重分區(qū)頁(yè)式管理、段式管理段頁(yè)式管理操作系統(tǒng)的存儲(chǔ)管理機(jī)構(gòu)必須解決以下問(wèn)題內(nèi)存分配存儲(chǔ)保護(hù)地址變換存儲(chǔ)共享存儲(chǔ)擴(kuò)充差距硬件無(wú)關(guān)、應(yīng)用相關(guān)用戶對(duì)內(nèi)存的使用要求硬件相關(guān)、應(yīng)用無(wú)關(guān)內(nèi)存硬件的使用特性操作系統(tǒng)內(nèi)存管理功能的工作范圍：一、主存管理二、存儲(chǔ)層次、性能指標(biāo)、主存作用1、存儲(chǔ)層次、性能指標(biāo)(容量、速度、存取頻度、成本)內(nèi)存寄存器外存容量小速度高存取頻度高成本高存儲(chǔ)器主存（內(nèi)存）輔存（外存）系統(tǒng)區(qū)（OS標(biāo)準(zhǔn)子程序）

用戶區(qū)（用戶程序、數(shù)據(jù)）2、主存作用中級(jí)對(duì)主存的性能要求:(1)主存速度要快到與CPU執(zhí)行指令的速度相匹配主存技術(shù)的實(shí)際發(fā)展由于技術(shù)原因和經(jīng)濟(jì)原因,速度趕不上CPU速度容量趕不上或勉強(qiáng)趕上應(yīng)用程序長(zhǎng)增長(zhǎng)(2)主存容量要大到能裝下當(dāng)前運(yùn)行的程序與數(shù)據(jù)(3)開(kāi)機(jī)上電時(shí)主存能一直正常工作保持穩(wěn)定可靠§4.2分區(qū)式存儲(chǔ)管理地址重定位靜態(tài)重定位動(dòng)態(tài)重定位固定式分區(qū)可變式分區(qū)多重分區(qū)覆蓋與交換可變分區(qū)分配和釋放算法為多個(gè)程序安排內(nèi)存PCB1PCB2PCB3程序1程序2程序3OS

分配內(nèi)存程序1程序2程序3名字空間:程序中符號(hào)名的集合地址空間:一個(gè)目標(biāo)程序所限定的地址范圍,通常把編譯程序形成的從0開(kāi)始編址的地址空間稱為作業(yè)的地址空間。每個(gè)可執(zhí)行程序都有一個(gè)自己的地址空間。存儲(chǔ)空間：是指主存中一系列存儲(chǔ)信息的物理單元的集合。這些單元的編號(hào)稱為物理地址或絕對(duì)地址、內(nèi)存地址。存儲(chǔ)空間的大小是由主存的實(shí)際容量決定的。存儲(chǔ)空間按字節(jié)編址，從0開(kāi)始，擴(kuò)展到系統(tǒng)配置可用的最大數(shù)量。32位計(jì)算機(jī)的內(nèi)存空間最大值？地址空間是邏輯地址的集合。存儲(chǔ)空間是物理地址的集合一個(gè)是虛的概念，一個(gè)是實(shí)的物體。程序的名字空間、地址空間及存儲(chǔ)空間符號(hào)源程序目標(biāo)代碼可執(zhí)行代碼匯編編譯連接地址重定位名字空間*.C地址空間*.OBJ存儲(chǔ)空間*.EXE:x=x+1::R=XR=R+1X=R:0:K100:100+K:R=XR=R+1X=R:地址重定位:地址空間中使用的邏輯地址變換成主存空間中的物理地址的過(guò)程。物理（實(shí)際）地址=相對(duì)（邏輯）地址+定位地址

虛擬空間

內(nèi)存空間12345LoadA,500

0：100：500：800：

1000：0+1000123451500：500+10001800：800+1000LoadA,15001100：100+1000………靜態(tài)地址重定位裝入一個(gè)作業(yè)時(shí)，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對(duì)地址（地址轉(zhuǎn)換工作在作業(yè)執(zhí)行前集中一次完成）在作業(yè)執(zhí)行過(guò)程中無(wú)須再進(jìn)行地址轉(zhuǎn)換工作。優(yōu)點(diǎn)：加快作業(yè)的運(yùn)行速度。缺點(diǎn)：作業(yè)一旦被裝入內(nèi)存，不允許再移動(dòng)；程序的存儲(chǔ)空間連續(xù)。動(dòng)態(tài)地址重定位：動(dòng)態(tài)地址重地位是在程序執(zhí)行過(guò)程中，在cpu訪問(wèn)內(nèi)存之前,將要訪問(wèn)的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址.動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。

虛擬空間

內(nèi)存空間12345LoadA,500

0：100：500：1000

1500：

BRLoadA,15001000：1100：12345LoadA,500

優(yōu)點(diǎn)：（1）目標(biāo)?？觳患有薷亩b入內(nèi)存（2）一個(gè)程序有若干個(gè)相對(duì)獨(dú)立的目標(biāo)組成時(shí)，各目標(biāo)?？煅b入內(nèi)存的存儲(chǔ)區(qū)不必相連600：1600：實(shí)際地址-相對(duì)地址:1000-0+

VR500程序在其生命周期各階段表現(xiàn)出的地址形式（1）編譯或匯編階段

編譯兩個(gè)轉(zhuǎn)換:將語(yǔ)句轉(zhuǎn)換為機(jī)器指令將符號(hào)轉(zhuǎn)換為內(nèi)存地址注意:1.轉(zhuǎn)換出的地址可能是相對(duì)地址2.可能不是所有符號(hào)都已轉(zhuǎn)換為內(nèi)存地址（2）連接階段(可執(zhí)行目標(biāo)程序)

a.統(tǒng)一各目標(biāo)程序中的相對(duì)地址為該程序的相對(duì)地址b.符號(hào)地址內(nèi)存地址（相對(duì)地址）（3）裝入階段

可能需要重定位（4）執(zhí)行階段可能需要重定位（5）釋放空間以二進(jìn)制文件駐流在硬盤上一、分區(qū)式存儲(chǔ)管理將內(nèi)存劃分成若干個(gè)連續(xù)的區(qū)域，每個(gè)分區(qū)只能存儲(chǔ)一個(gè)程序。缺點(diǎn)：內(nèi)存不能充分利用、內(nèi)存不能擴(kuò)充二、固定分區(qū)分配

運(yùn)行其間不再劃分。內(nèi)存利用率不高區(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ō)明表可

變

分

區(qū)

示

例三、可變分區(qū)分配

分區(qū)的個(gè)數(shù)大小不是固定不變、分區(qū)根據(jù)裝入的作業(yè)動(dòng)態(tài)劃分可變分區(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ū)分配和釋放算法分配算法一般有：①最佳適應(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)形鏈，每次分配從上次分配的位置開(kāi)始查找合適的空閑區(qū)。

可變分區(qū)的分配算法F=F+1置空閑區(qū)號(hào)F=1=LocF的起始地址置置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鄰接？SizeSize+F2的大小已分配區(qū)說(shuō)明表中置R的狀態(tài)=空表目Size分區(qū)R的大小Loc分區(qū)的起始地址否是是是否否請(qǐng)求回收分區(qū)R置空閑分區(qū)F2的大小=Size+F1的大小置空閑分區(qū)F2的大小=Size始址=Loc返回F1四、多重分區(qū)基址寄存器1作業(yè)1作業(yè)1OS限長(zhǎng)寄存器1基址寄存器2限長(zhǎng)寄存器2提出背景：大程序、小空間解決方法：按需裝入數(shù)據(jù)，不同時(shí)刻執(zhí)行的代碼或數(shù)據(jù)相互覆蓋、需要事先確定所有代碼和數(shù)據(jù)的位置（相互覆蓋位置）五、覆蓋技術(shù)覆蓋技術(shù)舉例A20KB50KF30KC30KD20KE40KRAMA20K覆蓋區(qū)050K覆蓋區(qū)140KBCFDE對(duì)覆蓋的認(rèn)識(shí)（1）覆蓋由操作系統(tǒng)自動(dòng)化完成，但要求作業(yè)各模塊間有明確的調(diào)用結(jié)構(gòu)，程序員必須正確設(shè)計(jì)覆蓋結(jié)構(gòu)和編程，任務(wù)繁重（2）額外的I/O操作覆蓋通常限于用在微機(jī)和其他內(nèi)存容量有限的或缺乏對(duì)更先進(jìn)技術(shù)的硬件支持的系統(tǒng)中交換（swap）技術(shù)：發(fā)生進(jìn)程切換時(shí)，總是把當(dāng)前進(jìn)程的所有代碼、數(shù)據(jù)、棧全部從內(nèi)存復(fù)制至外存，再把新當(dāng)前進(jìn)程的所有代碼、數(shù)據(jù)、棧全部從外存復(fù)制至內(nèi)存。盤交換區(qū)：在外存中用于存放所有換出進(jìn)程的代碼、數(shù)據(jù)、棧。六、交換技術(shù)交換技術(shù)中的五個(gè)問(wèn)題:1.將哪個(gè)進(jìn)程換出(入)內(nèi)存?2.何時(shí)應(yīng)發(fā)生交換?3.交換時(shí)需要做那些工作?4.換回位置的確定原則5.交換所需時(shí)間導(dǎo)致對(duì)時(shí)間片的影響、對(duì)程序長(zhǎng)度保存使用要求、動(dòng)態(tài)擴(kuò)充時(shí)要及時(shí)登記的管理要求§4.3分頁(yè)式存儲(chǔ)管理實(shí)存管理分頁(yè)原理頁(yè)表地址變換機(jī)構(gòu)虛存管理頁(yè)表的擴(kuò)充缺頁(yè)中斷處理頁(yè)面淘汰算法快表頁(yè)面共享一、分頁(yè)原理1、等分內(nèi)存2、等分地址空間3、地址形式4、頁(yè)面尺寸:512-8KB0000010000000000

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

頁(yè)號(hào)相對(duì)頁(yè)號(hào)P頁(yè)內(nèi)地值D物理塊號(hào)頁(yè)號(hào)二、建立頁(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ò)程2023/2/4思考1：對(duì)指令LOADA5000進(jìn)行地址重定位（頁(yè)面長(zhǎng)1K；頁(yè)表中頁(yè)面對(duì)應(yīng)關(guān)系為0-1、1-3、2-4、3-6、4-7、5-8、6-9）。思考2：

對(duì)指令LOADA5000進(jìn)行地址重定位（頁(yè)面長(zhǎng)2K；頁(yè)表中頁(yè)面對(duì)應(yīng)關(guān)系為0-1、1-3、2-4、3-6、4-7、5-8、6-9）。請(qǐng)求分頁(yè)頁(yè)表頁(yè)號(hào)特征內(nèi)存塊號(hào)外存塊號(hào)修改位訪問(wèn)位0 00 11 01 1淘汰優(yōu)先級(jí)01此頁(yè)不在內(nèi)存此頁(yè)在內(nèi)存Linux頁(yè)表項(xiàng)定義缺頁(yè)中斷處理四、缺頁(yè)處理產(chǎn)生原因：當(dāng)前要執(zhí)行的頁(yè)信息不在主存中調(diào)用過(guò)程：文件系統(tǒng)管理設(shè)備管理進(jìn)程狀態(tài)地轉(zhuǎn)換缺頁(yè)中斷處理過(guò)程頁(yè)表

相對(duì)頁(yè)號(hào)

物理塊號(hào)

特征位

外存地址

0

1

2

3

m-1

存放位置、頁(yè)表始址寄存器（當(dāng)前運(yùn)行用戶程序的頁(yè)表始址）快表 序號(hào) 相對(duì)頁(yè)號(hào) 物理塊號(hào) 訪問(wèn)過(guò) 特征位 0

1

2

3

m-1

快表地址映象35805628快表的地址映象操作

五、頁(yè)面交換1、調(diào)頁(yè)方式請(qǐng)調(diào)：動(dòng)態(tài)地址變換機(jī)構(gòu)產(chǎn)生一個(gè)缺頁(yè)中斷信號(hào)，OS接到信號(hào)后調(diào)用缺頁(yè)中斷處理程序。預(yù)調(diào)：按照某種算法，預(yù)測(cè)不久將要用到的頁(yè)面并預(yù)先調(diào)入內(nèi)存待用。2、淘汰時(shí)機(jī)設(shè)置空閑臨界量3、淘汰算法

抖動(dòng)：頻繁進(jìn)行頁(yè)面調(diào)度，造成系統(tǒng)效率下降。頁(yè)面淘汰算法先進(jìn)先出(FIFO)最近最久未使用淘汰算法(LRU)最近不頻繁使用淘汰算法(LFU)最優(yōu)算法(OPT)以上幾種淘汰算法中，F(xiàn)IFO算法最簡(jiǎn)單，但效率不高，有異?，F(xiàn)象。LRU的近似算法和LFU是較為實(shí)用的算法，效果較好，實(shí)現(xiàn)也不難。OPT算法是一種最佳算法，但并不實(shí)用，因?yàn)橐櫢黜?yè)面方可預(yù)測(cè)未來(lái)。而這種預(yù)測(cè)往往是很困難的。目的：減少頁(yè)面交換次數(shù)，節(jié)約處理機(jī)時(shí)間其他補(bǔ)救措施：1、在內(nèi)存中的頁(yè)若未被修改則在被淘汰時(shí)不必寫(xiě)回外存2、預(yù)淘汰方式，內(nèi)存保留少量空頁(yè)，減少延遲時(shí)間3、優(yōu)化訪問(wèn)磁盤次序頁(yè)式存儲(chǔ)管理的保護(hù)措施：1、程序隔離：頁(yè)面映像方法2、頁(yè)面的存取控制：在頁(yè)表中設(shè)置一個(gè)保護(hù)位2023/2/4思考3：

采用先進(jìn)先出頁(yè)面淘汰算法的系統(tǒng)中，一進(jìn)程在內(nèi)存占4塊，頁(yè)面訪問(wèn)序列為1、2、3、4、1、2、5、1、2、3、4、5、6、。運(yùn)行時(shí)會(huì)產(chǎn)生()次缺頁(yè)中斷?！?.4分段存儲(chǔ)管理一、原因:

(1)分區(qū)容易出現(xiàn)碎片(固定、動(dòng)態(tài))

(2)分頁(yè)是利用率不高頁(yè)式系統(tǒng)中一頁(yè)或頁(yè)號(hào)相連的幾個(gè)邏輯頁(yè)上存放的內(nèi)容一般不是一個(gè)邏輯意義完整的信息單位，請(qǐng)調(diào)一頁(yè)時(shí)可能只用到一部分內(nèi)容。

段式地址結(jié)構(gòu)段號(hào)s段內(nèi)位移w分段地址空間:段表:二、段式地址變換段號(hào)段內(nèi)地址sw長(zhǎng)度基址段表第s段b+wl