【正文】 都分為大小相等的若干塊（或稱頁、行），每塊的大小為 2b 個(gè)字節(jié)，通常為 29 （ 512B）， 210（ 1 024B）或 2112 048B）等，以塊為單位進(jìn)行映射。 Cache管理中用硬件實(shí)現(xiàn)變換。 Cache管理中經(jīng)常使用的映像方式有 3種。 直接映像 : 全相聯(lián)映像 組相聯(lián)映像 74 75 假設(shè)某系統(tǒng)的主存容量為 220 =1MB，若每塊容量為 2b =210=1024B =1KB，則被分為 1 024塊（ M=2m =210 =1024 （ =1MB/1024B）塊）； cache容量為 213 =8KB，每塊容量也是 1KB，則被分為 2c =23 =8塊為 23 =8塊。下面以此為例，介紹三種 cache的地址映射方法。 76 1．直接地址映射（ direct mapping） 直接地址映射是指主存中每一個(gè)塊只能映射到某一固定的 cache中，如圖所示。 把主存按 cache大小分為若干組，每一組按對(duì)應(yīng)的塊號(hào)進(jìn)行映射。如主存的第 0塊、第 8塊、 … 、第 1 016塊，只能映射到 cache的第0塊；而主存的第 1塊、第 9塊、 … 、第 1 017塊只能映射到 cache的第1塊，依次類推。 直接映射是最簡(jiǎn)單的映射方式，它將每個(gè)主存塊固定地映射到某個(gè)Cache行。直接映射的優(yōu)點(diǎn)是硬件簡(jiǎn)單，容易實(shí)現(xiàn)，但利用率（命中率）較低。 77 主存塊數(shù)： M=2m =210 =1024 （ =1MB/1024B）塊。而主存的塊可被分為 1024/8=128個(gè) 8塊組。則這種映射下，每個(gè) Cache塊對(duì)應(yīng)主存 2mc=2103=27=128塊的直接映像，而mc=7位就是標(biāo)記位。 Cache為它的每一塊都設(shè)置一個(gè) 7位的標(biāo)記，此例中為 8塊，則其對(duì)應(yīng)的標(biāo)記就有 8個(gè)，它們被存儲(chǔ)在 CAM中。 主存地址格式： 塊標(biāo)記 Cache塊號(hào)（ 3位） 塊內(nèi)地址（ 10位） 主存塊號(hào)（ 10位） Cache的地址格式（ 13位） 組號(hào)（ 7位） 78 直接映射的組成原理和查找方法示意圖 注意主存地址由 3個(gè)部分組成： n＝ t＋ s＋ w。標(biāo)簽存儲(chǔ)器只需要存儲(chǔ)最高 t位頁號(hào)地址，就可以確定主存塊對(duì)應(yīng)的 Cache行。 （塊 c位）（塊內(nèi)字 b位） 79 直接映射的一個(gè)示例圖 主存地址組成： n（ 24）＝ t（ 8）＋ s（ 14）＋ w（ 2） (c) (b) 80 2．全相聯(lián)地址映射（ fully associative mapping） 全相聯(lián)地址映射是指主存中的每一塊都可以映射到 cache的任何一塊位置上，如圖所示。這種映射方法比較靈活，cache的利用率高，但地址轉(zhuǎn)換速度慢，且需要采用某種置換算法將 cache中的內(nèi)容調(diào)入調(diào)出，實(shí)現(xiàn)起來系統(tǒng)開銷大。 81 全相聯(lián)映射（ Full Associative Mapping） 全相聯(lián)映射可以將一個(gè)主存塊存儲(chǔ)到任意一個(gè) Cache行，使用靈活，利用率（命中率）高，但是實(shí)現(xiàn)電路比較復(fù)雜。 注意主存地址由 2個(gè)部分組成： n＝ t＋ w，標(biāo)簽存儲(chǔ)器中必須保存完整的主存塊地址 t。 82 全相聯(lián)映射圖例 主存地址組成： n（ 24）＝ t（ 22）＋ w（ 2）。 83 3．組相聯(lián)地址映射（ set associative mapping） 主存按 Cache大小分成若干區(qū)，每個(gè)區(qū)分為若干組， cache和主存一樣都分組，組內(nèi)塊數(shù)都相同。主存中一個(gè)區(qū)內(nèi)的組數(shù)與 cache中的分組數(shù)相同。組間采用直接地址映射，而組內(nèi)采用全相聯(lián)地址映射。主存中的各組與 cache的組號(hào)間有固定的映射關(guān)系，但可以自由映射到對(duì)應(yīng)的 cache組中的任何一塊。 84 組相聯(lián)的映象規(guī)則： (1) 主存和 Cache按同樣大小劃分成塊。 (2) 主存和 Cache按同樣大小劃分成組。 (3) 主存容量是緩存容量的整數(shù)倍，將主存空間按緩沖區(qū)的大小分成區(qū)，主存中每一區(qū)的組數(shù)與緩存的組數(shù)相同。 (4) 當(dāng)主存的數(shù)據(jù)調(diào)入緩存時(shí)，主存與緩存的組號(hào)應(yīng)相等，也就是各區(qū)中的某一塊只能存入緩存的同組號(hào)的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放，即從主存的組到 Cache的組之間采用直接映象方式；在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。 85 組相聯(lián) Cache的檢索過程 直接映像的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，缺點(diǎn)是不夠靈活，主存塊與Cache塊對(duì)應(yīng)關(guān)系死板，不能充分利用 Cache存儲(chǔ)空間。 例 1：設(shè)主存容量 1MB，有 16KB直接映像的 Cache ，假定該Cache的塊為 8個(gè) 32位的字。解答下列問題： 1. 寫出 Cache的地址格式。 2. 寫出主存地址格式。 3. 塊表的容量多大？ 4. 畫出直接方式地址映像及變換示意圖。 5. 主存地址為 0DE8F8H的存儲(chǔ)單元在 Cache中什么位置？ 86 例 1解： ⑴ Cache容量 16KB， 16KB=214，所以 Cache地址為 14位；塊的大小為 8個(gè) 32位的字，即 32字節(jié)，所以塊內(nèi)地址為 5位，塊地址為 9位。 Cache地址格式為： 13 5 4 0 ⑵ 主存容量 1MB， 1MB=220，所以主存地址為 20位；塊的大小為 32字節(jié)，所以塊內(nèi)地址為 5位，塊地址為 9位，塊標(biāo)記為 6位。主存地址格式為： 19 14 13 5 4 0 ⑶ Cache的每一塊在表中有一項(xiàng)， Cache的塊地址為 9位，所以塊表的單元數(shù)為 29；塊表中存放的是塊標(biāo)記，由于塊標(biāo)記為 6位，所以塊表的字長(zhǎng)為 6位。故塊表的容量為： 29字 6位。 ⑷直接方式地址映像及變換示意圖如下： 87 塊地址 塊內(nèi)地址 塊標(biāo)記 塊地址 塊內(nèi)地址 （組內(nèi)塊數(shù)） （組數(shù)）88 塊 0 塊 1 塊 32256 塊 0 塊 1 塊 511 組 0 塊 32767 塊 511 塊 32255 組 63 主存 Cache 塊標(biāo)記 6位 塊地址 9位 塊內(nèi)地址 5位 塊地址 9位 塊內(nèi)地址 5位 ⑸ Cache容量為 16KB=214B，塊長(zhǎng)為 8 32=32B，所以 Cache有16 1024/32=512個(gè)塊。 因?yàn)橹鞔娴刂窞?0DE8F8H=1101 1110 1000 1111 1000， 所以主存塊號(hào) =1101 1110 1000 111，塊內(nèi)地址 =11000。 在直接映像方式下，主存中的塊號(hào)被分為兩部分， 6位的組號(hào)和 9位的塊號(hào)，則這個(gè)主存塊號(hào)科寫成如下格式： 110111， 101000111 37H組， 147H塊 即這個(gè)主存塊映像到 Cache中第 147H塊中塊中； 而塊內(nèi)的字節(jié)號(hào)是 11000 18H=24，塊內(nèi)第 24字節(jié)，也就是 24B/4B=6，第六個(gè)字。 所以，地址 0DE8F8H的單元在 Cache中的地址為 10 1000 1111 1000 第 137H（ 311）塊的第 6個(gè)字處。 89 例 2 塊表 Cache 0 1 2 ③ 110 0010 3 4 5 6 ① 110 110 7 8 9 10 ② 111 1010 11 12 13 14 15 其中第 5次和第 8次為命中訪問。 Cache中最后的內(nèi)容為紅色數(shù)字塊的內(nèi)容。 90 ④ 101 0010 設(shè)一個(gè) Cache采用直接映象， Cache中有 16個(gè)塊，訪問主存進(jìn)行連續(xù)讀操作的塊地址流序列為： 1100110(66H)， 1111010(7AH)， 1100010(62H)， 1010010(52H)， 1111010(7AH)， 0100110(26H)， 0001010(0AH)， 1010010(52H) ， 求連續(xù)訪問主存后 Cache的映像情況，設(shè)初始Cache為空。 ⑤ 111 1010 ⑥ 010 0110 ⑦ 000 1010 ⑧ 101 0010 91 例 2：設(shè)一個(gè) Cache采用直接映象，Cache中有 16個(gè)塊，訪問主存進(jìn)行連續(xù)讀操作的塊地址序列流為1100110(66H)，1111010(7AH)，1100010(62H)，1010010(52H)，1111010(7AH)，0100110(26H)，0001010(0AH)， 1010010(52H) ，求連續(xù)訪問主存后 Cache的映像情況，設(shè)初始Cache為空。 主存 Cache 66H 7AH 62H 52H 7AH 26H 0AH 52H 0 1 2 62H 52H 52H 52H 52H 52H 3 4 5 6 66H 66H 66H 66H 66H 26H 26H 26H 7 8 9 10 7AH 7AH 7AH 7AH 7AH 0AH 0AH 11 12 13 14 15 命中 √ √ Cache替換算法 當(dāng)新的主存字塊需調(diào)入 Cache，而相應(yīng)的 Cache位置又已被原來的內(nèi)容占據(jù)時(shí)，就產(chǎn)生了替換問題。 有兩種常用的替換算法 先進(jìn)先出（ FIFO）：最先調(diào)入 Cache的內(nèi)容被替換掉。 近期最少使用（ LRU）算法：把一組中近期最少使用的字塊替換出去。它需隨時(shí)記錄 Cache中各字塊的使用情況。 92 ⑧ 101 0010 虛擬存儲(chǔ)器 虛存指的是“主存 輔存”層次，它能使計(jì)算機(jī)有主存的容量，接近于主存的速度。它可使程序員按比主存大得多的空間來編程。即按虛存空間編址。 虛存空間（邏輯空間）如何變換成主存空間（物理空間）是虛存中一個(gè)重要的技術(shù)環(huán)節(jié)。即虛存 主存的地址變換。 虛存中的地址變換和替換算法采用和 Cache大致相同的原理。 在虛存管理中，可采用段式、頁式、段頁式管理方法。 P160圖 主存的變換示意圖。 虛存空間和主存空間都分頁，每頁大小固定，常見的有 1024個(gè)字（ 1K）， 2K等。 在主存中建立一種頁表，提供虛實(shí)地址變換機(jī)制。表中主要記錄著虛地址所對(duì)應(yīng)的實(shí)地址，并包含一些有關(guān)頁面的控制信息。 93