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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、兩方面優(yōu)點(diǎn)互相抵觸：組內(nèi)頁(yè)數(shù)越多，實(shí)存空間劃分的組數(shù)就越少，實(shí)組號(hào)字段所占位數(shù)也少，這時(shí)改善實(shí)頁(yè)爭(zhēng)用現(xiàn)象的效果較好，而節(jié)省頁(yè)表空間的效果較差，反之亦然。實(shí)際使用中可根據(jù)性能要求選取合適參數(shù)。 這種映象方式性價(jià)比較好，在Cache-主存層次中被普遍使用。 組相聯(lián)映象方式的組相聯(lián)映象方式的優(yōu)點(diǎn)優(yōu)點(diǎn)： 塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低：每個(gè)虛頁(yè)在對(duì)應(yīng)實(shí)組范圍內(nèi)有若干映象實(shí)頁(yè)可供選擇，實(shí)頁(yè)爭(zhēng)用的發(fā)生頻率比直接相聯(lián)要低。另一方面，由于頁(yè)表內(nèi)原來(lái)存放的實(shí)頁(yè)號(hào)改成存組內(nèi)頁(yè)號(hào)，省略了實(shí)組號(hào)字段，所以頁(yè)表占用空間也減少了。 組相聯(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)的一個(gè)折中方案。它的分段方法與組相聯(lián)相同，不同的是所有虛段按照全相聯(lián)方式映射到實(shí)段集合，對(duì)應(yīng)的虛實(shí)段之間各頁(yè)則用直接相聯(lián)映射（因?yàn)樘搶?shí)段大小相同，所以實(shí)際上是一一對(duì)應(yīng)），如下頁(yè)示意圖(a)、(b)所示（設(shè)實(shí)段數(shù)為2）。 虛存 實(shí)頁(yè)0123虛段 0 00 1 實(shí)存1虛段 1 20 實(shí)段 02 31虛 3虛段 2 42 實(shí)段 1頁(yè) 4 535虛段 3 66 77(a) 虛頁(yè)集合與實(shí)頁(yè)集合的對(duì)應(yīng)關(guān)系 (b) 對(duì)應(yīng)關(guān)系表（為有關(guān)系）段相聯(lián)的地址映象方式與地址變換原理(a)(b)2003.3.124 段

21、相聯(lián)的虛實(shí)變換與組相聯(lián)類似，不過(guò)通過(guò)計(jì)算來(lái)確定的部分是在段內(nèi)，即頁(yè)表內(nèi)只儲(chǔ)存各虛頁(yè)對(duì)應(yīng)的實(shí)段號(hào)，段內(nèi)頁(yè)號(hào)則從虛頁(yè)號(hào)中簡(jiǎn)單直接復(fù)制，拼接在一起就是實(shí)頁(yè)號(hào)，簡(jiǎn)記為“段號(hào)查表、段內(nèi)復(fù)制”。2003.3.125 段相聯(lián)方式的主要段相聯(lián)方式的主要優(yōu)點(diǎn)優(yōu)點(diǎn)：段表比較簡(jiǎn)單，實(shí)現(xiàn)成本低。例如：例如：容量為256KB Cache，分8段，每段2048塊，每塊16B。 在段表存儲(chǔ)器中只需要存儲(chǔ)8個(gè)主存地址的段號(hào)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è)號(hào)對(duì)應(yīng)關(guān)系是固定的，每個(gè)虛頁(yè)在調(diào)入時(shí)可以選擇的只是實(shí)段號(hào)。由于虛實(shí)段大小相

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

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

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

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

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

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

28、義。 堆棧型替換算法的主要性質(zhì)就是命中率H隨著實(shí)頁(yè)分區(qū)容量n的上升而單調(diào)上升（不減性）。 可以證明，LFU、LRU、OPT等算法都是堆棧型算法，而RAND和FIFO算法不是堆棧型算法。P168的圖3.34是一個(gè)實(shí)例，當(dāng)實(shí)頁(yè)數(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í)頁(yè)數(shù)增加時(shí)，原來(lái)的命中點(diǎn)不丟。3.4.2 堆棧型替換算法(P166)2003.3.134實(shí)例：堆棧模擬圖 研究堆棧型替換算法的性質(zhì)，一方面可以設(shè)計(jì)優(yōu)化的操作系統(tǒng)算法（例如P167倒數(shù)第3行的PFF法），另一方面也

29、可推導(dǎo)出一些分析工具，例如“堆棧模擬法”。 堆棧模擬圖可以通過(guò)一次作圖，描述同一地址流在各種實(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í)行過(guò)程中的頁(yè)地址流分布情況。(2) 所采用的頁(yè)面替換算法。(3) 頁(yè)面大小。(4) 存儲(chǔ)器的容量(5) 所采用的頁(yè)面調(diào)度方法

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

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

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

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