第07章存儲管理

1、1第七章 存儲管理27.1 概念存儲器storage, memory能接收數(shù)據(jù)和保存數(shù)據(jù)、而且能根據(jù)命令提供這些數(shù)據(jù)的裝置。37.1 概念 存儲器分成兩類：內(nèi)存儲器（簡稱內(nèi)存、主存、物理存儲器）處理機能直接訪問的存儲器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點是存取速度快，存儲方式是以新?lián)Q舊，斷電信息丟失。外存儲器（簡稱外存、輔助存儲器）處理機不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內(nèi)存而言要慢得多，但它可用來長期保存用戶信息。在文件系統(tǒng)中介紹。47.1 概念 1. 內(nèi)存的物理組織物理地址： 把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內(nèi)存地址（物理地址

2、、絕對地址、實地址），存儲單元占8位，稱作字節(jié)（byte）。物理地址空間： 物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。57.1 概念 2.程序的邏輯結(jié)構(gòu)程序地址：用戶編程序時所用的地址（或稱邏輯地址 、虛地址 ），基本單位可與內(nèi)存的基本單位相同，也可以不相同。程序地址空間（邏輯地址空間、虛地址空間）:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開始的，可以是一維線性空間，也可以是多維空間。67.2存儲管理的功能 存儲管理功能：(1) (1) 地址地址映射映射 將程序地址空間中使用的邏輯地址變換成主存中的地址的過程；(2) (2) 主存主存分配分配 按照一

3、定的算法把某一空閑的主存區(qū)分配給作業(yè)或進程；(3) (3) 存儲存儲保護保護 保證用戶程序(或進程映象)在各自的存儲區(qū)域內(nèi)操作，互不干擾；(4) (4) 提供虛擬存儲技術(shù)提供虛擬存儲技術(shù)( (擴充擴充) ) 使用戶程序的大小和結(jié)構(gòu)不受主存容量和結(jié)構(gòu)的限制，即使在用戶程序比實際主存容量還要大的情況下，程序也能正確運行。77.2.1 提供虛存1、問題的提出、問題的提出 物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是有限的。物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是有限的。用戶程序結(jié)構(gòu)：用戶程序結(jié)構(gòu)：一維空間。一維空間。一個用戶程序就是一個程序，并且程序和數(shù)據(jù)是不分離一個用戶程序就是一個程序，并且程序和

4、數(shù)據(jù)是不分離的；的；二維空間。二維空間。程序由主程序和若干個子程序（或函數(shù)）組成，并且程程序由主程序和若干個子程序（或函數(shù)）組成，并且程序與數(shù)據(jù)是分離的；序與數(shù)據(jù)是分離的； n維空間。維空間。即一個大型程序，由一個主模塊和多個子模塊組成，其中即一個大型程序，由一個主模塊和多個子模塊組成，其中 ，各子模塊又由主程序和子程序（或函數(shù)）組成。，各子模塊又由主程序和子程序（或函數(shù)）組成。用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時候要大得多。候要大得多。87.2.1 提供虛存 如何將與物理內(nèi)存結(jié)構(gòu)不同，且大于物理內(nèi)存容量的用戶程序

5、裝入運行？這就是提出研究虛擬存儲器的原因，或稱為虛擬存儲技術(shù)發(fā)展的原動力。 局部性原理：局部性原理：程序訪問的指令和數(shù)據(jù)是相對聚簇的，即一段時間內(nèi)集中訪問程序編碼的一部分。（使虛存管理成為可能）97.2.1 提供虛存2. 虛擬存儲器概念 為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)稱為虛擬存儲器，或稱虛擬存儲技術(shù)。 它是用戶編程時所使用的一種用戶思維中的存儲器，它可以是任何結(jié)構(gòu)（一維線性空間、二維空間、乃至n維空間），并沒有容量的限制。 現(xiàn)代計算機操作系統(tǒng)都采用了這種技術(shù)，使得用戶編程序時不需要考慮物理內(nèi)存的結(jié)構(gòu)和容量，極大地方便了用戶。 虛擬存儲器需要大容量的外存儲器的支持，或稱

6、物質(zhì)基礎(chǔ)。107.2存儲管理的功能 7.2.2 地址映射一、什么是地址映射 將程序地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址映射。有時也稱為地址重定位 。117.2存儲管理的功能 7.2.2 地址映射二、地址映射方式 地址映射的功能就是要建立虛實地址的對應(yīng)關(guān)系，實現(xiàn)地址映射有三種方式： 編程或編譯時確定地址映射關(guān)系 靜態(tài)地址映射 動態(tài)地址映射127.2存儲管理的功能 7.2.2 地址映射1. 編程或編譯時確定地址映射關(guān)系 編程時確定虛實地址的關(guān)系是指在用機器指令編程時，程序員直接按物理內(nèi)存地址編程，這種程序在系統(tǒng)中是不能做任何移動的，否則就會出錯。137.2存儲管理的功能 7.2

7、.2 地址映射2.靜態(tài)地址映射 靜態(tài)地址映射是在程序裝入內(nèi)存時完成從邏輯地址到物理地址的轉(zhuǎn)換的。 在一些早期的系統(tǒng)中都有一個裝入程序（加載程序），它負責將用戶程序裝入系統(tǒng)，并將用戶程序中使用的訪問內(nèi)存的邏輯地址轉(zhuǎn)換成物理地址。如左圖所示。評價: 優(yōu)點是實現(xiàn)簡單，不要硬件的支持。缺點是程序一旦裝入內(nèi)存，移動就比較困難。有時間上的浪費。在程序裝入內(nèi)存時要將所有訪問內(nèi)存的地址轉(zhuǎn)換成物理地址。147.2存儲管理的功能 7.2.2 地址映射 2.靜態(tài)地址映射157.2存儲管理的功能 7.2.2 地址映射3.動態(tài)地址映射 動態(tài)地址映射是在程序執(zhí)行時由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的。 系統(tǒng)中設(shè)置了

8、重定位寄存器。167.2存儲管理的功能 7.2.2 地址映射 3.動態(tài)地址映射動態(tài)地址映射是由硬件地執(zhí)行時完成的，程序中不執(zhí)行的程序就不做地址映射的工作，這樣節(jié)省了CPU的時間 。 重定位寄存器的內(nèi)容由操作系統(tǒng)用特權(quán)指令來設(shè)置，比較靈活。實現(xiàn)動態(tài)地址映射必須有硬件的支持，并有一定的執(zhí)行時間延遲?，F(xiàn)代計算機系統(tǒng)中都采用動態(tài)地址映射技術(shù)。177.2存儲管理的功能 7.2.2 地址映射 3.動態(tài)地址映射動態(tài)地址映射技術(shù)能滿足以下目標：（1）具有給一個用戶程序任意分配內(nèi)存區(qū)的能力；（2）可實現(xiàn)虛擬存儲；（3）具有重新分配的能力（4）對于一個用戶程序，可以分配到多個不同的存儲區(qū)187.2.3 程序的邏輯

9、組織 一維地址結(jié)構(gòu)(傳統(tǒng)方式) 二維地址結(jié)構(gòu)(代碼段、數(shù)據(jù)段、棧段、特別段+段內(nèi)便宜地址)197.2.4 內(nèi)存分配 在多道程序設(shè)計的環(huán)境中，內(nèi)存分配的功能包括：制定分配策略、構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)、響應(yīng)系統(tǒng)的內(nèi)存分配的請求和回收系統(tǒng)釋放的內(nèi)存區(qū)。內(nèi)存管理策略有三種：1、放置策略 決定內(nèi)存中放置信息的區(qū)域（或位置），即如何在若干個空閑區(qū)中選擇一個或幾個空閑區(qū)的原則；2、調(diào)入策略 決定信息裝入內(nèi)存的時機，有兩種：在用戶請求時調(diào)入，稱為請調(diào)；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行前預先調(diào)入內(nèi)存，稱為預調(diào) ；3、淘汰策略 當內(nèi)存不足時，決定將某些信息調(diào)出內(nèi)存的策略 。207.2.5 存儲保護 在

10、多道程序設(shè)計的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個用戶程序同時存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？這就是存儲保護所要解決的問題。常用的存儲保護有兩種。 上、下界保護； 基址、限長寄存器保護；217.2.5 存儲保護 1.上下界保護下界寄存器：存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器：存放程序裝入內(nèi)存后的末地址判別式：下界寄存器 物理地址 上界寄存器227.2.5 存儲保護 1.上下界保護例：有一程序裝入內(nèi)存的首地址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。 下界寄存器：500 上界寄存器：1500 邏輯地址裝入內(nèi)存的首地 物理地址 1、

11、500500 1000 500 1000 1500 2、345500 845 500 845 1500 3、1000500 1500 500 1500 1500237.2.5 存儲保護 2.基址、限長寄存器保護例：有一程序裝入內(nèi)存的首地址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。 基址寄存器：500 限長寄存器：1000判別式：0 邏輯地址 限長寄存器 1、 500 1000 2、 345 1000 3、 1000 100024考點：在某系統(tǒng)中采用基址、限長寄存器的方法來保護存儲信息，判斷是否越界的判別式為（ ）。 （華中科技大學 2005年）A.0=被訪問的邏

12、輯地址限長寄存器的內(nèi)容B.0=被訪問的邏輯地址=限長寄存器的內(nèi)容C.0=被訪問的物理地址限長寄存器的內(nèi)容D.0=被訪問的物理地址=限長寄存器的內(nèi)容257.2.5 存儲保護 3.兩種存儲保護技術(shù)的區(qū)別區(qū)別：1、寄存器的設(shè)置不同；2、判別式中用的判別條件不同 上下界寄存器保護法用的是物理地址； 基址、限長寄存器保護法用的是程序的邏輯地址； 對于合法的訪問地址這兩者的效率是相同的，對不合法的訪問地址來說，上下界存儲保護浪費的CPU時間相對來說要多些。 267.3 分區(qū)存儲管理(partition) 7.3.1 概述 分區(qū)存儲管理是滿足多道程序設(shè)計的最簡單的一種存儲管理方法，它允許多個用戶程序同時存在

13、系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。 靜態(tài)靜態(tài)(固定固定)分區(qū)的方法。分區(qū)的方法。 最早期的分區(qū)存儲管理采用固定分區(qū)的方法，把內(nèi)存空間分成若干個大小不等的區(qū)域，稱為分區(qū)。每個用戶程序（作業(yè)、進程）調(diào)入內(nèi)存后，占用其中一個分區(qū)，程序運行完成后釋放該分區(qū)。這種存儲管理的方法的主要問題是內(nèi)存使用效率極低，很快就被淘汰了。277.3 分區(qū)存儲管理 7.3.1 概述動態(tài)分區(qū)存儲管理技術(shù)動態(tài)分區(qū)存儲管理技術(shù) 系統(tǒng)生成后，操作系統(tǒng)占用內(nèi)存的一部分，一般在物理內(nèi)存的開始處，比如，一個操作系統(tǒng)占20KB，裝入系統(tǒng)后占用020KB的內(nèi)存空間，剩下的部分作為一個空閑區(qū)，當一個用戶程序（作業(yè)、進程）調(diào)入內(nèi)存時，把這個空閑區(qū)的

14、低地址部分的區(qū)域分配給它，如圖所示。287.3 分區(qū)存儲管理 7.3.1 概述 當有作業(yè)完成后釋放所占用的存儲區(qū)。 在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的不連續(xù)的存儲區(qū)。297.3 分區(qū)存儲管理 7.3.1 概述分區(qū)存儲管理技術(shù)的實現(xiàn)： 地址映射 動態(tài)存儲管理的機構(gòu)（數(shù)據(jù)結(jié)構(gòu)） 分區(qū)的分配和回收 三種基本的放置策略307.3 分區(qū)存儲管理 7.3.2 用基地址寄存器實現(xiàn)動態(tài)地址映射 在這種存儲管理技術(shù)中，系現(xiàn)設(shè)置一個專用寄存器，稱為基地址寄存器，當一個進程（或程序、作業(yè)）被調(diào)度運行時，系統(tǒng)首先從PCB中取出該進程的首地址裝入基地址寄存器中，在該進程運行的過程中實現(xiàn)動態(tài)地址映射。317.3 分

15、區(qū)存儲管理 7.3.3 分區(qū)分配機構(gòu) 分區(qū)存儲管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表、空閑區(qū)隊列兩種。其形式如圖所示。分區(qū)描述器327.3 分區(qū)存儲管理 7.3.3 分區(qū)分配機構(gòu)等待隊列指針空閑區(qū)隊列指針分配程序入口資源信息塊pcb1pcb2pcbn.pd1pd2pdn.337.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收 內(nèi)存分配程序包括分配一個內(nèi)存塊（分區(qū)）和釋放內(nèi)存分配程序包括分配一個內(nèi)存塊（分區(qū)）和釋放一個內(nèi)存塊（分區(qū)）兩個函數(shù)，當進程需要一個大小一個內(nèi)存塊（分區(qū)）兩個函數(shù)，當進程需要一個大小為為size的內(nèi)存時，可以通過系統(tǒng)調(diào)用向系統(tǒng)申請。的內(nèi)存時，可以通過系統(tǒng)調(diào)用向系統(tǒng)申請。調(diào)用形式：

16、調(diào)用形式：request(size)返回：成功為分區(qū)的首地址，失敗為返回：成功為分區(qū)的首地址，失敗為0。 進程釋放一個分區(qū)時，調(diào)用：進程釋放一個分區(qū)時，調(diào)用： release(釋放區(qū)首地址）釋放區(qū)首地址） 返回：無返回：無347.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收一、分配算法 教材上的p167 的分配算法是以空閑內(nèi)存隊列的數(shù)據(jù)結(jié)構(gòu)進行分配。介紹空閑區(qū)表數(shù)據(jù)結(jié)構(gòu)的分配算法。 注：1、分配算法中切割空閑區(qū)是從低地址開始的，例如，一個空閑區(qū)大小是100KB，首址是230KB，一申請者要求80KB，分配時將從230KB開始的80KB分配給申請者，剩下的部分仍作為一個空閑區(qū)，其首址是310K

17、B，大小是20KB。2、門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值，就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請者。357.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收367.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收二、回收算法 當一個進程（或程序）釋放某內(nèi)存區(qū)時，要調(diào)用存儲區(qū)釋放算法release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空閑區(qū)表（或隊列）中的適當位置。 空閑釋放區(qū)與空閑區(qū)相鄰有四種情況。試用C語言寫出動態(tài)分區(qū)的回收算法。377.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收A、將r合并到f1：f1.addr

18、不變; f1.size=f1.size+r.sizeB、將r合并到f2：f2.addr=r.addr; f2.size =f2.size+r.sizeC、f1、r、f2 合并到f1, f1.addr： f1.size =f1.size+r.size+f2.size； 撤消f2空閑區(qū)；D、r作為一個空閑區(qū)，并插入到空閑區(qū)表的適當位置。387.3 分區(qū)存儲管理 7.3.5 幾種放置策略 分區(qū)分配和回收是對空閑區(qū)表（或空閑區(qū)隊列）數(shù)據(jù)結(jié)構(gòu)進行操作，空閑區(qū)表的組織有兩種方法：1、按空閑區(qū)大小的升序（降序）組織；2、按空閑區(qū)首址升序（降序）組織。 根據(jù)空閑區(qū)表組織的方法的不同，有不同的放置策略，它們是：

19、最佳適應(yīng)算法；首次適應(yīng)算法；最壞適應(yīng)算法；397.3 分區(qū)存儲管理 7.3.5 幾種放置策略一、首次適應(yīng)算法 首次適應(yīng)算法的表是按空閑區(qū)首址升序的（即空閑區(qū)表是按空閑區(qū)首址從小到大）方法組織的。 407.3 分區(qū)存儲管理 7.3.5 幾種放置策略一、首次適應(yīng)算法 分配時從表首開始，以請求內(nèi)存區(qū)的大小逐個與空閑區(qū)進行比較，找到第一個滿足要求的空閑后，若空閑區(qū)大小與請求區(qū)的大小相等，則將該空閑區(qū)分配給請求者，并撤消該空閑區(qū)所在表目；若大于請求區(qū)，就將該空閑區(qū)的一部分分配給請求者，然后，修改空閑區(qū)的大小和首址。417.3 分區(qū)存儲管理 7.3.5 幾種放置策略 切割空閑區(qū)有兩種方法： 從空閑區(qū)頭開始

20、 從空閑區(qū)尾開始空閑區(qū)大小50KB，首址156KB，申請34KB。一、首次適應(yīng)算法427.3 分區(qū)存儲管理 7.3.5 幾種放置策略 這種算法的實質(zhì)是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被切削成小的區(qū)，其目的是保證在以后有大的作業(yè)到來時有足夠大的空閑區(qū)來滿足請求者。 回收時，首先考察釋放區(qū)是否與系統(tǒng)中的某個空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放區(qū)作為一個空閑區(qū)按首址升序的規(guī)則插入到空閑區(qū)表適當?shù)奈恢?。一、首次適應(yīng)算法437.3 分區(qū)存儲管理 7.3.5 幾種放置策略二、最佳適應(yīng)算法 最佳適應(yīng)算法是將申請者放入與其大小最接近的空閑區(qū)中。切割后的空閑

21、區(qū)最小，若系統(tǒng)中有與申請區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請者。（首次適應(yīng)法則不一定）。447.3 分區(qū)存儲管理 7.3.5 幾種放置策略最佳適應(yīng)算法的空閑區(qū)表按空閑區(qū)大小升序方法組織。分配時，按申請的大小逐個與空閑區(qū)大小進行比較，找到一個滿足要求的空閑區(qū)，就說明它是最適合的（即最佳的）。這種算法最大的缺點是分割后的空閑區(qū)將會很小，直至無法使用，而造成浪費。二、最佳適應(yīng)算法457.3 分區(qū)存儲管理 7.3.5 幾種放置策略三、最壞適應(yīng)算法 為了克服最佳適應(yīng)算法把空閑區(qū)切割得太小的缺點，人們提出了一種最壞適應(yīng)算法，即每次分配時，總是將最大的空閑區(qū)切去一部分分配給請求者，其依據(jù)

22、是當一個很大的空閑區(qū)被切割了一部分后可能仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。467.3 分區(qū)存儲管理 7.3.5 幾種放置策略最壞適應(yīng)算法的空閑區(qū)表是按空閑區(qū)大小降序的方法組織的（從大到小的順序）。分配時總是取表中的第一個表目，若不能滿足申請者的要求，則表示系統(tǒng)中無滿足要求的空閑區(qū)，分配失?。环駝t，將從該空閑區(qū)中分配給申請者，然后修改空閑區(qū)的大小，并將它插入到空閑區(qū)表的適當位置。三、最壞適應(yīng)算法477.3 分區(qū)存儲管理 7.3.5 幾種放置策略這三種放置算法的優(yōu)劣很難區(qū)分，要具體情況具體分析。例如：某時刻系統(tǒng)中有三個空閑區(qū)其大小和首址為： (35KB，100KB)、(12KB，1

23、56KB)、(28KB，200KB)有一作業(yè)系列： (JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)487.3 分區(qū)存儲管理 7.3.5 幾種放置策略49優(yōu)點：簡單，容易實現(xiàn)。缺點：(1)固定分區(qū)面臨嚴重的“外零頭”問題，主存浪費嚴重；(2)動態(tài)分區(qū)面臨“外零頭”的拼接問題，系統(tǒng)開銷過大；7.3 分區(qū)存儲管理 7.3.6 分區(qū)存儲的優(yōu)缺點507.4 頁式存儲管理(page) 7.4.1 頁式系統(tǒng)應(yīng)解決的問題一、問題的提出 分區(qū)存儲管理的主要問題是碎片問題。 在采用分區(qū)存儲管理的系統(tǒng)中，會形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶（程序）利用而浪費。

24、造成這樣問題的主要原因是用戶程序裝入內(nèi)存時是整體裝入的，為解決這個問題，提出了分頁存儲管理技術(shù)。517.4 頁式存儲管理 7.4.1 頁式系統(tǒng)應(yīng)解決的問題二、分頁的概念 程序地址空間分成大小相等的頁面，同時把內(nèi)存也分成與頁面大小相等的塊，當一個用戶程序裝入內(nèi)存時，以頁面為單位進行分配。頁面的大小是為2n ,通常為1KB，2KB，nKB等。527.4 頁式存儲管理 7.4.1 頁式系統(tǒng)應(yīng)解決的問題頁式存儲管理要解決如下問題：1、頁式存儲管理系統(tǒng)的地址映射；2、調(diào)入策略；3、淘汰策略；4、放置策略。 537.4 頁式存儲管理 7.4.2 頁式地址變換一、頁表 頁表是頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)，它包括用

25、戶程序空間的頁面與內(nèi)存塊的對應(yīng)關(guān)系、頁面的存儲保護和存取控制方面的信息。 頁號 內(nèi)存塊號 存取控制 狀態(tài) 其它在實際的系統(tǒng)中，為了節(jié)省存儲空間，在頁表中可以省去頁號這個表目。547.4 頁式存儲管理 7.4.2 頁式地址變換557.4 頁式存儲管理 7.4.2 頁式地址變換二、虛地址結(jié)構(gòu) 虛地址是用戶程序中的邏輯地址，它包括頁號和頁內(nèi)地址（頁內(nèi)位移）。 區(qū)分頁號和頁內(nèi)地址的依椐是頁的大小，頁內(nèi)地址占虛地址的低位部分，頁號占虛地址的高位部分。 假定頁面大小1024字節(jié)，虛地址共占用2個字節(jié)(16位) 頁號 頁內(nèi)地址（位移量） P W 15 10 9 0567.4 頁式存儲管理 7.4.2 頁式地

26、址變換二、虛地址結(jié)構(gòu)577.4 頁式存儲管理 7.4.2 頁式地址變換三、頁式地址映射587.4 頁式存儲管理 7.4.2 頁式地址變換1. 虛地址（邏輯地址、程序地址）以十六進制、八進制、二進制的形式給出 將虛地址轉(zhuǎn)換成二進制的數(shù)； 按頁的大小分離出頁號和位移量； 根據(jù)題意產(chǎn)生頁表； 將位移量直接復制到內(nèi)存地址寄存器的低位部分； 以頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號，并將塊號轉(zhuǎn)換成二進制數(shù)填入地址寄存器的高位部分，從而形成內(nèi)存地址。三、頁式地址映射597.4 頁式存儲管理 7.4.2 頁式地址變換 2.虛地址以十進制數(shù)給出頁號虛地址頁大??；位移量虛地址 mod 頁大小；根據(jù)題意產(chǎn)生頁表；以

27、頁號查頁表，得到對應(yīng)頁裝入內(nèi)存的塊號；內(nèi)存地址塊號頁大小位移量；三、頁式地址映射607.4 頁式存儲管理 7.4.2 頁式地址變換例1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。虛地址0AFEH0000 1010 1111 1110P1 W010 1111 1110MR0100 1010 1111 1110 4AFEH三、頁式地址映射617.4 頁式存儲管理 7.4.2 頁式地址變換(1)虛地址1ADDH00011 01011011101P00011 ，W01011011101(2)查頁表M

28、R0010100101 010110111012ADDH三、頁式地址映射627.4 頁式存儲管理 7.4.2 頁式地址變換例2：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。三、頁式地址映射637.4 頁式存儲管理 7.4.2 頁式地址變換(1)虛地址 3412P3412 20481W3412 mod 20481364(2)查表1頁對應(yīng)塊號為9MR=9*2048+1364=19796虛地址3412的內(nèi)存地址是：19796三、頁式地址映射647.4 頁式存儲管理 7.4.2 頁式地址變換虛地址 71

29、45P7145 2048 3W7145 mod 2048 1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241三、頁式地址映射657.4 頁式存儲管理 7.4.2 頁式地址變換 在頁式存儲技術(shù)中，我們可看到每訪問一次內(nèi)存，就要做兩次訪問內(nèi)存的工作，即查頁表時要作一次訪問內(nèi)存的工作，然后是訪問程序要求訪問的內(nèi)存，這樣，存取速度降低一倍，將會影響整個系統(tǒng)的使用效率。在早期的計算機系統(tǒng)中有的采用聯(lián)想存儲器的技術(shù)來加快查表的速度，有的采用寄存器做頁表。四、采用相應(yīng)技術(shù)加快頁表的查詢速度667.4 頁式存儲管理 7.4.2 頁式地址變換 采用寄存器做頁表的典型是早期的U

30、NIX系統(tǒng)（PDP11系列計算機上）中，地址映射機構(gòu)中就有兩套頁表機構(gòu)，叫做頁地址映射寄存器組，一套用于核心態(tài)，另一套用于用戶態(tài)。每組有8對寄存器，每對寄存器中有一個地址寄存器和一個說明寄存器，地址寄存器中存放相應(yīng)頁在內(nèi)存的首地址，說明寄存器中存放對應(yīng)頁的大小，訪問方式，存儲保護等方面的信息。四、采用相應(yīng)技術(shù)加快頁表的查詢速度677.4 頁式存儲管理 7.4.3 請調(diào)策略 一、請求分頁概念一、請求分頁概念 請求分頁技術(shù)當一個用戶程序要調(diào)入內(nèi)存時，不是將該程序全部裝入內(nèi)存，而是只裝入部分頁到內(nèi)存，就可啟動程序運行，在運行的過程中，如果發(fā)現(xiàn)要運行的程序或要訪問數(shù)據(jù)不在內(nèi)存，則向系統(tǒng)發(fā)出缺頁中斷請求

31、，系統(tǒng)在處理這個中斷時，將在外存相應(yīng)的頁調(diào)入內(nèi)存，該程序繼續(xù)運行。687.4 頁式存儲管理 7.4.3 請調(diào)策略二、請求分頁要解決的問題二、請求分頁要解決的問題采用這種技術(shù)要解決以下問題：1、如何發(fā)現(xiàn)執(zhí)行的程序或訪問的數(shù)據(jù)不在內(nèi)存；2、程序或數(shù)據(jù)什么時候調(diào)入內(nèi)存，調(diào)入策略；3、當一些頁調(diào)入內(nèi)存時，內(nèi)存沒有空閑內(nèi)存時，將淘汰哪些頁，淘汰策略。697.4 頁式存儲管理 7.4.3 請調(diào)策略三、數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu) 為了實現(xiàn)請求分頁技術(shù)，頁表應(yīng)增加相應(yīng)的內(nèi)容，反映該頁是否在內(nèi)存，在外存的位置，在內(nèi)存的時間的長短等。中斷位：中斷位：0 表示該頁在內(nèi)存，1表示該頁不在內(nèi)存。引用位：引用位：0 表示最近沒

32、有進程訪問，1表示最近有進程訪問。修改位：修改位：0 該頁調(diào)入內(nèi)存后沒有修改，1表示頁調(diào)入內(nèi)存后修改過。707.4 頁式存儲管理 7.4.3 請調(diào)策略三、數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)結(jié)構(gòu)717.4 頁式存儲管理 7.4.3 請調(diào)策略1、預調(diào) 系統(tǒng)根據(jù)作業(yè)（進程）運行的情況，預測哪些頁將要運行，在其運行之前先行調(diào)入內(nèi)存，這樣在程序運行的過程中就不會出現(xiàn)缺頁中斷。這樣方法從表面上看起來很好，但系統(tǒng)無法預計系統(tǒng)中作業(yè)的運行情況，難以實現(xiàn)。2、請調(diào) 程在執(zhí)行的過程中，發(fā)現(xiàn)要執(zhí)行的程序或處理的數(shù)據(jù)不在內(nèi)存，向系統(tǒng)提出調(diào)入相應(yīng)程序的請求，系統(tǒng)響應(yīng)用戶的請求。727.4 頁式存儲管理 7.4.4 淘汰策略 置換算法 假

33、定程序p共有n頁，而系統(tǒng)分配給它的內(nèi)存只有m塊（1mn），當要索取一頁面并送入到全滿的內(nèi)存中時，必須把已在內(nèi)存中的某一頁淘汰掉。用來選擇淘汰哪一頁的規(guī)則叫做置換算法。73 最佳置換算法最佳置換算法OPTOPT 先進先出置換算法先進先出置換算法FIFOFIFO 最久未使用置換算法最久未使用置換算法LRULRU7.4 頁式存儲管理 7.4.5 幾種置換算法747.4 頁式存儲管理 7.4.5 幾種置換算法一、最佳算法一、最佳算法OPT(optimal replacement algorithm)OPT(optimal replacement algorithm)最佳算法：當要調(diào)入一新頁而必須淘汰一

34、舊頁時，所淘汰的頁是以后不再使用的，或者是以后相當長的時間內(nèi)不會使用的。 這種算法是不可能的。 原因？75例：一個程序共有5個頁面，分別為P1P5。對應(yīng)進程固定占用3塊物理內(nèi)存，程序執(zhí)行過程中依此用到的頁面為：P1，P2，P1，P5，P4，P1，P3，P4，P2，P4。P1P2P1P5P4P1P3P4P2P4111111*3*3*332222*222225*444444調(diào)入 調(diào)入 命中 調(diào)入替換 命中 替換 命中 命中 命中OPT算法實際命中次數(shù)為5次。7.4 頁式存儲管理 7.4.5 幾種置換算法767.4 頁式存儲管理 7.4.5 幾種置換算法二、先進先出算法二、先進先出算法FIFOFIF

35、O先進入內(nèi)存的頁，先退出內(nèi)存。實質(zhì)上是淘汰在內(nèi)存駐留時間最長的頁。其理由是：最早調(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。 這種算法簡單，實現(xiàn)容易。 777.4 頁式存儲管理 7.4.5 幾種置換算法P1P2P1P5P4P1P3P4P2P41111*444*4*222222*1111*4555*3333*調(diào)入 調(diào)入 命中 調(diào)入替換 替換 替換 命中 替換 替換FIFO算法實際命中次數(shù)為2次。787.4 頁式存儲管理 7.4.5 幾種置換算法三、最久未使用淘汰算法三、最久未使用淘汰算法LRU(Least RcentlyLRU(Least Rcently used algorithm)

36、used algorithm) 這種算法的實質(zhì)：當需要淘汰一頁時，選擇最長時間未使用的頁。 依據(jù)的理論是如果某頁被訪問，它可能馬上還要被訪問；相反，如果某頁長時間未被訪問，它可能最近也不可能被訪問。NRU(Not RcentlyNRU(Not Rcently used)- used)-最近不用最近不用 UNIX UNIX 頁表訪問位頁表訪問位797.4 頁式存儲管理 7.4.5 幾種置換算法P1P2P1P5P4P1P3P4P2P411111*111*22222*444*444555*333*3*調(diào)入 調(diào)入 命中 調(diào)入替換 命中 替換 命中 替換 命中LRU算法實際命中次數(shù)為4次。80其他置換算

37、法：其他置換算法：隨機算法隨機算法RAND(random algorithm)RAND(random algorithm)最不經(jīng)常使用算法最不經(jīng)常使用算法LFULFU（least frequently least frequently used algorithm)used algorithm)7.4 頁式存儲管理 7.4.5 幾種置換算法 顛簸（不恰當?shù)闹脫Q算法造成的頻繁的頁面置換）817.4 頁式存儲管理 7.4.5 幾種置換算法OPT算法（最佳置換算法）和其它算法之間的關(guān)系：1、OPT 算法無疑是效率最高的，但由于其要求知道程序?qū)淼膱?zhí)行情況，所以幾乎是不能實現(xiàn)的。2、其它算法都是根據(jù)歷

38、史去推測將來。算法的效率取決于推測的準確性。比如，在前面的例子中， OPT算法實際命中次數(shù)為5次 FIFO算法實際命中次數(shù)為2次 LRU算法實際命中次數(shù)為4次LRU算法的效率高于FIFO算法，普遍情況也是如此。 827.4 頁式存儲管理 7.4.6 頁式系統(tǒng)的存儲保護 頁式系統(tǒng)的存儲保護的方法類似于基址限長存儲保護，當?shù)刂酚成錂C構(gòu)分離出頁號和頁內(nèi)位移后。 若0頁號用戶程序的總頁數(shù)，則訪問合法，否則訪問越界。 頁式系統(tǒng)的存儲保護還包括存取控制。 在頁表中增加存取控制位，表示該頁的存取控制權(quán)限，如r表示可讀，w表示可讀可寫，e表示可執(zhí)行。 當有一程序訪問該頁時，系統(tǒng)就按存取控制位設(shè)置的權(quán)限實施存取

39、控制。837.4 頁式存儲管理7.4.7 頁式系統(tǒng)的優(yōu)缺點優(yōu)點：(1)可提供大容量的多個虛存；(2)更有效地利用了物理主存；(3)多道程序運行的程度更高了；(4)更加方便了用戶，特別大作業(yè)用戶；缺點：(1)采用動態(tài)地址變換機構(gòu),增加了計算機的成本，降低了處理機的速度；(2)必須以部分存儲空間來存放各種表格，且需要花費一部分處理機時間來建立和管理這些表；(3)雖然分區(qū)間的零頭問題消除了，但是出現(xiàn)了塊內(nèi)的零頭問題。(4)純分頁系統(tǒng)仍然需要全部裝入主存。(5)在請求頁式系統(tǒng)中，為處理頁面中斷增加了系統(tǒng)開銷。847.5 段式系統(tǒng)（segment） 一個用戶程序往往由幾個程序段（主程序、子程序和函數(shù)）所

40、組成，當一個程序裝入內(nèi)存時，按段進行分配，每個段的大小是不相等的。程序地址的組成：S：W例:S1 ：XXXXS2 ：XXXXS3 ：XXXX857.5 段式系統(tǒng)保護位段號S段長L中斷I引用位改變位RWEA段首址b擴充段表867.5 段式系統(tǒng)優(yōu)點：(1)便于程序模塊化處理；(2)便于處理變化的數(shù)據(jù)結(jié)構(gòu)；(3)便于動態(tài)鏈接動態(tài)鏈接；(4)便于共享分段共享分段；(5)便于實現(xiàn)多段式虛擬存儲，“擴充”主存容量；缺點：(1)和頁式系統(tǒng)一樣，處理機要為地址變換花費時間，給中表格需要附加存儲，使操作系統(tǒng)復雜化；(2)為了滿足分段的動態(tài)增長和減少外零頭，需要采用拼接手段；(3)在輔存中管理不定長度的分段困難較

41、多；(4)分段的最大尺寸受到主存可用空間的限制。段式系統(tǒng)的優(yōu)缺點877.6段頁式系統(tǒng)段頁式系統(tǒng)：在段式系統(tǒng)中，若段內(nèi)分頁，稱為段頁式系統(tǒng)。887.6 UNIX系統(tǒng)存儲管理7.6.1 概述 UNIX系統(tǒng)的早期版本采用純分頁存儲管理，進程的存儲映象可以在內(nèi)存和交換區(qū)之間傳遞，稱為對換。 在目前的一些UNIX系統(tǒng)中，采用請求分頁存儲管理，也就是采用虛擬存儲技術(shù)，稱為請求調(diào)頁。 UNIX SYSTEM 采用請求調(diào)頁（請求分頁）。以后的UNIX系統(tǒng)的各種版本均采用了請求調(diào)頁技術(shù)。邏輯地址分區(qū)(segment,section)，因此實際是典型的段頁式存儲管理。897.6.2 對換空間的管理系統(tǒng)盤的結(jié)構(gòu)：7

42、.6 UNIX系統(tǒng)存儲管理907.6.2 對換空間的管理對換存儲管理的數(shù)據(jù)結(jié)構(gòu)系統(tǒng)設(shè)置了兩個相同的結(jié)構(gòu)： coremap 內(nèi)存空閑區(qū)表 swapmap 對換區(qū)空閑區(qū)表空閑區(qū)的分配采用最佳適應(yīng)法。程序是：malloc(map,size)空閑區(qū)回收程序： mfree(map,size,aa) map:內(nèi)存（或?qū)Q區(qū)）；size:大小 ； aa：釋放區(qū)首址空閑區(qū)首址空閑區(qū)大小123 50300 1500 0 7.6 UNIX系統(tǒng)存儲管理917.6 UNIX系統(tǒng)存儲管理 7.6.3 對換進程 對換進程就是0號進程，它一個永遠處于核心態(tài)的進程。其任務(wù)是將進程的映象在內(nèi)存和對換區(qū)之間傳遞。927.6 UN

43、IX系統(tǒng)存儲管理 7.6.3 對換進程（一）進程換入 當內(nèi)存空閑時，0號進程將對換區(qū)中處于就緒狀態(tài)的進程的映象調(diào)入內(nèi)存，直到內(nèi)存滿，或者是對換區(qū)中已經(jīng)沒有處于就緒狀態(tài)的進程。 調(diào)入就緒進程的依據(jù)是進程在對換區(qū)中駐留的時間，每次調(diào)入一個在對換區(qū)中駐留時間最長的進程映象進入內(nèi)存。937.6 UNIX系統(tǒng)存儲管理 7.6.3 對換進程（二）進程換出 當內(nèi)存空間不足時，0號進程將內(nèi)存中的某些進程換到對換區(qū)。 不能換出的進程是核心態(tài)的進程（UNIX核心）、處于創(chuàng)建狀態(tài)的進程、上鎖的進程，在內(nèi)存中駐留時間不足兩分鈔鐘的就緒進程。 換出的順序是：處于睡眠狀態(tài)的進程、暫停狀態(tài)的進程。 若無以上這兩類進程，就是

44、處于就緒狀態(tài)的進程。 按就緒狀態(tài)的進程在內(nèi)存中駐留時間從長到短的順序依次調(diào)出內(nèi)存，直到內(nèi)存中無進程可調(diào)出為止。 947.6 UNIX系統(tǒng)存儲管理 7.6.4 請求調(diào)頁數(shù)據(jù)結(jié)構(gòu)進程映象的結(jié)構(gòu)： U區(qū)、正文區(qū)、數(shù)據(jù)區(qū)、用戶棧區(qū)。 其中U區(qū)的大小是固定的，其它的各區(qū)的大小不是固定的。Page103,105957.6 UNIX系統(tǒng)存儲管理 7.6.4 請求調(diào)頁數(shù)據(jù)結(jié)構(gòu)967.6 UNIX系統(tǒng)存儲管理 7.6.4 請求調(diào)頁數(shù)據(jù)結(jié)構(gòu)（一）進程區(qū)表 在UNIX system 中，一個進程可以有正文區(qū)、數(shù)據(jù)區(qū)、用戶棧區(qū)和U區(qū)。其中U區(qū)只有處于運行狀態(tài)的進程才有，其它狀態(tài)的進程沒有U區(qū)。每個區(qū)又分成若干個頁。所

45、以，每個區(qū)有一個頁表。977.6 UNIX系統(tǒng)存儲管理 7.6.4 請求調(diào)頁數(shù)據(jù)結(jié)構(gòu)（二）頁和頁表 將用戶的程序空間分成大小相等的單位，稱為頁。并把內(nèi)存空間也分成與之相等的塊。頁的大小為512字節(jié)。剛好與磁盤的物理塊大小相等。 頁表的格式如下：987.6 UNIX系統(tǒng)存儲管理 7.6.4 請求調(diào)頁數(shù)據(jù)結(jié)構(gòu)塊號：內(nèi)存塊號 年齡：該塊在工作集中駐留的時間修改：表示該頁調(diào)入內(nèi)存后修改過，置1，否則為0；訪問：該頁調(diào)入內(nèi)存后，被訪問過；有效：為1表示該頁在內(nèi)存，否則不在內(nèi)存；保護：該頁的存儲保護信息；對換設(shè)備：指明對換設(shè)備；磁盤塊號：該頁在對換設(shè)備上的磁盤物理塊號。進程頻繁訪問的頁面集合997.6 U

46、NIX系統(tǒng)存儲管理 7.6.5 頁地址映射pw31 10 9 06843210=000000000000000100001011010100002UNIX虛地址結(jié)構(gòu):1007.6 UNIX系統(tǒng)存儲管理 7.6.6 頁面錯（缺頁中斷）在在UNIX系統(tǒng)中產(chǎn)生頁面錯有兩種情況：系統(tǒng)中產(chǎn)生頁面錯有兩種情況：1.進程企圖訪問虛存空間范圍之外的頁面，即段違例，在這種情況下，核心向違例的進程發(fā)送一個“段違例”的軟中斷。（這是一般操作系統(tǒng)中頁面錯的處理方法）。2.進程企圖訪問一個有效位為0的頁（該頁不在內(nèi)存），這時將產(chǎn)生一個有效位錯的中斷（類似于一般OS中的缺頁中斷）。核心處理該中斷時，將所缺的頁面調(diào)入內(nèi)存。

47、1017.6 UNIX系統(tǒng)存儲管理 7.6.6 頁面錯（缺頁中斷）偷頁（頁面淘汰）進程 當有進程需要調(diào)入一些頁面時，又沒有內(nèi)存空間時，核心將按某種策略將系統(tǒng)中的一些頁面調(diào)出內(nèi)存，在一般的OS中稱為頁面淘汰，在UNIX中稱為偷頁。1.選擇淘汰的頁；2.選中了淘汰頁后，執(zhí)行淘汰，若修改位為1，表示該頁調(diào)入內(nèi)存后已經(jīng)修改，淘汰時，要將要淘汰的頁面寫到相應(yīng)的磁盤塊。若修改位為0，表示該頁面調(diào)入內(nèi)存后沒有修改過，只是把該頁置為空。102典型習題：(1)存儲器管理的主要功能有主存儲器的分配和管理、地址映射、 ( )和( )。（電子科技大學 2005年）(2)在某系統(tǒng)中采用基址、限長寄存器的方法來保護存儲信息，判斷是否越界的判別式為( )。 （華中科技大學 2005年）A.0=被訪問的邏輯地址限長寄存器的內(nèi)容B.0=被訪問的邏輯地址=限長寄存器的內(nèi)容C.0=被訪問的物理地址限長寄存器的內(nèi)容D.0=被訪問的物理地址=限長寄存器的內(nèi)容(3)一個虛擬存儲器系統(tǒng)中，設(shè)主存的容量是16MB,輔存的容量是1GB，而地址寄存器的位數(shù)為32位。在這樣的系統(tǒng)中，虛存的最大容量是( )。(南昌大學 2005年) A.1G B.1