#11111111(XXXX)(XXXX)32100000000100100011C1立方置換函數(shù)：0000000100100011010001010110011101000101011001111000100110101011100010011010101111001101111011111100110111101111C2立方置換函數(shù)：C(XXXX)=(XXXX)23210321000000001001000110100010101100111100010011010101111001101000000010010001101000101000000010010001101000101011001111000100110101011110011011110C3立方置換函數(shù)：C(XXXX)(XXXX)2321032100000000100000001001000110100010101100111100010011010101111001101111011110000000100100011010001010110011110001001101010111100110111101111在頁式虛擬存儲器中，一個程序由P1~P5共5個頁面組成。在程序執(zhí)行過程中依次訪問的頁面如下：P2,P3,P2,P1,P5,P2,P4,P5,P3,P2,P5，P2假設系統(tǒng)分配給這個程序的主存有3個頁面■分別采用FIFO.LFU和OPT三種頁面替換算法對這3頁主存進行調(diào)度。（1）畫出主存頁面調(diào)入、替換和命中的情況表。（2）統(tǒng)計三種頁面替換算法的頁命中率解：三種替換算法的替換過程：頁地址流2321524532522222*555*5*3333*FIFO3333*2222*2*55命中3次111*44444*2調(diào)調(diào)命調(diào)替替替命替命替替進進中進換換換中換中換換222152453252LRU33215245325命中5次3*2*1*5*2*4*5*3*3*調(diào)調(diào)命調(diào)替命替命替替命命進進中進換中換中換換中中222222*4*4*4*222OPT3333*33333*33命中6次1*55555555調(diào)調(diào)命調(diào)替命替命命替命命進進中進換中換中中換中中一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用戶最多要用1024個頁面，每頁4K字節(jié)，主存容量8M字節(jié)。（1）寫出多用戶虛地址的格式，并標出各字段的長度。（2）寫出主存地址的格式，并標出各字段的長度。（3）快表的字長為多少位？分幾個字段？各字段的長度為多少位？（4）慢表的容量是多少個存儲字？每個存儲字的長度為多少位？答：用戶號：64=26，虛頁號：1024=210,頁內(nèi)地址：4K=2i2，主存頁數(shù)：8M/4K=2ii（1）多用戶虛地址：用戶號（6位）＋虛頁號（10位）＋頁內(nèi)地址（12位）共28位（2）主存地址：主存實頁號（11位）＋頁內(nèi)地址（12位）共23位（3）快表字長27位；分3個字段：用戶號6位，虛頁號10位，實頁號11位（4）慢表容量為2（6+10），每個存儲字長為：主存頁號＋1=12位。一個程序由五個虛頁組成，采用LFU替換算法，在程序執(zhí)行過程中依次訪問的地址流如下：4，5，3，2，5，1，3，2，3，5，1，3（1）可能的最高頁命中率是多少？（2）至少要分配給該程序多少個主存頁面才能獲得最高的命中率。（3）如果在程序執(zhí)行過程中訪問一個頁面，平均要對該頁面內(nèi)的存儲單元訪問1024次，求訪問存儲單元的命中率。解：（1）由于在頁地址流中互不相同的頁共有5頁，因此最多分配5個主存頁面就可獲得最高頁中命中率，可能的最高命中率為h=12z5=L1212（2）因為LFU替換算法為堆棧型換算法，即隨著分配給該程序的主存頁面數(shù)的減少，其命中率單調(diào)遞減，所以為獲得最高命中率H=7/12，可米用逐步減少所分配的主存頁數(shù)的方法來推算，若分配n個主存頁面時可獲得最高命中率，但分配n-1個頁面時命中率卻減少，則此時我們可以得出這樣的結論：至少要分配給該程序n個主存頁面才能獲得最高的命中率。由表可知，至少要分配給該程序4個主存頁面才能獲得最高的命中率。頁地址流453251322513S(l)453251322513

堆S(2)45325133251棧S(3)4532511325內(nèi)S(4)443255132容S(5)4444444S⑹n=1H實n=2H頁n=3HH數(shù)n=4HHHHHHHn>=5HHHHHHH1024x12-1024x12-51024x12沁0.99959值得說明的是，在此例中，盡管LFU屬于堆棧替換算法，但是分配的實際頁數(shù)n也并不是越多越好，當命中率H達到飽和后，實際頁數(shù)n的增加不僅不會提高命中率，反而會使實存的利用率下降。假設一臺模型計算機共有10種不同的操作碼，如果采用固定長操作碼需要4位。已知各種操作碼在程序中岀現(xiàn)的概率如下表所示，計算采用Huffman編碼法的操作碼平均長度，并計算固定長操作碼和Huffman操作碼的信息冗余量(假設最短平均長度H(假設最短平均長度H3.1位)。指令序號指令使用頻度Pi指令序號指令使用頻度PiI10.17I60.09I20.15I70.08I30.15I80.07I40.13I90.03I50.12I100.01答：構造Huffman樹如下：

Huffman編碼如下表：指令號指令使用頻度PiHuffman編碼碼長指令號指令使用頻度PiHuffman碼碼長I10.17102I60.0901104I20.150003I70.0801114I30.150013I80.0711104I40.130103I90.03111105I50.121103I100.01111115Huffman編碼的平均碼長為：1.0000.400.600.2300.300.300010.0401000.150.010.030.070.120.170.080.090.130.150.170.111.0000.400.600.2300.300.300010.0401000.150.010.030.070.120.170.080.090.130.150.170.11丈0Pl=0.17x2+(0.15+0.15+0.13+0.12)x3+(0.09+0.08+0.07)x4+(0.03+0.01)x5iii=1=3.15冗余量=(3.15—3.10)/3.15=1.59%固定碼長：log210=4冗余量=(4—3.10)/4=22.5%8．一臺模型機的各條指令的頻度如下：SHR（右移）：1%CLL（循環(huán)左移）：2%CLA（累加器清SHR（右移）：1%CLL（循環(huán)左移）：2%CLA（累加器清0）:22%STP（停機）：1%SUB（減）:13%JOM（按頁轉移）：6%STO（存）：5%JMP（轉移）：7%

試設計這9條指令的哈夫曼編碼的操試設計這9條指令的哈夫曼編碼的操作碼表示以及2-4等長擴展操作Huffman編碼如下表：指令指令使用頻度PiHuffman編碼碼長2-4擴展碼碼長ADD0.4301002CLA0.221003012SUB0MP0.071100410014JOM0.061101410104STO0.051110410114CLL0.0211110511004SHR0.01111110611014STP0.01111111611104Huffman編碼的平均碼長為：工Pl二0.43x1+(0.22+0.13)x3+(0.07+0.06+0.05)x4+0.02x5+(0.01+0.01)x6二2.42iii=12-4編碼的平均碼長為：工Pl=(0.43+0.22)x2+(0.13+0.07+0.06+0.05+0.02+0.01+0.01)x4=2.7iii=114?用一條4段浮點加法器流水線求8個浮點數(shù)的和：Z=A+B+C+D+E+F+G+H,求流水線的吞吐率、加速比和效率，其中代1=址2=代3"啊=代。

輸入—輸入—S1—S2S3—>S4△tl輸出答：可對原式作一簡單變化，得到：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]7個加法8個數(shù)的流水線時空圖如下：結果A+BC+DE+FG+HA+B+C+DE+F+G+H結果A+BC+DE+FG+HA+B+C+DE+F+G+HZ用一條4段浮點加法器流水線求8個數(shù)之和的流水線時空圖從流水線的時空圖中可以很清楚地看到，7個浮點加法共用了15個時鐘周期。流水線的吞吐率為:流水線的加速比為:流水線的效率為：TP=—=—T15-At流水線的吞吐率為:流水線的加速比為:流水線的效率為：TP=—=—T15-AtkE亠k-Tk=0-47At4x7-At15At=1-874x7-At4x15-At=0-479.設有兩個向.A,B，各有4個元素，若在如圖所示的靜態(tài)雙功能流水線上，al船理功瓏渝水建計算向量點積：其中，1—2—3—5組成加法流水線，1—4—5組成乘法流水線。又設每個流水線所經(jīng)過的時間均為而且流水線的輸出結果可以直接返回到輸入或暫存于相應的緩沖寄存器中，其延遲時間和功能切換所需的時間都可以忽略不計。請使用合

理的算法，能使完成向量點積A*B所用的時間最短，并求出流水線在此期間實際的吞吐率TP和效率E。解：首先，應選擇適合于靜態(tài)流水線工作的算法。對于本題，應先連續(xù)計算al*bl、a2*b2、a3*b3和a4*b4共4次乘法，然后功能切換，按f(albl+a2b2)+(a3b3+a4b4))經(jīng)3次加法來求得最后的結果。按此算法可畫出流水線工作時的時空圖。