【正文】 ii ?發(fā)出的訪問總次數(shù)級不命中次數(shù)第全局不命中率CP Uii ? 計算機系統(tǒng)結(jié)構(gòu) 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)結(jié)構(gòu) 21 多級存儲層次的平均訪問時間公式重寫 將這些局部不命中率、全局不命中率的定義式代入到前面的多級存儲層次平均訪問時間公式中，我們可以得到更容易記憶的公式形式： AnnAAAAnnAAAATTTTTFFTFFTFTT???????????????????????13221111321211 全局不命中率全局不命中率全局不命中率?? 計算機系統(tǒng)結(jié)構(gòu) 22 例 考慮某一兩級 Cache： 第一級 Cache為 L1， 第二級 Cache為 L2。 例題說明： 31331 101F 10110 ??? ，H訪問 次數(shù) 1 2 ? 1000 1001 ? 虛 地址 0 1 ? 999 1000 ? 數(shù)據(jù) 流向 M2 → M1 → CPU M1 → CPU ? M1 → CPU M2 → M1 → CPU ? 訪問 時間 T A2 + T A 1 T A 1 ? T A 1 T A2 + T A 1 ? 訪問 結(jié)果 失效 （ 不 命中 ） 命中 ? 命中 失效 （ 不 命中 ） ? 32332 101F 10110 ??? ，H 計算機系統(tǒng)結(jié)構(gòu) 19 剛才推導中使用的不命中率都是局部不命中率。此后 M1向 M2發(fā)出的 999次請求都能立即響應，而再下一次請求又需要等待 … 。 M2的初始狀態(tài)為“空”，對于 M1的首次請求不能立即滿足，需要先從 M3索取 1000000字節(jié)數(shù)據(jù)填滿自己，再向 M1提供所要的 1000字節(jié)數(shù)據(jù)?！笆А钡亩x是經(jīng)過等待后完成的訪問，而“命中”是不需要等待即完成的訪問，僅此不同。 計算機系統(tǒng)結(jié)構(gòu) 18 (1)問中，為什么 ？ 答：每當 CPU訪問 M1不命中時，存儲系統(tǒng)會從 M3裝入 1000字節(jié)到 M1， 再從 M1取 1個字節(jié)送給 CPU， 所以本次訪問結(jié)果為“失效”，但是緊接著的 999次訪問將“命中”，以后又是如此重復， …… 。 (1)按圖 (a)求 TA和 e； (2)按圖 (b)推導三層體系的 TA公式； (3)按圖 (b)求 TA和 e； (4)比較 (1)(3)結(jié)果，有何結(jié)論？ 解： 計算機系統(tǒng)結(jié)構(gòu) 16 多級存儲層次的平均訪問時間 2 ? ?322221111111331131331 )2(%91 %)101(101100101 101F 10110 )1(AMMAMMAAAAAAAATTTFTTTFTTTTeTsssTFTTH?????????????????????????，此處，???? ?22121122211 MAAMAAATFFTFTTFTFTT??????????由這 2式合并得 此公式參見教材 P214倒數(shù)第 12行。假定指令字長 =1字節(jié)，程序中無轉(zhuǎn)移指令和內(nèi)存讀 /寫指令。 (1) 分別計算三種方案的等效訪問時間； (2) 分別計算三種方案每 KB的平均價格； (3) 分別根據(jù)等效訪問時間、每 KB的平均價格排序； (4) 根據(jù)等效訪問時間和平均價格的乘積排序。 多級存儲層次的單次訪問時間 CPU M 1 M 2 M n 圖 存儲層次模型 計算機系統(tǒng)結(jié)構(gòu) 14 課堂練習 設計 “Cache主存 ” 層次， Cache的容量有三種選擇，如上表所示。 計算機系統(tǒng)結(jié)構(gòu) 13 假設： TAi表示第 i級器件讀 /寫時間； TBi表示第 i級向上級傳送時間 。 ?????? ereH e r = 1 r = 9 0 1 H H 和 r 對 e 的作用 訪問效率 e 受 H 和 r 的影響（參見右圖）： 是鄰級速度比）。 (1) 容量： S = S2 （ 理論上 ） (2) 單價： （ 美分 /bit） 2021212121221121l i m1ccSSccSSSSScSccSS???????????它的最小值是 計算機系統(tǒng)結(jié)構(gòu) 11 (3) 速度 表現(xiàn)訪問速度的參數(shù)較多。 典型存儲層次（ PC計算機，以 Intel芯片組為例） 名稱 容量 二進制 訪問時間 頁（塊）尺寸 路數(shù) 一級 Cache 3 2 KB 2 2 15 1 n s = 1 10 9 1 6 B = 2 4 2 二級 Cache 2 M B 混合 2 20 2 n s = 2 10 9 16 主存 1 GB 2 30 3 0 n s = 3 10 8 4 KB = 2 12 硬盤 5 0 0 GB 2 39 3 m s = 3 10 3 計算機系統(tǒng)結(jié)構(gòu) 10 存儲層次的性能指標（ P189） 先以 2級存儲層次為例進行公式推導 ， 并且只考慮各級存儲器件自身的操作 ， 忽略控制機構(gòu)的附加開銷 。 速度比：幾倍。 虛實轉(zhuǎn)換：頁表（以虛頁號為索引） ? “Cache主存 ” 層次 目的：提高等效速度。 基本調(diào)度單位：頁，幾百 Byte到幾千 Byte。 (4)列出被修改過的主存頁面號。 (2)如果不發(fā)生主存頁面失效的話，計算訪問主存的物理地址。 計算機系統(tǒng)結(jié)構(gòu) 7 課堂練習 （續(xù) ） 虛地址經(jīng)變址尋址和基址尋址 (B)+(X)+D形成。修改標志為 “ 0” 表示該頁還沒有被修改過，為 “ 1” 則表示該頁已經(jīng)被修改過。 計算機系統(tǒng)結(jié)構(gòu) 6 課堂練習 一個頁式虛擬存儲器按字節(jié)編址，頁面大小為 1K字節(jié)，每個數(shù)據(jù)的字長為 4個字節(jié)。 它的實現(xiàn)最復雜 ， 僅用于主存 —輔存層次 。 其虛實變換算法是先查段表 ， 查出該段的頁表起始地址再查相應的頁表 。 (3)段頁式管理 。 頁式管理方法的虛實變換算法是查頁表 。 我們把用戶文件劃分得到的一個長度單位稱為 “ 虛頁 ” ，因為它的頁號是在虛地址空間中編排的；實地址空間按頁的大小劃分得到的一個長度單位稱為 “ 實頁 ” 。頁是系統(tǒng)規(guī)定的固定長度單位。 因其實現(xiàn)較復雜 ， 僅用于主存 —輔存層次 。 段式管理方法的主要缺點是各段長短不一 ， 調(diào)進調(diào)出之后容易形成大量不規(guī)則的零碎空間 。段的長度不一，但段內(nèi)所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進行信息保護。 (1)段式管理。依劃分標準不同，存在 3種存儲層次管理方式。 頁和塊 ：前者用于主 輔層次，后者用于 Cache主存層次，意義相同。 頁失效 指當前被訪問存儲級中沒有所需的信息，也就是不命中現(xiàn)象。 地址映象方式 指的是虛頁集合與實頁集合的對應規(guī)則，或者說是約束關系。 物理地址的取值范圍稱為物理地址空間 、 實空間或?qū)嵈?。 邏輯地址的取值范圍稱為邏輯地址空間 、 虛空間或虛存 。 ? 模型：如右圖所示 ， 存儲層次由 n層組成 ， 滿足 3個不等式： TAiTAi+1， cici+1， SiSi+1 。 它既能滿足 CPU的快速存取需要 ， 又有很大的存儲容量 ， 平均單位價格也很低 ， 等效于同時滿足 3方面要求的理想單一存儲部件 。 本章基本公式： (1)平均時間 T = P1 T1 + P2 T2 其中 P1 + P2 = 100%，并且 T1 和 T2 都可以再用該式迭代展開，復雜 時，可用概率樹來表示（全概率公式）； (2)實際時間 T = 理想時間 + P3 每次額外開銷時間 其中 P3 是不利事件發(fā)生概率。 計算機系統(tǒng)結(jié)構(gòu) 1 第 7章 存儲層次（ P188） Memory Hirarchy 長期存在的問題：在合理的總價格限制下，單一型主存器件的速度跟不上 CPU的發(fā)展，容量不能滿足軟件尺寸擴大。 本章學習提高主存系統(tǒng)性能 /價格比的幾種結(jié)構(gòu)化方法，重點是“ Cache主存層次 ” ，焦點問題是 如何使流水線每拍完成一次訪存 。 1 P 1 P 2 P 11 P 12 P 21 P 22 計算機系統(tǒng)結(jié)構(gòu) 2 存儲層次原理及性能指標（ P188） 基本原理 ? “ 存儲層次 ” 的定義： （ 參見 P189第 3段 ） 由 2種或多種存儲部件構(gòu)成的復合存儲系統(tǒng) ， 通過內(nèi)部管理機構(gòu)的 自動更換機制 ， 能夠不斷將大容量低速存儲部件中的活躍內(nèi)容復制到小容量高速存儲部件中 （ 后者作為前者的 局部副本 ） 。 ? 依據(jù)：程序訪問的局部化原理 （ 時間局部化 ， 空間局部化 ） 。 CPU M 1 M 2 M n 圖 存儲層次模型 計算機系統(tǒng)結(jié)構(gòu) 3 存儲層次的基本術(shù)語 邏輯地址 （ 又稱為相對地址 、 虛地址 ） 是程序員在編寫和編譯一個程序模塊時分配指令和數(shù)據(jù)的空間單位序號 ， 總是從 0開始 （ 可以按字節(jié)編址 、 按CPU字編址等 ） 。 物理地址 （ 又稱為絕對地址 、 實地址 ） 是任一級存儲器為全部存儲單元分配的序號 。 從 M1到 Mn各層都有自己的物理地址空間 ， 而對當前執(zhí)行的程序模塊來說 ，邏輯地址空間只有一個 。 地址變換 （又叫虛實變換）指邏輯地址到物理地址的變換過程或者算法。 實頁爭用 又叫實頁沖突，指虛頁調(diào)入時，根據(jù)地址映象方式劃定的實空間范圍內(nèi)已沒有空閑實頁的狀況。 計算機系統(tǒng)結(jié)構(gòu) 4 存儲層次的管理方式 (P230) 根據(jù)程序的局部化性質(zhì)，存儲層次機構(gòu)對用戶文件的管理應該劃分成較小的基本調(diào)度單位來進行。 目前在主存 —輔存層次實現(xiàn)中，具體機器可能采用 3種方式中的某 1種，而 Cache主存層次普遍只采用第 2種，因為它簡單，便于硬件實現(xiàn)。段是程序中的一個邏輯單位，可以是一個程序模塊，或者是一個數(shù)據(jù)結(jié)構(gòu)。 每段使用獨立的邏輯地址空間 ， 即都從 0開始計算地址 。 段式管理方法的虛實變換算法是查段表 。 計算機系統(tǒng)結(jié)構(gòu) 5 存儲層次的管理方式 (續(xù) ) (2)頁式管理。按頁劃分用戶文件可以避免上述零碎空間浪費。 頁式管理方法的主要缺點是按固定長度分出來的同一頁內(nèi)常有不同屬性的信息，不便于信息保護的實現(xiàn)。 兩種層次都用此技術(shù) 。 它把上述兩種管理方式結(jié)合起來 ， 首先將整個文件分段 ，然后在各段內(nèi)分頁 ， 所以有一個段表和若干個頁表 。 段頁式管理的主要缺點是多查一次表 ， 虛實變換費時較多 ， 占用空間也較大 。 段頁式管理方法的最小調(diào)度單位仍是頁 ， 基本操作可歸于頁式管理 ?，F(xiàn)有一個程序的頁表如下： 虛頁號 裝入標志 主存頁號 修改標志 訪問方式 0 1 2 0 RW 1 1 3 0 R 2 0 0 0 R 3 1 1 0 X 4 0 0 0 RW 5 1 0 0 R 6 0 0 0 X 表中的裝入標志為