【正文】 取進(jìn)法:當(dāng)訪存第i塊發(fā)生Cache塊失效時(shí)，才將要訪問的主存第i塊調(diào)入Gache. 恒預(yù)取法:只要訪問到主存第i塊，不論Cache是否命中，恒預(yù)取主存第i十1塊進(jìn)Cache. 不命中時(shí)才預(yù)取法:只當(dāng)在訪問主存第i塊不命中Cache時(shí)，才預(yù)取主存中的第i+1塊。、LRU替換的Cache存儲(chǔ)器的等效訪問速度不夠高，此時(shí)增大主存容量和增大Cache容量，會(huì)對(duì)Cache存儲(chǔ)器等效訪問速度有何影響，并分析其原因。 答:Cache存儲(chǔ)器的等效訪問時(shí)間ta=Hc?tc+(1 Hc)tm。等效訪問速度不高，就是ta太長(zhǎng)。；當(dāng)Hc很高時(shí)，就要減少tc。增大主存容圣，不會(huì)對(duì)Hc有顯著影響，可能會(huì)因tm梢徽增大，而使ta略有增大。 如果Hc很高時(shí)，tm的增大，也不會(huì)使ta有明顯上升。由于LRU替換算法是堆棧形的算法，在增大Cache容量時(shí)，如果原Hc較低時(shí)，將會(huì)使Hc顯著上升而顯著縮短ta。知果原Hc已較高時(shí)，因Hc上升不明顯而使其ta不會(huì)有明顯縮短。1設(shè)二級(jí)虛擬存儲(chǔ)器的TA1=10^(7)s、TA2=10^(2)s,為使存儲(chǔ)層次的訪問效率e達(dá)到最大值的80%以上，命中率H至少要求達(dá)到多少？實(shí)際上這樣高的命中率是很難達(dá)到的，那么從存儲(chǔ)層次上如何改進(jìn)？ P100 自考通解：∵e=1/[H+(1H)r] 且 r=TA2/TA1 ∴%這樣的命中率很難達(dá)到，可在二級(jí)存儲(chǔ)器間加一層電子磁盤，降低r，從而降低對(duì)H的要求。 1程序存放在模32單字交叉存儲(chǔ)器中，設(shè)訪存申請(qǐng)隊(duì)的轉(zhuǎn)移概率λ為25%,求每個(gè)存儲(chǔ)周期能訪問到的平均字?jǐn)?shù)。當(dāng)模數(shù)為16呢？由此你可得到什么結(jié)論？ 解：B=[ 1(1λ)^m] /λ 由λ=,m=32 求得：B=44*(3/4)^32=4同理，m=16時(shí) ,B=44*(3/4)^16=由此可看出，當(dāng)轉(zhuǎn)移概率λ為25%比較大時(shí)，采用模32與模16的每個(gè)存儲(chǔ)周期能訪問的平均字?jǐn)?shù)非常相近。就是說，此時(shí)，提高模數(shù)m對(duì)提高主存實(shí)際頻寬已不顯著。實(shí)際上，模數(shù)m的進(jìn)一步增大，會(huì)因工程實(shí)現(xiàn)上的問題，導(dǎo)致實(shí)際性能反而可能比模16的還要低，且價(jià)格更高。所以模數(shù)m不宜太大。對(duì)于λ為25%的情況，可以計(jì)算機(jī)出m=8時(shí)。設(shè)主存每個(gè)分體的存取周期為2μs，寬度為4個(gè)字節(jié)。采用模m多分體交叉存取?，F(xiàn)要求主存實(shí)際頻寬為4MB/S,問主存模數(shù)m應(yīng)取多少方能使兩者速度基本適配？其中m取2的冪。P101自考通解：由題意已知存取周期Tm=2*10^(6)s,寬度W=4B,B實(shí)==4*2^20B/S,Bm=W*m/Tm=*10^6B/Sm=Bm*Tm/W=*10^6*2*10^6/4=所以m取4能滿足要求①微秒（百萬分之一秒)　　　1μs=10^6s②計(jì)量單位中的M(兆)是10的6次方，見到M自然想起要在該數(shù)值的后邊續(xù)上六個(gè)0，即擴(kuò)大一百萬倍。在二進(jìn)制中，MB也表示到了百萬級(jí)的數(shù)量級(jí)，但1MB不正好等于1000000字節(jié)，而是1048576字節(jié)，即 1MB = 2E+20 Bytes = 1048576Bytes。 2某虛擬存儲(chǔ)器共8個(gè)頁面，每頁1024個(gè)字，實(shí)際主存為4096個(gè)字，采用頁表法進(jìn)行地址映象。映象表的內(nèi)容如下表1所示。實(shí)頁號(hào)31232100裝入位11001010表1 虛頁01234567實(shí)頁號(hào)31232100裝入位11001010表2 (1)列出會(huì)發(fā)生頁面失效的全部虛頁號(hào)；解：根據(jù)頁表法列出表2，當(dāng)裝入位為0時(shí)，即為頁面失效，再找出相對(duì)應(yīng)的虛頁號(hào)即可。會(huì)發(fā)生頁面失效的全部虛頁號(hào)為：2,3,5,7 (2)按以下虛地址計(jì)算主存實(shí)地址：0，3728，1023，1024，2055，7800，4096，6800。解：虛頁號(hào)=│_虛地址/頁面大小_│ 實(shí)地址＝(實(shí)頁號(hào)*頁面大小)＋(虛地址－虛頁號(hào)*頁面大小) 虛地址 0 3728 1023 1024 2055 7800 4096 6800 虛頁號(hào) 0 3 0 1 2 7 4 6 實(shí)頁號(hào) 3 3 3 1 2 0 2 0 裝入位 1 0 1 1 0 0 1 1實(shí)地址 3072 3728 4095 1024 2055 632 2048 656 2一個(gè)段頁式虛擬存儲(chǔ)器。虛地址有2位段號(hào)、2位頁號(hào)、11位頁內(nèi)位移（按字編址），主存容量為32K字。每段可有訪問方式保護(hù)，其頁表和保護(hù)位如下表所示。(1) 此地址空間中共有多少個(gè)虛頁？解：2Nv頁，而Nv=用戶虛頁號(hào)=段號(hào)S+頁號(hào)P此地址空間中共有2^Nv=2^(2+2)=16個(gè)虛頁 24..采用頁式管理的虛擬存儲(chǔ)器，分時(shí)運(yùn)行兩道程序。其中，程序X為 DO 50 I=1,3　　B(I)=A(I)C(I)　　IF(B(I)?LE?0)GOTO 40　　D(I)=2*C(I)A(I)　　IF(D(I)?EQ?0)GOTO 5040　E(I)=050　CONTINUEData: A=(4,+2,0)　　　C=(3,0,+1)每個(gè)數(shù)組分別放在不同的頁面中。而程序Y在運(yùn)行過程中，其數(shù)組將依次用到程序空間的第3,5,4,2,5,3,1,3,2,5,1,3,1,5,2頁。如果采用LRU算法，實(shí)存卻只有8頁位置可供存放數(shù)組之用。試問為這兩首程序的數(shù)組分別分配多少個(gè)實(shí)頁最為合適？為什么？ P104自考通解答： 分別分配給程序X和Y的數(shù)組4個(gè)實(shí)頁最為合適。 根據(jù)題意，程序X依次調(diào)用數(shù)組A,C,B,B,E, A,C,B,B,C,A,D,D,E, A,C,B,B,E中的數(shù)據(jù)。 設(shè)程序X中的數(shù)組A,B,C,D,E分別存放于程序空間的第1,2,3,4,5頁，則程序的頁地址流為：1，3，2，2，5， 1，3，2，2，3，1，4，4，5， 1，3，2，2，5。分析使用LRU算法對(duì)程序X的頁地址流進(jìn)行堆棧處理的過程可知，分配給程序X的數(shù)組5個(gè)實(shí)頁最為合適。分析使用LRU算法對(duì)程序Y的頁地址流進(jìn)行堆棧處理的過程可知，分配給程序Y的數(shù)組4個(gè)實(shí)頁最為合適。 但實(shí)存只有8頁位置可供存放數(shù)組之用，所以，分別分配給程序X和Y的數(shù)組4個(gè)實(shí)頁。 note: 分時(shí)運(yùn)行在微觀上是串行的，就是說，分時(shí)運(yùn)行時(shí)把時(shí)間劃分為若干時(shí)間片，每個(gè)程序輪流占用時(shí)間片。在宏觀上是并行的，就是說，每個(gè)程序在一個(gè)時(shí)間片內(nèi)并不能運(yùn)行完?？偟膩砜?，是同時(shí)運(yùn)行的，所以兩個(gè)程序分配的實(shí)頁和不能大于8。 參考：上面的FORTRAN源代碼轉(zhuǎn)成C后main(){int A[]={4,2,0}。int C[]={3,0,1}。for (i=0,i3,i++){B[i]=A[i]C[i]。if (B[i]0)E[i]=0。else{D[i]=2*C[i]A[i]。if (D[i]0)E[i]=0。}。}。}，它應(yīng)可對(duì)應(yīng)1K個(gè)任務(wù)，但在一段較長(zhǎng)時(shí)間內(nèi)，一般只有4個(gè)任務(wù)在使用，故用容量為4行的相聯(lián)寄存器組硬件來縮短被變換的虛地址中的用戶位位數(shù)；每個(gè)任務(wù)的程序空間最大可達(dá)4096頁，每頁為512個(gè)字節(jié)，實(shí)主存容量為2＾20位；設(shè)快表用按地址訪問存儲(chǔ)器構(gòu)成，行數(shù)為32，快表的地址是經(jīng)散列形成；為減少散列沖突，配有兩套獨(dú)立相等比較電路。請(qǐng)?jiān)O(shè)計(jì)該地址變換機(jī)構(gòu)，內(nèi)容包括： (1)畫出其虛、實(shí)地址經(jīng)快表變換之邏輯結(jié)構(gòu)示意圖； (2)相聯(lián)寄存器組中每個(gè)寄存器的相聯(lián)比較位數(shù)； (3)相聯(lián)寄存器組中每個(gè)寄存器的總位數(shù)； (4)散列變換硬件的輸入位數(shù)和輸出位數(shù)； (5)每個(gè)相等比較器的位數(shù)； (6)快表的總?cè)萘浚ㄒ晕粸閱挝唬?P105自考通解: (1)依題意得知： 虛地址為34位，其中用戶號(hào)為10位（對(duì)應(yīng)1K的任務(wù)）、虛頁號(hào)12位（每個(gè)任務(wù)4096頁）、頁內(nèi)位移12位（每頁512字節(jié)，512字節(jié)=512*8=1024*4=2^12）實(shí)地址為20位，其中實(shí)頁號(hào)8位，頁內(nèi)位移12位（與虛頁頁內(nèi)位移對(duì)應(yīng)） 相聯(lián)寄存器的作用：把10位的用戶號(hào)轉(zhuǎn)換為2位的ID（因?yàn)橐话阒挥?個(gè)任務(wù)在使用），并把ID與虛地址的虛頁號(hào)合并到快表中查實(shí)頁號(hào)。 快表的作用：相當(dāng)于頁表，即虛頁號(hào)對(duì)實(shí)頁號(hào)的對(duì)應(yīng)關(guān)系。但又有所簡(jiǎn)化（原因是如果用用戶號(hào)和虛頁號(hào)與實(shí)頁號(hào)對(duì)應(yīng)，前者就有22位，現(xiàn)改進(jìn)后虛頁號(hào)只有14位了）(2)相聯(lián)寄存器組中每個(gè)寄存器的相聯(lián)比較位數(shù)為10（與虛地址中的用戶號(hào)寬度對(duì)應(yīng)）(3)相聯(lián)寄存器組中每個(gè)寄存器的總數(shù)為12（用戶號(hào)寬度+ID寬度）(4)散列變換硬件的輸入位數(shù)為14位（虛頁號(hào)寬度+相聯(lián)寄存器中ID的寬度），輸出位數(shù)為8位（與主存中的實(shí)頁號(hào)寬度對(duì)應(yīng)）(5)每個(gè)相等比較器的位數(shù)=ID+用戶虛頁號(hào)nv39。=2+12=14(位)。 (6)快表的總?cè)萘浚?2行*（14(輸入位數(shù))+8（輸出位數(shù)））*2=32*22*2 ，其訪問虛存的地址流為20，22，208，214，146，618，370，490，492，868，916，728。 (1)若頁面大小為200字，主存容量為400字，采用FIFO替換算法，請(qǐng)按訪存的各個(gè)時(shí)刻，寫出其虛頁地址流，計(jì)算主存的命中率； (2)若頁面大小為100字，再做一遍； (3)若頁面大小為400字，再做一遍； (4)由(1)、(2)、(3)的結(jié)果可得出什么結(jié)論？ (5)若把主存容量增加到800字，按第(1)小題再做一遍，又可得出什么結(jié)論？ P106自考通解： (1)主存容量400字，頁面大小200字，所以主存實(shí)頁數(shù)為2； 把地址流轉(zhuǎn)換為頁地址流，以第一個(gè)虛地址流轉(zhuǎn)換為頁地址流為例說明：求模公式為：INT（地址/頁面大?。褪前训刂氛陧撁娲笮?，得INT（20/200）=0，下同，所以頁地址流為：0,0,1,1,0,3,1,2,2,4,4,3 按FIFO算法得出替換過程為：0（調(diào)入），0（命中），1（調(diào)入），1（命中），0（命中），3（替換0，0比1先入隊(duì)，所以被替換，下同），1（命中），2（替換1），2（命中），4（替換3），4（命中），3（替換2），所以總共命中6次。 故命中率H=6/12=50% (2)方法同（1）H=25% (3)H=50% (4)由以上結(jié)論可得，F(xiàn)IFO算法的條件下，當(dāng)頁面大小發(fā)生變化時(shí)，其命中率變化是：一開始隨頁面大小增大命中率（第一步與第二步比較），但當(dāng)頁面大小增到一定時(shí)，命中率不再增加（第一步與第三步比較）。 (5)命中率為58%，結(jié)論是如果分配給主存容量增加時(shí)可以搞高命中率。 27. 在一個(gè)頁式二級(jí)虛擬存儲(chǔ)器中，采用FIFO算法進(jìn)行頁面替換，發(fā)現(xiàn)命中率H太低，因此有下列建議： (1)增大輔存容量。 (2)增大主存容量(頁數(shù))。 (3)FIFO改為L(zhǎng)RU。 (4)FIFO改為L(zhǎng)RU，并增大主存容量(頁數(shù))。 (5)FIFO改為L(zhǎng)RU，并增大頁面大小。試分析上述各建議對(duì)命中率的影響情況。解答： (1)增大輔存容量，對(duì)命中率H無影響。 (2)增大主存容量(頁數(shù))，可普遍提高命中率。 (3)FIFO改為L(zhǎng)RU，一般可提高命中率。 (4)FIFO改為L(zhǎng)RU，并增大主存容量(頁數(shù))，一般可使命中率有較大提高。 (5)FIFO改為L(zhǎng)RU，并增大頁面大小，如果原來頁面很小，則會(huì)使命中率顯著上升，如果原來頁面很大，則會(huì)使命中率下降。 ，Cache為1KB，要求Cache的每一塊在一個(gè)主存周期內(nèi)能從主存取得。主存模4交叉，每個(gè)分體寬為32位，總?cè)萘繛?56KB。用按地址訪問存儲(chǔ)器構(gòu)成相聯(lián)目錄表實(shí)現(xiàn)主存地址到Cache地址的變換，并約定用4個(gè)外相等比較電路。請(qǐng)?jiān)O(shè)計(jì)此相聯(lián)目錄表，求出該表之行數(shù)、總位數(shù)及每個(gè)比較電路的位數(shù)。 P108自考通解答： 設(shè)Cache地址中的組內(nèi)塊號(hào)為s，相聯(lián)目錄表的行數(shù)是2^(13s)，總位數(shù)是(8+2s)*2^(15s)，每個(gè)比較電路的位數(shù)為8+s。 剖析：在一個(gè)主存周期內(nèi)主存能訪問到的字節(jié)數(shù)為mW=4*32/8=16(Byte)。要求Cache的每一塊在一個(gè)主存周期內(nèi)能從主存取得，所以，Cache中每塊的塊內(nèi)字?jǐn)?shù)不能大于16Bytes。為了加速調(diào)塊，一般讓每塊的大小等于在一個(gè)主存周期內(nèi)主存能訪問到的字?jǐn)?shù)，即16Bytes。 設(shè)Cache地址中的組內(nèi)塊號(hào)為s，相聯(lián)目錄表的行數(shù)=Cache地址內(nèi)的組數(shù)Q=Cache容量/(每組塊數(shù)*每塊大小)=1KB/(S*4*32)=2^13/(2^s*2^7)=2^(6s)。 主存塊數(shù)/Cache塊數(shù)=256=2*8，所以，主存地址中的區(qū)號(hào)nd=8。每個(gè)比較電路的位數(shù)=nd+s39。=nd+s=8+s。 相聯(lián)目錄表的總位數(shù)=表中子目錄表的個(gè)數(shù)*每個(gè)子目錄表的位數(shù)*相聯(lián)目錄表的行數(shù)=4*(nd+s39。+s)*Q=4*(8+2s)*2^(6s)=(8+2s)*2^(8s)。note：若認(rèn)為相等比較電路的個(gè)數(shù)=組內(nèi)塊數(shù)，則相聯(lián)目錄表的行數(shù)=2^4，每個(gè)比較電路的位數(shù)=10，相聯(lián)目錄表的總位數(shù)=12*2^6。 。主存共分8個(gè)塊(0~7),Cache為4個(gè)塊(0~3),采用組相聯(lián)映象，組內(nèi)塊數(shù)為2塊，替換算法為近期最少使用算法(LRU)。 (1)畫出主存、Cache地址的各字段對(duì)應(yīng)關(guān)系(標(biāo)出位數(shù))圖。 (2)畫出主存、Cache空間塊的映象對(duì)應(yīng)關(guān)系示意圖。 (3)對(duì)于如下主存塊地址流：1,2,4,1,3,7,0,1,2,5,4,6,4,7,2,如主存中內(nèi)容一開始未裝入Cache中，請(qǐng)列出Cache中各塊隨時(shí)間的使用狀況。 (4)對(duì)于(3),指出塊失效又發(fā)生塊爭(zhēng)用的時(shí)刻。 (5)對(duì)于(3),求出此期間Cache的命中率。 P109自考通解答：(1)主存地址、Cache地址的各字段的位數(shù)及其對(duì)應(yīng)關(guān)系如下圖所示 (2)主存塊、Cache塊的映象對(duì)應(yīng)關(guān)系如下圖所示 (3)Cache中各塊隨時(shí)間的使用狀況如下圖所示。圖中標(biāo)*號(hào)的是候選替換塊的塊號(hào)，H：命中。R：替換。L：失效。 (4)發(fā)生塊失效又發(fā)生塊爭(zhēng)用的時(shí)刻有11115。