第4章

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

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

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

虛擬空間

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

0：100：500：800：

1000：0+1000123451500：500+10001800：800+1000LoadA,15001100：100+1000………靜態(tài)地址重定位裝入一個作業(yè)時，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對地址（地址轉(zhuǎn)換工作在作業(yè)執(zhí)行前集中一次完成）在作業(yè)執(zhí)行過程中無須再進(jìn)行地址轉(zhuǎn)換工作。優(yōu)點(diǎn)：加快作業(yè)的運(yùn)行速度。缺點(diǎn)：作業(yè)一旦被裝入內(nèi)存，不允許再移動；程序的存儲空間連續(xù)。動態(tài)地址重定位：動態(tài)地址重地位是在程序執(zhí)行過程中，在cpu訪問內(nèi)存之前,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址.動態(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)模快不加修改而裝入內(nèi)存（2）一個程序有若干個相對獨(dú)立的目標(biāo)組成時，各目標(biāo)模快裝入內(nèi)存的存儲區(qū)不必相連600：1600：實(shí)際地址-相對地址:1000-0+

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

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

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

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

運(yùn)行其間不再劃分。內(nèi)存利用率不高區(qū)號大小起始地址標(biāo)志123416K32K64K124K20K36K68K132K已分配已分配已分配未分配操作系統(tǒng)作業(yè)A作業(yè)C作業(yè)B020K36K68K132K第1分區(qū)第2分區(qū)第3分區(qū)第4分區(qū)（未分配）（b）內(nèi)存分配圖（a）分區(qū)說明表可

變

分

區(qū)

示

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

分區(qū)的個數(shù)大小不是固定不變、分區(qū)根據(jù)裝入的作業(yè)動態(tài)劃分可變分區(qū)說明表序號P大小起址狀態(tài)18K20K已分配232K28K已分配3——空表目4120K92K已分配5——空表目…………已分配分區(qū)說明

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

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

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

頁內(nèi)地址

頁號相對頁號P頁內(nèi)地值D物理塊號頁號二、建立頁表有效（虛地址）操作系統(tǒng)物理塊號特征頁號作業(yè)2頁表4528物理地址物理塊號頁表起始地址頁表長度頁表始址寄存器頁號頁內(nèi)相對位移內(nèi)存8644外存LOAD1,25004522150三、地址變換過程2023/2/4思考1：對指令LOADA5000進(jìn)行地址重定位（頁面長1K；頁表中頁面對應(yīng)關(guān)系為0-1、1-3、2-4、3-6、4-7、5-8、6-9）。思考2：

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

相對頁號

物理塊號

特征位

外存地址

0

1

2

3

m-1

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

1

2

3

m-1

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

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

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

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

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

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

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