【文章內(nèi)容簡介】 32，w＝512，Tm＝1280ns， Bm＝n w/tm＝32180。512b/1280ns ＝ ＝ ＝400MW/s T＝， 與Tm相比，峰值速度提高512倍。一個程序共有5個頁面組成，分別為P1～P5。程序執(zhí)行過程中的頁地址流（即程序執(zhí)行中依次用到的頁面）如下：P1，P2，P1，P5，P5，P1，P3，P4，P3，P4假設分配給這個程序的主存儲器共有3個頁面。給出FIFO、LRU和OPT三種頁面替換算法對這3頁主存的使用情況，包括調(diào)入、替換和命中等。時間t12345678910實際頁地址流P1P2P1P5P4P1P3P4P2P4命中次數(shù)1111*444*4*22先進先出算法2222*1111*4（FIFO算法）555*3333*調(diào)入調(diào)入命中調(diào)入替換替換替換命中替換替換2次11111111*22最久沒有使用算法222*444*444（LRU算法）55*5*333*3*調(diào)入調(diào)入命中調(diào)入替換命中替換命中替換命中4次111111*3*3*33最優(yōu)替換算法2222*22222（OPT算法）5*444444調(diào)入調(diào)入命中調(diào)入替換命中替換命中命中命中5次三種頁面替換算法對同一個頁地址流的調(diào)度過程一個循環(huán)程序，依次使用P1，P2，P3，P4四個頁面，分配給這個程序的主存頁面數(shù)為3個。FIFO、LRU和OPT三種頁面替換算法對主存頁面的調(diào)度情況如下圖所示。在FIFO和LRU算法中，總是發(fā)生下次就要使用的頁面本次被替換出去的情況，這就是“顛簸”現(xiàn)象。時間t12345678實際頁地址流P1P2P3P4P1P2P3P4命中次數(shù)111*444*33先進先出算法222*111*4（FIFO算法）333*222*調(diào)入調(diào)入調(diào)入替換替換替換替換替換0次111*444*33最久沒有使用算法222*111*4（LRU算法）333*222*調(diào)入調(diào)入調(diào)入替換替換替換替換替換0次11111*111最優(yōu)替換算法22222*3*3（OPT算法）3*4*4444*調(diào)入調(diào)入調(diào)入替換命中命中替換命中3次頁面調(diào)度中的顛簸現(xiàn)象由三個訪問速度、存儲容量和每位價格都不相同的存儲器構成一個存儲體系。其中，M1靠近CPU，回答下列問題： M1(T1,S1,C1) M2(T2,S2,C2) M3(T3,S3,C3)（1） 寫出這個三級存儲體系的等效訪問時間T，等效存儲容量S和等效每位價格C的表達式。（2）在什么條件下，整個存儲體系的每位價格接近于C3？直接代公式計算存儲層次性能指標。(1)74ns，38ns，(2)，(3)T256K T128K T64K c256K c128K c64K(4)。答案是256K方案最優(yōu)。已知，其中g=依題意有≥，解出，向下取整，得15；按另一種題意理解是向上取整，得16，也對。方式1：16個模塊高位交叉方式2：16個模塊并行訪問 方式3：16個模塊低位交叉 方式4：2路高位交叉8路低位交叉16個存儲模塊每8個組成一個大的模塊：方式5：4路高位交叉4路低位交叉16個存儲模塊每4個組成一個大的模塊：方式6：4路并行訪問4路低位交叉（1）這幾種存儲器都能夠并行工作，因此可以提高頻帶寬度?？偟膩碚f，并行訪問存儲器的優(yōu)點是實現(xiàn)簡單、容易，缺點是訪問沖突大；高位交叉訪問存儲器的優(yōu)點是擴充方便，缺點是訪問效率不高；低位交叉訪問存儲器可以用分時的方法來提高速度，但擴充不方便。（2）各種存儲器的頻帶寬度和他們的工作頻率有關，在不考慮沖突的情況下，如果有足夠多的獨立控制電路和寄存器，那么，他們的頻帶寬度是相同的。（3）存儲器的邏輯示意圖略。注意，并行訪問存儲器和低位交叉訪問存儲器很相象，只不過，并行訪問存儲器使用存儲模塊號（存儲體號）來對已經(jīng)輸出的結果進行選擇，而低位交叉訪問存儲器則用來生成對存儲模塊（存儲體）的片選信號，他通過流水的方式來提高訪問的速度。在頁式虛擬存儲器中，一個程序由P1~P5共5個虛頁組成。在程序執(zhí)行過程中依次訪問到的頁面如下： P2 ，P3，P2，P1 ，P5 ，P2 ，P4 ，P5 ，P3 ，P2 ，P5 ，P2 假設系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種替換算法對這三頁主存進行調(diào)度。（1） 畫出主存頁面調(diào)入、替換和命中的情況表。（2） 統(tǒng)計三種頁面替換算法的頁命中率。（1）在分配的主存頁面數(shù)目大于等于5的情況下，這時，除了第一次調(diào)入不命中，以后的訪問均命中，可以達到最高的頁面命中率：實際命中的次數(shù)為7次，所以可能達到的最高頁面命中率為：（2）由于在頁面數(shù)大于等于5的情況下，肯定可以達到最高命中率，所以我們來看頁面數(shù)小于5時能否達到該命中率：分配的主存頁面數(shù)等于4時，調(diào)度過程如下： LFU算法44444*11111*11命中7次555*55555*5553333*33*333*32222*22222調(diào)入調(diào)入調(diào)入調(diào)入命中調(diào)入命中命中命中命中命中命中此時也可以達到最高命中率；分配的主存頁面等于3時，調(diào)度過程如下： LFU算法444*222*33*333*3命中3次555*555*222*11333*1111*555調(diào)入調(diào)入調(diào)入調(diào)入命中調(diào)入調(diào)入調(diào)入命中調(diào)入調(diào)入命中此時不能達到最高命中率。所以至少應該分配4個主存頁面。（3) 我們假設程序每次只訪問一個存儲單元，這樣，對每一個特定頁面的訪問過程可以描述如下：因為第一次總是不命中的，而平均起來，隨后的1023次總是命中的，然后再次被調(diào)出主存，并再次重復先前的過程。所以訪問存儲單元的命中率為： 欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關系。下圖就是“堆棧模擬圖”，其中“√”表示命中。P=453251323513命中次數(shù)4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7(1)Hmax=7/12≈%(2)n=4(3)當1次頁面訪問代表連續(xù)1024次該頁內(nèi)存儲單元訪問時，后1023次單元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁命中（折算為71024次單元命中），5次頁不命中（折算為51023次單元命中，也可寫為510245），單元訪問總次數(shù)為121024，故有：Hcell=(1210245)/(121024)=12283/12288≈%加1題 一個二級存儲層次，采用全相聯(lián)映象和最久沒有使用算法，實存共5頁，為2道程序分享，頁地址流分別如下P1 = 1 2 3 4 1 3 2 1P2 = 1 2 3 4 2 2 3 3試作2個實存分配方案，分別使2道程序滿足(1)命中率相同；(2)命中次數(shù)之和最大。P1 =12341321命中次數(shù)N(1)12341321123413212341312244n1= 10n1= 20n1= 3√√2n1= 4√√√√4解：分別為2道程序作“堆棧模擬圖”，其中“√”表示命中。P2 =12342233命中次數(shù)N(2)12342233123442212334411111n2= 1√√2n2= 2√√2n2= 3√√√√4n2= 4√√√√465 N(1)+N(2)432 N(1) N(2)1 1+4 2+3 3+2 4+1將兩圖結果綜合，得到4個分配方案的命中率情況表如下n11234N(1)0024n24321N(2)4422N(1)+N(2)4446結論如下(1)命中率相同的方案是n1= 3而n2= 2；(2)命中次數(shù)之和最大的方案是n1= 4而n2= 1。（1）主存共有2個區(qū)，每個區(qū)2組，每個組2塊，每塊16個字節(jié)，如果按字節(jié)尋址，那么主存需要7位，如下圖所示：（2）Cache地址需要6位，如下圖所示：中(3)(4)(6)(8)問 虛存 實頁 0 1 2 3虛組0 0 0 √ √ 1 實存 1 √ √ 虛組1 2 0 實組0 2 √ √ 3 1 虛 3 √ √虛組2 4 2 實組1 頁 4 √ √ 5 3 5 √ √ 虛組3 6 6 √ √ 7 7 √ √ (a) 虛頁集合與實頁集合的對應關系 (b) 對應關系表（√為有關系）(3)(4)通過作“實存狀況圖”模擬各虛塊的調(diào)度情況，可獲得Cache的塊地址流序列。P=624146304573C044*4444*44*4*4*C111*1*1*00*555C266*6*6*6*66*6*6*6*77*