【正文】 結(jié)構(gòu) 30 直接相聯(lián)的地址映象方式與地址變換原理 虛存 實頁 0 1 2 3 0 0 √ 1 所有虛組按照直接相聯(lián)方式映射到實組集合 ， 對應(yīng)的虛實組之間各頁則用全相聯(lián)映射 ， 如下頁示意圖 (a)、 (b)所 示 （ 設(shè)實組數(shù)為 2） 。 這種映象方式性價比較好 ， 在 Cache主存層次中被普遍使用 。 計算機(jī)系統(tǒng)結(jié)構(gòu) 33 組相聯(lián)的地址映象方式與地址變換原理 (c) 虛地址 虛組號 1 0 組內(nèi)頁號 1 頁內(nèi)偏移量 D實地址 實組號 0 組內(nèi)頁號 0 頁內(nèi)偏移量 d0 組子表 項 0 ： ： ： 項 1 ： ： ：1 組子表 項 0 ： ： ： 項 1 ： ： ：2 組子表 項 0 ： ： ： 項 1 0 裝入位 1 ：3 組子表 項 0 ： ： ： 項 1 ： ： ：( c ) 求模運算與分組查表結(jié)合進(jìn)行虛實變換示例 計算機(jī)系統(tǒng)結(jié)構(gòu) 34 (4) 位選擇組相聯(lián) (P194圖 ) 位選擇組相聯(lián)映象方式映象關(guān)系中 ， 實存分組 ， 虛存按實組數(shù)分區(qū) ， 區(qū)內(nèi)不分組 。 由于在虛存與實存之間是以塊為單位進(jìn)行調(diào)度的 ， 而實存是以字為單位訪問的 ， 只要實存中的一個字不跨越兩個塊 ， 在實存內(nèi)部的塊與塊之間的分布是否連續(xù)對實存的正常工作是沒有關(guān)系的 。進(jìn)一步發(fā)展就會形成“多級頁表” ， 導(dǎo)致虛實變換分多步進(jìn)行，時間大大延長。 虛實變換基本方法（續(xù) 2） 虛擬地址 〈 36 〉 〈 12 〉 虛頁號 頁內(nèi)位移 物理地址 〈 1 〉 V R/W ① ② ③ ④ ? U/S D A 〈 1 〉 〈 1 〉 〈 36 〉 標(biāo)識 〈 28 〉 ? ? 40 選 1 多路選擇器 ? 〈 28 〉 〈 12 〉 40 位 物理地址 （ 低 12 位地址 ） （ 高 28 位地址 ） 計算機(jī)系統(tǒng)結(jié)構(gòu) 40 (4) 目錄表法（ P196第 1段） 只對已經(jīng)裝入實存的虛頁造表，其項數(shù)比頁表少得多。 (1) 比較直接相聯(lián)、組相聯(lián)的優(yōu)缺點 從例 ，直接相聯(lián)的命中時間較短，而多路組相聯(lián)的失效率較低，所以它們的平均訪問時間依兩個因素的作用大小而互有輸贏。再找不到就只好訪問下一級存儲器。 (1) 推導(dǎo)偽相聯(lián)平均訪存時間公式； (2) 當(dāng) Cache容量分別為 2KB和 128KB時，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種 的平均訪存時間最短 ？ 偽相聯(lián)（續(xù) 4） 命中周期數(shù) 不命中率 2KB 不命中率 128KB 不命中 開銷 1 路 Ca che 1. 0 9. 8% 1. 0% 50 2 路 Ca che 1. 1 7. 6% 0. 7% 50 計算機(jī)系統(tǒng)結(jié)構(gòu) 50 解： (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路 偽相聯(lián)（續(xù) 5） 計算機(jī)系統(tǒng)結(jié)構(gòu) 51 將后 3式依次向前代入，得到所需公式： 平均訪存時間 偽相聯(lián) ＝命中時間 1路 ＋ (不命中率 1路 －不命中率 2路 ) 2周期 ＋不命中率 2路 不命中開銷 1路 (2) 當(dāng) Cache容量為 2KB時： 平均訪存時間 1路 ＝ ＋ 50＝ 平均訪存時間 2路 ＝ ＋ 50＝ 平均訪存時間 偽相聯(lián)， 2KB ＝ ＋ (－ ) 2＋ ( 50)＝ 當(dāng) Cache容量為 128KB時： 平均訪存時間 1路 ＝ ＋ 50＝ 平均訪存時間 2路 ＝ ＋ 50＝ 平均訪存時間 偽相聯(lián)， 128KB＝ ＋ (－ ) 2＋ ( 50)＝ 可見，對于這兩種 Cache容量，偽相聯(lián) Cache都是速度最快的。對流水執(zhí)行的處理機(jī) ， CPI定義為相鄰兩條指令啟動時間相差的平均周期數(shù) 。 訪存時間對 CPU性能的影響 3 次數(shù)訪問次數(shù)不命中iiii MMHF ??? 1??? ni iiA HTT 111???ni iHMiiiiA TFTT ??? 計算機(jī)系統(tǒng)結(jié)構(gòu) 57 (4) 程序執(zhí)行時間 （ 即 “ CPU時間 ” ） ： a. b. c. d. () e. () f. () g. 訪存時間對 CPU性能的影響 4 C Y C L EC P IICT e ??? 實際? ? C Y C L EFC P IICT e ?????? 平均不命中開銷每條指令平均訪存次數(shù) 平均理想? ? C Y C L EC P IICT e ???? 數(shù)每條指令平均等待周期理想? ? C Y C L EC P UT e ??? 等待存儲器周期數(shù)實際執(zhí)行周期數(shù)? ? C Y C L EC P IICT e ????? 平均不命中開銷數(shù)每條指令平均不命中次理想平均不命中開銷周期數(shù)訪存次數(shù)等待存儲器周期數(shù) 平均 ??? F寫不命中開銷周期數(shù)“寫”次數(shù)讀不命中開銷周期數(shù)“讀”次數(shù)等待存儲器周期數(shù)寫讀 ???????FF 計算機(jī)系統(tǒng)結(jié)構(gòu) 58 例 （ P204） 假設(shè) Cache不命中開銷為 50個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是 ，訪問 Cache不命中率為 2%，平均每條指令訪存 。 (1) 平均訪存時間為： 平均訪存時間＝命中時間＋不命中率不命中開銷 因此，兩種結(jié)構(gòu)的平均訪存時間分別是： 平均訪存時間 1路 ＝ ＋（ 70）＝ 平均訪存時間 2路 ＝ ＋（ 70）＝ 兩路組相聯(lián) Cache的平均訪存時間短一些。具體實現(xiàn)方案可以把時鐘周期調(diào)慢為 （這將使所有動作都減慢 1%，甚至主存訪問 ），或者僅在命中時增加 1個時鐘周期。 物理內(nèi)存分頁，一個物理頁的大小為 4K字節(jié)，第 0個物理頁從物理地址 0x00000000 處開始。 CPU用來把虛擬地址轉(zhuǎn)換成物理地址的信息存放在叫做頁目錄和頁表的結(jié)構(gòu)里。頁目錄中的每一項的內(nèi)容（每項 4個字節(jié)）高20bit用來放一個頁表（頁表放在一個物理頁中）的物理地址，低 12bit放著一些標(biāo)志。 CPU把虛擬地址轉(zhuǎn)換成物理地址： 一個虛擬地址，大小 4個字節(jié) (32bit)， 包含著找到物理地址的信息，分為3個部分：第 22位到第 31位這 10位（最高 10位）是頁目錄中的索引，第 12位到第 21位這 10位是頁表中的索引，第 0位到第 11位這 12位（低 12位）是頁內(nèi)偏移。 一個虛擬地址轉(zhuǎn)換成物理地址的計算過程就是，處理器通過 CR3找到當(dāng)前頁目錄所在物理頁，取虛擬地址的高 10bit,然后把這 10bit右移 2bit（ 因為每個頁目錄項 4個字節(jié)長，右移 2bit相當(dāng)于乘 4）得到在該頁中的地址，取出該地址處 PDE（ 4個字節(jié)），就找到了該虛擬地址對應(yīng)頁表所在物理頁，取虛擬地址第 12位到第 21位這 10位，然后把這 10bit右移 2bit（ 因為每個頁表項 4個字節(jié)長，右移 2bit相當(dāng)于乘 4）得到在該頁中的地址，取出該地址處的 PTE（ 4個字節(jié)），就找到了該虛擬地址對應(yīng)物理頁的地址，最后加上 12bit的頁內(nèi)偏移得到了物理地址。所以以頁為單位，頁目錄和頁表可以保證 4G的地址空間中的每頁和物理內(nèi)存的映射。 不命中時需要增加的操作就是首先調(diào)出一頁，調(diào)出之后再調(diào)入稱為 “ 替換 ” 。訪問系統(tǒng)地址空間需要程序有 ring0的權(quán)限。 1024個頁表負(fù)責(zé) 1024*4M=4G的地址空間映射。一個頁表也有 1024項，虛擬地址中間部分的 10bit， 剛好索引 1024項。對于初始化之后的 Win2k 我們觀察 CR0 ， 發(fā)現(xiàn)第 31位為 1。由 1024個4字節(jié)的頁目錄項組成。物理內(nèi)存也被分頁，來映射地址空間。而訪問物理內(nèi)存，需要使用物理地址。 另外，在不使用 L3Cache情況下，“不命中開銷 L2 ＝ 50個時鐘周期”意思是“主存平均訪問時間 ＝ 50個時鐘周期”。 計算機(jī)系統(tǒng)結(jié)構(gòu) 60 例 （續(xù) 1） 解： 摘要：理想 CPI=2， 不命中開銷 =70ns， 每條指令訪存 ， F直接 =%， F組 =%， Cycle直接 =2ns， Cycle組 =。 (2) 存儲系統(tǒng)的平均訪問時間 （ 從 CPU看 ） ： 其中 H1～ Hn是來自互斥事件的完備群 ， 它們滿足關(guān)系式： 注意該公式忽略了各級之間的傳送時間 。 衡量處理機(jī)速度的常用標(biāo)準(zhǔn)是 CPI， 因為它與程序執(zhí)行時間成正比 。 偽相聯(lián)（續(xù) 2） 計算機(jī)系統(tǒng)結(jié)構(gòu) 48 偽相聯(lián)（續(xù) 3） 折中方案：偽相聯(lián)（ 2路） ， 目錄表法（ P209） P 位 S 位 虛地址 虛塊號 偏移 標(biāo)識段 索引段 （ p 1 位 ） p 位 最高位 實地址 先補(bǔ) 0 常通方向 實存 目錄表 1 塊 =2S 標(biāo)識 0 實塊號 0 標(biāo)志位 裝入？ ∶ 先比較 正常命中？ ∶ 后比較 偽命中？ 標(biāo)識 1 實塊號 1 標(biāo)志位 裝入？ ∶ 行數(shù) =2P 行數(shù) = 塊數(shù) 8b 塊數(shù) =2p 正常命中： 偽命中（增加 2 拍）： AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB AF IF ID EX ME WB 計算機(jī)系統(tǒng)結(jié)構(gòu) 49 例 （補(bǔ)充， 2版 P198例 ） 一個偽相聯(lián) Cache，當(dāng)在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個位置才找到數(shù)據(jù)（偽命中）時需要增加 2個額外的周期。若不命中，則再到另一區(qū)相應(yīng)的位置去查找。 索引 =0的實塊里裝的虛塊標(biāo)識可以是 00， 01， …… ， 99，對應(yīng)的虛塊號就是 000， 010， 020，030， …… ， 990。 虛實變換基本方法（續(xù) 1） 虛頁號 項號 標(biāo)識 實頁號 裝入標(biāo)志 其它標(biāo)志 標(biāo)識 11 索引 10 00 11 01 1 ? 01 00 00 0 ? 10 01 11 1 ? 11 10 10 1 ? 計算機(jī)系統(tǒng)結(jié)構(gòu) 39 (3) 快慢表方法（ P231） 這是頁表法的一種加快方案。這種方法原理簡單，但是占用空間非常大。 另外 ， 從數(shù)據(jù)的分布情況看。 2 實組 1 頁 4 √ √ 5 當(dāng)然這兩方面優(yōu)點是互相抵觸的：組內(nèi)頁數(shù)越多 ， 實存空間劃分的組數(shù)就越少 ， 實組號字段所占位數(shù)也少 ， 這時改善實頁爭用現(xiàn)象的效果較好 ， 而節(jié)省頁表空間的效果較差 ， 反之亦然 。 6 √ 7 7 √( a ) 虛頁集合與實頁集合的對應(yīng)關(guān)系 ( b) 對應(yīng)關(guān)系表 （ √ 為有關(guān)系）虛地址 虛頁號 1 1 1 頁內(nèi)偏移量 D實地址 實頁號 1 1 頁內(nèi)偏移量 d( c ) 通過 求模運算進(jìn)行虛實變換示例 計算機(jī)系統(tǒng)結(jié)構(gòu) 31 (3) 組相聯(lián) (set associative， P194) 組相聯(lián)映象方式是全相聯(lián)與直接相聯(lián)的一個折中方案 ， 性能也是二者的折中 。 這種映象方式主要用于對實存價格 、 速度敏感的 Cache主存層次 。 1 虛 3 √ √ √ √ 4 這種關(guān)系可用下頁示意圖 (a)、 (b)表示 。 例 計算機(jī)系統(tǒng)結(jié)構(gòu) 23 (2) TA＝