【文章內(nèi)容簡介】 tive， 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) （ 2way set associative）。 計算機系統(tǒng)結(jié)構(gòu) 32 組相聯(lián)的地址映象方式與地址變換原理 (a)(b) 虛存 實頁 0 1 2 3虛組 0 0 0 √ √ 1 實存 1 √ √虛組 1 2 0 實組 0 2 √ √ 3 1 虛 3 √ √虛組 2 4 2 實組 1 頁 4 √ √ 5 3 5 √ √虛組 3 6 6 √ √ 7 7 √ √( a ) 虛頁集合與實頁集合的對應關系 ( b) 對應關系表 （ √ 為有關系）組相聯(lián)的 “ 候選位置 ” 為組內(nèi)頁數(shù)，即 “ 路數(shù) ” 。 計算機系統(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é)合進行虛實變換示例 計算機系統(tǒng)結(jié)構(gòu) 34 (4) 位選擇組相聯(lián) (P194圖 ) 位選擇組相聯(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)映象方式基本相同 。 計算機系統(tǒng)結(jié)構(gòu) 35 位選擇組相聯(lián)的地址映象方式與地址變換原理 (a)(b) 虛存 實頁 0 1 2 3 虛 區(qū) 0 0 0 √ √ 1 實存 1 √ √ 虛 區(qū) 1 2 0 實組 0 2 √ √ 3 1 虛 3 √ √ 虛 區(qū) 2 4 2 實組 1 頁 4 √ √ 5 3 5 √ √ 虛 區(qū) 3 6 6 √ √ 7 7 √ √ (a ) 虛頁集合與實頁集合的對應關系 (b ) 對應關系表（ √ 為有關系） 計算機系統(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) 頁表法 每個虛頁對應 1項，虛頁號就是項號，項內(nèi)存儲實頁號，如課堂練習 。這種方法原理簡單，但是占用空間非常大。當頁表尺寸超過 1頁時，它本身還要按頁面尺寸分割成許多分散存放的子表，再造一個“表上表”來找到當前需要的子表。進一步發(fā)展就會形成“多級頁表” ， 導致虛實變換分多步進行，時間大大延長。 虛實變換基本方法（ 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種方法都屬于這一類。（與 Hash查表有點相似） 表項數(shù)少于虛頁數(shù)意味著查表時會有多個虛頁查到表中同一項的情況發(fā)生，另外也意味著區(qū)分表中項號的地址位數(shù)少于虛頁號的位數(shù)，虛頁號中未用的位數(shù)正是造成重復的原因。 表項數(shù)少于虛頁數(shù)的做法既是節(jié)省成本的需要，也符合任何時刻只有少部分虛頁占用實存的實際，問題是每個表項必須說明它當前記錄的是一組共享虛頁中的哪一個的信息，這就要用到“標識”字段。 虛頁號里用于計算表內(nèi)地址的部分稱為 “ 索引 ” index ， 用來與查表內(nèi)容相比較的部分稱為 “ 標識 ” tag。 下圖以組相聯(lián)為例說明 “ 標識 ” 的意義 ， 它有 16個虛頁 ， 只用 4個表項 。 虛實變換基本方法（續(xù) 1） 虛頁號 項號 標識 實頁號 裝入標志 其它標志 標識 11 索引 10 00 11 01 1 ? 01 00 00 0 ? 10 01 11 1 ? 11 10 10 1 ? 計算機系統(tǒng)結(jié)構(gòu) 39 (3) 快慢表方法（ P231） 這是頁表法的一種加快方案。地址變換緩沖器 TLB（ Translation Lookaside Buffer） 是一個專用的高速緩沖器，用于存放近期經(jīng)常使用的頁表項副本， TLB利用程序的局部性原理，以小表代替大表，縮短查找時間。 虛實變換基本方法（續(xù) 2） 虛擬地址 〈 36 〉 〈 12 〉 虛頁號 頁內(nèi)位移 物理地址 〈 1 〉 V R/W ① ② ③ ④ ? U/S D A 〈 1 〉 〈 1 〉 〈 36 〉 標識 〈 28 〉 ? ? 40 選 1 多路選擇器 ? 〈 28 〉 〈 12 〉 40 位 物理地址 （ 低 12 位地址 ） （ 高 28 位地址 ） 計算機系統(tǒng)結(jié)構(gòu) 40 (4) 目錄表法（ P196第 1段） 只對已經(jīng)裝入實存的虛頁造表，其項數(shù)比頁表少得多。 為避免逐行比對，須使用相聯(lián)存儲器來存放，通過并行比較實現(xiàn)一次查遍，器件價格遠高于普通存儲器。 虛實變換基本方法（續(xù) 3） 從 2g組中 選擇一組 h 位 g 位 標識 索引 相聯(lián)比較 … … 總?cè)萘浚?2g n 項 組內(nèi)塊地址（ log 2 n 位） n 個項 標識存儲器 計算機系統(tǒng)結(jié)構(gòu) 41 (5) 單體多字存儲器＋多比較器查表方法（ P196第 2段 ） 這是 目錄表 法的一種廉價方案，對組相聯(lián)非常適用。限制條件是組內(nèi)頁數(shù)不太多，下圖為 4的情況。 虛實變換基本方法（續(xù) 4） 計算機系統(tǒng)結(jié)構(gòu) 42 主 ─輔層次虛實變換實現(xiàn) 主流方案：全相聯(lián)，頁表法（ P232） P 位 S 位 虛地址 虛頁號 偏移 p 位 實地址 實存 頁表 1 頁 =2S 實頁號 標志位 裝入？ ∶ ∶ 行數(shù) =2P 行數(shù) 頁數(shù) 8b 頁數(shù) =2p 計算機系統(tǒng)結(jié)構(gòu) 43 Cache ─ 主存層次虛實變換實現(xiàn)（直接相聯(lián)） 快命中方案：直接相聯(lián)，目錄表法（ P196， 圖 ） P 位 S 位 虛地址 虛塊號 偏移 標識段 索引段 （ p 位 ） p 位 實地址 實存 目錄表 1 塊 =2S 標識 實塊號 標志位 裝入？ 比較 命中？ ∶ ∶ 行數(shù) =2P 行數(shù) = 塊數(shù) 8b 塊數(shù) =2p 舉例：為了方便用 10進制討論。設虛塊號 =000～ 999，實塊號 =0～ 9，于是有索引 =0～ 9，而標識 =00～ 99。 索引 =0的實塊里裝的虛塊標識可以是 00， 01， …… ， 99，對應的虛塊號就是 000， 010， 020，030， …… ， 990。 計算機系統(tǒng)結(jié)構(gòu) 44 Cache─主存層次虛實變換實現(xiàn)（組相聯(lián)） 低失效方案：位選擇組相聯(lián)（ 2路），目錄表法（ P196， 圖 ） P 位 S 位 虛地址 虛塊號 偏移 標識段 索引段 （ p 1 位 ） p 位 2 實地址 取 2 行 選擇 實存 目錄表 1 塊 =2S 標識 0 實塊號 0 標志位 裝入？ 標識 1 實塊號 1 標志位 裝入？ ∶ 0 比較 命中 0 ？ ∶ 1 比較 命中 1 ？ ∶ 行數(shù) =2P 行數(shù) = 塊數(shù) 8b 塊數(shù) =2p 直接相聯(lián)： 位選擇組相聯(lián)（時鐘延長 1 0 % ）： 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 I F ID EX ME WB AF IF ID EX ME WB 計算機系統(tǒng)結(jié)構(gòu) 45 偽相聯(lián)（ P209） 優(yōu) 點 缺 點 直接映象 組相