【正文】 1） 解： 摘要：理想 CPI=2， 不命中開銷 =70ns， 每條指令訪存 ， F直接 =%， F組 =%， Cycle直接 =2ns， Cycle組 =。 比較直接映象 Cache（ 即 1路）與 2路組相聯(lián) Cache的平均訪存時(shí)間、 CPU時(shí)間。 (1) 平均訪存時(shí)間為： 平均訪存時(shí)間＝命中時(shí)間＋不命中率不命中開銷 因此，兩種結(jié)構(gòu)的平均訪存時(shí)間分別是： 平均訪存時(shí)間 1路 ＝ ＋（ 70）＝ 平均訪存時(shí)間 2路 ＝ ＋（ 70）＝ 兩路組相聯(lián) Cache的平均訪存時(shí)間短一些。 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 61 例 （續(xù) 2） (2) CPU時(shí)間＝ IC（ CPIexecution＋ 每條指令的平均訪存次數(shù) 不命中率不命中開銷） 時(shí)鐘周期時(shí)間 ＝ IC（ CPIexecution 時(shí)鐘周期時(shí)間＋每條指令的 平均訪存次數(shù)不命中率不命中開銷時(shí)鐘周期時(shí)間） 代入?yún)?shù)得： CPU時(shí)間 1路 ＝ IC ( 2＋ ( 70)) ＝ IC CPU時(shí)間 2路 ＝ IC ( 2 ＋ ( 70)) ＝ IC 直接映象 Cache的 CPU時(shí)間短一些。 IC CPU時(shí)間 1路 ───── ＝ ───── ＝ IC CPU時(shí)間 2路 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 62 欲設(shè)計(jì)一個(gè) L2Cache， 已知它的不命中開銷 L2 ＝ 50個(gè)時(shí)鐘周期，問下列兩種映像方式對(duì)不命中開銷有何影響。 (1) L2Cache采用直接相聯(lián)，局部不命中率 L2 ＝ 25%，命中時(shí)間 L2 ＝ 10個(gè)時(shí)鐘周期； (2) L2Cache采用兩路組相聯(lián)，局部不命中率 L2 ＝ 20% ，命中時(shí)間 L2 ＝ 。 解： （此例與 P204的例 ，注意區(qū)別） 題目已經(jīng)給出了 L2Cache恒定的“不命中開銷 L2”，那么它的不同映像方式影響的只能是 L1Cache的不命中開銷，根據(jù)多級(jí)存儲(chǔ)層次原理，TM1 ＝ M2的平均訪問時(shí)間。所以本題實(shí)質(zhì)上是問哪種映像方式下 L2Cache的平均訪問時(shí)間較小。 另外，在不使用 L3Cache情況下，“不命中開銷 L2 ＝ 50個(gè)時(shí)鐘周期”意思是“主存平均訪問時(shí)間 ＝ 50個(gè)時(shí)鐘周期”。 例 （ P216） 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 63 (1) L2Cache采用直接相聯(lián) 平均訪問時(shí)間 ＝ ＋ 25% 50 ＝ 個(gè)時(shí)鐘周期 (2) L2Cache采用兩路組相聯(lián) 平均訪問時(shí)間 ＝ ＋ 20% 50 ＝ 個(gè)時(shí)鐘周期 (3) 兩路組相聯(lián)的命中時(shí)間之所以比直接相聯(lián)增加 ，是因?yàn)樘搶?shí)變換按組查表后要進(jìn)行多路選擇（ P199圖 P198第 8段），需要額外增加時(shí)間。具體實(shí)現(xiàn)方案可以把時(shí)鐘周期調(diào)慢為 （這將使所有動(dòng)作都減慢 1%，甚至主存訪問 ），或者僅在命中時(shí)增加 1個(gè)時(shí)鐘周期。 按增加 1個(gè)時(shí)鐘周期的方案， L2Cache的命中時(shí)間為 11，有： 平均訪問時(shí)間 ＝ 11＋ 20% 50 ＝ 個(gè)時(shí)鐘周期 (2)(3)情況下 L2Cache的平均訪問時(shí)間都比直接相聯(lián)小，所以 L2Cache采用兩路組相聯(lián)性能更好。 注：教材中該例中說“幸運(yùn)的話，取整為 10個(gè)周期”，就是說多路選擇動(dòng)作時(shí)間有可能“擠”進(jìn)原有的 10周期中，習(xí)題中通常不這樣給條件。 習(xí)題 例 （續(xù) ） 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 64 各次作業(yè)應(yīng)交的內(nèi)容 作業(yè) 10（第 11次課） 2 月 19 日 1. 10 ( 改 ) ， 1. 7 ， 1. 1 1( 2 解法 ) 4 月 9 日 7. 14 ( 難題 ) ， 7. 12 ( 難題 ) 2 月 26 日 2. 14 ( 補(bǔ)充 ) ，實(shí)驗(yàn) 1 ， 3. 8 ， 3. 10 4 月 16 日 8. 12 ( 補(bǔ) ) ， 8. 1 1( 改 ) ( 難題 ) 3 月 5 日 3. 1 1( 改 ) ，實(shí)驗(yàn) 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 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 65 Windows 2021 使用基于分頁(yè)機(jī)制的虛擬內(nèi)存。每個(gè)進(jìn)程有 4GB的虛擬地址空間。程序中使用的都是 4GB地址空間中的虛擬地址。而訪問物理內(nèi)存，需要使用物理地址。 物理內(nèi)存以字節(jié)（ 8位）為單位編址。 物理內(nèi)存分頁(yè)，一個(gè)物理頁(yè)的大小為 4K字節(jié)，第 0個(gè)物理頁(yè)從物理地址 0x00000000 處開始。由于頁(yè)的大小為 4KB， 就是 0x1000字節(jié)，所以第 1頁(yè)從物理地址 0x00001000處開始。第 2頁(yè)從物理地址 0x00002021處開始?？梢钥吹接捎陧?yè)的大小是 4KB， 所以只需要 32bit的地址中高 20bit來尋址物理頁(yè)。 使用了分頁(yè)機(jī)制之后， 4G的地址空間被分成了固定大小的頁(yè)，每一頁(yè)或者被映射到物理內(nèi)存，或者被映射到硬盤上的交換文件中，或者沒有映射任何東西。對(duì)于一般程序來說， 4G的地址空間，只有一小部分映射了物理內(nèi)存，大片大片的部分是沒有映射任何東西。物理內(nèi)存也被分頁(yè)，來映射地址空間。對(duì)于 32bit的 Win2k， 頁(yè)的大小是 4K字節(jié)。 CPU用來把虛擬地址轉(zhuǎn)換成物理地址的信息存放在叫做頁(yè)目錄和頁(yè)表的結(jié)構(gòu)里。 Windows 2021虛擬存儲(chǔ)器 1 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 66 頁(yè)表 ———一個(gè)頁(yè)表的大小為 4K字節(jié)，放在一個(gè)物理頁(yè)中。由 1024個(gè) 4字節(jié)的頁(yè)表項(xiàng)組成。頁(yè)表項(xiàng)的大小為 4個(gè)字節(jié) (32bit)， 所以一個(gè)頁(yè)表中有1024個(gè)頁(yè)表項(xiàng)。頁(yè)表中的每一項(xiàng)的內(nèi)容（每項(xiàng) 4個(gè)字節(jié) ,32bit） 高 20bit用來放一個(gè)物理頁(yè)的物理地址，低 12bit放著一些標(biāo)志。 頁(yè)目錄 ———一個(gè)頁(yè)目錄大小為 4K字節(jié)，放在一個(gè)物理頁(yè)中。由 1024個(gè)4字節(jié)的頁(yè)目錄項(xiàng)組成。頁(yè)目錄項(xiàng)的大小為 4個(gè)字節(jié) (32bit)， 所以一個(gè)頁(yè)目錄中有 1024個(gè)頁(yè)目錄項(xiàng)。頁(yè)目錄中的每一項(xiàng)的內(nèi)容（每項(xiàng) 4個(gè)字節(jié)）高20bit用來放一個(gè)頁(yè)表（頁(yè)表放在一個(gè)物理頁(yè)中）的物理地址，低 12bit放著一些標(biāo)志。 對(duì)于 x86系統(tǒng)，頁(yè)目錄的物理地址放在 CPU的 CR3寄存器中。 如果 CPU寄存器中的分頁(yè)標(biāo)志位被設(shè)置，那么執(zhí)行內(nèi)存操作的機(jī)器指令時(shí)， CPU會(huì)自動(dòng)根據(jù)頁(yè)目錄和頁(yè)表中的信息，把虛擬地址轉(zhuǎn)換成物理地址，完成該指令。比如 mov eax,004227b8h ， 這是把地址 004227b8h處的值賦給寄存器的匯編代碼， 004227b8這個(gè)地址就是虛擬址。 CPU在執(zhí)行這行代碼時(shí)，發(fā)現(xiàn)寄存器中的分頁(yè)標(biāo)志位已經(jīng)被設(shè)定，就自動(dòng)完成虛擬地址到 Windows 2021虛擬存儲(chǔ)器 2 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 67 物理地址的轉(zhuǎn)換，使用物理地址取出值，完成指令。對(duì)于 Intel CPU 來說，分頁(yè)標(biāo)志位是寄存器 CR0的第 31位，為 1表示使用分頁(yè)，為 0表示不使用分頁(yè)。對(duì)于初始化之后的 Win2k 我們觀察 CR0 ， 發(fā)現(xiàn)第 31位為 1。表明Win2k是使用分頁(yè)的。 CPU把虛擬地址轉(zhuǎn)換成物理地址： 一個(gè)虛擬地址，大小 4個(gè)字節(jié) (32bit)， 包含著找到物理地址的信息，分為3個(gè)部分：第 22位到第 31位這 10位（最高 10位）是頁(yè)目錄中的索引，第 12位到第 21位這 10位是頁(yè)表中的索引，第 0位到第 11位這 12位（低 12位）是頁(yè)內(nèi)偏移。對(duì)于一個(gè)要轉(zhuǎn)換成物理地址的虛擬地址， CPU首先根據(jù) CR3中的值，找到頁(yè)目錄所在的物理頁(yè)。然后根據(jù)虛擬地址的第 22位到第 31位這10位（最高的 10bit)的值作為索引，找到相應(yīng)的頁(yè)目錄項(xiàng) (PDE,page directory entry),頁(yè)目錄項(xiàng)中有這個(gè)虛擬地址所對(duì)應(yīng)頁(yè)表的物理地址。有了頁(yè)表的物理地址，根據(jù)虛擬地址的第 12位到第 21位這 10位的值作為索引，找到該頁(yè)表中相應(yīng)的頁(yè)表項(xiàng) (PTE,page table entry),頁(yè)表項(xiàng)中就有這個(gè)虛擬地址所對(duì)應(yīng)物理頁(yè)的物理地址。最后用虛擬地址的最低 12位，也就是頁(yè)內(nèi) Windows 2021虛擬存儲(chǔ)器 3 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 68 偏移，加上這個(gè)物理頁(yè)的物理地址，就得到了該虛擬地址所對(duì)應(yīng)的物理地址。 一個(gè)頁(yè)目錄有 1024項(xiàng)，虛擬地址最高的 10bit剛好可以索引 1024項(xiàng)（ 2的10次方等于 1024）。一個(gè)頁(yè)表也有 1024項(xiàng)，虛擬地址中間部分的 10bit， 剛好索引 1024項(xiàng)。虛擬地址最低的 12bit（ 2的 12次方等于 4096），作為頁(yè)內(nèi)偏移，剛好可以索引 4KB， 也就是一個(gè)物理頁(yè)中的每個(gè)字節(jié)。 一個(gè)虛擬地址轉(zhuǎn)換成物理地址的計(jì)算過程就是，處理器通過 CR3找到當(dāng)前頁(yè)目錄所在物理頁(yè)，取虛擬地址的高 10bit,然后把這 10bit右移 2bit（ 因?yàn)槊總€(gè)頁(yè)目錄項(xiàng) 4個(gè)字節(jié)長(zhǎng)，右移 2bit相當(dāng)于乘 4）得到在該頁(yè)中的地址，取出該地址處 PDE（ 4個(gè)字節(jié)），就找到了該虛擬地址對(duì)應(yīng)頁(yè)表所在物理頁(yè)，取虛擬地址第 12位到第 21位這 10位，然后把這 10bit右移 2bit（ 因?yàn)槊總€(gè)頁(yè)表項(xiàng) 4個(gè)字節(jié)長(zhǎng)，右移 2bit相當(dāng)于乘 4）得到在該頁(yè)中的地址，取出該地址處的 PTE（ 4個(gè)字節(jié)），就找到了該虛擬地址對(duì)應(yīng)物理頁(yè)的地址，最后加上 12bit的頁(yè)內(nèi)偏移得到了物理地址。 Windows 2021虛擬存儲(chǔ)器 4 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 69 32bit的一個(gè)指針，可以尋址范圍 0x000000000xFFFFFFFF， 4GB大小。也就是說一個(gè) 32bit的指針可以尋址整個(gè) 4GB地址空間的每一個(gè)字節(jié)。一個(gè)頁(yè)表項(xiàng)負(fù)責(zé) 4K的地址空間和物理內(nèi)存的映射，一個(gè)頁(yè)表 1024項(xiàng)，也就是負(fù)責(zé) 1024*4k=4M的地址空間的映射。一個(gè)頁(yè)目錄項(xiàng)，對(duì)應(yīng)一個(gè)頁(yè)表。一個(gè)頁(yè)目錄有 1024項(xiàng)，也就對(duì)應(yīng)著 1024個(gè)頁(yè)表，每個(gè)頁(yè)表負(fù)責(zé) 4M地址空間的映射。 1024個(gè)頁(yè)表負(fù)責(zé) 1024*4M=4G的地址空間映射。一個(gè)進(jìn)程有一個(gè)頁(yè)目錄。所以以頁(yè)為單位，頁(yè)目錄和頁(yè)表可以保證 4G的地址空間中的每頁(yè)和物理內(nèi)存的映射。 每個(gè)進(jìn)程都有自己的 4G地址空間，從 0x000000000xFFFFFFFF。 通過每個(gè)進(jìn)程自己的一套頁(yè)目錄和頁(yè)表來實(shí)現(xiàn)。由于每個(gè)進(jìn)程有自己的頁(yè)目錄和頁(yè)表，所以每個(gè)進(jìn)程的地址空間映射的物理內(nèi)存是不一樣的。兩個(gè)進(jìn)程的同一個(gè)虛擬地址處（如果都有物理內(nèi)存映射）的值一般是不同的，因?yàn)樗麄兺鶎?duì)應(yīng)不同的物理頁(yè)。 4G地址空間中低 2G， 0x000000000x7FFFFFFF是用戶地址空間， 4G地址空間中高 2G， 0x800000000xFFFFFFFF 是系統(tǒng)地址空間。訪問系統(tǒng)地址空間需要程序有 ring0的權(quán)限。 Windows 2021虛擬存儲(chǔ)器 5 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 70 Windows 2021虛實(shí)變換示意圖 指令 b 3 1 =1 表示分頁(yè) IR 操作碼 操作數(shù)（直接尋址） 實(shí)存空間（最多 4 G B ） 虛地址 CR1 寄存器 10b 10b 12b ∶ （虛頁(yè)號(hào)） 4 4 實(shí)地址 1 頁(yè) =212B CR3 寄存器 （ 4 KB ） 頁(yè)目錄首址 頁(yè)表 0 （取高 20 位） 實(shí)頁(yè)號(hào) 標(biāo)志位 頁(yè)目錄 20b 12b ∶ 頁(yè)表首址高 20 位 標(biāo)志位 ∶ ∶ ∶ ∶ ∶ ∶ ∶ 20b 12b 頁(yè)表 1023 ∶ 實(shí)頁(yè)號(hào) 標(biāo)志位 注：頁(yè)目錄、頁(yè)表大小都是 4 KB 20b 12b 8b 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 71 替換算法 (P198) 上面所講的地址映象方式是在虛頁(yè)調(diào)入時(shí)的 “ 選址 ” 規(guī)則，而地址變換方法則是命中時(shí)獲得實(shí)地址的手段。 不命中時(shí)需要增加的操作就是首先調(diào)出一頁(yè)，調(diào)出之后再調(diào)入稱為 “ 替換 ” 。 替換算法要解決的是選擇調(diào)出對(duì)象的問題。 替換算法的目的是在發(fā)生實(shí)頁(yè)爭(zhēng)用（即根據(jù)地址映象方式，將要調(diào)入的虛頁(yè)被允許進(jìn)入的所有實(shí)頁(yè)均被其它虛頁(yè)占用）時(shí)，選擇將