【正文】 存 。 頁失效 指當前被訪問存儲級中沒有所需的信息，也就是不命中現(xiàn)象。依劃分標準不同，存在 3種存儲層次管理方式。段的長度不一，但段內所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進行信息保護。 因其實現(xiàn)較復雜 ， 僅用于主存 —輔存層次 。 我們把用戶文件劃分得到的一個長度單位稱為 “ 虛頁 ” ，因為它的頁號是在虛地址空間中編排的；實地址空間按頁的大小劃分得到的一個長度單位稱為 “ 實頁 ” 。 (3)段頁式管理 。 它的實現(xiàn)最復雜 ， 僅用于主存 —輔存層次 。修改標志為 “ 0” 表示該頁還沒有被修改過，為 “ 1” 則表示該頁已經被修改過。 (2)如果不發(fā)生主存頁面失效的話，計算訪問主存的物理地址。 基本調度單位：頁，幾百 Byte到幾千 Byte。 速度比：幾倍。 (1) 容量： S = S2 （ 理論上 ） (2) 單價： （ 美分 /bit） 2021212121221121l i m1ccSSccSSSSScSccSS???????????它的最小值是 計算機系統(tǒng)結構 11 (3) 速度 表現(xiàn)訪問速度的參數(shù)較多。 計算機系統(tǒng)結構 13 假設： TAi表示第 i級器件讀 /寫時間； TBi表示第 i級向上級傳送時間 。 (1) 分別計算三種方案的等效訪問時間； (2) 分別計算三種方案每 KB的平均價格； (3) 分別根據(jù)等效訪問時間、每 KB的平均價格排序； (4) 根據(jù)等效訪問時間和平均價格的乘積排序。 (1)按圖 (a)求 TA和 e； (2)按圖 (b)推導三層體系的 TA公式； (3)按圖 (b)求 TA和 e； (4)比較 (1)(3)結果，有何結論？ 解： 計算機系統(tǒng)結構 16 多級存儲層次的平均訪問時間 2 ? ?322221111111331131331 )2(%91 %)101(101100101 101F 10110 )1(AMMAMMAAAAAAAATTTFTTTFTTTTeTsssTFTTH?????????????????????????，此處，???? ?22121122211 MAAMAAATFFTFTTFTFTT??????????由這 2式合并得 此公式參見教材 P214倒數(shù)第 12行?！笆А钡亩x是經過等待后完成的訪問，而“命中”是不需要等待即完成的訪問，僅此不同。此后 M1向 M2發(fā)出的 999次請求都能立即響應，而再下一次請求又需要等待 … 。 局部不命中率與全局不命中率（ P214） 級訪問次數(shù)到達第級不命中次數(shù)第局部不命中率iii ?發(fā)出的訪問總次數(shù)級不命中次數(shù)第全局不命中率CP Uii ? 計算機系統(tǒng)結構 20 因為： 所以： 依此類推， …… 局部不命中率與全局不命中率（續(xù) ） 級訪問次數(shù)到達第級不命中次數(shù)第 1?? ii111 局部不命中率發(fā)出的訪問總次數(shù)級不命中次數(shù)第全局不命中率 ??CP U2121212局部不命中率局部不命中率級不命中次數(shù)第級不命中次數(shù)第發(fā)出的訪問總次數(shù)級不命中次數(shù)第發(fā)出的訪問總次數(shù)級不命中次數(shù)第全局不命中率?????C P UC P U3213231213局部不命中率局部不命中率局部不命中率級不命中次數(shù)第級不命中次數(shù)第級不命中次數(shù)第級不命中次數(shù)第發(fā)出的訪問總次數(shù)級不命中次數(shù)第發(fā)出的訪問總次數(shù)級不命中次數(shù)第全局不命中率???????C P UC P U 計算機系統(tǒng)結構 21 多級存儲層次的平均訪問時間公式重寫 將這些局部不命中率、全局不命中率的定義式代入到前面的多級存儲層次平均訪問時間公式中，我們可以得到更容易記憶的公式形式： AnnAAAAnnAAAATTTTTFFTFFTFTT???????????????????????13221111321211 全局不命中率全局不命中率全局不命中率?? 計算機系統(tǒng)結構 22 例 考慮某一兩級 Cache： 第一級 Cache為 L1， 第二級 Cache為 L2。 例 計算機系統(tǒng)結構 23 (2) TA＝ TA1＋ F1 (TA2＋ F2 TM2) ＝ 1＋ 4% (10＋ 50% 100) ＝ 1＋ 4% 60＝ 式中后面部分 4% 60為每次訪存的平均停頓時間（即 失效開銷 ）： 每次訪存的平均停頓時間（即 失效開銷 ）＝ 4% 60＝ 由于平均每條指令訪存 ，所以： 每條指令的平均停頓時間＝ ＝ 習題 例 （續(xù)） 計算機系統(tǒng)結構 24 各次作業(yè)應交的內容 作業(yè) 8（第 9次課） 2 月 19 日 1. 10 ( 改 ) ， 1. 7 ， 1. 1 1( 2 解法 ) 4 月 9 日 7. 14 ( 難題 ) ， 7. 12 ( 難題 ) 2 月 26 日 2. 14 ( 補充 ) ，實驗 1 ， 3. 8 ， 3. 10 4 月 16 日 8. 12 ( 補 ) ， 8. 1 1( 改 ) ( 難題 ) 3 月 5 日 3. 1 1( 改 ) ，實驗 2 ， 5. 1 1 ， 5. 8 ， 5. 9 4 月 23 日 9. 9( 改 ) ， 9. 13 3 月 12 日 6. 8( 改 ) ， 6. 7 ， 7. 9 4 月 30 日 10 .6 ， 10 .9 ( 難題 ) 4 月 2 日 7. 1 1 ， 7. 10 計算機系統(tǒng)結構 25 地址映象問題的提出 頁表必須存放在實存 M1里 。 為避免逐行比對 ， 利用相聯(lián)存儲器存放此表 ， 它具有并行比較功能 ， 但價格遠高于普通存儲器 。 這種關系可用下頁示意圖 (a)、 (b)表示 。 由于頁表必須常駐在實存中 ， 而主存 輔存層次的實存 （ 即主存 ） 相對Cache主存層次的實存 （ 即 Cache存儲器 ） 容量大得多 ， 所以全相聯(lián)映象方式一般用于主存 輔存層次 。 1 虛 3 √ √ √ √ 4 實現(xiàn)起來非常簡單 ， 因為在二進制中 ， 任何數(shù) X對 2的整次冪 n求模等價于截取 X的最低 log2n位 ， 如下頁示意圖 (c)所示 。 這種映象方式主要用于對實存價格 、 速度敏感的 Cache主存層次 。 0 2 √ 3 6 √ 7 7 √( a ) 虛頁集合與實頁集合的對應關系 ( b) 對應關系表 （ √ 為有關系）虛地址 虛頁號 1 1 1 頁內偏移量 D實地址 實頁號 1 1 頁內偏移量 d( c ) 通過 求模運算進行虛實變換示例 計算機系統(tǒng)結構 31 (3) 組相聯(lián) (set associative， P194) 組相聯(lián)映象方式是全相聯(lián)與直接相聯(lián)的一個折中方案 ， 性能也是二者的折中 。 在虛實變換時 ， 首先根據(jù)虛頁號所在的虛組號 ， 通過求模運算確定實組號 ， 再按虛組號在相應的子表內讀出組內頁號 ， 拼接在一起就是實頁號 。 當然這兩方面優(yōu)點是互相抵觸的：組內頁數(shù)越多 ， 實存空間劃分的組數(shù)就越少 ， 實組號字段所占位數(shù)也少 ， 這時改善實頁爭用現(xiàn)象的效果較好 ， 而節(jié)省頁表空間的效果較差 ， 反之亦然 。 下頁圖示為 2路組相聯(lián) （ 2way set associative）。 2 實組 1 頁 4 √ √ 5 例如 ， 虛塊 0可以映象到實組 0的任意一塊中 。 另外 ， 從數(shù)據(jù)的分布情況看。 位選擇組相聯(lián)的地址變換過程比一般組相聯(lián)映象方式簡單 ， 而與全相聯(lián)映象方式基本相同 。這種方法原理簡單，但是占用空間非常大。（與 Hash查表有點相似） 表項數(shù)少于虛頁數(shù)意味著查表時會有多個虛頁查到表中同一項的情況發(fā)生，另外也意味著區(qū)分表中項號的地址位數(shù)少于虛頁號的位數(shù)，虛頁號中未用的位數(shù)正是造成重復的原因。 虛實變換基本方法（續(xù) 1） 虛頁號 項號 標識 實頁號 裝入標志 其它標志 標識 11 索引 10 00 11 01 1 ? 01 00 00 0 ? 10 01 11 1 ? 11 10 10 1 ? 計算機系統(tǒng)結構 39 (3) 快慢表方法（ P231） 這是頁表法的一種加快方案。 虛實變換基本方法（續(xù) 3） 從 2g組中 選擇一組 h 位 g 位 標識 索引 相聯(lián)比較 … … 總容量： 2g n 項 組內塊地址（ log 2 n 位） n 個項 標識存儲器 計算機系統(tǒng)結構 41 (5) 單體多字存儲器＋多比較器查表方法（ P196第 2段 ） 這是 目錄表 法的一種廉價方案，對組相聯(lián)非常適用。 索引 =0的實塊里裝的虛塊標識可以是 00， 01， …… ， 99，對應的虛塊號就是 000， 010， 020，030， …… ， 990。優(yōu)點是命中時間短、 不命中 率還低，所以它的平均訪問時間往往比直接相聯(lián)、組相聯(lián)都短 。若不命中，則再到另一區(qū)相應的位置去查找。 每次訪問時間有 3種可能： ? 正常命中（快速命中） ? 偽命中（慢速命中） ? 不命中 偽相聯(lián)（續(xù) 1） 索引 至 CPU 取出數(shù)據(jù)送往 CPU 偽相聯(lián)組 … … 計算機系統(tǒng)結構 47 (4) 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中，就是命中率要高。 偽相聯(lián)（續(xù) 2） 計算機系統(tǒng)結構 48 偽相聯(lián)（續(xù) 3） 折中方案：偽相聯(lián)（ 2路） ， 目錄表法（ P209） P 位 S 位 虛地址 虛塊號 偏移 標識段 索引段 （ p 1 位 ） p 位 最高位 實地址 先補 0 常通方向 實存 目錄表 1 塊 =2S 標識 0 實塊號 0 標志位 裝入？ ∶ 先比較 正常命中？ ∶ 后比較 偽命中？ 標識 1 實塊號 1 標志位 裝入？ ∶ 行數(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 計算機系統(tǒng)結構 49 例 （補充， 2版 P198例 ） 一個偽相聯(lián) Cache，當在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個位置才找到數(shù)據(jù)（偽命中）時需要增加 2個額外的周期。這種情況下 1路要增加 50拍。 衡量處理機速度的常用標準是 CPI， 因為它與程序執(zhí)行時間成正比 。 下圖說明訪存等待 （ 不命中 ） 會延長 瞬時 CPI。 (2) 存儲系統(tǒng)的平均訪問時間 （ 從 CPU看 ） ： 其中 H1～ Hn是來自互斥事件的完備群 ， 它們滿足關系式： 注意該公式忽略了各級之間的傳送時間 。 解： 已知 TA1=， 即理想 CPI = ， TA2=50， F=2%， 平均每條指令訪存 CPU時間 有 cache＝ IC （ CPIexecution＋ 每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時鐘周期時間 ＝ IC （ ＋ 2 % 50） 時鐘周期時間 ＝ IC 時鐘周期時間 從此式知，實際 CPI＝ ＋ 2 % 50＝ ， 是理想情況下的 ＝ (倍 )，換言之， CPU時間是理想情況下的 。