計算機系統(tǒng)結(jié)構電子教案

第7章存儲層次（P188）

MemoryHirarchy長期存在的問題：在合理的總價格限制下，單一型主存器件的速度跟不上CPU的發(fā)展，容量不能滿足軟件尺寸擴大。本章學習提高主存系統(tǒng)性能/價格比的幾種結(jié)構化方法，重點是“Cache-主存層次”，焦點問題是如何使流水線每拍完成一次訪存。本章基本公式：(1)平均時間T=P1×T1+P2×T2其中P1+P2=100%，并且T1和T2都可以再用該式迭代展開，復雜時，可用概率樹來表示（全概率公式）；(2)實際時間T=理想時間+P3

×每次額外開銷時間其中P3是不利事件發(fā)生概率。2014.2.171計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第1頁!7.1存儲層次原理及性能指標（P188）7.1.1基本原理“存儲層次”的定義：（參見P189第3段）由2種或多種存儲部件構成的復合存儲系統(tǒng)，通過內(nèi)部管理機構的自動更換機制，能夠不斷將大容量低速存儲部件中的活躍內(nèi)容復制到小容量高速存儲部件中（后者作為前者的局部副本）。它既能滿足CPU的快速存取需要，又有很大的存儲容量，平均單位價格也很低，等效于同時滿足3方面要求的理想單一存儲部件。依據(jù)：程序訪問的局部化原理（時間局部化，空間局部化）。模型：如右圖所示，存儲層次由n層組成，滿足3個不等式：TAi<TAi+1，ci>ci+1，Si<Si+1。2014.2.172計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第2頁!存儲層次的基本術語

邏輯地址（又稱為相對地址、虛地址）是程序員在編寫和編譯一個程序模塊時分配指令和數(shù)據(jù)的空間單位序號，總是從0開始（可以按字節(jié)編址、按CPU字編址等）。邏輯地址的取值范圍稱為邏輯地址空間、虛空間或虛存。

物理地址（又稱為絕對地址、實地址）是任一級存儲器為全部存儲單元分配的序號。物理地址的取值范圍稱為物理地址空間、實空間或?qū)嵈妗腗1到Mn各層都有自己的物理地址空間，而對當前執(zhí)行的程序模塊來說，邏輯地址空間只有一個。

地址映象方式指的是虛頁集合與實頁集合的對應規(guī)則，或者說是約束關系。

地址變換（又叫虛實變換）指邏輯地址到物理地址的變換過程或者算法。

頁失效指當前被訪問存儲級中沒有所需的信息，也就是不命中現(xiàn)象。

實頁爭用又叫實頁沖突，指虛頁調(diào)入時，根據(jù)地址映象方式劃定的實空間范圍內(nèi)已沒有空閑實頁的狀況。

頁和塊：前者用于主-輔層次，后者用于Cache-主存層次，意義相同。2014.2.173計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第3頁!7.7.1存儲層次的管理方式(續(xù))(2)頁式管理。頁是系統(tǒng)規(guī)定的固定長度單位。按頁劃分用戶文件可以避免上述零碎空間浪費。我們把用戶文件劃分得到的一個長度單位稱為“虛頁”，因為它的頁號是在虛地址空間中編排的；實地址空間按頁的大小劃分得到的一個長度單位稱為“實頁”。頁式管理方法的主要缺點是按固定長度分出來的同一頁內(nèi)常有不同屬性的信息，不便于信息保護的實現(xiàn)。頁式管理方法的虛實變換算法是查頁表。兩種層次都用此技術。(3)段頁式管理。它把上述兩種管理方式結(jié)合起來，首先將整個文件分段，然后在各段內(nèi)分頁，所以有一個段表和若干個頁表。其虛實變換算法是先查段表，查出該段的頁表起始地址再查相應的頁表。段頁式管理的主要缺點是多查一次表，虛實變換費時較多，占用空間也較大。它的實現(xiàn)最復雜，僅用于主存—輔存層次。段頁式管理方法的最小調(diào)度單位仍是頁，基本操作可歸于頁式管理。2014.2.174計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第4頁!課堂練習7.1（續(xù)）虛地址經(jīng)變址尋址和基址尋址(B)+(X)+D形成?，F(xiàn)有一個程序，出現(xiàn)下列訪問主存的操作：(1)列出產(chǎn)生主存頁面失效的操作序號。(2)如果不發(fā)生主存頁面失效的話，計算訪問主存的物理地址。(3)列出非法操作的序號。(4)列出被修改過的主存頁面號。2014.2.175計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第5頁!7.1.4存儲層次的基本問題(P192)①映象規(guī)則——一個虛塊（頁）被允許放到哪些實塊（頁）上；②查找算法——如何在實存中找到指定的虛塊（頁）（主要是虛實變換）；③替換算法——塊（頁）爭用時，調(diào)出哪個虛塊（頁）；④寫策略——寫存儲層次的具體操作。典型存儲層次（PC計算機，以Intel芯片組為例）2014.2.176計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第6頁!(3)速度

表現(xiàn)訪問速度的參數(shù)較多。命中率H：被訪問數(shù)據(jù)事先已在M1的概率不命中率F：不命中的概率，又稱失效率，F(xiàn)=1-H平均訪存時間：命中時的訪存時間為TA1，不命中時的訪存時間為TA2，平均訪存時間則是它們的概率均值其中TM是失效開銷，TM=TA2+TB22014.2.177計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第7頁!假設：TAi表示第i級器件讀/寫時間；TBi表示第i級向上級傳送時間。根據(jù)模型有：命中M1時：TA=TA1命中M2時：TA=TA1+TA2+TB2≈TA2……命中Mn時：TA=TA1+TA2+TB2+……+TAn+TBn≈Tan區(qū)別：單次訪問總時間近似等于本次到達的最低一層的訪問時間，因為每層都只訪問一次；大量訪問的平均時間則由各層訪問時間共同構成，因為較高層的一次訪問時間雖短，但它們被訪問的百分比遠遠大于較低層。多級存儲層次的單次訪問時間2014.2.178計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第8頁!多級存儲層次的平均訪問時間1

M1103BTA1=1us103B

M2106BTA2=10usM3109BTA3=100us109B(a)(b)例7.0有一個109字節(jié)的程序被裝入右圖所示的M3準備運行。假定指令字長=1字節(jié)，程序中無轉(zhuǎn)移指令和內(nèi)存讀/寫指令。忽略傳送時間TB。(1)按圖(a)求TA和e；(2)按圖(b)推導三層體系的TA公式；(3)按圖(b)求TA和e；(4)比較(1)(3)結(jié)果，有何結(jié)論？解：2014.2.179計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第9頁!多級存儲層次的平均訪問時間3(4)結(jié)論：插入中間層后，層間速度差減少，訪問效率提高。2014.2.1710計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第10頁!剛才推導中使用的不命中率都是局部不命中率。為了避免混淆，有必要分清兩種不命中率：全局不命中率是一個比局部不命中率更有意義的指標，它指出了在CPU發(fā)出的所有訪存請求中，究竟有多大比例是穿過該級，到達下一級存儲器的。7.4.1局部不命中率與全局不命中率（P214）2014.2.1711計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第11頁!多級存儲層次的平均訪問時間公式重寫將這些局部不命中率、全局不命中率的定義式代入到前面的多級存儲層次平均訪問時間公式中，我們可以得到更容易記憶的公式形式：2014.2.1712計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第12頁!(2)TA＝TA1＋F1×(TA2＋F2×TM2)＝1＋4%×(10＋50%×100)＝1＋4%×60＝3.4個時鐘周期式中后面部分4%×60為每次訪存的平均停頓時間（即失效開銷）：每次訪存的平均停頓時間（即失效開銷）＝4%×60＝2.4由于平均每條指令訪存1.5次，所以：每條指令的平均停頓時間＝2.4×1.5＝3.6個時鐘周期習題7.9例7.3（續(xù)）2014.2.1713計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第13頁!地址映象問題的提出1.頁表占用空間過大問題頁表必須存放在實存M1里。實際上，命中情況下的訪存時間等于查表時間加上訪問目標數(shù)據(jù)的時間，所以頁表不能放在M2。頁表占用空間=頁表行數(shù)×每行寬度其中，頁表行數(shù)=虛存容量/頁面大小以Win2K為例，虛存頁表=4×4G/4K=22

×232/212=222=4MB

Cache-主存層次的頁表=4×4G/16=230=1GB，而Cache1只有32K減少頁表空間的思路分減少行數(shù)和減少行寬兩類。2.相聯(lián)目錄表方法（又稱“實頁表”）/減少行數(shù)僅保留頁表中已裝入的虛頁記錄。為避免逐行比對，利用相聯(lián)存儲器存放此表，它具有并行比較功能，但價格遠高于普通存儲器。P196圖7.10示意Cache中用多字并行比較方法實現(xiàn)的相聯(lián)目錄表。此法須嚴格限制字數(shù)。3.快慢表方法（TLB）/減少行數(shù)4.改變地址映象/減少行寬2014.2.1714計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第14頁!全相聯(lián)的地址映象方式與地址變換原理示意圖(a)(b)2014.2.1715計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第15頁!(2)直接相聯(lián)(directmapped)直接相聯(lián)是一種最強的約束關系，它規(guī)定每個虛頁只對應唯一的實頁。為了便于虛實變換，用求模運算作為變換關系式：將虛頁號對實頁總數(shù)求模得到實頁號。實現(xiàn)起來非常簡單，因為在二進制中，任何數(shù)X對2的整次冪n求模等價于截取X的最低log2n位，如下頁示意圖(c)所示。例5.2已知虛頁號=7，實頁總數(shù)=4，用直接相聯(lián)求實頁號。解：可用十進制形式求：7mod4=3；也可用二進制形式求：由于n=4，所以log2n=2，取7的二進制形式111B的最低2位，得11B，即3。直接相聯(lián)映象方式不需要借助頁表來進行虛實變換，顯然大大節(jié)省了相應的空間與時間（當然頁表中的裝入位和修改位還得保留），但是由于每個虛頁的選擇范圍太小，實頁爭用的發(fā)生頻率較高，常出現(xiàn)明明實存有空閑空間卻不得不調(diào)出一個現(xiàn)有虛頁以騰出所在實頁的情況，這使系統(tǒng)的命中率和運行效率下降。這種映象方式主要用于對實存價格、速度敏感的Cache-主存層次。直接相聯(lián)的“候選位置”為1個實頁，它又被簡稱為“1路Cache”。2014.2.1716計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第16頁!(3)組相聯(lián)(setassociative，P194)組相聯(lián)映象方式是全相聯(lián)與直接相聯(lián)的一個折中方案，性能也是二者的折中。具體做法是先將實存分組，每組內(nèi)有若干實頁，然后將虛存空間也以同樣大小分組。所有虛組按照直接相聯(lián)方式映射到實組集合，對應的虛實組之間各頁則用全相聯(lián)映射，如下頁示意圖(a)、(b)所示（設實組數(shù)為2）。由于包含了兩層不同的映射關系，頁表須按虛組劃分成許多子表。在虛實變換時，首先根據(jù)虛頁號所在的虛組號，通過求模運算確定實組號，再按虛組號在相應的子表內(nèi)讀出組內(nèi)頁號，拼接在一起就是實頁號。簡記為“組號計算、組內(nèi)查表”。如圖(c)所示。采用組相聯(lián)映象方式時，每個虛頁在對應實組范圍內(nèi)有若干映象實頁可供選擇，實頁爭用的發(fā)生頻率比直接相聯(lián)要低；另一方面，由于頁表內(nèi)原來存放的實頁號改成存組內(nèi)頁號，省略了實組號字段，所以頁表占用空間也減少了。當然這兩方面優(yōu)點是互相抵觸的：組內(nèi)頁數(shù)越多，實存空間劃分的組數(shù)就越少，實組號字段所占位數(shù)也少，這時改善實頁爭用現(xiàn)象的效果較好，而節(jié)省頁表空間的效果較差，反之亦然。實際使用中可根據(jù)性能要求選取合適參數(shù)。這種映象方式性價比較好，在Cache-主存層次中被普遍使用。實組內(nèi)頁數(shù)被稱為“路數(shù)”，又稱為“相聯(lián)度”（associativity）,它表明一個虛頁的選擇范圍。下頁圖示為2路組相聯(lián)（2-waysetassociative）。2014.2.1717計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第17頁!組相聯(lián)的地址映象方式與地址變換原理(c)2014.2.1718計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第18頁!位選擇組相聯(lián)的地址映象方式與地址變換原理(a)(b)2014.2.1719計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第19頁!(1)頁表法

每個虛頁對應1項，虛頁號就是項號，項內(nèi)存儲實頁號，如課堂練習7.2。這種方法原理簡單，但是占用空間非常大。當頁表尺寸超過1頁時，它本身還要按頁面尺寸分割成許多分散存放的子表，再造一個“表上表”來找到當前需要的子表。進一步發(fā)展就會形成“多級頁表”，導致虛實變換分多步進行，時間大大延長。7.2.3虛實變換基本方法（P195）2014.2.1720計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第20頁!(3)快慢表方法（P231）這是頁表法的一種加快方案。地址變換緩沖器TLB（TranslationLook-asideBuffer）是一個專用的高速緩沖器，用于存放近期經(jīng)常使用的頁表項副本，TLB利用程序的局部性原理，以小表代替大表，縮短查找時間。7.2.3虛實變換基本方法（續(xù)2）2014.2.1721計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第21頁!(5)單體多字存儲器＋多比較器查表方法（P196第2段）這是目錄表法的一種廉價方案，對組相聯(lián)非常適用。限制條件是組內(nèi)頁數(shù)不太多，下圖為4的情況。7.2.3虛實變換基本方法（續(xù)4）2014.2.1722計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第22頁!Cache─主存層次虛實變換實現(xiàn)（直接相聯(lián)）快命中方案：直接相聯(lián)，目錄表法（P196，圖7.9）舉例：為了方便用10進制討論。設虛塊號=000～999，實塊號=0～9，于是有索引=0～9，而標識=00～99。索引=0的實塊里裝的虛塊標識可以是00，01，……，99，對應的虛塊號就是000，010，020，030，……，990。2014.2.1723計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第23頁!7.3.5偽相聯(lián)（P209）優(yōu)點缺點直接映象組相聯(lián)命中時間小命中時間大不命中率高不命中率低“偽相聯(lián)”又稱“列相聯(lián)”，按原理還可稱為“伴生Cache”。(1)比較直接相聯(lián)、組相聯(lián)的優(yōu)缺點從例7.4我們將看到，直接相聯(lián)的命中時間較短，而多路組相聯(lián)的失效率較低，所以它們的平均訪問時間依兩個因素的作用大小而互有輸贏。有沒有什么方法取二者之長呢？(2)偽相聯(lián)的優(yōu)點偽相聯(lián)就是直接相聯(lián)、組相聯(lián)的一種組合方案。優(yōu)點是命中時間短、不命中率還低，所以它的平均訪問時間往往比直接相聯(lián)、組相聯(lián)都短。2014.2.1724計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第24頁!(4)快速命中與慢速命中

要保證絕大多數(shù)命中都是快速命中，就是命中率要高。一種簡單的辦法是在出現(xiàn)偽命中時，交換上下兩個區(qū)的內(nèi)容，因為當前在下區(qū)的塊很可能是“常用塊”。偽命中情況下需要增加2個額外的時鐘周期（其中1個周期是多找1次花去的，1個周期是交換操作所需）。(5)偽相聯(lián)的缺點：

它的多種命中時間使得CPU流水線上各指令之間的時間對齊變得困難，所以往往應用在離CPU比較遠的Cache上，比如L2-Cache。7.3.5偽相聯(lián)（續(xù)2）2014.2.1725計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第25頁!例7.3.5（補充，2版P198例5.6）

一個偽相聯(lián)Cache，當在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個位置才找到數(shù)據(jù)（偽命中）時需要增加2個額外的周期。其它已知條件如下表所示。(1)推導偽相聯(lián)平均訪存時間公式；(2)當Cache容量分別為2KB和128KB時，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構中，哪一種的平均訪存時間最短？7.3.5偽相聯(lián)（續(xù)4）2014.2.1726計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第26頁!將后3式依次向前代入，得到所需公式：

平均訪存時間偽相聯(lián)＝命中時間1路＋(不命中率1路－不命中率2路)×2周期＋不命中率2路×不命中開銷1路(2)當Cache容量為2KB時：平均訪存時間1路＝1.0＋0.098×50＝5.90平均訪存時間2路＝1.1＋0.076×50＝4.90平均訪存時間偽相聯(lián)，2KB＝1.0＋(0.098－0.076)×2＋(0.076×50)＝4.844當Cache容量為128KB時：平均訪存時間1路＝1.0＋0.010×50＝1.50平均訪存時間2路＝1.1＋0.007×50＝1.45平均訪存時間偽相聯(lián)，128KB＝1.0＋(0.010－0.007)×2＋(0.007×50)＝1.356可見，對于這兩種Cache容量，偽相聯(lián)Cache都是速度最快的。7.3.5偽相聯(lián)（續(xù)6）2014.2.1727計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第27頁!各次作業(yè)應交的內(nèi)容作業(yè)9（第10次課）7.112014.2.1728計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第28頁!所以在計算平均CPI時，應該加上存儲器平均“不命中開銷”。本章僅考慮存儲器等待在平均CPI計算中的作用，暫時不考慮流水線因相關、沖突導致的延遲，所以上式簡化寫為又被稱為以下是計算二者關系的幾組常用公式。7.2.7訪存時間對CPU性能的影響22014.2.1729計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第29頁!(4)程序執(zhí)行時間（即“CPU時間”）：a.b.c.d. (7.3)e. (7.1)f. (7.2)g.7.2.7訪存時間對CPU性能的影響42014.2.1730計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第30頁!例7.2（P204）

考慮兩種不同組織結(jié)構的Cache：直接映象Cache和兩路組相聯(lián)Cache，

(1)理想Cache（命中率為100%）情況下的CPI為2.0，時鐘周期為2ns，平均每條指令訪存1.3次；

(2)兩種Cache容量均為64KB，塊大小都是32B；

(3)在組相聯(lián)Cache中，由于多路選擇器的存在而使CPU的時鐘周期增加到原來的1.10倍。這是因為對Cache的訪問總是處于關鍵路徑上，對CPU的時鐘周期有直接的影響；

(4)這兩種結(jié)構Cache的不命中開銷都是70ns（在實際應用中，應取整為整數(shù)個時鐘周期）；

(5)命中時間為1個時鐘周期，64KB直接映象Cache的不命中率為1.4%，相同容量的兩路組相聯(lián)Cache的不命中率為1.0%。

分別比較它們的平均訪存時間、CPU時間。2014.2.1731計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第31頁!例7.2（續(xù)2）(2)

CPU時間＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷）×時鐘周期時間＝IC×（CPIexecution×時鐘周期時間＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷×時鐘周期時間）代入?yún)?shù)得：CPU時間1路＝IC×(2.0×2＋(1.3×0.014×70))

＝5.27×ICCPU時間2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))

＝5.31×IC直接映象Cache的CPU時間短一些。5.31×ICCPU時間1路─────＝─────＝1.015.27×ICCPU時間2路2014.2.1732計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第32頁!(1)L2-Cache采用直接相聯(lián)

平均訪問時間

＝10.0＋25%×50＝22.5

個時鐘周期(2)L2-Cache采用兩路組相聯(lián)

平均訪問時間

＝10.1＋20%×50＝20.1

個時鐘周期(3)兩路組相聯(lián)的命中時間之所以比直接相聯(lián)增加0.1個時鐘周期，是因為虛實變換按組查表后要進行多路選擇（P199圖7.12和P198第8段），需要額外增加時間。具體實現(xiàn)方案可以把時鐘周期調(diào)慢為1.01倍（這將使所有動作都減慢1%，甚至主存訪問），或者僅在命中時增加1個時鐘周期。按增加1個時鐘周期的方案，L2-Cache的命中時間為11，有：

平均訪問時間＝11＋20%×50＝21.0

個時鐘周期(2)(3)情況下L2-Cache的平均訪問時間都比直接相聯(lián)小，所以L2-Cache采用兩路組相聯(lián)性能更好。注：教材中該例中說“幸運的話，取整為10個周期”，就是說多路選擇動作時間有可能“擠”進原有的10周期中，習題中通常不這樣給條件。習題7.10例7.4（續(xù)）2014.2.1733計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第33頁!Windows2000使用基于分頁機制的虛擬內(nèi)存。每個進程有4GB的虛擬地址空間。程序中使用的都是4GB地址空間中的虛擬地址。而訪問物理內(nèi)存，需要使用物理地址。物理內(nèi)存以字節(jié)（8位）為單位編址。物理內(nèi)存分頁，一個物理頁的大小為4K字節(jié)，第0個物理頁從物理地址0x00000000處開始。由于頁的大小為4KB，就是0x1000字節(jié)，所以第1頁從物理地址0x00001000處開始。第2頁從物理地址0x00002000處開始?？梢钥吹接捎陧摰拇笮∈?KB，所以只需要32bit的地址中高20bit來尋址物理頁。使用了分頁機制之后，4G的地址空間被分成了固定大小的頁，每一頁或者被映射到物理內(nèi)存，或者被映射到硬盤上的交換文件中，或者沒有映射任何東西。對于一般程序來說，4G的地址空間，只有一小部分映射了物理內(nèi)存，大片大片的部分是沒有映射任何東西。物理內(nèi)存也被分頁，來映射地址空間。對于32bit的Win2k，頁的大小是4K字節(jié)。CPU用來把虛擬地址轉(zhuǎn)換成物理地址的信息存放在叫做頁目錄和頁表的結(jié)構里。Windows2000虛擬存儲器12014.2.1734計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第34頁!物理地址的轉(zhuǎn)換，使用物理地址取出值，完成指令。對于IntelCPU來說，分頁標志位是寄存器CR0的第31位，為1表示使用分頁，為0表示不使用分頁。對于初始化之后的Win2k我們觀察CR0，發(fā)現(xiàn)第31位為1。表明Win2k是使用分頁的。

CPU把虛擬地址轉(zhuǎn)換成物理地址：一個虛擬地址，大小4個字節(jié)(32bit)，包含著找到物理地址的信息，分為3個部分：第22位到第31位這10位（最高10位）是頁目錄中的索引，第12位到第21位這10位是頁表中的索引，第0位到第11位這12位（低12位）是頁內(nèi)偏移。對于一個要轉(zhuǎn)換成物理地址的虛擬地址，CPU首先根據(jù)CR3中的值，找到頁目錄所在的物理頁。然后根據(jù)虛擬地址的第22位到第31位這10位（最高的10bit)的值作為索引，找到相應的頁目錄項(PDE,pagedirectoryentry),頁目錄項中有這個虛擬地址所對應頁表的物理地址。有了頁表的物理地址，根據(jù)虛擬地址的第12位到第21位這10位的值作為索引，找到該頁表中相應的頁表項(PTE,pagetableentry),頁表項中就有這個虛擬地址所對應物理頁的物理地址。最后用虛擬地址的最低12位，也就是頁內(nèi)Windows2000虛擬存儲器32014.2.1735計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第35頁!32bit的一個指針，可以尋址范圍0x00000000-0xFFFFFFFF，4GB大小。也就是說一個32bit的指針可以尋址整個4GB地址空間的每一個字節(jié)。一個頁表項負責4K的地址空間和物理內(nèi)存的映射，一個頁表1024項，也就是負責1024*4k=4M的地址空間的映射。一個頁目錄項，對應一個頁表。一個頁目錄有1024項，也就對應著1024個頁表，每個頁表負責4M地址空間的映射。1024個頁表負責1024*4M=4G的地址空間映射。一個進程有一個頁目錄。所以以頁為單位，頁目錄和頁表可以保證4G的地址空間中的每頁和物理內(nèi)存的映射。每個進程都有自己的4G地址空間，從0x00000000-0xFFFFFFFF。通過每個進程自己的一套頁目錄和頁表來實現(xiàn)。由于每個進程有自己的頁目錄和頁表，所以每個進程的地址空間映射的物理內(nèi)存是不一樣的。兩個進程的同一個虛擬地址處（如果都有物理內(nèi)存映射）的值一般是不同的，因為他們往往對應不同的物理頁。4G地址空間中低2G，0x00000000-0x7FFFFFFF是用戶地址空間，4G地址空間中高2G，0x80000000-0xFFFFFFFF是系統(tǒng)地址空間。訪問系統(tǒng)地址空間需要程序有ring0的權限。Windows2000虛擬存儲器52014.2.1736計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第36頁!7.2.5替換算法(P198)上面所講的地址映象方式是在虛頁調(diào)入時的“選址”規(guī)則，而地址變換方法則是命中時獲得實地址的手段。不命中時需要增加的操作就是首先調(diào)出一頁，調(diào)出之后再調(diào)入稱為“替換”。替換算法要解決的是選擇調(diào)出對象的問題。替換算法的目的是在發(fā)生實頁爭用（即根據(jù)地址映象方式，將要調(diào)入的虛頁被允許進入的所有實頁均被其它虛頁占用）時，選擇將來不太可能使用或者使用最晚的虛頁作為調(diào)出對象，以騰出一個實頁來。2014.2.1737計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第37頁!從LFU到LRU的近似邏輯推理：近期最少使用LFU→最近一個單位時間內(nèi)使用次數(shù)最少→相鄰兩次使用的平均間隔時間最大→上次使用時間離現(xiàn)在最久→最久沒有使用LRU偶然偏差：使用稀疏的頁面有可能恰巧剛剛用過，離現(xiàn)在更近。統(tǒng)計性能：“現(xiàn)在”離“上次”使用時間的平均距離，應為相鄰兩次使用時間距離的1/2，所以大多數(shù)情況下LRU與LFU的判斷結(jié)論應該是一致的。2014.2.1738計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第38頁!課堂練習7.3（鄭緯民題3-19中3、4、6、8小問，稍改）假設在一個采用位選擇組相聯(lián)映象方式的Cache中，主存由B0～B7共8塊組成，Cache有2組，每組2塊，每塊的大小為16個字節(jié)，采用LRU塊替換算法。程序執(zhí)行過程中依次訪問這個Caehe的塊地址流如下：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3(3)畫出主存與Cache之間各個塊的映象對應關系。(4)Cache塊號記為C0、C1、C2和C3，列出程序執(zhí)行過程中Cache地址流。(6)計算Cache的塊命中率。(8)如果上述地址流中的每個塊號實際代表對該塊的連續(xù)16次訪問，計算在這種情況下的Cache命中率（也稱為存儲單元命中率）。2014.2.1739計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第39頁!7.2.4Cache的工作過程（P197）概況：塊大小32B，塊數(shù)256，直接映象，寫直達，采用不按寫分配2014.2.1740計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第40頁!Cache“寫”訪問2014.2.1741計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第41頁!(2)混合式（統(tǒng)一式）Cache在命中情況下，每次有效MEM操作都會迫使后面一條指令的IF停頓（結(jié)構沖突）。分離式Cache與混合式Cache（續(xù)1）混合式Cache結(jié)構示意圖IFIDWBMEMEX混合Cache下一級存儲器2014.2.1742計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第42頁!例7.5（2版P186例5.1）假設Cache的命中時間為1個時鐘周期，失效開銷為50個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期，根據(jù)上表所列的失效率，試問指令Cache和數(shù)據(jù)Cache容量均為16KB的分離Cache與容量為32KB的混合Cache相比，哪種Cache的失效率更低？又假設采用寫直達策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。請問上述兩種情況下平均訪存時間各是多少？解：(1)平均失效率測試表明，（經(jīng)驗值）。平均失效率分離16KB+16KB＝(75%×0.64%)＋(25%×6.47%)＝2.10%

平均失效率混合32KB＝1.99%（查表）

混合Cache較低。分離式Cache與混合式Cache（續(xù)3）2014.2.1743計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第43頁!平均訪存時間＝命中時間＋不命中率×不命中開銷可以從三個方面改進Cache的性能：降低不命中率減少不命中開銷減少Cache命中時間本書介紹了17種Cache優(yōu)化技術（P223表7.5）8種用于降低不命中率5種用于減少不命中開銷4種用于減少命中時間本課堂內(nèi)只了解一下其中兩個概念，細節(jié)內(nèi)容不作深入了。7.2.8改進Cache性能（P205）2014.2.1744計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第44頁!減少三種不命中的方法強制性不命中：增加塊大小，預取（本身很少）容量不命中：增加容量

（抖動現(xiàn)象）沖突不命中：提高相聯(lián)度（理想情況：全相聯(lián)）許多降低不命中率的方法會增加命中時間或不命中開銷7.3.1三種類型的不命中（續(xù)）2014.2.1745計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第45頁!7.6并行主存系統(tǒng)（非層次技術，P223）本小節(jié)不在課堂講授，供需要的同學自學。并行存儲器技術可以提高主存系統(tǒng)的整體等效速度，實際應用中，常將它與存儲層次技術組合使用，可以互為補充，獲得很高的性能。并行存儲器技術的基本思想是用多個獨立的存儲部件組成主存系統(tǒng)，讓它們并行工作，在一個存儲周期內(nèi)可以訪問到多個數(shù)據(jù)，從而實現(xiàn)較高的存取流量。教材P224～P224介紹了3種提高主存速度的技術：1.多字寬存儲器；2.多體交叉存儲器；3.避免體沖突的軟硬件方法。下面介紹提高訪問常用的低位多體交叉訪問存儲器。2014.2.1746計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第46頁!主存地址與結(jié)構參數(shù)的換算（P225）：其中：n──存儲體個數(shù)，A──主存地址，

j──體內(nèi)地址，k──體序號（k=0，1，2，…，n-1）例5.1已知n=4，問主存地址13是在幾號體的幾號單元？解：由于n=4，體選譯碼信號使用主存地址的最低log2n=2位，所以地址13（其二進制為1101B）對應的體號k=1（即01B）、體內(nèi)地址j=3（即11B），也就是說，地址13位于1號體的3號單元（參看前一頁插圖）。 根據(jù)上式，所有k值（即體號）相同的地址之間均相差n的整倍數(shù)，稱之為“模n同余”。2014.2.1747計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第47頁!

Kg=010.0g=0.24.463.682.00g=0.51.00g=10110n并行存儲器平均加速倍數(shù)（西安電子科技大學李學干教材2版）1.只考慮取指地址序列（假設地址順序遞增，直至出現(xiàn)一條轉(zhuǎn)移指令）：其中g是指令序列中出現(xiàn)轉(zhuǎn)移指令的概率。此公式在右圖中用綠線表示。2.只考慮取數(shù)地址序列（假設地址完全隨機）此公式在右圖中用紅線表示。2014.2.1748計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第48頁!7.7.1存儲層次的管理方式(P230)根據(jù)程序的局部化性質(zhì)，存儲層次機構對用戶文件的管理應該劃分成較小的基本調(diào)度單位來進行。依劃分標準不同，存在3種存儲層次管理方式。目前在主存—輔存層次實現(xiàn)中，具體機器可能采用3種方式中的某1種，而Cache-主存層次普遍只采用第2種，因為它簡單，便于硬件實現(xiàn)。(1)段式管理。段是程序中的一個邏輯單位，可以是一個程序模塊，或者是一個數(shù)據(jù)結(jié)構。段的長度不一，但段內(nèi)所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進行信息保護。每段使用獨立的邏輯地址空間，即都從0開始計算地址。段式管理方法的主要缺點是各段長短不一，調(diào)進調(diào)出之后容易形成大量不規(guī)則的零碎空間。段式管理方法的虛實變換算法是查段表。因其實現(xiàn)較復雜，僅用于主存—輔存層次。2014.2.1749計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第49頁!課堂練習7.1一個頁式虛擬存儲器按字節(jié)編址，頁面大小為1K字節(jié)，每個數(shù)據(jù)的字長為4個字節(jié)?，F(xiàn)有一個程序的頁表如下：表中的裝入標志為“1”表示該虛頁已經(jīng)裝入主存，為“0”則表示還未裝入主存。修改標志為“0”表示該頁還沒有被修改過，為“1”則表示該頁已經(jīng)被修改過。訪問方式“RW”表示該頁可以讀可以寫，但不能作為指令來執(zhí)行；“R”表示該頁只能讀，不能寫和執(zhí)行；“X”表示該頁只能作為指令來執(zhí)行，不能讀和寫。2014.2.1750計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第50頁!7.1.3“主─輔”層次與“Cache─主存”層次的對比（P192表7.1，P231表7.7）“主存-輔存”層次目的：提高等效容量?；菊{(diào)度單位：頁，幾百Byte到幾千Byte。速度比：幾萬倍。虛實轉(zhuǎn)換：頁表（以虛頁號為索引）“Cache-主存”層次目的：提高等效速度。基本調(diào)度單位：塊，幾十Byte。速度比：幾倍。虛實轉(zhuǎn)換：目錄表（以實頁號為索引）2014.2.1751計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第51頁!7.1.2存儲層次的性能指標（P189）先以2級存儲層次為例進行公式推導，并且只考慮各級存儲器件自身的操作，忽略控制機構的附加開銷。多級層次以及附加開銷留到以后討論。(1)容量：S=S2（理論上）(2)單價：（美分/bit）2014.2.1752計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第52頁!訪問效率e（補充）訪問效率e受H和r的影響（參見右圖）：

e是一個相對值，便于不同系統(tǒng)之間的比較。2014.2.1753計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第53頁!課堂練習7.2設計“Cache-主存”層次，Cache的容量有三種選擇，如上表所示。忽略平均訪存時間TA公式中的TB。(1)分別計算三種方案的等效訪問時間；(2)分別計算三種方案每KB的平均價格；(3)分別根據(jù)等效訪問時間、每KB的平均價格排序；(4)根據(jù)等效訪問時間和平均價格的乘積排序。2014.2.1754計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第54頁!多級存儲層次的平均訪問時間2由這2式合并得此公式參見教材P214倒數(shù)第12行。2014.2.1755計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第55頁!(1)問中，為什么？答：每當CPU訪問M1不命中時，存儲系統(tǒng)會從M3裝入1000字節(jié)到M1，再從M1取1個字節(jié)送給CPU，所以本次訪問結(jié)果為“失效”，但是緊接著的999次訪問將“命中”，以后又是如此重復，……。同學們不要把訪問“失效”理解為訪問“失敗”，認為CPU在M1找不到數(shù)據(jù)就會放棄本次訪問?！笆А钡亩x是經(jīng)過等待后完成的訪問，而“命中”是不需要等待即完成的訪問，僅此不同。(3)問中，為什么？答：M2接受M1的數(shù)據(jù)請求，每次是1000字節(jié)。M2的初始狀態(tài)為“空”，對于M1的首次請求不能立即滿足，需要先從M3索取1000000字節(jié)數(shù)據(jù)填滿自己，再向M1提供所要的1000字節(jié)數(shù)據(jù)。這次訪問稱為“失效”。此后M1向M2發(fā)出的999次請求都能立即響應，而再下一次請求又需要等待…。如此重復，所以H2=999/1000。例題說明：2014.2.1756計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第56頁!因為：所以：依此類推，……7.4.1局部不命中率與全局不命中率（續(xù)）2014.2.1757計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第57頁!例7.3考慮某一兩級Cache：級Cache為L1，第二級Cache為L2。(1)假設在1000次訪存中，Cache1的不命中是40次，Cache2的不命中是20次。求各種局部不命中率和全局不命中率；(2)假設Cache1的命中時間是1個時鐘周期，Cache2的命中時間是10個時鐘周期，不命中開銷是100時鐘周期，平均每條指令訪存1.5次，不考慮寫操作的影響。問：平均訪存時間是多少？每條指令的平均停頓時間（即失效開銷）是多少個時鐘周期？解：(1)級Cache的不命中率（全局和局部）是40/1000，即4%；第二級Cache的局部不命中率是20/40，即50%；第二級Cache的全局不命中率是20/1000，即2%。例7.32014.2.1758計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第58頁!各次作業(yè)應交的內(nèi)容作業(yè)8（第9次課）7.92014.2.1759計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第59頁!7.2.2四種常見的地址映象方式（P193）(1)全相聯(lián)(fullyassociative)全相聯(lián)就是無約束對應，或者說是一個完全關系，意思就是一個虛頁可以調(diào)入任何一個實頁。這種關系可用下頁示意圖(a)、(b)表示。全相聯(lián)的虛實變換信息完全來自于變換表，查表過程如圖(c)所示。全相聯(lián)映象方式使虛頁調(diào)入有最大的選擇范圍，發(fā)生實頁爭用的可能性最小，調(diào)入/調(diào)出的操作開銷也最少，有利于命中率提高。但這種方式的頁表占用空間和查表時間開銷都比較大,也就是說實現(xiàn)成本比較高，在命中情況下花費在虛實變換上的時間也比較多。由于頁表必須常駐在實存中，而主存-輔存層次的實存（即主存）相對Cache-主存層次的實存（即Cache存儲器）容量大得多，所以全相聯(lián)映象方式一般用于主存-輔存層次。一個虛頁被允許進入的實頁集合稱為“候選位置”（P195），全相聯(lián)的“候選位置”為整個實存。2014.2.1760計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第60頁!全相聯(lián)的地址映象方式與地址變換原理示意圖(c)2014.2.1761計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第61頁!直接相聯(lián)的地址映象方式與地址變換原理2014.2.1762計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第62頁!組相聯(lián)的地址映象方式與地址變換原理(a)(b)組相聯(lián)的“候選位置”為組內(nèi)頁數(shù)，即“路數(shù)”。2014.2.1763計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第63頁!(4)位選擇組相聯(lián)(P194圖7.7c)位選擇組相聯(lián)映象方式映象關系中，實存分組，虛存按實組數(shù)分區(qū)，區(qū)內(nèi)不分組。虛塊號與實組號之間是直接映象關系，而虛塊與該實組內(nèi)的各個實塊之間是全相聯(lián)映象方式。例如，虛塊0可以映象到實組0的任意一塊中。在一般組相聯(lián)映象方式中，一個虛組與一個實組之間是多個塊到多個塊的映象。而在位選擇組相聯(lián)映象方式中，改成了一個虛塊到實組中多個塊的映象。映象關系明顯簡單，實現(xiàn)起來可以容易些。另外，從數(shù)據(jù)的分布情況看。對于一般組相聯(lián)映象方式，虛存中的幾個連續(xù)塊映象到實存中可能也是連續(xù)的，而對于位選擇組相聯(lián)映象方式，虛存中的連續(xù)塊映象到實存中肯定是不連續(xù)的，它們被分散到實存的各個組中。由于在虛存與實存之間是以塊為單位進行調(diào)度的，而實存是以字為單位訪問的，只要實存中的一個字不跨越兩個塊，在實存內(nèi)部的塊與塊之間的分布是否連續(xù)對實存的正常工作是沒有關系的。由于虛存每個區(qū)中的塊數(shù)與實組數(shù)相等，而且它們之間采用直接映象方式，因此，虛存地址中的區(qū)內(nèi)塊號可以直接作為實組號。位選擇組相聯(lián)的地址變換過程比一般組相聯(lián)映象方式簡單，而與全相聯(lián)映象方式基本相同。2014.2.1764計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第64頁!位選擇組相聯(lián)的地址映象方式與地址變換原理(c)2014.2.1765計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第65頁!(2)部分虛實表法（P195圖7.8）

這是一種統(tǒng)稱，指表項數(shù)少于虛頁數(shù)的情形，下面要介紹的3種方法都屬于這一類。（與Hash查表有點相似）

表項數(shù)少于虛頁數(shù)意味著查表時會有多個虛頁查到表中同一項的情況發(fā)生，另外也意味著區(qū)分表中項號的地址位數(shù)少于虛頁號的位數(shù)，虛頁號中未用的位數(shù)正是造成重復的原因。

表項數(shù)少于虛頁數(shù)的做法既是節(jié)省成本的需要，也符合任何時刻只有少部分虛頁占用實存的實際，問題是每個表項必須說明它當前記錄的是一組共享虛頁中的哪一個的信息，這就要用到“標識”字段。虛頁號里用于計算表內(nèi)地址的部分稱為“索引”index，用來與查表內(nèi)容相比較的部分稱為“標識”tag。下圖以組相聯(lián)為例說明“標識”的意義，它有16個虛頁，只用4個表項。7.2.3虛實變換基本方法（續(xù)1）2014.2.1766計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第66頁!(4)目錄表法（P196第1段）

只對已經(jīng)裝入實存的虛頁造表，其項數(shù)比頁表少得多。為避免逐行比對，須使用相聯(lián)存儲器來存放，通過并行比較實現(xiàn)一次查遍，器件價格遠高于普通存儲器。7.2.3虛實變換基本方法（續(xù)3）2014.2.1767計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第67頁!主─輔層次虛實變換實現(xiàn)主流方案：全相聯(lián)，頁表法（P232）2014.2.1768計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第68頁!Cache─主存層次虛實變換實現(xiàn)（組相聯(lián)）低失效方案：位選擇組相聯(lián)（2路），目錄表法（P196，圖7.9）2014.2.1769計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第69頁!(3)基本思想及工作原理

在邏輯上把直接相聯(lián)Cache的空間分為上、下兩個區(qū)。對于任何一次訪問，偽相聯(lián)Cache先按直接相聯(lián)Cache的方式去處理。若命中，則其訪問過程與直接相聯(lián)Cache的情況一樣。若不命中，則再到另一區(qū)相應的位置去查找。若找到，則發(fā)生了偽命中。再找不到就只好訪問下一級存儲器。

顯然偽相聯(lián)的“候選位置”=2，與2路組相聯(lián)相同。

每次訪問時間有3種可能：正常命中（快速命中）偽命中（慢速命中）不命中7.3.5偽相聯(lián)（續(xù)1）2014.2.1770計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第70頁!7.3.5偽相聯(lián)（續(xù)3）折中方案：偽相聯(lián)（2路），目錄表法（P209）2014.2.1771計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第71頁!解：(1)首先按通用形式寫出偽相聯(lián)的平均訪存時間公式：平均訪存時間偽相聯(lián)＝平均命中時間偽相聯(lián)＋不命中率偽相聯(lián)×不命中開銷偽相聯(lián)

然后根據(jù)偽相聯(lián)原理，可以寫出其中的：

平均命中時間偽相聯(lián)＝命中時間1路＋偽命中率偽相聯(lián)×2周期

由于偽相聯(lián)不命中時，就是2個候選位置都不命中，所以：

不命中率偽相聯(lián)＝不命中率2路

又由于偽相聯(lián)的2個候選位置命中率之和等于2路組相聯(lián)，所以：

偽命中率偽相聯(lián)＝命中率2路－命中率1路

＝(1－不命中率2路)－(1－不命中率1路)

＝不命中率1路－不命中率2路7.3.5偽相聯(lián)（續(xù)5）2014.2.1772計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第72頁!結(jié)論：從不命中率看，F(xiàn)2路=F偽相聯(lián)<F1路，偽相聯(lián)因不命中帶來的平均延時與2路一樣短（1路較長）；從命中時間看，偽相聯(lián)在正常命中時與1路一樣短（2路較長），偽命中時要增加2拍，后者概率=H2路–H1路。這種情況下1路要增加50拍。代入2KB、128KB容量的數(shù)據(jù)，算出平均訪存時間TA都是偽相聯(lián)最短。缺點：多種命中時間習題：7.117.3.5偽相聯(lián)（續(xù)7）2014.2.1773計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第73頁!衡量訪存時間是否合適的主要標準是處理機速度，具體說是處理機分配來讀/寫存儲器的時間長短。處理機速度越高要求訪存時間越短。衡量處理機速度的常用標準是CPI，因為它與程序執(zhí)行時間成正比。

對順序執(zhí)行的處理機，CPI定義為每條指令執(zhí)行所需的平均周期數(shù)。對流水執(zhí)行的處理機，CPI定義為相鄰兩條指令啟動時間相差的平均周期數(shù)。我們現(xiàn)在只關心流水處理機。

下圖說明訪存等待（不命中）會延長瞬時CPI。7.2.7訪存時間對CPU性能的影響1（P203）IFIDEXMemWBstallIFIDEXMemWBIFIDEXMemWBIFIDEXMemWBIFIDEXMemWBCPI=1CPI=22014.2.1774計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第74頁!(1)第i級的不命中率：特殊地，F(xiàn)1又可以記為F，因為M1被訪問次數(shù)就是CPU的總訪存次數(shù)。(2)存儲系統(tǒng)的平均訪問時間（從CPU看）：其中H1～Hn是來自互斥事件的完備群，它們滿足關系式：注意該公式忽略了各級之間的傳送時間。(3)第i級的平均訪問時間：其中Ti是第i級的命中時間，TMi是第i級的失效開銷時間。7.2.7訪存時間對CPU性能的影響32014.2.1775計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第75頁!例7.1（P204）

假設Cache不命中開銷為50個時鐘周期，當不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期，訪問Cache不命中率為2%，平均每條指令訪存1.33次。比較有Cache與無Cache情況下的CPU時間。解：已知TA1=2.0，即理想CPI=2.0，TA2=50，F(xiàn)=2%，平均每條指令訪存1.33次CPU時間有cache＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷）×時鐘周期時間＝IC×（2.0＋1.33×2%×50）×時鐘周期時間＝IC×3.33×時鐘周期時間從此式知，實際CPI＝2.0＋1.33×2%×50＝3.33，是理想情況下的3.33/2.0＝1.67(倍)，換言之，CPU時間是理想情況下的1.67倍。

若不采用Cache，則每次訪存增加50個時鐘周期，每條指令的周期數(shù)為：CPI無cache＝2.0＋1.33×50＝68.5，是理想情況下的68.5/2.0＝34.25倍！2014.2.1776計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第76頁!例7.2（續(xù)1）解：摘要：理想CPI=2，不命中開銷=70ns，每條指令訪存1.3次，F(xiàn)直接=1.4%，F(xiàn)組=1.0%，Cycle直接=2ns，Cycle組=2.2ns。比較直接映象Cache（即1路）與2路組相聯(lián)Cache的平均訪存時間、CPU時間。(1)平均訪存時間為：平均訪存時間＝命中時間＋不命中率×不命中開銷因此，兩種結(jié)構的平均訪存時間分別是：

平均訪存時間1路＝2.0＋（0.014×70）＝2.98ns

平均訪存時間2路＝2.0×1.10＋（0.010×70）＝2.90ns

兩路組相聯(lián)Cache的平均訪存時間短一些。2014.2.1777計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第77頁!

欲設計一個L2-Cache，已知它的不命中開銷L2＝50個時鐘周期，問下列兩種映像方式對不命中開銷有何影響。

(1)L2-Cache采用直接相聯(lián)，局部不命中率L2＝25%，命中時間L2＝10個時鐘周期；

(2)L2-Cache采用兩路組相聯(lián)，局部不命中率L2＝20%，命中時間L2＝10.1個時鐘周期。解：（此例與P204的例7.2參數(shù)相似，注意區(qū)別）

題目已經(jīng)給出了L2-Cache恒定的“不命中開銷L2”，那么它的不同映像方式影響的只能是L1-Cache的不命中開銷，根據(jù)多級存儲層次原理，TM1＝M2的平均訪問時間。所以本題實質(zhì)上是問哪種映像方式下L2-Cache的平均訪問時間較小。

另外，在不使用L3-Cache情況下，“不命中開銷L2＝50個時鐘周期”意思是“主存平均訪問時間＝50個時鐘周期”。例7.4（P216）2014.2.1778計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第78頁!各次作業(yè)應交的內(nèi)容作業(yè)10（第11次課）7.102014.2.1779計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第79頁!頁表———一個頁表的大小為4K字節(jié)，放在一個物理頁中。由1024個4字節(jié)的頁表項組成。頁表項的大小為4個字節(jié)(32bit)，所以一個頁表中有1024個頁表項。頁表中的每一項的內(nèi)容（每項4個字節(jié),32bit）高20bit用來放一個物理頁的物理地址，低12bit放著一些標志。頁目錄———一個頁目錄大小為4K字節(jié)，放在一個物理頁中。由1024個4字節(jié)的頁目錄項組成。頁目錄項的大小為4個字節(jié)(32bit)，所以一個頁目錄中有1024個頁目錄項。頁目錄中的每一項的內(nèi)容（每項4個字節(jié)）高20bit用來放一個頁表（頁表放在一個物理頁中）的物理地址，低12bit放著一些標志。對于x86系統(tǒng)，頁目錄的物理地址放在CPU的CR3寄存器中。如果CPU寄存器中的分頁標志位被設置，那么執(zhí)行內(nèi)存操作的機器指令時，CPU會自動根據(jù)頁目錄和頁表中的信息，把虛擬地址轉(zhuǎn)換成物理地址，完成該指令。比如moveax,004227b8h，這是把地址004227b8h處的值賦給寄存器的匯編代碼，004227b8這個地址就是虛擬址。CPU在執(zhí)行這行代碼時，發(fā)現(xiàn)寄存器中的分頁標志位已經(jīng)被設定，就自動完成虛擬地址到Windows2000虛擬存儲器22014.2.1780計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第80頁!偏移，加上這個物理頁的物理地址，就得到了該虛擬地址所對應的物理地址。一個頁目錄有1024項，虛擬地址最高的10bit剛好可以索引1024項（2的10次方等于1024）。一個頁表也有1024項，虛擬地址中間部分的10bit，剛好索引1024項。虛擬地址最低的12bit（2的12次方等于4096），作為頁內(nèi)偏移，剛好可以索引4KB，也就是一個物理頁中的每個字節(jié)。一個虛擬地址轉(zhuǎn)換成物理地址的計算過程就是，處理器通過CR3找到當前頁目錄所在物理頁，取虛擬地址的高10bit,然后把這10bit右移2bit（因為每個頁目錄項4個字節(jié)長，右移2bit相當于乘4）得到在該頁中的地址，取出該地址處PDE（4個字節(jié)），就找到了該虛擬地址對應頁表所在物理頁，取虛擬地址第12位到第21位這10位，然后把這10bit右移2bit（因為每個頁表項4個字節(jié)長，右移2bit相當于乘4）得到在該頁中的地址，取出該地址處的PTE（4個字節(jié)），就找到了該虛擬地址對應物理頁的地址，最后加上12bit的頁內(nèi)偏移得到了物理地址。Windows2000虛擬存儲器42014.2.1781計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第81頁!Windows2000虛實變換示意圖2014.2.1782計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第82頁!幾種常用的替換算法(1)隨機算法RAND──在比較范圍內(nèi)任取一頁作為淘汰頁；(2)先進先出算法FIFO──在比較范圍內(nèi)選取調(diào)入最早的一頁作為淘汰頁；(3)最不經(jīng)常使用算法LFU──在比較范圍內(nèi)選取最近一個單位時間內(nèi)使用次數(shù)最少的一頁作為淘汰頁；(4)最不接近使用算法LRU──在比較范圍內(nèi)選取最后一次使用離現(xiàn)在最久的一頁作為淘汰頁。2014.2.1783計算機系統(tǒng)結(jié)構計算機系統(tǒng)結(jié)構》電子教案共94頁，您現(xiàn)在瀏覽的是第83頁!算法模擬：實存狀況圖(清華教材圖3.32)以下是FIFO、L