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

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

3、程 (2) 主存分配 按照一定的算法把某一空閑的主存區(qū)分配給作業(yè)或進程。 (3) 存儲保護 保證用戶程序(或進程映象)在各自的存儲區(qū)域內(nèi)操作 ，互不干擾。 (4) 提供虛擬存儲技術(shù) 使用戶程序的大小和結(jié)構(gòu)不受主存容量和結(jié)構(gòu)的限制，即使在用戶程序比實際主存容量還要大的情況下，程序也能正確運行,8,7.2存儲管理的功能 7.2.1 地址映射,一、什么是地址映射 地址映射 將程序地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址映射。有時也稱為地址重定位 。,9,7.2存儲管理的功能 7.2.1 地址映射,二、地址映射方式 地址映射的功能就是要建立虛實地址的對應(yīng)關(guān)系，實現(xiàn)地址映射有三種方式：

4、1.編程或編譯時確定地址映射關(guān)系 2.靜態(tài)地址映射 3.動態(tài)地址映射,10,7.2存儲管理的功能 7.2.1 地址映射,1. 編程或編譯時確定地址映射關(guān)系 編程時確定虛實地址的關(guān)系是指在用機器指令編程時，程序員直接按物理內(nèi)存地址編程，這種程序在系統(tǒng)中是不能做任何移動的，否則就會出錯。,11,7.2存儲管理的功能 7.2.1 地址映射,2.靜態(tài)地址映射 靜態(tài)地址映射是在程序裝入內(nèi)存時完成從邏輯地址到物理地址的轉(zhuǎn)換的。 在一些早期的系統(tǒng)中都有一個裝入程序（加載程序），它負責(zé)將用戶程序裝入系統(tǒng)，并將用戶程序中使用的訪問內(nèi)存的邏輯地址轉(zhuǎn)換成物理地址。如左圖所示。 評價: 優(yōu)點是實現(xiàn)簡單，不要硬件的支持

5、。 缺點是程序一旦裝入內(nèi)存，移動就比較困難。有時間上的浪費。在程序裝入內(nèi)存時要將所有訪問內(nèi)存的地址轉(zhuǎn)換成物理地址。,12,7.2存儲管理的功能 7.2.1 地址映射 2.靜態(tài)地址映射,13,7.2存儲管理的功能 7.2.1 地址映射,3.動態(tài)地址映射 動態(tài)地址映射是在程序執(zhí)行時由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的。 系統(tǒng)中設(shè)置了重定位寄存器。,14,7.2存儲管理的功能 7.2.1 地址映射 3.動態(tài)地址映射,動態(tài)地址映射是由硬件地執(zhí)行時完成的，程序中不執(zhí)行的程序就不做地址映射的工作，這樣節(jié)省了CPU的時間 。 重定位寄存器的內(nèi)容由操作系統(tǒng)用特權(quán)指令來設(shè)置，比較靈活。 實現(xiàn)動態(tài)地址映射必

6、須有硬件的支持，并有一定的執(zhí)行時間延遲?，F(xiàn)代計算機系統(tǒng)中都采用動態(tài)地址映射技術(shù)。,15,7.2存儲管理的功能 7.2.1 地址映射 3.動態(tài)地址映射,動態(tài)地址映射技術(shù)能滿足以下目標： （1）具有給一個用戶程序任意分配內(nèi)存區(qū)的能力； （2）可實現(xiàn)虛擬存儲； （3）具有重新分配的能力 （4）對于一個用戶程序，可以分配到多個不同的存儲區(qū),16,7.2.3 程序的邏輯組織,見7.1 2.程序的邏輯結(jié)構(gòu),17,7.2.3 內(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)存中

7、放置信息的區(qū)域（或位置），即如何在若干個空閑區(qū)中選擇一個或幾個空閑區(qū)的原則； 2、調(diào)入策略 決定信息裝入內(nèi)存的時機，有兩種：在用戶請求時調(diào)入，稱為請調(diào)；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行前預(yù)先調(diào)入內(nèi)存，稱為預(yù)調(diào) ； 3、淘汰策略 當(dāng)內(nèi)存不足時，決定將某些信息調(diào)出內(nèi)存的策略 。,18,7.2.4 提供虛存1、問題的提出,1、問題的提出 物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是有限的。 用戶程序結(jié)構(gòu)： 一維空間 一個用戶程序就是一個程序，并且程序和數(shù)據(jù)是不分離的； 二維空間 程序由主程序和若干個子程序（或函數(shù)）組成，并且程序 與數(shù)據(jù)是分離的； n維空間 即一個大型程序，由一個主模塊和

8、多個子模塊組成，其中 ，各子模塊又由主程序和子程序（或函數(shù)）組成。 用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時候要大得多。,19,7.2.4 提供虛存1、問題的提出,如何將與物理內(nèi)存結(jié)構(gòu)不同，且大于物理內(nèi)存容量的用戶程序裝入運行？這就是提出研究虛擬存儲器的原因，或稱為虛擬存儲技術(shù)發(fā)展的原動力。,20,7.2.4 提供虛存2. 虛擬存儲器概念,虛擬存儲器 為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)稱為虛擬存儲器，或稱虛擬存儲技術(shù)。 它是用戶編程時所使用的一種用戶思維中的存儲器，它可以是任何結(jié)構(gòu)（一維線性空間、二維空間、乃至n維空間），并沒有容量的限制。 現(xiàn)代計算機操

9、作系統(tǒng)都采用了這種技術(shù)，使得用戶編程序時不需要考慮物理內(nèi)存的結(jié)構(gòu)和容量，極大地方便了用戶。 虛擬存儲器需要大容量的外存儲器的支持，或稱物資基礎(chǔ)。,21,7.2.5 存儲保護,在多道程序設(shè)計的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個用戶程序同時存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？這就是存儲保護所要解決的問題。 常用的存儲保護有兩種。,22,7.2.5 存儲保護 1.上下界保護,下界寄存器 存放程序裝入內(nèi)存后的開始地址（首址） 上界寄存器 存放程序裝入內(nèi)存后的末地址 判別式： 下界寄存器 物理地址 上界寄存器,23,7.2.5 存儲保護 1.上下界保護,例： 有一程序裝入內(nèi)存的首地

10、址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。 下界寄存器：500 上界寄存器：1500 邏輯地址裝入內(nèi)存的首地 物理地址 1、500500 1000 500 1000 1500 2、345500 845 500 845 1500 3、1000500 1500 500 1500 1500,24,7.2.5 存儲保護 2.基址、限長寄存器保護,例： 有一程序裝入內(nèi)存的首地址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。 下界寄存器：500 上界寄存器：1500 1、 500 500 1000 2、 500 345 1000 3、 500

11、1000 1000,25,7.2.5 存儲保護3.兩種存儲保護技術(shù)的區(qū)別,區(qū)別： 1、寄存器的設(shè)置不同； 2、判別式中用的判別條件不同 上下界寄存器保護法用的是物理地址 基址、限長寄存器保護法用的是程序的邏輯地址 對于合法的訪問地址這兩者的效率是相同的，對不合法的訪問地址來說，上下界存儲保護浪費的CPU時間相對來說要多些。 在7.4 頁式存儲管理中將介紹其存儲保護機制。,26,7.3 分區(qū)存儲管理7.3.1 概述,分區(qū)存儲管理是滿足多道程序設(shè)計的最簡單的一種存儲管理方法，它允許多個用戶程序同時存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。 最早期的分區(qū)存儲管理采用固定分區(qū)的方法，把內(nèi)存空間分成若干個大小不等

12、的區(qū)域，稱為分區(qū)。每個用戶程序（作業(yè)、進程）調(diào)入內(nèi)存后，占用其中一個分區(qū)，程序運行完成后釋放該分區(qū)。 這種存儲管理的方法的主要問題是內(nèi)存使用效率極低，很快就被淘汰了。,27,7.3 分區(qū)存儲管理7.3.1 概述,動態(tài)分區(qū)存儲管理技術(shù) 系統(tǒng)生成后，操作系統(tǒng)占用內(nèi)存的一部分，一般在物理內(nèi)存的開始處，比如，一個操作系統(tǒng)占20KB，裝入系統(tǒng)后占用020KB的內(nèi)存空間，剩下的部分作為一個空閑區(qū)，當(dāng)一個用戶程序（作業(yè)、進程）調(diào)入內(nèi)存時，把這個空閑區(qū)的低地址部分的區(qū)域分配給它，如圖所示。,28,7.3 分區(qū)存儲管理7.3.1 概述,當(dāng)有作業(yè)完成后釋放所占用的存儲區(qū)。 在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的

13、不連續(xù)的存儲區(qū)，稱主空閑。,29,7.3 分區(qū)存儲管理7.3.1 概述,分區(qū)存儲管理技術(shù)的實現(xiàn)： 1、地址映射 2、動態(tài)存儲管理的機構(gòu)（數(shù)據(jù)結(jié)構(gòu)） 3、分區(qū)的分配和回收 4、三種基本的放置策略,30,7.3 分區(qū)存儲管理 7.3.2 用基地址寄存器實現(xiàn)動態(tài)地址映射,在這種存儲管理技術(shù)中，系現(xiàn)設(shè)置一個專用寄存器，稱為基地址寄存器，當(dāng)一個進程（或程序、作業(yè)）被調(diào)度運行時，系統(tǒng)首先從PCB中取出該進程的首地址裝入基地址寄存器中，在該進程運行的過程中實現(xiàn)動態(tài)地址映射。,31,7.3 分區(qū)存儲管理 7.3.3 分區(qū)分配機構(gòu),分區(qū)存儲管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表、空閑區(qū)隊列兩種。其形式如圖所示。,32

14、,7.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收,內(nèi)存分配程序包括分配一個內(nèi)存塊（分區(qū)）和釋放一個內(nèi)存塊（分區(qū)）兩個函數(shù)，當(dāng)進程需要一個大小為size的內(nèi)存時，可以通過系統(tǒng)調(diào)用向系統(tǒng)申請。 調(diào)用形式：request(size) 返回：成功為分區(qū)的首地址，失敗為0。 進程釋放一個分區(qū)時，調(diào)用： release(釋放區(qū)首地址） 返回：無,33,7.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收,一、分配算法 教材上的p156 的分配算法是以空閑內(nèi)存隊列的數(shù)據(jù)結(jié)構(gòu)進行分配。介紹空閑區(qū)表數(shù)據(jù)結(jié)構(gòu)的分配算法。 注： 1、分配算法中切割空閑區(qū)是從低地址開始的，例如，一個空閑區(qū)大小是100KB，首址是2

15、30KB，一申請者要求80KB，分配時將從230KB開始的80KB分配給申請者，剩下的部分仍作為一個空閑區(qū)，其首址是310KB，大小是20KB。 2、門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值，就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請者。,34,7.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收,35,7.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收,二、回收算法 當(dāng)一個進程（或程序）釋放某內(nèi)存區(qū)時，要調(diào)用存儲區(qū)釋放算法release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空閑區(qū)表（或隊列）中的適當(dāng)位置。 空閑釋放區(qū)與空閑區(qū)相

16、鄰有四種情況。 試用C語言寫出動態(tài)分區(qū)的回收算法。,36,7.3 分區(qū)存儲管理 7.3.4 分區(qū)的分配與回收,A、將r合并到f1，f1.addr;f1.size+r.size=f.size B、將r合并到f2, r.addr;r.size+r.size=f2.size C、f1、r、f2 合并到f1, f1.addr; f1.size+r.size+f2.size=f1.size 撤消f2空閑區(qū) D、r作為一個空閑區(qū)，并插入到空閑區(qū)表的適當(dāng)位置。,37,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略,分區(qū)分配和回收是對空閑區(qū)表（或空閑區(qū)隊列）數(shù)據(jù)結(jié)構(gòu)進行操作，空閑區(qū)表的組織有兩種方法： 1、按

17、空閑區(qū)大小的升序（降序）組織； 2、按空閑區(qū)首址升序（降序）組織。 根據(jù)空閑區(qū)表組織的方法的不同，有不同的放置策略，它們是最佳適應(yīng)算法、首次適應(yīng)算法和最壞適應(yīng)算法三種。,38,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略,一、首次適應(yīng)算法 首次適應(yīng)算法的表是按空閑區(qū)首址升序的（即空閑區(qū)表是按空閑區(qū)首址從小到大）方法組織的。,39,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略 一、首次適應(yīng)算法,分配時從表首開始，以請求內(nèi)存區(qū)的大小逐個與空閑區(qū)進行比較，找到第一個滿足要求的空閑后，若空閑區(qū)大小與請求區(qū)的大小相等，則將該空閑區(qū)分配給請求者，并撤消該空閑區(qū)所在表目；若大于請求區(qū)，就將該空閑區(qū)的一部

18、分分配給請求者，然后，修改空閑區(qū)的大小和首址。,40,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略 一、首次適應(yīng)算法,切割空閑區(qū)有兩種方法： 從空閑區(qū)頭開始 從空閑區(qū)尾開始 空閑區(qū)大小50KB，首址156KB，申請34KB。,41,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略 一、首次適應(yīng)算法,這種算法的實質(zhì)是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被切削成小的區(qū)，其目的是保證在以有有大的作業(yè)的到來有足夠大的空閑區(qū)來滿足請求者。 回收時，首先考察釋放區(qū)是否與系統(tǒng)中的某個空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放區(qū)作為一個空閑區(qū)按首址升序的規(guī)則插入到空

19、閑區(qū)表適當(dāng)?shù)奈恢谩?42,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略,二、最佳適應(yīng)算法 最佳適應(yīng)算法是將申請者放入與其大小最接近的空閑區(qū)中。切割后的空閑區(qū)最小，若系統(tǒng)中有與申請區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請者。（首次適應(yīng)法則不一定）。,43,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略 二、最佳適應(yīng)算法,最佳適應(yīng)算法的空閑區(qū)表按空閑區(qū)大小升序方法組織。 分配時，按申請的大小逐個與空閑區(qū)大小進行比較，找到一個滿足要求的空閑區(qū)，就說明它是最適合的（即最佳的）。 這種算法最大的缺點是分割后的空閑區(qū)將會很小，直至無法使用，而造成浪費。,44,7.3 分區(qū)存儲管理 7.3

20、.5 幾種放置策略,三、最壞適應(yīng)算法 為了克服最佳適應(yīng)算法把空閑區(qū)切割得大小的缺點，人們提出了一種最壞適應(yīng)算法，即每次分配時，總是將最大的空閑區(qū)切去一部分分配給請求者，其依據(jù)是當(dāng)一個很大的空閑區(qū)被切割了一部分后可能仍是一個較大的空閑區(qū)。避免了空閑區(qū)越分越小的問題。,45,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略 三、最壞適應(yīng)算法,最壞適應(yīng)算法的空閑區(qū)表是按空閑區(qū)大小降序的方法組織的（從大到小的順序）。 分配時總是取表中的第一個表目，若不能滿足申請者的要求，則表示系統(tǒng)中無滿足要求的空閑區(qū)，分配失?。环駝t，將從該空閑區(qū)中分配給申請者，然后修改空閑區(qū)的大小，并將它插入到空閑區(qū)表的適當(dāng)位置。,4

21、6,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略,這三種放置算法的優(yōu)劣很難區(qū)分，要具體情況具體分析。 例如：某時刻系統(tǒng)中有三個空閑區(qū) 其大小和首址為： (35KB，100KB)、(12KB，156KB)、(28KB，200KB) 有一作業(yè)系列： (JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB),47,7.3 分區(qū)存儲管理 7.3.5 幾種放置策略,48,7.4 頁式存儲管理7.4.1 頁式系統(tǒng)應(yīng)解決的問題,一、問題的提出 分區(qū)存儲管理的主要問題是碎片問題。 在采用分區(qū)存儲管理的系統(tǒng)中，會形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶（程序）利用而浪費。

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

23、戶程序空間的頁面與內(nèi)存塊的對應(yīng)關(guān)系、頁面的存儲保護和存取控制方面的信息。 頁號 內(nèi)存塊號 存取控制 狀態(tài) 其它 在實際的系統(tǒng)中，為了節(jié)省存儲空間，在頁表中可以省去頁號這個表目。,52,7.4.2 頁式地址變換,53,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 0,54,7.4.2 頁式地址變換 二、虛地址結(jié)構(gòu),55,7.4.2

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

25、存的塊號 內(nèi)存地址塊號頁大小位移量,58,7.4.2 頁式地址變換 三、頁式地址映射,例1：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。 虛地址0AFEH 0000 1010 1111 1110 P1 W010 1111 1110 MR0100 1010 1111 1110 4AFEH,59,7.4.2 頁式地址變換 三、頁式地址映射,虛地址1ADDH 0001 1010 1101 1101 P3 W010 1101 1101 MR0010 1010 1101 11012ADDH,60,7.4

26、.2 頁式地址變換 三、頁式地址映射,例2：有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。,61,7.4.2 頁式地址變換 三、頁式地址映射,虛地址 3412 P3412 2048 1 W 3412 mod 2048 1364 MR=9*2048+1364=19796 虛地址3412的內(nèi)存地址 是：19796,62,7.4.2 頁式地址變換 三、頁式地址映射,虛地址 7145 P7145 2048 3 W7145 mod 2048 1001 MR=5*2048+1001=11241 虛地址7145

27、的內(nèi)存地址是：11241,63,7.4.2 頁式地址變換,四、采用相應(yīng)技術(shù)加快頁表的查詢速度 在頁式存儲技術(shù)中，我們可看到每訪問一次內(nèi)存，就要做兩次訪問內(nèi)存的工作，即，查頁表時要作一次訪問內(nèi)存的工作，然后是訪問程序要求訪問的內(nèi)存，這樣，存取速度降低一倍，將會影響整個系統(tǒng)的使用效率。在早期的計算機系統(tǒng)中有的采用聯(lián)想存儲器的技術(shù)來加快查表的速度，有的采用寄存器做頁表。,64,7.4.2 頁式地址變換 四、采用相應(yīng)技術(shù)加快頁表的查詢速度,采用寄存器做頁表的典型是早期的UNIX系統(tǒng)（PDP11系統(tǒng)計算機上）中，地址映射機構(gòu)中就有兩套頁表機構(gòu)，叫做頁地址映射寄存器組，一套用于核心態(tài)，另一套用于用戶態(tài)。每

28、組有8對寄存器，每對寄存器中有一個地址寄存器和一個說明寄存器，地址寄存器中存放相應(yīng)頁在內(nèi)存的首地址，說明寄存器中存放對應(yīng)頁的大小，訪問方式，存儲保護等方面的信息。,65,7.4.3 請調(diào)策略,一、問題的提出 在頁式存儲管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，換句話說，當(dāng)一個用戶程序的頁數(shù)大于當(dāng)前總空閑內(nèi)存塊數(shù)時，系統(tǒng)就不能將該程序裝入運行。即用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。為了解決這個問題，人們提出請求分頁存儲管理技術(shù)。,66,7.4.3 請調(diào)策略,二、請求分頁概念 請求分頁技術(shù)當(dāng)一個用戶程序要調(diào)入內(nèi)存時，不是將該程序全部裝入內(nèi)存，而是只裝入部分頁到內(nèi)存，就可啟動程序運行，在運行的過

29、程中，如果發(fā)現(xiàn)要運行的程序或要訪問數(shù)據(jù)不在內(nèi)存，則向系統(tǒng)發(fā)出缺頁中斷請求，系統(tǒng)在處理這個中斷時，將在外存相應(yīng)的頁調(diào)入內(nèi)存，該程序繼續(xù)運行。,67,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、當(dāng)一些頁調(diào)入內(nèi)存時，內(nèi)存沒有空閑內(nèi)存時，將淘汰哪些頁，淘汰策略。,68,7.4.3 請調(diào)策略,四、數(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 表示最近沒有

30、進程訪問 1示最近有進程訪問 修改位：0 該頁調(diào)入內(nèi)存后沒有修改 1頁調(diào)入內(nèi)存后修改過 在請求分頁技術(shù)中，頁表中的頁號是不能省略的，為什么？,69,7.4.3 請調(diào)策略四、數(shù)據(jù)結(jié)構(gòu),70,7.4.3 請調(diào)策略,五. 調(diào)入策略 1、預(yù)調(diào) 系統(tǒng)根據(jù)作業(yè)（進程）運行的情況，預(yù)測哪些頁將要運行，在其運行之前先行調(diào)入內(nèi)存，這樣在程序運行的過程中就不會出現(xiàn)缺頁中斷。這樣方法從表面上看起來很好，但系統(tǒng)無法預(yù)計系統(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)用戶的請求。,71,7.4.4 淘汰策略,一、置換算法 當(dāng)要索

31、取一頁面并送入到全滿的內(nèi)存中時，必須把已在內(nèi)存中的某一頁淘汰掉。用來選擇淘汰哪一頁的規(guī)則叫做置算法。 二、顛簸,72,一、最佳算法 假定程序p共有n頁，而系統(tǒng)分配給它的內(nèi)存只有m塊（1mn），并且以作業(yè)在執(zhí)行的過程中頁面置換的頻率的高低來衡量算法的優(yōu)劣。 訪問的頁在內(nèi)存，稱訪問成功，否則為失敗。 a=s+f a:訪問的總次數(shù) s：訪問成功的次數(shù) f：訪問失敗的次數(shù),7.4.5 幾種置換算法,73,7.4.5 幾種置換算法,缺頁中斷率f, = f/a 則有： f f(r,m,p） 最佳算法是指對于任何m和p，r:調(diào)度算法 有ff(r,m,p）最小。 最佳算法：當(dāng)要調(diào)入一新頁而必須淘汰一舊頁時，所

32、淘汰的頁是以后不再使用的，或者是以后相當(dāng)長的時間內(nèi)不會使用的。這種算法是不可能的。 原因？,74,7.4.5 幾種置換算法,二、先進先出算法 先進入內(nèi)存的頁，先退出內(nèi)存。 實質(zhì)上是淘汰在內(nèi)存駐留時間最長的頁。 其理由是：最早調(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。 這種算法簡單，實現(xiàn)容易。 具體實現(xiàn)的方法留給大家,75,7.4.5 幾種置換算法,三、最久未使用淘汰算法（lRU算法） 這種算法的實質(zhì)：當(dāng)需要淘汰一頁時，選擇最長時間未使用的頁。 依據(jù)的理論是如果某頁被訪問，它可能馬上還要被訪問；相反，如果某頁長時間未被訪問，它可能最近也不可能被訪問。 算法的實現(xiàn)（軟件）：設(shè)置一個活動頁

33、面棧，當(dāng)訪問某頁時，將此頁號壓入棧頂，然后，考察棧內(nèi)是否有與此頁面相同的頁號，若有則抽出。淘汰一頁時，總是從棧底抽出一個頁號，它就是最久未使用的。,76,7.4.6 頁式系統(tǒng)的存儲保護,頁式系統(tǒng)的存儲保護的方法類似于基址限長存儲保護，當(dāng)?shù)刂酚成錂C構(gòu)分離出頁號和頁內(nèi)位移后。 若0頁號用戶程序的總頁數(shù)，則訪問合法，否則訪問越界。 頁式系統(tǒng)的存儲保護還包括存取控制。 在頁表中增加存取控制位，表示該頁的存取控制權(quán)限，如r表示可讀，w表示可讀可寫，e表示可執(zhí)行。 當(dāng)有一程序訪問該頁時，系統(tǒng)就按存取控制位設(shè)置的權(quán)限實施存取控制。,77,7.5 段式系統(tǒng),一個用戶程序往往由幾個程序段（主程序、子程序和函數(shù)）

34、所組成，當(dāng)一個程序裝入內(nèi)存時，按段進行分配，每個段的大小是不相等的。 程序地址的組成：S：W 例: S1：XXXX S2：XXXX S3；XXXX,78,7.5 段式系統(tǒng),79,7.5 段式系統(tǒng),段頁式系統(tǒng)： 在段式系統(tǒng)中，若段內(nèi)分頁，稱為段頁式系統(tǒng)。 目前流行的UNIX系統(tǒng)采用這種存儲管理的方式，一個進程的圖象分為U區(qū)、共享正文區(qū)、用戶棧區(qū)和數(shù)據(jù)區(qū)，各進程的各個區(qū)的大小是不相等的，只有U區(qū)的大小是相等的。這里的區(qū)類似于段。每個段又分成大小相等的頁，內(nèi)存的分配是以頁為單位的。 因此，在UNIX系統(tǒng)中存儲管理（上下文，context）機構(gòu)包括區(qū)表和頁表，其結(jié)構(gòu)參見7.6.4。,80,7.6 UN

35、IX系統(tǒng)存儲管理,7.1 概述 UNIX系統(tǒng)的早期版本采用分頁存儲管理，進程的存儲映象可以在內(nèi)存和交換區(qū)之間傳遞，稱為對換； UNIX 第6、7版采用對換。 在目前的一些UNIX系統(tǒng)中，采用請求分頁存儲管理，也就是采用虛擬存儲技術(shù)，稱為請求調(diào)頁。 UNIX SYSTEM 采用請求調(diào)頁（請求分頁）。以后的UNIX系統(tǒng)的各種版本均采用了請求調(diào)頁技術(shù)。,81,7.6.2 對換空間的管理,系統(tǒng)盤的結(jié)構(gòu)：,82,7.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ū)首址,83,7.6.3 對換進程,對換進程就是0號進程，它一個永遠處于核心態(tài)的進程。其任務(wù)是將進程的映象在內(nèi)存和對換區(qū)之間傳遞。,84,7.6.3 對換進程,（一）進程換入 當(dāng)內(nèi)存空閑時，0號進程將對換區(qū)中處于就緒狀態(tài)的進程的映象調(diào)入內(nèi)存，直到內(nèi)存滿，或者是對換區(qū)中已經(jīng)沒