1、一、在頁式虛擬存儲(chǔ)器中，一個(gè)程序由 04 共 5 個(gè)虛頁組成，在程序執(zhí)行過程中，訪存虛頁地 址流為： 0，1，0 ，4，3，0 ，2，3，1 ，3假設(shè)分配給這個(gè)程序的主存空間有 3 個(gè)實(shí)頁，分 別采用 FIFO 、LRU 和OPT 替換算法進(jìn)行替換調(diào)度。（1 ）分別畫出 3 種替換算法對(duì)主存 3 個(gè)實(shí)頁位置的使用過程。（2 ）分別計(jì)算 3 種替換算法的主存命中率。解（1 ）分別用 FIFO 、LRU 和OPT 替換算法對(duì)主存 3 個(gè)實(shí)頁位置的使用過程如圖（2 ）由使用過程可得：FIFO 替換算法的主存命中率為： H1=2/10=0.20；LRU 替換算法的主存命中率為：H2=4/10=0.40

2、； OPT 替換算法的主存命中率為： H3=5/10=0.50 。二、有一個(gè) Cache 存儲(chǔ)器，主存有 8 塊（ 07 ），Cache 有4 塊（ 03 ），采用 組相聯(lián)映像，組內(nèi)塊數(shù)為 2 塊。采用 LRU 替換算法1 ）寫出主存地址和 Cache 地址的格式，并指出各字段的長度2 ）指出主存各塊與 Cache 各塊之間的映像關(guān)系。3 ）某程序運(yùn)行過程中，訪存的主存塊地址流為：地址格式為：1，2，4，1 ，3，7 ，0，1，2 ，5，4 ，6 ，4 ，7 ，2說明該程序訪存對(duì) Cache 的塊位置的 使用情況，指出發(fā)生塊失效且塊爭用的時(shí)刻，計(jì)算 Cache 命中率。解：（1 ）采用組相聯(lián)映

3、像時(shí)，主存地址格式和 Cache主存按 Cache 大小劃分為區(qū)，主存容量為 8 塊， Cache 容量為 4 塊，故主存分為 2 個(gè) 區(qū)，區(qū)號(hào) E 的長度為 1 位。組內(nèi)有 2 塊，故組內(nèi)塊號(hào) B 和b 的長度都是 1 位。 Cache 被分為2 組，故組號(hào) g 的長度是 1 位；主存的一個(gè)區(qū)也被分為 2 組，故區(qū)內(nèi)組號(hào) G 的長度也是 1 位。塊內(nèi)地址 W 和 w 的長度由塊的大小確定， 由本題給出的條件， 不能確定塊的大小， 因而不能確定 W 和 w 的長度。（2 ）組相聯(lián)映像規(guī)定：主存的組到 Cache 的組之間是直接映像，對(duì)應(yīng)組的塊之間是全相聯(lián)映 像。因此，主存塊 07 與Cache

4、 塊03 之間的映像關(guān)系如圖 4.15 所示?？傻贸鲋鞔鎵K 07 與Cache 塊03 之間的映像關(guān)系是： 主存塊0、1、4、5 只能裝入 Cache 塊0、1 的任何塊位置上 主存塊 2、3、6、7 只能裝入 Cache 塊 2、3 的任何塊位置上意的是：當(dāng)裝入 Cache 塊 04.16 所示。需要注和塊 1 位置上的主存塊發(fā)生塊沖突時(shí)，就要由替換算法指定其中的被替換主存塊；當(dāng)裝入 Cache 塊2 和塊 3 位置上的主存塊發(fā)生塊沖突時(shí)，也要由替換算法 指定其中的被替換主存塊。因此，當(dāng) Cache 的 4 個(gè)塊位置（ 03 ）都被裝入時(shí)，其中的 2 個(gè) 主存塊就會(huì)被指定為被替換塊。在圖 4

5、.16 中用星號(hào)“ * ”標(biāo)示被替換算法指定的被替換塊。發(fā)生塊失效且塊爭用時(shí)需要進(jìn)行替換，在 Cache 使用過程中，發(fā)生塊失效且塊爭用的時(shí)刻有： t6, t7, t9, t10, t11, t12, t14, t15 。命中3 次：在t4 時(shí)，命中 Cache 塊0 位置上的主存 塊1 ；在t8 時(shí)，再次命中主存塊 1 ；在t13 時(shí)，命中Cache 塊0 位置上的主存塊 4 。Cache 命 中率為 H=3/15=0.20 。三、假設(shè)某程序不計(jì)訪存時(shí)間的指令執(zhí)行時(shí)間都為 2 個(gè)時(shí)鐘周期， 平均每條指令訪存 1.33 次。 增設(shè)Cache 后，程序訪存命中 Cache 的概率為98% ，命中

6、Cache 時(shí)指令用于訪存所需時(shí)間為 2 個(gè)時(shí)鐘周期， 未命中 Cache 時(shí)指令用于訪存所需時(shí)間為 50 個(gè)時(shí)鐘周期。 請(qǐng)分別計(jì)算不設(shè)置 Cache 和增設(shè) Cache 兩種情況下的程序的指令平均執(zhí)行時(shí)間(指令平均時(shí)鐘周期數(shù)) ，以及增 設(shè) Cache 相對(duì)于不設(shè)置 Cache 的加速比。解 : 不設(shè)置 Cache 時(shí)，平均每條指令訪存所需時(shí)間為：50 ×1. 33=66 . 5 時(shí)鐘周期不計(jì)訪存時(shí)間的指令平均執(zhí)行時(shí)間為 2 個(gè)時(shí)鐘周期，所以，包括訪存時(shí)間在內(nèi)的指令執(zhí)行的平 均時(shí)鐘周期數(shù)為：CPIM= 66 . 5+2 = 68 . 5 時(shí)鐘周期增設(shè) Cache 后，平均每條指令一次訪存所需時(shí)間為：T = HTc+(1 H)TM= 0 . 98 × 2+(10 . 98) × 50=2 .96 時(shí)鐘周期包括訪存時(shí)間在內(nèi)的指令執(zhí)行的平均時(shí)鐘周期數(shù)為：CP