存儲(chǔ)管理.PPT

1、1第3章 存儲(chǔ)管理 2第第4 4章章 存儲(chǔ)管理存儲(chǔ)管理 本章的主要內(nèi)容如下：n(1)存儲(chǔ)管理的目的和四大基本功能。 n(2)實(shí)存管理中講述了固定分區(qū)存儲(chǔ)管理、可變式分區(qū)存儲(chǔ)管理、純分頁存儲(chǔ)管理三種存儲(chǔ)管理方案的實(shí)現(xiàn)原理n(3)虛存管理以請(qǐng)求式分頁存儲(chǔ)管理為重點(diǎn) n(4)總結(jié)各種存儲(chǔ)管理方案中存在的碎片和抖動(dòng)問題及解決方法33.1 存儲(chǔ)管理的功能 n存儲(chǔ)管理的主要功能：n內(nèi)存的分配與回收 n地址重定位n存儲(chǔ)保護(hù) n虛擬存儲(chǔ)器 存儲(chǔ)管理的主要目的：存儲(chǔ)管理的主要目的： 一是提高資源一是提高資源 的利用率的利用率 二是方便用戶使用主存儲(chǔ)器二是方便用戶使用主存儲(chǔ)器43.1.1 內(nèi)存的分配與回收 n內(nèi)存

2、分配按分配時(shí)機(jī)的不同，可分為兩種方式。n（1）靜態(tài)存儲(chǔ)分配：指內(nèi)存分配是在作業(yè)運(yùn)行之前各目標(biāo)模塊連接后，把整個(gè)作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個(gè)運(yùn)行過程中，不允許作業(yè)再申請(qǐng)其他內(nèi)存，或在內(nèi)存中移動(dòng)位置。也就是說，內(nèi)存分配是在作業(yè)運(yùn)行前一次性完成的。n（2）動(dòng)態(tài)存儲(chǔ)分配：作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時(shí)分配的，但在作業(yè)運(yùn)行過程中，允許作業(yè)申請(qǐng)附加的內(nèi)存空間，或是在內(nèi)存中移動(dòng)，即分配工作可以在作業(yè)運(yùn)行前及運(yùn)行過程中逐步完成。53.1.2 地址重定位 n1.程序的名空間n2.內(nèi)存空間（或物理空間）n3邏輯空間n4地址重定位61.程序的字符名空間程序的字符名空間main() int a

3、,b,c;.a=6;b=b+a;.72邏輯空間邏輯空間n源程序經(jīng)過匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來用符號(hào)名訪問的單元用具體的數(shù)據(jù)單元號(hào)取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡(jiǎn)稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問的操作數(shù)地址統(tǒng)稱為邏輯地址。8n物理地址：n 把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱為內(nèi)存地址（物理地址、絕對(duì)地址、實(shí)地址），存儲(chǔ)單元占8位，稱作字節(jié)（byte）。n物理地址空間：n 物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維的線性空間。3內(nèi)存空間（或物理

4、空間）內(nèi)存空間（或物理空間）9作業(yè)的名空間、邏輯地址空間和裝入后的物理空間作業(yè)的名空間、邏輯地址空間和裝入后的物理空間10n將程序地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址重定位,有時(shí)也稱為地址映射。n1)靜態(tài)地址重定位n2)動(dòng)態(tài)地址重定位地址重定位地址重定位111)靜態(tài)地址重定位靜態(tài)地址重定位靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的重靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的重定位裝入程序完成的。定位裝入程序完成的。12(2)動(dòng)態(tài)地址重定位 n 動(dòng)態(tài)重定位是在程序執(zhí)行時(shí)由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的。系統(tǒng)中設(shè)置了重定位寄存器。0100200300.LOAD A 2

5、003456邏輯地址空間邏輯地址空間110012001300物理地址空間物理地址空間200VR+1000BR133.1.3 存儲(chǔ)保護(hù) n（1）上、下界存儲(chǔ)保護(hù)：上、下界保護(hù)是一種簡(jiǎn)單的存儲(chǔ)保護(hù)技術(shù)。系統(tǒng)可為每個(gè)作業(yè)設(shè)置一對(duì)上、下界寄存器，分別用來存放當(dāng)前運(yùn)行作業(yè)在內(nèi)存空間的上、下邊界地址，用它們來限制用戶程序的活動(dòng)范圍。 n（2）基址限長(zhǎng)存儲(chǔ)保護(hù)：上、下界保護(hù)的一個(gè)變種是采用基址限長(zhǎng)存儲(chǔ)保護(hù)。 14界限寄存器的兩種存儲(chǔ)保護(hù)方式界限寄存器的兩種存儲(chǔ)保護(hù)方式153.1.4 虛擬存儲(chǔ)器 n 虛擬存儲(chǔ)技術(shù)的基本思想是把有限的內(nèi)存空間與大容量的外存統(tǒng)一管理起來，構(gòu)成一個(gè)遠(yuǎn)大于實(shí)際內(nèi)存的、虛擬的存儲(chǔ)器。此

6、時(shí)，外存是作為內(nèi)存的直接延伸，用戶并不會(huì)感覺到內(nèi)、外存的區(qū)別，即把兩級(jí)存儲(chǔ)器當(dāng)作一級(jí)存儲(chǔ)器來看待。一個(gè)作業(yè)運(yùn)行時(shí)，其全部信息裝入虛存，實(shí)際上可能只有當(dāng)前運(yùn)行的必需一部分信息存入內(nèi)存，其他則存于外存，當(dāng)所訪問的信息不在內(nèi)存時(shí)，系統(tǒng)自動(dòng)將其從外存調(diào)入內(nèi)存。 163.2 實(shí)存管理 n3.2.1 固定分區(qū)存儲(chǔ)管理 n3.2.2 可變式分區(qū)存儲(chǔ)管理n3.2.3 純分頁存儲(chǔ)管理 173.2.1 固定分區(qū)存儲(chǔ)管理 n固定分區(qū)存儲(chǔ)管理是實(shí)現(xiàn)多道程序設(shè)計(jì)的最簡(jiǎn)單的一種存儲(chǔ)管理技術(shù)。n其基本思想是，預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連續(xù)區(qū)域，稱為一個(gè)分區(qū)。每個(gè)分區(qū)的大小可以相同也可以不同，如圖所示。但分區(qū)大小

7、固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)n因?yàn)樵谙到y(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以固定式分區(qū)也稱為靜態(tài)分區(qū)。18n對(duì)作業(yè)的組織分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個(gè)輸入隊(duì)列多個(gè)輸入隊(duì)列單個(gè)輸入隊(duì)列單個(gè)輸入隊(duì)列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)700K400K100K019固定式分區(qū)內(nèi)存分配示意圖（固定式分區(qū)內(nèi)存分配示意圖（a）和（）和（b）固定）固定式分區(qū)分配表式分區(qū)分配表203.2.2 可變式分區(qū)存儲(chǔ)管理 n1空閑分區(qū)的組織形式 n2內(nèi)存的分配與回收 n3常用的分配算法 n4可變式分區(qū)的地址重定位 內(nèi)存的分配：內(nèi)存不是預(yù)先劃分好的，而是當(dāng)內(nèi)存

8、的分配：內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足夠的空間，則用情況來決定是否分配。若有足夠的空間，則按需要分割與作業(yè)相對(duì)地址空間同樣大小分區(qū)按需要分割與作業(yè)相對(duì)地址空間同樣大小分區(qū)給該進(jìn)程；否則令其等待主存空間給該進(jìn)程；否則令其等待主存空間。21可變式分區(qū)內(nèi)存使用情況示意圖可變式分區(qū)內(nèi)存使用情況示意圖221空閑分區(qū)的組織形式 n空閑分區(qū)鏈表的組織是這樣的：在每個(gè)空閑分區(qū)的起始部分開辟出一個(gè)單元，存放一個(gè)鏈表指針和該分區(qū)的大小，鏈表指針指向下一個(gè)空閑分區(qū)。系統(tǒng)中用一個(gè)固定單元作為空閑分區(qū)鏈表的鏈表頭指

9、針，指向第一塊空閑分區(qū)首地址，最后一塊空閑分區(qū)的鏈表指針存放鏈尾標(biāo)志。如圖4.7（a）所示 。23空閑分區(qū)鏈表組織形式空閑分區(qū)鏈表組織形式242內(nèi)存的分配與回收 n當(dāng)某一個(gè)用戶作業(yè)完成釋放所占分區(qū)時(shí)，系統(tǒng)應(yīng)進(jìn)行回收。在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰，若相鄰，則應(yīng)進(jìn)行合并，形成一個(gè)較大的空閑區(qū)，并對(duì)相應(yīng)的鏈表指針進(jìn)行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。n 253常用的分配算法 n（1）首次適應(yīng)算法 n（2）最佳適應(yīng)算法 n（3）最差適應(yīng)算法 26首次適應(yīng)算法空閑分區(qū)鏈表組織形式首次適應(yīng)算法空閑分區(qū)鏈表組織形式27最佳適應(yīng)算法的空閑分區(qū)鏈表組織形式最佳適應(yīng)

10、算法的空閑分區(qū)鏈表組織形式28最差適應(yīng)算法的空閑分區(qū)鏈表組織形式最差適應(yīng)算法的空閑分區(qū)鏈表組織形式29內(nèi)存使用情況內(nèi)存使用情況 30用三種適應(yīng)算法處理同一作業(yè)序列用三種適應(yīng)算法處理同一作業(yè)序列314可變式分區(qū)的地址重定位 n可變式分區(qū)的地址重定位可采用靜態(tài)重定位，也可采用動(dòng)態(tài)重定位。如采用靜態(tài)重定位，因用戶作業(yè)進(jìn)入內(nèi)存后，程序的邏輯地址實(shí)現(xiàn)了重定位，不能在內(nèi)存中再進(jìn)行移動(dòng)，經(jīng)過一段時(shí)間的運(yùn)行，內(nèi)存中不能再分配利用的小碎片會(huì)越來越多。有時(shí)可能會(huì)出現(xiàn)這種情況，即當(dāng)一個(gè)作業(yè)申請(qǐng)一定數(shù)量的內(nèi)存時(shí)，雖然此時(shí)空閑區(qū)的總和大于新作業(yè)的內(nèi)存要求，但卻沒有單個(gè)的空閑區(qū)足以裝下該作業(yè)。n采用動(dòng)態(tài)重定位的可變式分區(qū)

11、管理技術(shù)，在執(zhí)行內(nèi)存分配時(shí)，如無足夠大空閑塊，應(yīng)考慮實(shí)現(xiàn)緊湊操作。其分配算法如圖所示 。 32采用動(dòng)態(tài)重定位的可變式分區(qū)分配算法采用動(dòng)態(tài)重定位的可變式分區(qū)分配算法333.2.3 純分頁存儲(chǔ)管理 n1純分頁存儲(chǔ)管理中存儲(chǔ)塊的分配與回收 n2純分頁存儲(chǔ)管理的地址重定位問題n3聯(lián)想存儲(chǔ)器 n4存儲(chǔ)保護(hù) 34純分頁存儲(chǔ)管理示意圖純分頁存儲(chǔ)管理示意圖35n分頁的概念n 內(nèi)存空間分成大小相等的若干塊頁面，同時(shí)把程序邏輯地址也分成與塊大小相等的若干頁面，當(dāng)一個(gè)用戶程序裝入內(nèi)存時(shí)，以頁面為單位進(jìn)行分配。頁面的大小是為2n ,通常為1KB，2KB，nKB等。1純分頁存儲(chǔ)管理中存儲(chǔ)塊的分配與回收 36n通 常 有

12、兩 種 記錄 空 閑存 儲(chǔ) 塊的方法：位 圖 法和 鏈 表法。（a）存儲(chǔ)塊使用情況 （b）存儲(chǔ)塊使用情況的位圖表示存儲(chǔ)塊的位圖管理法存儲(chǔ)塊的位圖管理法372純分頁存儲(chǔ)管理的地址重定位問題 n純分頁存儲(chǔ)管理中的地址重定位是非常重要的，要使不連續(xù)的、分散的用戶程序能正常運(yùn)行，須采用動(dòng)態(tài)地址重定位。此時(shí)，可采用重定位寄存器方式，如分頁太多，則重定位寄存器用得太多。通常可在內(nèi)存中為每個(gè)作業(yè)開辟一塊特定區(qū)域，建立起作業(yè)的邏輯頁與存儲(chǔ)塊之間的對(duì)應(yīng)表格關(guān)系，這種表常稱為頁面映象表，簡(jiǎn)稱頁表。 3839純分頁存儲(chǔ)管理地址重定位實(shí)現(xiàn)過程純分頁存儲(chǔ)管理地址重定位實(shí)現(xiàn)過程40n一、頁表n 頁表是頁式存儲(chǔ)管理的數(shù)據(jù)結(jié)

13、構(gòu)，它包括用戶程序空間的頁面與內(nèi)存塊的對(duì)應(yīng)關(guān)系、頁面的存儲(chǔ)保護(hù)和存取控制方面的信息。n 頁號(hào) 內(nèi)存塊號(hào) 存取控制 狀態(tài) 其它n 在實(shí)際的系統(tǒng)中，為了節(jié)省存儲(chǔ)空間，在頁表中可以省去頁號(hào)這個(gè)表目。41n二、虛地址結(jié)構(gòu)(程序字)n 虛地址是用戶程序中的邏輯地址，它包括頁號(hào)和頁內(nèi)地址（頁內(nèi)位移）。n 區(qū)分頁號(hào)和頁內(nèi)地址的依椐是頁的大小，頁內(nèi)地址占虛地址的低位部分，頁號(hào)占虛地址的高位部分。n 假定頁面大小1024字節(jié)，虛地址共占用2個(gè)字節(jié)(16位)n 頁號(hào) 頁內(nèi)地址（位移量）n P Wn 15 10 9 0423聯(lián)想存儲(chǔ)器 n從上面介紹的地址變換過程可以看出：如果把頁表全部放在內(nèi)存，那么存取一個(gè)數(shù)據(jù)時(shí)，

14、至少要訪問二次內(nèi)存。一次是訪問頁表，形成實(shí)際內(nèi)存地址；另一次是根據(jù)形成的內(nèi)存地址存取數(shù)據(jù)。顯然，這比通常執(zhí)行指令的速度要慢得多，使計(jì)算機(jī)的運(yùn)行速度幾乎降低一半。n應(yīng)用聯(lián)想存儲(chǔ)器和頁表相結(jié)合的方式，可有效地提高系統(tǒng)動(dòng)態(tài)地址轉(zhuǎn)換的速度，是一種行之有效的方法。43采用快表和頁表相結(jié)合的分頁地址變換過程示意圖采用快表和頁表相結(jié)合的分頁地址變換過程示意圖444存儲(chǔ)保護(hù) n四種保護(hù)方式：禁止做任何操作，只能執(zhí)行，只能讀，能讀/寫，當(dāng)要訪問某頁時(shí)，先判斷該頁的存取控制和存儲(chǔ)保護(hù)信息是否允許。n添加了存取控制信息的頁表表目如下圖所示： 45Windows NT兩級(jí)頁表地址變換示意圖兩級(jí)頁表地址變換示意圖46（

15、2）面對(duì)大的頁表，地址的映射怎樣才能比較快地實(shí)現(xiàn)？ n使用快表：即利用前面我們已介紹的高速緩沖存儲(chǔ)器來存放經(jīng)常使用的頁表表目，以提高頁表的查詢速度。47 段式存儲(chǔ)管理 基本思想（工作原理） 作業(yè)的地址空間被劃分為若干個(gè)段,每個(gè)段定義了一組邏輯信息.系統(tǒng)為每個(gè)段分配一個(gè)連續(xù)的分區(qū),進(jìn)程中的各個(gè)段可以離散地放入內(nèi)存中不同的分區(qū)中.48.0S工作區(qū)段工作區(qū)段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段子程序段Y0116N數(shù)組數(shù)組A12345.49操作系統(tǒng)操作系統(tǒng).B0SA0NY0LX0PM0K邏輯段號(hào)邏輯段號(hào)01234作業(yè)

16、作業(yè)1的地址空間的地址空間10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000長(zhǎng)度長(zhǎng)度 段地址段地址01234操作系統(tǒng)操作系統(tǒng)50用戶程序劃分用戶程序劃分 按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號(hào)。段號(hào)從0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的。51邏輯地址邏輯地址內(nèi)存劃分 內(nèi)存空間被動(dòng)態(tài)的劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，這些區(qū)域被稱為物理段，每個(gè)物理段由起始地址和長(zhǎng)度確定。段號(hào) 段內(nèi)地址52內(nèi)存分配內(nèi)存分配 以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機(jī)分割，需要多少分配多少

17、），但各段之間可以不連續(xù)存放。53管理管理段表： 它記錄了段號(hào)，段的首（地）址和長(zhǎng)度之間的關(guān)系。 每一個(gè)程序設(shè)一個(gè)段表段號(hào)01254硬件支持硬件支持一對(duì)寄存器段表始址寄存器： 用于保存正在運(yùn)行進(jìn)程的段表的始址。段表長(zhǎng)度寄存器： 用于保存正在運(yùn)行進(jìn)程的段表的長(zhǎng)度（例如上圖的段表長(zhǎng)度為3）。55 Cl Cb+段號(hào)段號(hào)S S 段內(nèi)地址段內(nèi)地址d比較比較比較比較b + d比較比較段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表長(zhǎng)度寄存器段表長(zhǎng)度寄存器邏輯地址邏輯地址lb.Slb地址越界地址越界d=1d=1地址映射及存儲(chǔ)保護(hù)機(jī)制地址越界地址越界地址越界地址越界比較比較56優(yōu)點(diǎn)：

18、 便于動(dòng)態(tài)申請(qǐng)內(nèi)存 管理和使用統(tǒng)一化 便于共享 便于動(dòng)態(tài)鏈接缺點(diǎn)：產(chǎn)生碎片57段頁式存儲(chǔ)管理段頁式存儲(chǔ)管理產(chǎn)生背景及基本思想 背景：結(jié)合了二者優(yōu)點(diǎn) 克服了二者的缺點(diǎn)58基本思想：基本思想： 用戶程序劃分：按段式劃分（對(duì)用戶來講，按段的邏輯關(guān)系進(jìn)行劃分；對(duì)系統(tǒng)講，按頁劃分每一段） 邏輯地址：內(nèi)存劃分：按頁式存儲(chǔ)管理方案內(nèi)存分配：以頁為單位進(jìn)行分配59管理管理1 段表：記錄了每一段的頁表始址和頁表長(zhǎng)度2 頁表：記錄了邏輯頁號(hào)與內(nèi)存塊號(hào)的對(duì)應(yīng)關(guān)系。（每一段有一個(gè)，一個(gè)程序可能有多個(gè)頁表）4 分配：同頁式管理603.3 虛擬存儲(chǔ)器管理 n3.3.1 虛擬存儲(chǔ)器的概念 n3.3.2 請(qǐng)求式分頁存儲(chǔ)管理與

19、動(dòng)態(tài)地址重定位 n3.3.3 現(xiàn)代計(jì)算機(jī)系統(tǒng)改進(jìn)的動(dòng)態(tài)地址重定位 n3.3.4 頁面置換算法 n3.3.5 請(qǐng)求式分頁存儲(chǔ)管理性能分析舉例 n3.3.6 請(qǐng)求式分段存儲(chǔ)管理 61 早在早在19681968年年P(guān) PDenningDenning就指出過，程序在執(zhí)行時(shí)將呈就指出過，程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律，即在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于現(xiàn)出局部性規(guī)律，即在一段時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)某個(gè)部分；相應(yīng)地，它所訪問的存儲(chǔ)空間也局限于某個(gè)區(qū)域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸域內(nèi)。那么程序?yàn)槭裁磿?huì)出現(xiàn)局部性規(guī)律呢？原因可以歸結(jié)為以

20、下幾點(diǎn)：結(jié)為以下幾點(diǎn)：程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，程序在執(zhí)行時(shí)，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，大多數(shù)仍是順序執(zhí)行的。大多數(shù)仍是順序執(zhí)行的。子程序調(diào)用將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另子程序調(diào)用將會(huì)使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超一部分區(qū)域。但在大多數(shù)情況下，過程調(diào)用的深度都不超過過5 5。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中存在許多循環(huán)結(jié)構(gòu)，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)連續(xù)的存儲(chǔ)程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理，如對(duì)連續(xù)的存儲(chǔ)空間空間數(shù)組的訪問，往往局限于很小

21、的范圍內(nèi)。數(shù)組的訪問，往往局限于很小的范圍內(nèi)。623.3.1 虛擬存儲(chǔ)器的概念 n局部性原理(principle of locality)：指程序在執(zhí)行過程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。在一段時(shí)間內(nèi)一個(gè)程序的執(zhí)行往往呈現(xiàn)出高度的局部性，表現(xiàn)在時(shí)間與空間兩方面:n時(shí)間局限性：如果程序中的某條指令一旦執(zhí)行，則不久的將來該指令可能再次被執(zhí)行；如果某個(gè)存儲(chǔ)單元被訪問，則不久以后該存儲(chǔ)單元可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因是在程序中存在著大量的循環(huán)操作。n 空間局限性：一旦程序訪問了某個(gè)存儲(chǔ)單元，則在不久的將來，其附近的存儲(chǔ)單元也最有可能被訪問。 即程序

22、在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。63（1）程序中往往會(huì)有一些彼此互斥的部分。）程序中往往會(huì)有一些彼此互斥的部分。 （2）在一個(gè)完整的程序中，會(huì)有一些諸如出錯(cuò)處理這樣的子）在一個(gè)完整的程序中，會(huì)有一些諸如出錯(cuò)處理這樣的子程序，在作業(yè)正常運(yùn)行情況下不會(huì)執(zhí)行這些程序，沒有必要把程序，在作業(yè)正常運(yùn)行情況下不會(huì)執(zhí)行這些程序，沒有必要把它們調(diào)入內(nèi)存。它們調(diào)入內(nèi)存。 基于程序局部性原理和上述情況，就沒有必要把一個(gè)作業(yè)一基于程序局部性原理和上述情況，就沒有必要把一個(gè)作業(yè)一次性全部裝入內(nèi)存再開始運(yùn)行。而是可以把程序當(dāng)前執(zhí)行所涉次性全部裝入內(nèi)存再開始運(yùn)行。而是可以把

23、程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)調(diào)入，由操作及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)調(diào)入，由操作系統(tǒng)和硬件相配合來完成主存和輔存之間信息的動(dòng)態(tài)調(diào)度。系統(tǒng)和硬件相配合來完成主存和輔存之間信息的動(dòng)態(tài)調(diào)度。虛擬存儲(chǔ)器的定義虛擬存儲(chǔ)器的定義 根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒有必要把全部作根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁面或段，先裝業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁面或段，先裝入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上。入內(nèi)存便可啟動(dòng)運(yùn)行，其余部分暫時(shí)留在磁盤上。643.3.2 請(qǐng)求式分頁存儲(chǔ)管理與動(dòng)

24、態(tài)地址重定位 n請(qǐng)求式分頁存儲(chǔ)管理與純分頁存儲(chǔ)管理在內(nèi)存塊的分配與回收，存儲(chǔ)保護(hù)某方面都十分相似，不同之處在于地址重定位問題。在請(qǐng)求式分頁存儲(chǔ)管理的地址重定位時(shí)，可能會(huì)出現(xiàn)所需頁面不在主存的情況，此時(shí)，系統(tǒng)必須解決以下兩個(gè)問題：n（1）當(dāng)程序要訪問的某頁不在內(nèi)存時(shí)，如何發(fā)現(xiàn)這種缺頁情況？發(fā)現(xiàn)后應(yīng)如何處理？n（2）當(dāng)需要把外存上的某個(gè)頁面調(diào)入內(nèi)存時(shí)，此時(shí)內(nèi)存中沒有空閑塊應(yīng)怎么辦？65所示是請(qǐng)求式分頁存儲(chǔ)管理的存儲(chǔ)映像所示是請(qǐng)求式分頁存儲(chǔ)管理的存儲(chǔ)映像 66n為了幫助操作系統(tǒng)對(duì)要置換出內(nèi)存的頁面進(jìn)行選擇，在頁表中還可以增加一個(gè)引用位，以反映該頁最近的使用情況。n一般來說，一個(gè)頁表的表目通常可包括如

25、下的數(shù)據(jù)內(nèi)容：67請(qǐng)求式分頁存儲(chǔ)管理中的地址重定位和缺頁中斷處請(qǐng)求式分頁存儲(chǔ)管理中的地址重定位和缺頁中斷處理過程如圖所示。理過程如圖所示。683.3.4 頁面置換算法 n1最優(yōu)算法（OPT算法）n2先進(jìn)先出算法（FIFO算法）n3最久未使用頁面置換算法（LRU算法）n4LRU近似算法691最優(yōu)算法（ OptimalOptimal 算法）n它是一種理想化的算法，性能最好，但在實(shí)際上難于實(shí)現(xiàn)。即選即選擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁面置換擇那些永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁面置換出去出去。但是要確定哪一個(gè)頁面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，目前來說是很難估計(jì)的，所以該

26、算法通常用來評(píng)價(jià)其它算法。n例：例：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號(hào)引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下圖所示，進(jìn)程運(yùn)行時(shí)先將7，0，1三個(gè)頁面裝入內(nèi)存。當(dāng)進(jìn)程訪問頁面2時(shí)，產(chǎn)生缺頁中斷，此時(shí)OS根據(jù)最佳置換算法，頁面7將在第18次才被訪問，是三頁中將最久不被訪問的頁面，所以被淘汰。接著訪問頁面0時(shí)，發(fā)現(xiàn)已在內(nèi)存中，而不會(huì)產(chǎn)生缺頁中斷，以此類推。從圖可以看出，采用最佳置換算法，只發(fā)生了6次頁面置換。702先進(jìn)先出算法（FIFO算法）n這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁面，即先進(jìn)入內(nèi)存的頁面先被

27、置換掉。理由是：最先進(jìn)入內(nèi)存的頁面不再被訪問的可能性最大。 71先進(jìn)先出算法存儲(chǔ)分塊表構(gòu)造先進(jìn)先出算法存儲(chǔ)分塊表構(gòu)造723最久未使用頁面置換算法（LRULeast Recently UsedLeast Recently Used算法）n這種算法的基本思想是，如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長(zhǎng)時(shí)間沒有被訪問，那么最近也不太可能會(huì)被訪問。這種算法考慮了程序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間最久未使用的頁面予以淘汰。n實(shí)現(xiàn)這種算法可通過周期性地對(duì)“引用位”進(jìn)行檢查，并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，淘汰時(shí)選擇t最大的頁面

28、。 734LRU近似算法n這種算法，只要在存儲(chǔ)分塊表（或頁表）中設(shè)一個(gè)“引用位”，當(dāng)存儲(chǔ)分塊表中的某一頁被訪問時(shí)，該位由硬件自動(dòng)置1，并由頁面管理軟件周期性把所有引用位置0。這樣，在一個(gè)時(shí)間周期T內(nèi)，某些被訪問過的頁面其引用位為1，而未被訪問過的頁面其引用位為0。因此，可根據(jù)引用位的狀態(tài)來判別各頁面最近的使用情況。當(dāng)需要置換一頁面時(shí)，選擇其引用位為0的頁，如圖4.21所示的算法 。圖4.22是這種近似算法的一個(gè)例子。 74LRU近似算法近似算法 75LRU近似算法舉例近似算法舉例763.3.5 請(qǐng)求式分頁存儲(chǔ)管理性能分析舉例 n1程序設(shè)計(jì)的質(zhì)量n2頁面的大小n3分配的內(nèi)存塊數(shù)n4頁面置換算法性

29、能77n【例1】主存塊數(shù)m=3，置換算法采用FIFO算法，缺頁中斷次數(shù)及缺頁率如圖4.23所示。n在圖4.23中，P行表示頁面走向，M行表示在主存中的頁面號(hào)，其中帶有+的表示新調(diào)入頁面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將被淘汰頁面，F(xiàn)行表示是否引起缺頁中斷，帶號(hào)的表示引起缺頁中斷。從圖4.23可以看出，缺頁中斷頁數(shù)為9次，缺頁率f=9/12=75%。78FIFO算法性能分析（算法性能分析（m=3）79n【例2】設(shè)m=4，仍采用FIFO算法，缺頁中斷次數(shù)及缺頁率如圖4.24所示。可以算出，在分配給該作業(yè)的內(nèi)存塊數(shù)增加到4時(shí)，缺頁中斷由圖4.23的9次反而增加到了10次，缺頁率由75%增加到10/12=83%，這就是FIFO算法的一種異?，F(xiàn)象。隨著分配的主存塊數(shù)的增加，缺頁中斷次數(shù)不但沒有降低，反而增加了。這與該算法定全不考慮程