【正文】 替換算法要解決的是選擇調(diào)出對象的問題。 4G地址空間中低 2G， 0x000000000x7FFFFFFF是用戶地址空間， 4G地址空間中高 2G， 0x800000000xFFFFFFFF 是系統(tǒng)地址空間。 每個進(jìn)程都有自己的 4G地址空間，從 0x000000000xFFFFFFFF。一個頁目錄有 1024項，也就對應(yīng)著 1024個頁表，每個頁表負(fù)責(zé) 4M地址空間的映射。 Windows 2021虛擬存儲器 4 計算機系統(tǒng)結(jié)構(gòu) 69 32bit的一個指針，可以尋址范圍 0x000000000xFFFFFFFF， 4GB大小。 一個頁目錄有 1024項，虛擬地址最高的 10bit剛好可以索引 1024項（ 2的10次方等于 1024）。對于一個要轉(zhuǎn)換成物理地址的虛擬地址， CPU首先根據(jù) CR3中的值，找到頁目錄所在的物理頁。對于 Intel CPU 來說，分頁標(biāo)志位是寄存器 CR0的第 31位，為 1表示使用分頁，為 0表示不使用分頁。 對于 x86系統(tǒng)，頁目錄的物理地址放在 CPU的 CR3寄存器中。 頁目錄 ———一個頁目錄大小為 4K字節(jié)，放在一個物理頁中。 Windows 2021虛擬存儲器 1 計算機系統(tǒng)結(jié)構(gòu) 66 頁表 ———一個頁表的大小為 4K字節(jié)，放在一個物理頁中。對于一般程序來說， 4G的地址空間，只有一小部分映射了物理內(nèi)存，大片大片的部分是沒有映射任何東西。由于頁的大小為 4KB， 就是 0x1000字節(jié)，所以第 1頁從物理地址 0x00001000處開始。程序中使用的都是 4GB地址空間中的虛擬地址。 按增加 1個時鐘周期的方案， L2Cache的命中時間為 11，有： 平均訪問時間 ＝ 11＋ 20% 50 ＝ 個時鐘周期 (2)(3)情況下 L2Cache的平均訪問時間都比直接相聯(lián)小，所以 L2Cache采用兩路組相聯(lián)性能更好。所以本題實質(zhì)上是問哪種映像方式下 L2Cache的平均訪問時間較小。 計算機系統(tǒng)結(jié)構(gòu) 61 例 （續(xù) 2） (2) CPU時間＝ IC（ CPIexecution＋ 每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時鐘周期時間 ＝ IC（ CPIexecution 時鐘周期時間＋每條指令的 平均訪存次數(shù)不命中率不命中開銷時鐘周期時間） 代入?yún)?shù)得： CPU時間 1路 ＝ IC ( 2＋ ( 70)) ＝ IC CPU時間 2路 ＝ IC ( 2 ＋ ( 70)) ＝ IC 直接映象 Cache的 CPU時間短一些。 分別比較它們的平均訪存時間、 CPU時間。 比較有 Cache與無 Cache情況下的 CPU時間。 訪存時間對 CPU性能的影響 2 存儲器平均不命中開銷延遲流水線自身產(chǎn)生的平均每條指令平均延遲理想理想平均?????C P IC P IC P I銷每條指令平均不命中開理想平均 ?? C P IC P I平均CPI 實際CPI 計算機系統(tǒng)結(jié)構(gòu) 56 (1) 第 i級的不命中率： 特殊地 ， F1又可以記為 F， 因為 M1被訪問次數(shù)就是 CPU的總訪存次數(shù) 。 我們現(xiàn)在只關(guān)心流水處理機 。 處理機速度越高要求訪存時間越短 。 偽相聯(lián)（續(xù) 6） 計算機系統(tǒng)結(jié)構(gòu) 52 結(jié)論： ? 從 不命中 率看， F2路 = F偽相聯(lián) F1路 ，偽相聯(lián)因不命中帶來的平均延時與 2路一樣短（ 1路較長）； ? 從命中時間看，偽相聯(lián)在正常命中時與 1路一樣短（ 2路較長），偽命中時要增加 2拍，后者概率 = H2路 – H1路 。 (5) 偽相聯(lián)的缺點： 它的多種命中時間使得 CPU流水線上各指令之間的時間對齊變得困難，所以往往應(yīng)用在離 CPU比較遠(yuǎn)的 Cache上，比如 L2Cache。 顯然偽 相聯(lián)的 “ 候選位置 ” =2， 與 2路組相聯(lián)相同。若命中，則其訪問過程與直接 相聯(lián) Cache的情況一樣。有沒有什么方法取二者之長呢？ (2) 偽相聯(lián)的優(yōu)點 偽相聯(lián)就是直接相聯(lián)、組相聯(lián)的一種組合方案。設(shè)虛塊號 =000～ 999，實塊號 =0～ 9，于是有索引 =0～ 9，而標(biāo)識 =00～ 99。 為避免逐行比對，須使用相聯(lián)存儲器來存放，通過并行比較實現(xiàn)一次查遍，器件價格遠(yuǎn)高于普通存儲器。 下圖以組相聯(lián)為例說明 “ 標(biāo)識 ” 的意義 ， 它有 16個虛頁 ， 只用 4個表項 。 虛實變換基本方法（ P195） 頁映象 L4 基址寄存器（ CR3 ） 63 000 ? 0 或 111 ? 1 頁映象 L4 頁映象 L4 表 頁映象項 + 頁目錄 + 頁目錄項 頁表項 指針項 + 頁目錄指針 頁目錄 頁表 頁內(nèi)位移 48 47 39 38 30 29 21 20 12 11 0 … … 頁目錄指針表 頁目錄表 頁表 + … … 物理地址 物理頁號 頁內(nèi)位移 主存儲器 計算機系統(tǒng)結(jié)構(gòu) 38 (2) 部分虛實 表法（ P195圖 ） 這是一種統(tǒng)稱，指表項數(shù)少于虛頁數(shù)的情形，下面要介紹的 3種方法都屬于這一類。 2 實組 1 頁 4 √ √ 5 3 5 √ √ 虛 區(qū) 3 6 6 √ √ 7 7 √ √ (a ) 虛頁集合與實頁集合的對應(yīng)關(guān)系 (b ) 對應(yīng)關(guān)系表（ √ 為有關(guān)系） 計算機系統(tǒng)結(jié)構(gòu) 36 位選擇組相聯(lián)的地址映象方式與地址變換原理 (c) 虛頁號 P 虛地址 虛區(qū)號 10 區(qū)內(nèi)頁號 1 頁內(nèi)偏移量 D 實地址 實組號 1 組內(nèi)頁號 0 頁內(nèi)偏移量 d 組內(nèi)頁號 裝入位 修改位 表項 0 ： ： ： ： ： ： ： 表項 P 0 1 0 ： ： ： ： 表項 7 ： ： ： (c ) 位選擇組相聯(lián)映象方式的 虛實變換 計算機系統(tǒng)結(jié)構(gòu) 37 (1) 頁表法 每個虛頁對應(yīng) 1項，虛頁號就是項號，項內(nèi)存儲實頁號，如課堂練習(xí) 。 由于虛存每個區(qū)中的塊數(shù)與實組數(shù)相等 ， 而且它們之間采用直接映象方式， 因此 ， 虛存地址中的區(qū)內(nèi)塊號可以直接作為實組號 。 映象關(guān)系明顯簡單 ， 實現(xiàn)起來可以容易些 。 虛塊號與實組號之間是直接映象關(guān)系 ， 而虛塊與該實組內(nèi)的各個實塊之間是全相聯(lián)映象方式 。 1 虛 3 √ √虛組 2 4 實組內(nèi)頁數(shù)被稱為 “ 路數(shù) ” ， 又稱為 “ 相聯(lián)度 ” （ associativity） ,它表明一個虛頁的選擇范圍 。 采用組相聯(lián)映象方式時 ， 每個虛頁在對應(yīng)實組范圍內(nèi)有若干映象實頁可供選擇 ， 實頁爭用的發(fā)生頻率比直接相聯(lián)要低；另一方面 ， 由于頁表內(nèi)原來存放的實頁號改成存組內(nèi)頁號 ， 省略了實組號字段 ， 所以頁表占用空間也減少了 。 由于包含了兩層不同的映射關(guān)系 ， 頁表須按虛組劃分成許多子表 。 3 5 √ 6 實存 1 √ 2 直接相聯(lián)映象方式不需要借助頁表來進(jìn)行虛實變換 ， 顯然大大節(jié)省了相應(yīng)的空間與時間 （ 當(dāng)然頁表中的裝入位和修改位還得保留 ） ， 但是由于每個虛頁的選擇范圍太小 ， 實頁爭用的發(fā)生頻率較高 ， 常出現(xiàn)明明實存有空閑空間卻不得不調(diào)出一個現(xiàn)有虛頁以騰出所在實頁的情況 ， 這使系統(tǒng)的命中率和運行效率下降 。 為了便于虛實變換 ， 用求模運算作為變換關(guān)系式：將虛頁號對實頁總數(shù)求模得到實頁號 。 0 2 √ √ √ √ 3 但這種方式的頁表占用空間和查表時間開銷都比較大 ,也就是說實現(xiàn)成本比較高 ， 在命中情況下花費在虛實變換上的時間也比較多 。 （ TLB） / 減少行數(shù) / 減少行寬 計算機系統(tǒng)結(jié)構(gòu) 26 四種常見的地址映象方式（ P193） (1) 全相聯(lián) (fully associative) 全相聯(lián)就是無約束對應(yīng) ， 或者說是一個完全關(guān)系 ， 意思就是一個虛頁可以調(diào)入任何一個實頁 。 （ 又稱 “ 實頁表 ” ） / 減少行數(shù) 僅保留頁表中已裝入的虛頁記錄 。問：平均訪存時間是多少？每條指令的平均停頓時間（即 失效開銷 ）是多少個時鐘周期？ 解： (1) 第一級 Cache的不命中率（全局和局部）是 40/1000，即 4%； 第二級 Cache的局部不命中率是 20/40，即 50%； 第二級 Cache的全局不命中率是 20/1000，即 2%。為了避免混淆，有必要分清兩種不命中率： 全局不命中率是一個比局部不命中率更有意義的指標(biāo)，它指出了在CPU發(fā)出的所有訪存請求中，究竟有多大比例是穿過該級，到達(dá)下一級存儲器的。這次訪問稱為“失效”。同學(xué)們不要把訪問“失效”理解為訪問“失敗”，認(rèn)為 CPU在 M1找不到數(shù)據(jù)就會放棄本次訪問。忽略傳送時間 TB。忽略平均訪存時間 TA公式中的 TB。（，其中 rTTreAA 11012 ????rFTFTTTTeAAAAA???????112111 e 是一個相對值，便于不同系統(tǒng)之間的比較。 多級層次以及附加開銷留到以后討論 。 基本調(diào)度單位：塊，幾十 Byte。 計算機系統(tǒng)結(jié)構(gòu) 8 “主 ─輔”層次與“ Cache─主存”層次的對比 （ P192表 ， P231表 ） ? “ 主存 輔存 ” 層次 目的：提高等效容量。現(xiàn)有一個程序，出現(xiàn)下列訪問主存的操作： 虛存地址 序號 操作 ( B ) ( X ) D 1 取數(shù) 124 30 50 2 取數(shù) 2021 1000 60 3 存數(shù) 4000 2021 600 4 存數(shù) 1200 4600 60 5 取數(shù) 3000 640 100 6 取數(shù) 4096 500 20 7 加并存數(shù) 400 1200 80 8 加并存數(shù) 36 360 64 9 轉(zhuǎn)移 2500 600 100 10 轉(zhuǎn)移 3600 1200 56 (1)列出產(chǎn)生主存頁面失效的操作序號?，F(xiàn)有一個程序的頁表如下： 虛頁號 裝入標(biāo)志 主存頁號 修改標(biāo)志 訪問方式 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 表中的裝入標(biāo)志為 “ 1” 表示該虛頁已經(jīng)裝入主存，為 “ 0” 則表示還未裝入主存。 段頁式管理的主要缺點是多查一次表 ， 虛實變換費時較多 ， 占用空間也較大 。 兩種層次都用此技術(shù) 。按頁劃分用戶文件可以避免上述零碎空間浪費。 段式管理方法的虛實變換算法是查段表 。段是程序中的一個邏輯單位，可以是一個程序模塊，或者是一個數(shù)據(jù)結(jié)構(gòu)。 計算機系統(tǒng)結(jié)構(gòu) 4 存儲層次的管理方式 (P230) 根據(jù)程序的局部化性質(zhì)，存儲層次機構(gòu)對用戶文件的管理應(yīng)該劃分成較小的基本調(diào)度單位來進(jìn)行。 地址變換 （又叫虛實變換）指邏輯地址到物理地址的變換過程或者算法。 物理地址 （ 又稱為絕對地址 、 實地址 ） 是任一級存儲器為全部存儲單元分配的序號 。 ? 依據(jù)：程序訪問的局部化原理 （ 時間局部化 ， 空間局部化 ） 。 本章學(xué)習(xí)提高主存系統(tǒng)性能 /價格比的幾種結(jié)構(gòu)化方法，重點是“ Cache主存層次 ” ，焦點問題是 如何使流水線每拍完成一次訪存 。 本章基本公式： (1)平均時間 T = P1 T1 + P2 T2 其中 P1 + P2 = 100%，并且 T1 和 T2 都可以再用該式迭代展開，復(fù)雜 時，可用概率樹來表示（全概率公式）； (2)實際時間 T = 理想時間 + P3 每次額外開銷時間 其中 P3 是不利事件發(fā)生概率。 ? 模型：如右圖所示 ， 存儲層次由 n層組成 ， 滿足 3個不等式： TAiTAi+1， cici+1， SiSi+1 。 物理地址的取值范圍稱為物理地址空間 、 實空間或?qū)?