計(jì)算機(jī)存儲器的層次結(jié)構(gòu)-文檔資料

1、2003.3.113.1.2 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)第一層第二層第三層第四層第五層每級存儲器的性能參數(shù)可以表示為每級存儲器的性能參數(shù)可以表示為TiTi，SiSi，CiCi。存儲系統(tǒng)的。存儲系統(tǒng)的性能可表示為：性能可表示為：TiTi+1TiTi+1；SiSi+1SiCi+1CiCi+1。速速 度度 提提 高高容容 量量 增增 加加 通用寄存器通用寄存器M1高速緩沖存儲器高速緩沖存儲器M2 主存儲器主存儲器M3 脫機(jī)大容量存儲器脫機(jī)大容量存儲器M5 輔助存儲器輔助存儲器M4 2003.3.12 Data location Data identifacation Data replacem

2、ent Data Write policy2003.3.13地址映象與變換(P174)基本術(shù)語：基本術(shù)語： 邏輯地址邏輯地址（又稱為相對地址相對地址、虛地址虛地址）是程序員在編寫和編譯一個程序模塊時(shí)分配指令和數(shù)據(jù)的空間單位序號，總是從0開始（可以按字節(jié)編址、按CPU字編址等）。邏輯地址的取值范圍稱為邏輯地址空間邏輯地址空間、虛空間虛空間或虛存虛存。 物理地址物理地址（又稱為絕對地址絕對地址、實(shí)地址實(shí)地址）是任一級存儲器為全部存儲單元分配的序號。物理地址的取值范圍稱為物理地址空間物理地址空間、實(shí)空間實(shí)空間或?qū)嵈鎸?shí)存。 從M1到Mn各層都有自己的物理地址空間，而對當(dāng)前執(zhí)行的程序模塊來說，邏輯地址空

3、間只有一個。 地址映象地址映象方式指的是虛頁集合與實(shí)頁集合的對應(yīng)規(guī)則，或者說是約束關(guān)系。 地址變換地址變換（又叫虛實(shí)變換虛實(shí)變換）指邏輯地址到物理地址的變換過程或者算法。 頁失效頁失效指當(dāng)前被訪問存儲級中沒有所需的信息，也就是不命中現(xiàn)象。 實(shí)頁爭用實(shí)頁爭用又叫實(shí)頁沖突實(shí)頁沖突，指虛頁調(diào)入時(shí)，根據(jù)地址映象方式劃定的實(shí)空間范圍內(nèi)已沒有空閑實(shí)頁的狀況。2003.3.14存儲層次的管理方式(P147) 根據(jù)程序的局部化性質(zhì)，存儲層次機(jī)構(gòu)對用戶文件的管理應(yīng)該劃分成較小的基本調(diào)度單位來進(jìn)行。依劃分標(biāo)準(zhǔn)不同，存在3種存儲層次管理方式。(1)段式管理段式管理(P148) 段是程序中的一個邏輯單位，可以是一個程

4、序模塊，或者是一個數(shù)據(jù)結(jié)構(gòu)。段的長度不一，但段內(nèi)所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進(jìn)行信息保護(hù)。 每段使用獨(dú)立的邏輯地址空間，即都從0開始計(jì)算地址。 段式管理方法的主要缺點(diǎn)是各段長短不一，調(diào)進(jìn)調(diào)出之后容易形成大量不規(guī)則的零碎空間。 段式管理方法的虛實(shí)變換算法是查段表(P150)。2003.3.15段式虛擬存儲器的地址映象 主程序（0段）1段2段3段段號段長起始地址01231K5002002008K16K9K30K段 表程序空間主存儲器01K05000200020008K9K16K30K2003.3.16段式虛擬存儲器的優(yōu)點(diǎn)如下：程序的模塊性能好。對于大程序，可以劃分成多個程 序段，每個程

5、序段賦予不同的名字，由多個程序員并行編寫，分別編譯和調(diào)試。由于各個程序段在功能上是相互獨(dú)立的，因此，一個程序段的修改和增刪等不會影響其他程序段，從而可以縮短程序的編制和調(diào)試時(shí)間。便于程序和數(shù)據(jù)的共享。由于程序段是按功能來劃分的，如子程序段、數(shù)據(jù)段、表格段等。每個程序段有比較完整的功能，因此，被共享的可能性很大。程序的動態(tài)鏈接和調(diào)試比較容易。由于每個程序段都是一組有獨(dú)立意義的數(shù)據(jù)塊或具有完整功能的程序段，因此，在程序運(yùn)行過程中，可以根據(jù)需要一次就把一個程序段或數(shù)據(jù)塊都裝入到主存儲器中，并且在裝入時(shí)才實(shí)行動態(tài)鏈接。 1.便于實(shí)現(xiàn)信息保護(hù)。在一般情況下，一段程序是否需要保護(hù)是根據(jù)這個程序的功能來決定

6、的。因此，只有在段表中設(shè)置一個信息保護(hù)字段，就能根據(jù)需要很方便地實(shí)現(xiàn)對該程序的保護(hù)。2003.3.17段式虛擬存儲器的缺點(diǎn)：地址變換所花費(fèi)的時(shí)間比較長。從多用戶虛地址變換到主存實(shí)地址需要查兩次，做兩次加法運(yùn)算。主存儲器的利用率往往比較低。由于每個程序段的長度不同的，一個程序段通常要裝在一個連續(xù)的主存空間中，程序段在主存儲器中不斷地調(diào)入調(diào)出，有些程序段在執(zhí)行過程中還要動態(tài)增加長度，從而使得主存儲器中有很多的空隙存在。當(dāng)然，也可以采用一些好的算法來減少空隙的數(shù)量，或者通過定時(shí)運(yùn)行回收程序來合并著這些空隙，但這無疑增加了系統(tǒng)的開銷。1.對輔存（磁盤存儲器）的管理比較難。磁盤存儲器通常是按固定大小的塊

7、來訪問的，如何把不定長度的程序段映象到固定長度的磁盤存儲器中，需要做一次地址變換。 2003.3.18(2)頁式管理頁式管理(P151)。 頁是系統(tǒng)規(guī)定的固定長度單位。按頁劃分用戶文件可以避免上述零碎空間浪費(fèi)。 我們把用戶文件劃分得到的一個長度單位稱為“虛頁虛頁”，因?yàn)樗捻撎柺窃谔摰刂房臻g中編排的；實(shí)地址空間按頁的大小劃分得到的一個長度單位稱為“實(shí)頁實(shí)頁”。 頁式管理方法的主要缺點(diǎn)是按固定長度分出來的同一頁內(nèi)常有不同屬性的信息，不便于信息保護(hù)的實(shí)現(xiàn)。 頁式管理方法的虛實(shí)變換算法是查頁表(P152)。頁號主存頁號0123主存儲器頁 表0頁1頁2頁3頁用戶程序頁式虛擬存儲器的地址映象2003.3

8、.19頁式虛擬存儲器的優(yōu)點(diǎn)是：主存儲器的利用率比較高。每個用戶程序只有不到一頁（平均為半頁）的浪費(fèi)，與段式虛擬存儲器每兩個程序段之間都有浪費(fèi)相比要節(jié)省許多。頁表相對比較簡單。它需要保存的字段數(shù)比較少，一些關(guān)鍵字段的長度要短許多，因此，節(jié)省了頁表的存儲器容量。地址映象和變換的速度比較快。在把用戶程序裝入到主存儲器的過程中，只要建立用戶程序的虛頁號與主存儲器的實(shí)頁號之間的對應(yīng)關(guān)系即可不必使用整個主存的地址長度，也不必考慮頁號的長度等。對輔存（磁盤存儲器）的管理比較容易。因?yàn)轫摰拇笮∫话闳〈疟P存儲器物理塊的大?。?12字節(jié)）的整數(shù)倍。頁式虛擬存儲器的缺點(diǎn)主要有兩個： 程序的模塊化性能不好。由于用戶程

9、序是強(qiáng)制按照固定大小的頁來劃分的，而程序段的實(shí)際長度一般是不固定的。因此，頁式虛擬存儲器中一頁通常不能表示一個完整的程序功能。1.頁表很長，需要占用很大的存儲空間。通常，虛擬存儲器中的每一頁在頁表中都需要占用一個存儲字。2003.3.110(3)段頁式管理段頁式管理(P153)。 它把上述兩種管理方式結(jié)合起來，首先將整個文件分段，然后在各段內(nèi)分頁，所以有一個段表和若干個頁表。 其虛實(shí)變換算法是先查段表，查出該段的頁表起始地址再查相應(yīng)的頁表(P154)。 段頁式管理的主要缺點(diǎn)是多查一次表，虛實(shí)變換費(fèi)時(shí)較多，占用空間也較大。 由于段頁式管理方法的最小調(diào)度單位仍是頁，或者說它是分段之后的分頁管理，為

10、了敘述簡單，下面的分析還是以頁式管理為模型。2003.3.111段頁式虛擬存儲器的地址映象0段（12K）1段（10K）2段（5K）每頁4KB頁表長度頁表地址332段 表0段0頁0段1頁0段2頁1段0頁1段1頁1段2頁0段頁表1段頁表2段0頁2段1頁2段頁表用戶程序主存儲器2003.3.112相聯(lián)目錄表技術(shù)1.1.頁表占用空間過大問題頁表占用空間過大問題 頁表必須存放在實(shí)存M1里。實(shí)際上，命中情況下的訪存時(shí)間等于查表時(shí)間加上訪問目標(biāo)數(shù)據(jù)的時(shí)間，所以頁表不能放在M2。 頁表占用空間 = 頁表行數(shù) 每行寬度其中，頁表行數(shù) = 虛存容量 / 頁面大小 以PC機(jī)為例，頁表行數(shù) 64G / 4K = 23

11、6 / 212 = 224 1600萬！按每行寬度6字節(jié)估算約需96MB。 減少頁表空間的思路分減少行數(shù)和減少行寬兩類。2.2.相聯(lián)目錄表方法（相聯(lián)目錄表方法（P158P158） 僅保留頁表中已裝入的虛頁記錄。為避免逐行比對，利用相聯(lián)存儲器存放此表，它具有并行比較功能，但價(jià)格遠(yuǎn)高于普通存儲器。3.3.快慢表方法（快慢表方法（P159P159）4.4.通過地址映象減少行寬通過地址映象減少行寬 如下文所示2003.3.1134種常見的地址映象方式3.3.1 全相聯(lián)(P174) 全相聯(lián)全相聯(lián)就是無約束對應(yīng)，或者說是一個完全關(guān)系，意思就是一個虛頁可以調(diào)入任何一個實(shí)頁。 虛存 實(shí)頁 0 1 2 3 0

12、0 1 實(shí)存 1 2 0 2 3 1 虛 3 4 2 頁 4 5 3 5 6 6 7 7 (a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系） 全相聯(lián)的地址映象方式與地址變換原理示意圖(a)(b)2003.3.114全相聯(lián)的地址映象方式與地址變換原理示意圖(c)虛地址虛頁號 P頁內(nèi)偏移量 D實(shí)地址實(shí)頁號 p頁內(nèi)偏移量d實(shí)頁號 裝入位 修改位表項(xiàng) 0 ： ： ： ： ：表項(xiàng) P p1 0 ： ： ：表項(xiàng) 7 ： ：(c) 通過查表進(jìn)行虛實(shí)變換全相聯(lián)的虛實(shí)變換信息完全來自于變換表。 全相聯(lián)映象使虛頁調(diào)入有最大的選擇范圍，發(fā)生實(shí)頁爭用可能性最小，調(diào)入/調(diào)出操作開銷也最少，有利于命中率

13、提高。但頁表占用空間和查表時(shí)間開銷較大, 實(shí)現(xiàn)成本較高，命中時(shí)的虛實(shí)變換時(shí)間也較多。由于頁表必須常駐實(shí)存，而主存-輔存層次的實(shí)存（即主存）相對Cache-主存層次的實(shí)存（即Cache存儲器）要低廉一些，所以全相聯(lián)映象一般用于主存-輔存層次。2003.3.1153.3.2 直接相聯(lián)(P176) 直接相聯(lián)直接相聯(lián)是一種最強(qiáng)的約束關(guān)系，規(guī)定每個虛頁只對應(yīng)唯一實(shí)頁。為便于虛實(shí)變換，用求模運(yùn)算作為變換關(guān)系式：將虛頁號對實(shí)頁總數(shù)求模得到實(shí)頁號。實(shí)現(xiàn)簡單，二進(jìn)制中，任何數(shù)X對2的整次冪n求模等價(jià)于截取X的最低log2n位。 例已知虛頁號 = 7，實(shí)頁總數(shù) = 4，用直接相聯(lián)求實(shí)頁號。 解：可用十進(jìn)制形式求：

14、7 mod 4 = 3； 也可用二進(jìn)制形式求：由于n = 4，所以log2n = 2， 取7的二進(jìn)制形式111B的最低2位，得11B，即3。 直接相聯(lián)映象不需借助頁表進(jìn)行虛實(shí)變換，節(jié)省了相應(yīng)的空間與時(shí)間（當(dāng)然頁表中的裝入位和修改位還得保留），但是由于每個虛頁選擇范圍太小，實(shí)頁爭用頻率較高，常出現(xiàn)實(shí)存有空閑空間卻不得不調(diào)出一個現(xiàn)有虛頁以騰出實(shí)頁的情況，使系統(tǒng)的命中率和運(yùn)行效率大大下降。 這種映象方式主要用于對實(shí)存價(jià)格非常敏感的Cache-主存層次。2003.3.116直接相聯(lián)的地址映象方式與地址變換原理 虛存 實(shí)頁0123 00 1 實(shí)存1 202 31虛 3 42頁 4 535 66 77(a

15、) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）虛地址 虛頁號 1 1 1頁內(nèi)偏移量 D實(shí)地址實(shí)頁號 1 1頁內(nèi)偏移量d(c) 通過求模運(yùn)算進(jìn)行虛實(shí)變換示例2003.3.117例：假設(shè)在某計(jì)算機(jī)系統(tǒng)中Cache容量為64K字節(jié)，數(shù)據(jù)塊大小是 16個字節(jié)，主存容量是4M，地址映象為直接相聯(lián)方式。（1）主存地址多少位？如何分配？（2）Cache地址多少位？如何分配？（3）目錄表的格式和容量？主存地址格式：主存地址格式： 區(qū)號區(qū)號區(qū)內(nèi)塊號區(qū)內(nèi)塊號塊內(nèi)地址塊內(nèi)地址21 16 15 4 3 0 緩存地址格式：緩存地址格式： 塊塊 號號塊內(nèi)地址塊內(nèi)地址15 4 3 0 目錄表的格式：目錄表

16、的格式： 主存區(qū)號主存區(qū)號有效位有效位6 1 0 解： 容量：應(yīng)與緩存塊數(shù)量相同即容量：應(yīng)與緩存塊數(shù)量相同即212=4096 2003.3.1182003.3.1193.3.3 組相聯(lián)(P178) 組相聯(lián)組相聯(lián)映象是全相聯(lián)與直接相聯(lián)的一個折中方案，性能也是二者折中。做法：先將實(shí)存分組，每組內(nèi)有若干實(shí)頁，然后將虛存空間也以同樣大小分組。虛組按直接相聯(lián)方式映射到實(shí)組集合，對應(yīng)虛實(shí)組間各頁則用全相聯(lián)映射，如下頁示意圖(a)、(b)所示（設(shè)實(shí)組數(shù)為2）。組相聯(lián)的地址映象方式與地址變換原理(a)(b) 虛存 實(shí)頁0123虛組 0 00 1 實(shí)存1虛組 1 20 實(shí)組 02 31虛3虛組 2 42 實(shí)組

17、1頁4 535虛組 3 66 77(a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）2003.3.120組相聯(lián)的地址變換區(qū)號區(qū)號E組號組號G組內(nèi)塊號組內(nèi)塊號B塊內(nèi)地址塊內(nèi)地址W塊內(nèi)地址塊內(nèi)地址w組內(nèi)塊號組內(nèi)塊號b組號組號g相聯(lián)比較相聯(lián)比較主存地址主存地址相等相等Cache地址地址Cb個塊個塊區(qū)號區(qū)號E，組內(nèi)塊號，組內(nèi)塊號B組內(nèi)塊號組內(nèi)塊號b由于包含了兩層不同的映射關(guān)系，頁表須按虛組劃分成許多子表。在虛實(shí)變換時(shí)，先根據(jù)虛頁號所在的虛組號，通過求模運(yùn)算確定實(shí)組號，再按虛組號在相應(yīng)的子表內(nèi)讀出組內(nèi)頁號，拼接在一起就是實(shí)頁號。簡記為“組號計(jì)算、組內(nèi)查表”2003.3.121例：主存容

18、量為1MB，緩存容量為32KB，每塊為64個字節(jié)， 緩存共分128（27）組。請寫出：（1）主存與Cache的格式；（2）相關(guān)存儲器的格式與容量解：主存地址：主存地址： 區(qū)號區(qū)號組號組號塊號塊號塊內(nèi)地址塊內(nèi)地址19 15 14 8 7 6 5 0 緩存地址：緩存地址： 組號組號塊號塊號塊內(nèi)地址塊內(nèi)地址14 8 7 6 5 0 區(qū)號區(qū)號Ei塊號塊號Bi緩存塊號緩存塊號bi裝入位裝入位9 5 4 3 2 1 0 相關(guān)存儲器的格式：相關(guān)存儲器的格式：相關(guān)存儲器的容量，應(yīng)與緩存的塊數(shù)相同，即相關(guān)存儲器的容量，應(yīng)與緩存的塊數(shù)相同，即: 組數(shù)組數(shù)組內(nèi)塊數(shù)組內(nèi)塊數(shù)=1284=512 2003.3.122 這

19、兩方面優(yōu)點(diǎn)互相抵觸：組內(nèi)頁數(shù)越多，實(shí)存空間劃分的組數(shù)就越少，實(shí)組號字段所占位數(shù)也少，這時(shí)改善實(shí)頁爭用現(xiàn)象的效果較好，而節(jié)省頁表空間的效果較差，反之亦然。實(shí)際使用中可根據(jù)性能要求選取合適參數(shù)。 這種映象方式性價(jià)比較好，在Cache-主存層次中被普遍使用。 組相聯(lián)映象方式的組相聯(lián)映象方式的優(yōu)點(diǎn)優(yōu)點(diǎn)： 塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低：每個虛頁在對應(yīng)實(shí)組范圍內(nèi)有若干映象實(shí)頁可供選擇，實(shí)頁爭用的發(fā)生頻率比直接相聯(lián)要低。另一方面，由于頁表內(nèi)原來存放的實(shí)頁號改成存組內(nèi)頁號，省略了實(shí)組號字段，所以頁表占用空間也減少了。 組相聯(lián)映象方式的組相聯(lián)映象方式的缺點(diǎn)缺點(diǎn)： 實(shí)現(xiàn)難度和造價(jià)要比

20、直接映象方式高。2003.3.1233.3.4 段相聯(lián)(P184) 段相聯(lián)映象方式也是全相聯(lián)與直接相聯(lián)的一個折中方案。它的分段方法與組相聯(lián)相同，不同的是所有虛段按照全相聯(lián)方式映射到實(shí)段集合，對應(yīng)的虛實(shí)段之間各頁則用直接相聯(lián)映射（因?yàn)樘搶?shí)段大小相同，所以實(shí)際上是一一對應(yīng)），如下頁示意圖(a)、(b)所示（設(shè)實(shí)段數(shù)為2）。 虛存 實(shí)頁0123虛段 0 00 1 實(shí)存1虛段 1 20 實(shí)段 02 31虛 3虛段 2 42 實(shí)段 1頁 4 535虛段 3 66 77(a) 虛頁集合與實(shí)頁集合的對應(yīng)關(guān)系 (b) 對應(yīng)關(guān)系表（為有關(guān)系）段相聯(lián)的地址映象方式與地址變換原理(a)(b)2003.3.124 段

21、相聯(lián)的虛實(shí)變換與組相聯(lián)類似，不過通過計(jì)算來確定的部分是在段內(nèi)，即頁表內(nèi)只儲存各虛頁對應(yīng)的實(shí)段號，段內(nèi)頁號則從虛頁號中簡單直接復(fù)制，拼接在一起就是實(shí)頁號，簡記為“段號查表、段內(nèi)復(fù)制”。2003.3.125 段相聯(lián)方式的主要段相聯(lián)方式的主要優(yōu)點(diǎn)優(yōu)點(diǎn)：段表比較簡單，實(shí)現(xiàn)成本低。例如：例如：容量為256KB Cache，分8段，每段2048塊，每塊16B。 在段表存儲器中只需要存儲8個主存地址的段號S。 段相聯(lián)方式的主要段相聯(lián)方式的主要缺點(diǎn)缺點(diǎn)： 當(dāng)發(fā)生段失效時(shí)，要把本段內(nèi)已經(jīng)建立的映象關(guān)系全部撤消。 段相聯(lián)映象方式的虛實(shí)段內(nèi)頁號對應(yīng)關(guān)系是固定的，每個虛頁在調(diào)入時(shí)可以選擇的只是實(shí)段號。由于虛實(shí)段大小相

22、同，所以虛段號比實(shí)段號位數(shù)多，也就意味著“多少”的映射（組相聯(lián)是等量映射），其實(shí)頁爭用的發(fā)生頻率比組相聯(lián)要高。在節(jié)省頁表存儲空間方面，性能與組相聯(lián)差不多。2003.3.126多用戶虛地址格式 在多用戶或多進(jìn)程并發(fā)環(huán)境下，由于機(jī)器中同時(shí)保存并交替運(yùn)行多個程序模塊，各模塊中的相同虛頁號會發(fā)生混淆。這時(shí)從CPU發(fā)出的虛地址還需要在前面拼接上一個“當(dāng)前用戶號”字段，形成“多用戶虛地址”，如下圖所示(參見P154)。 在虛實(shí)變換時(shí)，上面所說的各種查表操作之前還得先去查一個“段表基址寄存器組”或“頁表基址寄存器組”的小表格(P150，P152)，確定現(xiàn)在該查哪一張段表或頁表。這個小表格建立在CPU里，讀寫

23、時(shí)間很短。當(dāng)前用戶號虛段號虛頁號頁內(nèi)偏移量思考題：P203，題112003.3.1273.4 替換算法(P164) 上面所講地址映象方式是在虛頁調(diào)入時(shí)的“選址”規(guī)則，而地址變換方法則是命中時(shí)獲得實(shí)地址的手段。 不命中時(shí)需要增加的操作就是首先調(diào)出一頁，調(diào)出之后再調(diào)入稱為 “替換”。 替換算法要解決的是選擇調(diào)出對象的問題。 替換算法的目的是在發(fā)生實(shí)頁爭用（即根據(jù)地址映象方式，將要調(diào)入的虛頁被允許進(jìn)入的所有實(shí)頁均被其它虛頁占用）時(shí)，選擇將來不太可能使用或者使用最晚的虛頁作為調(diào)出對象，以騰出一個實(shí)頁來。2003.3.1283.4.1 幾種常用的替換算法(P164)(1) 隨機(jī)算法RAND 在比較范圍內(nèi)

24、任取一頁作為淘汰頁；優(yōu)點(diǎn)：算法簡單，容易實(shí)現(xiàn)。缺點(diǎn)：沒有利用歷史信息，沒有反映程序的局部性，命中率低。(2) 先進(jìn)先出算法FIFO 在比較范圍內(nèi)選取調(diào)入最早的一頁作為淘汰頁；優(yōu)點(diǎn)：比較容易實(shí)現(xiàn)，利用了歷史信息，沒有反映程序的局部性。缺點(diǎn)：最先調(diào)入主存的頁面，很可能也是經(jīng)常要使用的頁面。(3) 最不經(jīng)常使用算法LFU 在比較范圍內(nèi)選取最近單位時(shí)間內(nèi)使用 次數(shù)最少的一頁作為淘汰頁；優(yōu)點(diǎn)：既充分利用了歷史信息，又反映了程序的局部性缺點(diǎn)：實(shí)現(xiàn)起來非常困難。2003.3.129(4) 最不接近使用算法LRU 在比較范圍內(nèi)選取最后一次使用離現(xiàn)在最久 的一頁作為淘汰頁；(5) 最優(yōu)替換算法OPT 在比較范圍

25、內(nèi)選取下一次使用時(shí)間離現(xiàn)在最久 的一頁作為淘汰頁。優(yōu)點(diǎn)：它把LFU算法中的“多”與“少”簡化成“有”與“無”， 實(shí)現(xiàn)起來比較容易。是一種理想化的算法。用來作為評價(jià)其它頁面替換算法好壞的標(biāo)準(zhǔn)。2003.3.130從LFU到LRU的近似邏輯推理：近期最少使用LFU 最近一個單位時(shí)間內(nèi)使用次數(shù)最少 相鄰兩次使用的平均間隔時(shí)間最大 上次使用時(shí)間離現(xiàn)在最久 最久沒有使用LRU偶然偏差：使用稀疏的頁面有可能恰巧剛剛用過，離現(xiàn)在更近。統(tǒng)計(jì)性能：“現(xiàn)在”離“上次”使用時(shí)間的平均距離，應(yīng)為相鄰兩次使用時(shí)間距離的1/2，所以大多數(shù)情況下LRU與LFU的判斷結(jié)論應(yīng)該是一致的。頁面 A 訪問使用頻繁，相鄰使用間隔小上

26、次使用時(shí)間離現(xiàn)在近時(shí)間 t頁面 B 訪問使用稀疏，相鄰使用間隔大上次使用時(shí)間離現(xiàn)在遠(yuǎn)時(shí)間 t現(xiàn)在（要淘汰一頁）2003.3.131算法模擬：實(shí)存狀況圖（P166圖3.32）以 LRU 算法為例（其中*號表示被選中的淘汰頁）：已訪問次數(shù) t012345678910被訪問虛頁號無1215413424命中總次數(shù)0空11111*111*221空空222*444*444實(shí)存空間使用情況（實(shí)頁號為 0、1、2）2空空空空555*333*3*操作名稱初態(tài)(空)調(diào)入調(diào)入命中調(diào)入替換命中替換命中替換命中4 次被訪問實(shí)頁號01021021012003.3.1322003.3.133 這是對某些替換算法的統(tǒng)稱。如果

27、某些算法在同一地址流同一時(shí)刻的小容量分區(qū)情況下的保留頁面集合必是大容量分區(qū)情況下的保留頁面集合的子集（當(dāng)容量超過虛頁總數(shù)時(shí)，保留頁面集合相同），則小容量下的命中點(diǎn)到大容量情況下仍然是命中點(diǎn)，并且隨著容量加大，還可能會有新的命中點(diǎn)產(chǎn)生。具有這一特性的一類替換算法中成為“堆棧型算法”。例如：P166圖3.32中，對LRU算法，如果實(shí)頁數(shù)增加到4，則t=5時(shí)為了調(diào)入虛頁4就不必替換掉虛頁2，而是將虛頁1、2、4、5都留在實(shí)存，這時(shí)大容量分區(qū)情況下的保留頁面集合S2 = 1，2，4，5，同一時(shí)刻的小容量分區(qū)情況下的保留頁面集合S1 = 1，4，5。顯然有S1S2。 P167第48行是堆棧型算法的數(shù)學(xué)定

28、義。 堆棧型替換算法的主要性質(zhì)就是命中率H隨著實(shí)頁分區(qū)容量n的上升而單調(diào)上升（不減性）。 可以證明，LFU、LRU、OPT等算法都是堆棧型算法，而RAND和FIFO算法不是堆棧型算法。P168的圖3.34是一個實(shí)例，當(dāng)實(shí)頁數(shù)從3增加到4時(shí)，F(xiàn)IFO的命中率反倒從3降到2。具體觀察，比如t = 7時(shí)，S1 = 1，2，5，S2 = 2，3，4，5，不滿足子集關(guān)系。所以FIFO不能保證當(dāng)實(shí)頁數(shù)增加時(shí)，原來的命中點(diǎn)不丟。3.4.2 堆棧型替換算法(P166)2003.3.134實(shí)例：堆棧模擬圖 研究堆棧型替換算法的性質(zhì)，一方面可以設(shè)計(jì)優(yōu)化的操作系統(tǒng)算法（例如P167倒數(shù)第3行的PFF法），另一方面也

29、可推導(dǎo)出一些分析工具，例如“堆棧模擬法”。 堆棧模擬圖可以通過一次作圖，描述同一地址流在各種實(shí)存分區(qū)容量下的命中情況。 例3.4t123456789101112P232152453252st(1)232152453252st(2)23215245325st(3)321524533st(4)33112444st(5)331111st(6)命中次數(shù)n=10n=2*2n=3*5n=4*6n=5*72003.3.1353.5 提高命中率的方法影響命中率的主要因素：(1) 程序在執(zhí)行過程中的頁地址流分布情況。(2) 所采用的頁面替換算法。(3) 頁面大小。(4) 存儲器的容量(5) 所采用的頁面調(diào)度方法

30、。以下，對后三個因素進(jìn)行分析。 2003.3.1361. 頁面大小與命中率的關(guān)系 頁面大小為某個值時(shí)，命中率達(dá)到最大。 解釋：假設(shè)At和At+1是相鄰兩次訪問主存儲器的邏輯地址，d=|At - At+1|。 如果dSp，At和At+1一定不在同一個頁面內(nèi)。隨著Sp的增大，主存的頁面數(shù)減少，頁面的替換將更加頻繁。隨著Sp的增大而降低。1命命 2S中中率率 SH 頁面大小頁面大小SP 頁面大小與主存命中率的關(guān)系頁面大小與主存命中率的關(guān)系當(dāng)Sp比較小的時(shí)候，前一種情況是主要的，隨著Sp的增大而提高。當(dāng)Sp達(dá)到某一最大值后，后一種情況成為主要的，隨Sp增大而降低。 當(dāng)頁面大小增大時(shí)，造成的浪費(fèi)也要增加

31、；當(dāng)頁面大小減小時(shí)，頁表和頁面表在主存儲器中所占的比例將增加。2003.3.1372. 主存容量與命中率的關(guān)系 主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升。 在S比較小的時(shí)候，H提高得非?？?。隨著S的逐漸增加，H提高的速度逐漸降低。當(dāng)S增加到某一個值之后，H幾乎不再提高。1.0 命命 中中 率率 H 主存容量主存容量S 主存命中率主存命中率H于貯存容量于貯存容量S的關(guān)系的關(guān)系2003.3.1383. 頁面調(diào)度方式與命中率的關(guān)系 請求式：當(dāng)使用到的時(shí)候，再調(diào)入主存。 預(yù)取式：在程序重新開始運(yùn)行之前，把上次停止運(yùn)行前一段 時(shí)間內(nèi)用到的頁面先調(diào)入到主存儲器，然后才開始 運(yùn)行程序。 優(yōu)點(diǎn)

32、：可以避免在程序開始運(yùn)行時(shí)，頻繁發(fā)生頁面失效的情況。 缺點(diǎn)：如果調(diào)入的頁面用不上，浪費(fèi)了調(diào)入的時(shí)間，占用了主 存資源。 2003.3.1393.6 虛擬存儲器與Cache的特點(diǎn)(P146，P172)常用的兩種存儲系統(tǒng):1. Cache 存儲系統(tǒng): 由 Cache + + 主存儲器構(gòu)成Cathe主存儲器從系統(tǒng)程序員看2. 虛擬存儲系統(tǒng) : 主存儲器 + 磁盤存儲器主存磁盤存儲器從應(yīng)用程序員看2003.3.140虛擬存儲器與Cache的主要區(qū)別（P173頁）存儲系統(tǒng)存儲系統(tǒng)Cache虛擬存儲器虛擬存儲器要達(dá)到的目標(biāo)提高（主存）速度擴(kuò)大（主存）容量實(shí)現(xiàn)方法全部硬件軟件為主，硬件為輔兩級存儲器的速度比

33、3倍10倍105倍頁（塊）大小1字16字1KB16KB等效存儲容量主存儲器虛擬存儲器透明性對系統(tǒng)和應(yīng)用程序員僅對應(yīng)用程序員不命中時(shí)處理方式等待主存儲器任務(wù)切換2003.3.141 使用Cache的動機(jī)動機(jī)： 容量大的存儲器（DRAM）速度慢 容量小的存儲器（SRAM）速度快通過如下策略，使得平均訪問時(shí)間變小： 在小量、高速的存儲器中完成大多數(shù)訪問減少對大容量存儲器的帶寬要求。2003.3.142Cache 塊號B塊內(nèi)地址W 主存-Cache地址變換 塊號b塊內(nèi)地址w Cache替換部件 主存地址替換塊裝入塊不命中命中數(shù)據(jù)或指令Cache地址主存地址(來自CPU) 已滿未滿主存儲器2003.3.143 工作流程命中不命中已滿替換策略替換塊未滿裝入塊 與虛存（VM）的區(qū)別