【正文】 利用堆棧技術模擬LRU在不同 n條件下頁面變化時空圖及命中率。LRU算法的實現(xiàn)方法 :堆棧法、比較對法167。167。 4存貯體系的兩個分支存貯體系的兩個分支虛擬存貯器的簡單工作過程Cache— 主存體系與虛擬存儲器異同之處167。5 內(nèi)部定向原理介紹內(nèi)部定向原理的 有向圖 和 有向簡圖 的繪制 組相聯(lián)映象的例子 頁面替換時空圖 主存地址到 Cache地址的變換 167。3替換算法及其實現(xiàn)替換算法及其實現(xiàn)FIFO、 LRU、 OPT上述算法在給定地址流及主存頁面數(shù)下頁面變化時空圖主存頁面數(shù) n的大小對命中率的影響6解： 1） 主存Nd q s Nrq’ s’ nrCache2）01234567主存頁號1位 1位 1位1位 1位 3) 可放入 Cache 0組的主存塊號 : 0 1 4 5 可放入 Cache 1組的主存塊號 : 2 3 6 74) 凡是不命中就是失效 。 失效而發(fā)生替換就是爭用。 塊失效、塊爭用的時刻 t = 6,7,9,10,11,12,14,155) tA=H*tc+(1H)*tm=*2+*15=(ns)時間 t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15地址流 1 2 4 1 3 7 0 1 2 5 4 6 4 7 20 0 1 1 1 1 1 1 1 1 1 1 4 4 4 4 41 4 4 4 4 0 0 0 5 5 5 5 5 51 0 2 2 2 2 7 7 7 7 7 7 6 6 6 21 3 3 3 3 2 2 2 2 2 7 7命中情況 失 失 失 中 失 爭 爭 中 爭 爭 爭 爭 中 爭 爭塊爭用 : 換出了不該換出的頁面 . 所以 :即失效又爭用的時刻是 : t=10,11,15t塊流qs1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 4 1 3 7 0 1 2 5 4 6 4 7 20 0 ① 1 1 1 1 1 1 1 1 1 4 4 4 4 41 ④ 4 4 4 0 0 0 ⑤ 5 5 5 5 51 0 ② 2 2 2 ⑦ 7 7 7 7 7 ⑥ 6 6 ②1 ③ 3 3 3 ② 2 2 2 2 ⑦ 7失 失 失 中 失 失 失 中 失 爭 爭 失 中 失 爭[例 ] 考慮一個 920個字的程序，其訪問輔存的地址流為20， 22， 208， 214， 146， 618， 370， 490， 492，868， 916， 728。 若頁面大小為 200字，主存容量為 400字，采用全相聯(lián) FIFO替換算法，請按訪存的各個時刻，寫出其虛頁地址流，計算主存的命中率； [解 ] 虛頁號＝ └ 虛地址／頁面大小 ┘ 頁面大小為 200字，主存容量為 400字，可知主存頁數(shù)為 2頁。其虛頁地址流為 0， 0， 1， 1， 0， 3， 1， 2， 2， 4， 4， 3 下圖給出了采用 FIFO替換算法替換時的實際裝入和替換過程。其中， “”標記的是候選替換的虛頁頁號，下劃線表示命中。 t虛地址頁面流 20 22 208 214 146 618 370 490 492 868 916 7280 0 1 1 0 3 1 2 2 4 4 3? 0 0 0 0 ③ 3 3 3 ④ 4 4 ① 1 1 1 1 ② 2 2 2 ③H=6/12=1 2 3 4 5 6 7 8 9 10 11 12167。6 交叉訪問的存儲器交叉訪問的存儲器主存儲器由多個模塊構成。假設主存儲器包含 m=2a個存儲器模塊，每個模塊包含 w=2b個存儲單元（字），則總存儲容量為多體交叉存儲器的兩種組織方式交叉訪問的存儲器可以分為兩種：(1)低位交叉方式 （體內(nèi)斷續(xù)，體間連續(xù)）(2)高位交叉方式 （體內(nèi)連續(xù)，體間斷續(xù)）1）低位交叉方式存儲器地址的低 a位用來指明存儲器模塊，高 b位是每個模塊內(nèi)的字地址。低位 m路交叉存取如下圖：… …b位 a位地址譯碼器 MAB0m……m(w1)MDBM0MAB1m+1……mwm+1MDBM1……MABm12m1……mw1MDBMm1WAB字 模塊……地址ab數(shù)據(jù)總線存儲器數(shù)據(jù)緩沖器模塊地址緩沖器字地址緩沖器2）高位交叉方式存儲器地址的高 a位作為存儲器模塊地址，鄰接的存儲器單元被分配在同一個存儲器模塊中，在每個存儲器周期內(nèi)，只能對各模塊存取一個字。所以不支持鄰接單元的成塊存取。高位 m路交叉存取如下圖：地址譯碼器 MAB01……w1MDBM0MABww+1……2w1MDBM1……MAB(m1)wmww1……mw1MDBMm1WAB字模塊……地址ab數(shù)據(jù)總線存儲器數(shù)據(jù)緩沖器模塊地址緩沖器字地址緩沖器3）兩種方式的比較（ 1）低位交叉以流水線方式支持成塊存取 將存儲器周期稱為主周期，細分為 m個小周期（m稱為交叉存取度），如 8路交叉， m=8， w=8， a=b=3，設 ?為主周期， ?為小周期，則8路低位交叉存取如下圖：08…56存儲器地址寄存器 (6位 )M019…57M1210…58M2311…59M3412…60M4513…61M5614…62M6715…63M7數(shù)據(jù)低位交叉流水線方式示意圖：W0W7W6W5W4W3W2W1 ?? 時間?為主周期， ?= ?/m為小周期， m為交叉存取度（ 2） 如果應用問題很少共享地址空間，把一個進程的幾頁集中在高位交叉存儲器的某個給定的存儲器模塊中，能有效的減少存儲器干擾，即每個存儲器模塊只和一臺處理機有關，可以減少存儲器沖突。 將高位與低位交叉存取加以組合。高位交叉時，各存儲器模塊內(nèi)的地址是按順序連續(xù)編排的。對 8個存儲模塊，將它們分為 2個存儲器，體內(nèi)采用 4路低位交叉存取。示意圖如下：4） 容錯04…28存儲器地址寄存器 (6位 )M015…29M126…30M237…31M33236…60M43337…61M53438…62M63539…63M7體 0 體 1體地址字地址模塊地址對 8個存儲模塊，將它們分為 4個存儲器，體內(nèi)采用 2路低位交叉存取。示意圖如下：02…14存儲器地址寄存器 (6位 )M013…15M11618…30M21719…31M33234…46M43335…47M54850…62M64951…63M7體 0 體 2體地址字地址模塊地址體 1 體 3在一個模塊發(fā)生故障的情況下 ：8路（ 1體）交叉存取存儲器的最大存儲器帶寬減少到零；4路 2體交叉存儲器的最大帶寬減少到每周期 4個字（只有一個體被廢棄）；2路 4體交叉存儲器中，仍有 3個體工作，所以最大帶寬為 6個字。 習題 ：假定一個由 16個存儲器模塊構成的主存儲器系統(tǒng)有下列三種交叉存儲器設計方案。每個模塊的容量為 1M字節(jié)，機器按字節(jié)尋址。設計 1：用 1個存儲體 16路交叉。設計 2：用 2個存儲體 8路交叉。設計 3：用 4個存儲體 4路交叉。（ a） 確定上述存儲器組織的地址構成。（ b） 在上述每種存儲器組織中，假定只有一個存儲器模塊失效，確定能獲得的最大存儲器帶寬。設計 1： 1個存儲體 16路交叉。 a)地址構成：存儲器地址寄存器 (24位 )b）帶寬為 0?！?0位 4位數(shù)據(jù)024…22416存儲器地址寄存器 (24位 )M0124+1…22415M1241251…2241M15……設計 2： 2個存儲體 8路交叉。 a)地址構成： 存儲器地址寄存器 (24位 )b）帶寬為 50%。存儲器地址寄存器 (24位 )體地址 模塊地址08…2238M0715…M7…M8…M15體 0 體 1字地址存儲器地址寄存器 (24位 )體地址 模塊地址… …22312232248223+72241…存儲器地址寄存器 (24位 )體