第四章存儲管理

1、第第4 4章章 存儲管理存儲管理教學內(nèi)容教學內(nèi)容:1、程序的裝入和鏈接、程序的裝入和鏈接2、分區(qū)存儲管理方式、分區(qū)存儲管理方式3、虛擬存儲器的基本概念、虛擬存儲器的基本概念4、分頁存儲管理方式、分頁存儲管理方式5、頁面置換算法、頁面置換算法6、分段存儲管理方式、分段存儲管理方式7、段頁存儲管理方式、段頁存儲管理方式教學重點教學重點:1、程序的裝入（地址空間、名字空間、物理空間、地址重定位）、程序的裝入（地址空間、名字空間、物理空間、地址重定位）2、虛擬存儲器的基本概念、虛擬存儲器的基本概念3、分頁存儲管理方式、分頁存儲管理方式4、頁面置換算法、頁面置換算法教學難點教學難點:1、地址重定位、地址

2、重定位2、分頁存儲管理方式、分頁存儲管理方式3頁面置換算法頁面置換算法4.1 4.1 引言引言l 內(nèi)存管理的需求內(nèi)存管理的需求l 內(nèi)存管理使用的技術內(nèi)存管理使用的技術+ 分區(qū)式管理：固定式、可變式分區(qū)、多重分區(qū)分區(qū)式管理：固定式、可變式分區(qū)、多重分區(qū)+ 頁式管理、頁式管理、+ 段式管理段式管理+ 段頁式管理段頁式管理l 操作系統(tǒng)的存儲管理機構(gòu)必須解決以下問題操作系統(tǒng)的存儲管理機構(gòu)必須解決以下問題+ 內(nèi)存分配內(nèi)存分配+ 存儲保護存儲保護+ 地址變換地址變換+ 存儲共享存儲共享+ 存儲擴充存儲擴充差距差距硬件無關、應用相關硬件無關、應用相關用戶對內(nèi)存的使用要求用戶對內(nèi)存的使用要求硬件相關、應用無關

3、硬件相關、應用無關內(nèi)存硬件的使用特性內(nèi)存硬件的使用特性操作系統(tǒng)內(nèi)存管理功能的工作范圍：操作系統(tǒng)內(nèi)存管理功能的工作范圍：一、主存管理一、主存管理二、存儲層次、性能指標、主存作用二、存儲層次、性能指標、主存作用 1、存儲層次、存儲層次、性能指標性能指標( (容量、速度、存取頻度、成本容量、速度、存取頻度、成本) ) 內(nèi)存 寄存器 外存容量小速度高 存取頻度高 成本高存儲器主存（內(nèi)存）輔存（外存）系統(tǒng)區(qū)（OS標準子程序） 用戶區(qū)（用戶程序、數(shù)據(jù)）2、主存作用、主存作用中中級級對主存的性能要求:(1)主存速度要快到與CPU執(zhí)行指令的速度相匹配主存技術的實際發(fā)展由于技術原因和經(jīng)濟原因,速度趕不上CPU速

4、度容量趕不上或勉強趕上應用程序長增長(2)主存容量要大到能裝下當前運行的程序與數(shù)據(jù)(3)開機上電時主存能一 直正常工作保持穩(wěn)定可靠4.2 4.2 分區(qū)式存儲管理分區(qū)式存儲管理l 地址重定位地址重定位+ 靜態(tài)重定位靜態(tài)重定位+ 動態(tài)重定位動態(tài)重定位l 固定式分區(qū)固定式分區(qū)l 可變式分區(qū)可變式分區(qū)l 多重分區(qū)多重分區(qū)l 覆蓋與交換覆蓋與交換l 可變分區(qū)分配和釋放算法可變分區(qū)分配和釋放算法為多個程序安排內(nèi)存為多個程序安排內(nèi)存PCB1PCB2PCB3程序1程序2程序3 OS 分配內(nèi)存程序1程序2程序3名字空間名字空間:程序中符號名的集合地址空間地址空間:一個目標程序所限定的地址范圍, 通常把編譯程序形

5、成的從0開始編址的地址空間稱為作業(yè)的地址空間。每個可執(zhí)行程序都有一個自己的地址空間。存儲空間：存儲空間：是指主存中一系列存儲信息的物理單元的集合。這些單元的編號稱為物理地址或絕對地址、內(nèi)存地址。存儲空間的大小是由主存的實際存儲空間的大小是由主存的實際容量決定的。容量決定的。存儲空間按字節(jié)編址，從0開始，擴展到系統(tǒng)配置可用的最大數(shù)量。32位計算機的內(nèi)存空間最大值？地址空間是邏輯地址的集合。存儲空間是物理地址的集合一個是虛的概念，一個是實的物體。程序的名字空間、地址空間及存儲空間符號符號源程序源程序目標目標代碼代碼可執(zhí)行可執(zhí)行代碼代碼匯編匯編編譯編譯連接連接地址重定位地址重定位名 字 空 間名 字

6、 空 間*.C地址空間地址空間*.OBJ存儲空間存儲空間*.EXE:x=x+1:R=XR=R+1X=R:0:K100:100+K:R=XR=R+1X=R:地址重定位地址重定位: :地址空間中使用的邏輯地址變換成主存空間中的物理地址的過程。物理（實際）地址=相對（邏輯）地址+定位地址 虛擬空間虛擬空間 內(nèi)存空間內(nèi)存空間 12345Load A,500 0：100：500：800： 1000：0+1000 123451500：500+10001800：800+1000Load A,150015001100：100+1000靜態(tài)地址重定位靜態(tài)地址重定位 裝入一個作業(yè)時，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕

7、對地址（地址轉(zhuǎn)換工作在作業(yè)執(zhí)行前集中一次完成）在作業(yè)執(zhí)行過程中無須再進行地址轉(zhuǎn)換工作。優(yōu)點：加快作業(yè)的運行速度。缺點：作業(yè)一旦被裝入內(nèi)存，不允許再移動；程序的存儲空間連續(xù)。動態(tài)地址重定位：動態(tài)地址重定位： 動態(tài)地址重地位是在程序執(zhí)行過程中，在cpu訪問內(nèi)存之前,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址. 動態(tài)重定位依靠硬件地址變換機構(gòu)完成。 虛擬空間虛擬空間 內(nèi)存空間內(nèi)存空間 12345Load A,500 0：100：500：1000 1500： BRLoad A,15001000：1100： 12345Load A,500500 優(yōu)點：（1）目標模快不加修改而裝入內(nèi)存（2）一個程序有若干個相

8、對獨立的目標組成時，各目標模快裝入內(nèi)存的存儲區(qū)不必相連600：1600：實際地址-相對地址:1000-0+ VR500程序在其生命周期各階段表現(xiàn)出的地址形式程序在其生命周期各階段表現(xiàn)出的地址形式（1）編譯或匯編階段 n編譯u 兩個轉(zhuǎn)換:F將語句轉(zhuǎn)換為機器指令F將符號轉(zhuǎn)換為內(nèi)存地址u注意:1.轉(zhuǎn)換出的地址可能是相對地址2.可能不是所有符號都已轉(zhuǎn)換為內(nèi)存地址（2）連接階段(可執(zhí)行目標程序) a.統(tǒng)一各目標程序中的相對地址為該程序的相對地址 b.符號地址 內(nèi)存地址（相對地址）（3）裝入階段 可能需要重定位可能需要重定位（4）執(zhí)行階段 可能需要重定位可能需要重定位（5）釋放空間 以二進制文件駐流在硬盤

9、上一、一、分區(qū)式存儲管理分區(qū)式存儲管理將內(nèi)存劃分成若干個連續(xù)的區(qū)域，每個分區(qū)只能存儲一個程序。缺點：內(nèi)存不能充分利用、內(nèi)存不能擴充二、固定分區(qū)分配二、固定分區(qū)分配 運行其間不再劃分。內(nèi)存利用率不高區(qū)號區(qū)號大小大小起始地址起始地址標志標志123416K32K64K124K20K36K68K132K已分配已分配已分配已分配已分配已分配未分配未分配操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A作業(yè)作業(yè)C作業(yè)作業(yè)B020K36K68K132K第第1分區(qū)分區(qū)第第2分區(qū)分區(qū)第第3分區(qū)分區(qū)第第4分區(qū)分區(qū)（未分配）（未分配）（b） 內(nèi)存分配內(nèi)存分配圖圖（a） 分區(qū)說明表分區(qū)說明表可可變變分分區(qū)區(qū)示示例例三、可變分區(qū)分配三、可變分

10、區(qū)分配 分區(qū)的個數(shù)大小不是固定不變、分區(qū)根據(jù)裝入的作業(yè)動態(tài)劃分可變分區(qū)說明表可變分區(qū)說明表序號序號P P大小大小起址起址狀態(tài)狀態(tài)1 18 8K K2020K K已分配已分配2 23232K K2828K K已分配已分配3 3空表目空表目4 4120120K K9292K K已分配已分配5 5空表目空表目已分配分區(qū)說明已分配分區(qū)說明 序號序號F大小大小起址起址狀態(tài)狀態(tài)132K60K空閑空閑2300K212K空閑空閑3空表目空表目4空表目空表目5空表目空表目空閑分區(qū)說明表空閑分區(qū)說明表 可變分區(qū)分配和釋放算法可變分區(qū)分配和釋放算法分配算法一般有：最佳適應（Best Fit）算法，它從全部空閑區(qū)中找

11、出能滿足作業(yè)需求的容量最小的空閑區(qū)分配之，此法的著眼點是使碎片盡量小。最先適應（First Fit）算法，它按序查找，把最先找到的滿足需求的空閑區(qū)分配之，此法的目的在于盡量減少查找時間。最壞適應（Worst Fit）算法,此法的目的在于使剩下的空區(qū)最大，減少空區(qū)碎片機會。下次適應算法（Next Fit），此法將空閑區(qū)鏈成環(huán)形鏈，每次分配從上次分配的位置開始查找合適的空閑區(qū)。 可變分區(qū)的分配算法可變分區(qū)的分配算法F=F+1置空閑區(qū)號置空閑區(qū)號F =1=LocF的起始地址的起始地址置置置置F的狀態(tài)的狀態(tài)=空表目空表目置置置置P的大小的大小=Xk置置P的始址的始址=Loc置置P的的=已分配已分配本次

12、無法分配本次無法分配=申請分配一個申請分配一個xk大小的分區(qū)大小的分區(qū)F 已超出最大項號？已超出最大項號？F 的狀態(tài)的狀態(tài)=空表目？空表目？F的大小的大小 Xk?在已分配表中找一個在已分配表中找一個狀態(tài)狀態(tài)=空表目的序號空表目的序號P返回序號返回序號P否否是是是是否否否否否否大于大于等于等于F的大小的大小 Xk=新空閑塊大小新空閑塊大小Loc+Xk=新起始地址新起始地址回收示意圖回收示意圖空閑區(qū)空閑區(qū)F1程序區(qū)程序區(qū)回收區(qū)回收區(qū)R空閑區(qū)空閑區(qū)F1 空閑區(qū)空閑區(qū)F2程序區(qū)程序區(qū)回收區(qū)回收區(qū)R 空閑區(qū)空閑區(qū)F2程序程序程序程序回收區(qū)回收區(qū)R 程序區(qū)程序區(qū)程序區(qū)程序區(qū)回收區(qū)回收區(qū)R 空閑區(qū)空閑區(qū)F2

13、程序區(qū)程序區(qū)程序區(qū)程序區(qū)回收區(qū)回收區(qū)R可變分區(qū)的回收算法可變分區(qū)的回收算法=置新空閑分區(qū)的置新空閑分區(qū)的大小大小=Size始址始址=Loc狀態(tài)狀態(tài)=空閑空閑在空閑分區(qū)表中置在空閑分區(qū)表中置F2為空閑表目為空閑表目分區(qū)分區(qū)R與與F1鄰接？鄰接？分區(qū)分區(qū)R與與F1鄰接？鄰接？在空閑分區(qū)表中在空閑分區(qū)表中找一個空閑表目找一個空閑表目分區(qū)分區(qū)R與與F2鄰接？鄰接？SizeSize+ F2的大小的大小已分配區(qū)說明表中已分配區(qū)說明表中置置R的狀態(tài)的狀態(tài) = 空表目空表目Size分區(qū)分區(qū)R的大小的大小Loc分區(qū)的起始地址分區(qū)的起始地址否否是是是是是是否否否否請求回收分區(qū)請求回收分區(qū)R置空閑分區(qū)置空閑分區(qū)F

14、F2 2的大小的大小 =Size+ F1的大小的大小置空閑分區(qū)置空閑分區(qū)F2的的大小大小=Size始址始址=Loc返回返回F F1 1四、多重分區(qū)四、多重分區(qū)基址寄存器基址寄存器1作業(yè)作業(yè)1作業(yè)作業(yè)1OS限長寄存器限長寄存器1基址寄存器基址寄存器2限長寄存器限長寄存器2提出背景：大程序、小空間解決方法：按需裝入數(shù)據(jù)，按需裝入數(shù)據(jù)，不同時刻執(zhí)行的代碼或數(shù)據(jù)相互覆蓋、需要事先確定所有代碼和數(shù)據(jù)的位置（相互覆蓋位置）五、覆蓋技術五、覆蓋技術覆蓋技術舉例覆蓋技術舉例A 20KB 50KF 30KC 30KD 20KE 40KRAMA 20K覆蓋區(qū)覆蓋區(qū)0 50K覆蓋區(qū)覆蓋區(qū)1 40KBCFDE對覆蓋的

15、認識對覆蓋的認識（1）覆蓋由操作系統(tǒng)自動化完成，但要求作業(yè)各模塊間有 明確的調(diào)用結(jié)構(gòu)，程序員必須正確設計覆蓋結(jié)構(gòu)和編程， 任務繁重（2）額外的I/O操作 覆蓋通常限于用在微機和其他內(nèi)存容量有限的或缺乏對更 先進技術的硬件支持的系統(tǒng)中交換（swap）技術：發(fā)生進程切換時，總是把當前進程的所有代碼、數(shù)據(jù)、棧全部從內(nèi)存復制至外存，再把新當前進程的所有代碼、數(shù)據(jù)、棧全部從外存復制至內(nèi)存。盤交換區(qū)：在外存外存中用于存放所有換出進程的代碼、數(shù)據(jù)、棧。六、交換技術六、交換技術交換技術中的五個問題交換技術中的五個問題:1.將哪個進程換出(入)內(nèi)存?2.何時應發(fā)生交換?3.交換時需要做那些工作?4.換回位置的確

16、定原則5.交換所需時間導致對時間片的影響、對程序長度保存使用要求、動態(tài)擴充時要及時登記的管理要求4.3 4.3 分頁式存儲管理分頁式存儲管理l實存管理實存管理+ 分頁原理分頁原理+ 頁表頁表+ 地址變換機構(gòu)地址變換機構(gòu)l虛存管理虛存管理+ 頁表的擴充頁表的擴充+ 缺頁中斷處理缺頁中斷處理+ 頁面淘汰算法頁面淘汰算法+ 快表快表+ 頁面共享頁面共享一、分頁原理一、分頁原理1、等分內(nèi)存、等分內(nèi)存2、等分地址空間、等分地址空間3、地址形式、地址形式4、頁面尺寸、頁面尺寸:512-8KB0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 頁內(nèi)地址頁內(nèi)地址 頁號頁號相對頁號相對頁號P頁內(nèi)地值頁

17、內(nèi)地值D物理塊號物理塊號頁號頁號二、建立頁表二、建立頁表有效（虛地址）有效（虛地址）操作系統(tǒng)操作系統(tǒng)物理塊號物理塊號特征特征頁號頁號作業(yè)作業(yè)2頁表頁表4528物理地址物理地址物理塊號物理塊號頁表起始地址頁表起始地址頁表長度頁表長度頁表始址寄存器頁表始址寄存器頁號頁號頁內(nèi)相對位移頁內(nèi)相對位移內(nèi)存內(nèi)存8644外存外存LOAD 1,25004522150三、地址變換過程三、地址變換過程2022/2/20思考思考1 1： 對指令對指令LOAD A 5000LOAD A 5000進行地址重定位（頁面長進行地址重定位（頁面長1K1K；頁表中頁面對應關系為；頁表中頁面對應關系為0-10-1、1-31-3、2

18、-42-4、3-63-6、4-74-7、5-85-8、6-96-9）。）。思考思考2 2： 對指令對指令LOAD A 5000LOAD A 5000進行地址重定位（頁面長進行地址重定位（頁面長2K2K；頁表中頁面對應關系為；頁表中頁面對應關系為0-10-1、1-31-3、2-42-4、3-63-6、4-74-7、5-85-8、6-96-9）。）。請求分頁頁表請求分頁頁表頁號特征內(nèi)存塊號外存塊號修改位 訪問位0 0 011011淘汰優(yōu)先級0 1此頁不在內(nèi)存此頁在內(nèi)存Linux頁表項定義頁表項定義缺缺頁頁中中斷斷處處理理四、缺頁處理四、缺頁處理產(chǎn)生原因：產(chǎn)生原因： 當前要執(zhí)行的頁信息不在主存中當前

19、要執(zhí)行的頁信息不在主存中調(diào)用過程：調(diào)用過程： 文件系統(tǒng)管理文件系統(tǒng)管理 設備管理設備管理 進程狀態(tài)地轉(zhuǎn)換進程狀態(tài)地轉(zhuǎn)換 缺頁缺頁中斷處理中斷處理過程過程頁表頁表相對頁號物理塊號特征位外存地址0123m-1存放位置、頁表始址寄存器（當前運行用戶程序的頁表始址）存放位置、頁表始址寄存器（當前運行用戶程序的頁表始址）快表快表序號相對頁號物理塊號訪問過特征位0123m-1快表地址映象快表地址映象35805628快表的地址映象操作快表的地址映象操作 五、頁面交換五、頁面交換1、調(diào)頁方式 請調(diào)：動態(tài)地址變換機構(gòu)產(chǎn)生一個缺頁中斷信號，OS接到信號后調(diào)用缺頁中斷處理程序。 預調(diào)：按照某種算法，預測不久將要用到

20、的頁面并預先調(diào)入內(nèi)存待用。2、淘汰時機 設置空閑臨界量3、淘汰算法 抖動：頻繁進行頁面調(diào)度，造成系統(tǒng)效率下降。頁面淘汰算法頁面淘汰算法l先進先出(FIFO)l最近最久未使用淘汰算法(LRU)l最近不頻繁使用淘汰算法(LFU)l最優(yōu)算法(OPT) 以上幾種淘汰算法中，F(xiàn)IFO算法最簡單，但效率不高，有異常現(xiàn)象。LRU的近似算法和LFU是較為實用的算法，效果較好，實現(xiàn)也不難。OPT算法是一種最佳算法，但并不實用，因為要跟蹤各頁面方可預測未來。而這種預測往往是很困難的。目的：減少頁面交換次數(shù)，節(jié)約處理機時間其他補救措施：1、在內(nèi)存中的頁若未被修改則在被淘汰時不必寫回外存2、預淘汰方式，內(nèi)存保留少量空

21、頁，減少延遲時間3、優(yōu)化訪問磁盤次序頁式存儲管理的保護措施：1、程序隔離：頁面映像方法2、頁面的存取控制：在頁表中設置一個保護位2022/2/20思考思考3 3： 采用先進先出頁面淘汰算法的系統(tǒng)中，采用先進先出頁面淘汰算法的系統(tǒng)中，一進程在內(nèi)存占一進程在內(nèi)存占4 4塊，頁面訪問序列為塊，頁面訪問序列為1 1、2 2、3 3、4 4、1 1、2 2、5 5、1 1、2 2、3 3、4 4、5 5、6 6、。運行、。運行時會產(chǎn)生時會產(chǎn)生( )( )次缺頁中斷。次缺頁中斷。4.4 4.4 分段存儲管理分段存儲管理一、原因一、原因: (1)分區(qū)容易出現(xiàn)碎片分區(qū)容易出現(xiàn)碎片(固定、動態(tài)固定、動態(tài)) (2)分頁是利用率不高分頁是利用率不高 頁式系統(tǒng)中一頁或頁號相連的幾個邏輯頁上存頁式系統(tǒng)中一頁或頁號相連的幾個邏輯頁上存放的內(nèi)容一般不是一個邏輯意義完整的信息單位，放的內(nèi)容一般不是一個邏輯意義完整的信息單位，請調(diào)一頁時可能只用到一部分內(nèi)容。請調(diào)一頁時可能只用到一部分內(nèi)容。 段式地址結(jié)構(gòu)段式地址結(jié)構(gòu)段號段號s 段內(nèi)位移段內(nèi)位移w分段地址空間分段地址空間:段表段表:二、段式地址變換二、段式地址變換段號段號段內(nèi)地址段內(nèi)地址s w長度長度基址基址段表段表第第s段