計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第三章習(xí)題解答

1、1.什么是存儲(chǔ)系統(tǒng)？對(duì)于一個(gè)由兩個(gè)存儲(chǔ)器M1和M2構(gòu)成的存儲(chǔ)系統(tǒng)，假設(shè)M1的命中率為h,兩個(gè)存儲(chǔ)器的存儲(chǔ)容量分別為si和S2,存取時(shí)間分別為 tl和t2,每千字節(jié)的成本分別為C1和C2。在什么條件下，整個(gè)存儲(chǔ)系統(tǒng)的每千字節(jié)平均成本會(huì)接近于C2?該存儲(chǔ)系統(tǒng)的等效存取時(shí)間ta是多少?假設(shè)兩層存儲(chǔ)器的速度比r=t2/ti，并令e=ti/ta為存儲(chǔ)系統(tǒng)的訪問(wèn)效率。試以r和命中率h來(lái)表示訪問(wèn)效率e。如果r=100,為使訪問(wèn)效率e0.95,要求命中率h是多少?對(duì)于中的命中率實(shí)際上很難達(dá)到,假設(shè)實(shí)際的命中率只能達(dá)到0.96?，F(xiàn)在采用一種緩沖技術(shù)來(lái)解決這個(gè)問(wèn)題。當(dāng)訪問(wèn)Mi不命中時(shí)，把包括被訪問(wèn)數(shù)據(jù)在內(nèi)的一個(gè)數(shù)

2、據(jù)塊都從 M 2取到Mi中，并假設(shè)被取到M1中的每個(gè)數(shù)據(jù)答:平均可以被重復(fù)訪問(wèn)5次。請(qǐng)?jiān)O(shè)計(jì)緩沖深度（即每次從 M2取到M1中的數(shù)據(jù)塊的大?。Ｕ麄€(gè)存儲(chǔ)系統(tǒng)的每千字節(jié)平均成本為:c1 s1 c2 s2c s1 s2.s1 c c1 c2 _S2s1c2。即：s2s1時(shí)，整個(gè)存S2不難看出：當(dāng)s1/s2非常小的時(shí)候，上式的值約等于儲(chǔ)器系統(tǒng)的每千字節(jié)平均成本會(huì)接近于c2。存儲(chǔ)系統(tǒng)的等效存取時(shí)間ta為:ta h t1 (1 h)t2t1t1h (1 h) re ta h t1(1 h) t2將數(shù)值代入上式可以算得：h99.95%通過(guò)緩沖的方法，我們需要將命中率從0.96提高到0.9995。假設(shè)對(duì)存儲(chǔ)器

3、的訪問(wèn)次數(shù)為5,緩沖塊的大小為m。那么，不命中率減小到原來(lái)的1/5m,列出等式有:C CCCL , 1 0.960.9995 1 5m解這個(gè)方程得：m=16，即要達(dá)到中的訪問(wèn)效率，緩沖的深度應(yīng)該至少是16 （個(gè)數(shù)據(jù)單位）。2.要求完成一個(gè)兩層存儲(chǔ)系統(tǒng)的容量設(shè)計(jì)。第一層M1是Cache,其容量有三種選擇：64KB、128KB和256KB，它們的命中率分別為 0.7、0.9和0.98;第二層M2是主存儲(chǔ)器，其容量為4MB。并設(shè)兩個(gè)存儲(chǔ)器的存取時(shí)間分別為tl和t2，每千字節(jié)的成本分別為C1和C2。如果C1=20C2和t2=10tl。在ti=20ns的條件下，分別計(jì)算三種存儲(chǔ)系統(tǒng)的等效存取時(shí)間。如果C

4、2=0.2美元/KB，分別計(jì)算三種存儲(chǔ)系統(tǒng)每千字節(jié)的平均成本。對(duì)三種存儲(chǔ)系統(tǒng)的設(shè)計(jì)作一個(gè)比較，并分別按平均成本和等效存取時(shí)間指出它們性能的排列次序。根據(jù)等效存取時(shí)間和平均成本的乘積，選擇最優(yōu)的設(shè)計(jì)。答:ta h t1 (1 h) t2 20h(1h)200200 180h (ns)三種存儲(chǔ)系統(tǒng)的等效存取時(shí)間分別為:ta1 200 180h200 180 0.774nsta2 200 180h200 180 0.938ns23.6 nsta3 200 180h200 180 0.98c1s1c2s24$/KB64KB0.2$/KB 41024KBs1s264 KB4 1024KBc1s1c2s2

5、4$/KB128KB0.2$/ KB 41024KBs1s2128KB4 1024KBc1s1c2s24$/KB256KB0.2$/ KB 41024KBs1s2256KB4 1024KB三種存儲(chǔ)系統(tǒng)每千字節(jié)的平均成本為:0.26$/KB0.32$/KB0.42$ / KB 按照平均成本來(lái)說(shuō)Ca1Ca2Ca3，按照等效存取時(shí)間來(lái)說(shuō)ta3ta2LkKJliJill .IV /f 粘 2)I譯巧辭 事I 低、丫 I方式6: 4路并行訪問(wèn)4路低位交叉/!、/廠、/、htR i|1. 11mBK 1ho 1111i t t it t i t t t t t4 出E 割 1- r * - * 321 V

6、I AR1r MAR11 hL1t t1 tI宀mJ扣：4.一個(gè)程序由5個(gè)虛頁(yè)組成，采用LRU替換算法，在程序執(zhí)行過(guò)程中依次訪問(wèn)的頁(yè)地址流如下:P4, P5, P3, P2, P5, P1, P3, P2, P3, P5, P1, P3可能的最咼頁(yè)命中率是多少？如果在程序執(zhí)行過(guò)程中每訪問(wèn)一個(gè)頁(yè)面,平均要對(duì)該頁(yè)面內(nèi)的存儲(chǔ)單元訪問(wèn)至少要分配給該程序多少個(gè)主存頁(yè)面才能獲得最高的命中率1024次，求訪問(wèn)存儲(chǔ)單元的命中率。答:在分配的主存頁(yè)面數(shù)目足夠大的情況下,除了第一次調(diào)入不命中，以后的訪問(wèn)均命中，可以達(dá)到最高的頁(yè)面命中率，即:實(shí)際命中的次數(shù)為7次，所以可能達(dá)到的最高頁(yè)面命中率為:H 右 0.5833

7、由于在頁(yè)面數(shù)大于等于5的情況下，肯定可以達(dá)到最高命中率，所以我們來(lái)看頁(yè)面數(shù)小于5時(shí)能否達(dá)到該命中率:5555555*5*5553333*3333332222*2222*2*調(diào)入調(diào)入調(diào)入調(diào)入命中調(diào)入命中命中命中命中命中命中算法7次此時(shí)也可以達(dá)到最高命中率；若分配的主存頁(yè)面等于3時(shí)，調(diào)度過(guò)程如下:訪問(wèn)流P4P5P3P2P5P1P3P2P3P5P1P3統(tǒng)計(jì)LRU算法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)入命中此時(shí)不能達(dá)到最高命中率。所以至少應(yīng)該分配4個(gè)主存頁(yè)面。我們假設(shè)程序每次只訪問(wèn)一個(gè)存儲(chǔ)單元， 這樣，

8、對(duì)每一個(gè)特定頁(yè)面的訪問(wèn)過(guò)程可以描述如下：因?yàn)榈谝淮慰偸遣幻械?，而平均起?lái)，隨后的1023次總是命中的，然后再次被調(diào)出主存，并再次重復(fù)先前的過(guò)程。所以訪問(wèn)存儲(chǔ)單元的命 中率為:1023H 0.99910245.假設(shè)在一個(gè)采用組相聯(lián)映象方式的 Cache中，主存由B0B7共8塊組成,Cache有2組，每組2塊，每塊的大小為16個(gè)字節(jié)，采用LRU塊替換算法。 在一個(gè)程序執(zhí)行過(guò)程中依次訪問(wèn)這個(gè) Cache的塊地址流如下：B6， B2， B4， B1， B4， B6， B3， B0， B4， B5， B7， B3 寫(xiě)出主存地址的格式，并標(biāo)出各字段的長(zhǎng)度。寫(xiě)出Cache地址的格式，并標(biāo)出各字段的長(zhǎng)度。畫(huà)

9、出主存與Cache之間各個(gè)塊的映象對(duì)應(yīng)關(guān)系。如果Cache的各個(gè)塊號(hào)為C0、C1、C2和C3,列出程序執(zhí)行過(guò)程中 Cache的塊地址流情況。如果采用FIFO替換算法，計(jì)算Cache的塊命中率。如果采用LRU替換算法，計(jì)算Cache的塊命中率。(7)如果改用全相聯(lián)映象方式，再做和，可以得到什么結(jié)論?如果在程序執(zhí)行過(guò)程中，每從主存裝入一塊到Cache,則平均要對(duì)這個(gè)塊訪問(wèn)16次。請(qǐng)計(jì)算在這種情況下的 Cache命中率。答:主存地址的格式為:1bit組號(hào)1bit組內(nèi)塊號(hào)4bit塊內(nèi)地址主存1bit區(qū)號(hào)1bit組號(hào)1bit組內(nèi)塊號(hào)4bit塊內(nèi)地址咼低 Cache地址的格式為:主存的組到Cache的組之

10、間是直接映象，對(duì)應(yīng)組的塊之間是全相聯(lián)映象。即：主存塊0、1、4、5只能裝入Cache塊0、1的任何塊位置上，主存塊2、3、& 7只能裝入Cache塊2、3的任何塊位置上。由于主存按Cache大小分區(qū)，因此去掉主存塊地址中的區(qū)號(hào)就可以得出滿足組相聯(lián)映象關(guān)系的一種 Cache塊地址，所以該主存塊地址流相應(yīng)的一種Cache的塊地址流為:主存B6B2B4B1B4B6B3B0B4B5B7B3110010100001100110011000100101111011Cache101000010010110000011111C2C2C0C1C0C2C3C0C0C1C3C3 采用FIFO替換算法，Cache的塊

11、命中率為：3/12=0.25。訪問(wèn)流B6B2B4B1B4B6B3B0B4B5B7B3統(tǒng)計(jì)C0B4B4*B4*B4*B4*B0B0*B5B5B5命中3次C1B1B1B1B1B1*B4B4*B4*B4*C2B6B6*B6*B6*B6*B6*B3B3B3B3B3*B3*C3B2B2B2B2B2B2*B2*B2*B2*B7B7動(dòng)作調(diào)入調(diào)入調(diào)入調(diào)入命中命中調(diào)入調(diào)入調(diào)入調(diào)入調(diào)入命中 采用LRU替換算法，Cache的塊命中率為：4/12 0.33。訪問(wèn)流B6B2B4B1B4B6B3B0B4B5B7B3統(tǒng)計(jì)C0B4B4*B4B4B4B4*B4B4*B4*B4*命中4次C1B1B1*B1*B1*B0B0*B5B

12、5B5C2B6B6*B6*B6*B6*B6B6*B6*B6*B6*B7B7*C3B2B2B2B2B2*B3B3B3B3B3*B3動(dòng)作調(diào)入調(diào)入調(diào)入調(diào)入命中命中調(diào)入調(diào)入命中調(diào)入調(diào)入命中 采用全相聯(lián)映象、FIFO替換算法，Cache的塊命中率為：4/12 0.33。訪問(wèn)流B6B2B4B1B4B6B3B0B4B5B7B3統(tǒng)計(jì)C0B6B6*B6*B6*B6*B6*B3B3B3B3B3*B3*命中4次C1B2B2B2B2B2B2*B0B0B0B0B0C2B4B4B4B4B4B4*B4*B5B5B5C3B1B1B1B1B1B1B1*B7B7動(dòng)作調(diào)入調(diào)入調(diào)入調(diào)入命中命中調(diào)入調(diào)入命中調(diào)入調(diào)入命中采用全相聯(lián)映象、LRU替換算法，Cache的塊命中率為：3/12=0.25。訪問(wèn)流B6B2B4B1B4B6B3B0B4B5B7B3統(tǒng)計(jì)C