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