計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)期末重點(diǎn)題目及考點(diǎn)

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)期末重點(diǎn)題目及考點(diǎn)：1.2.如有一個經(jīng)解釋實(shí)現(xiàn)的計(jì)算機(jī)，可以按功能劃分成4級。每一級為了執(zhí)行一條指令需要下一級的N條指令解釋，若執(zhí)行第一級的一條指令需kns，那執(zhí)行第2級、第3級、第4級的指令需要多少時間？第1級1條1級指令kns第2級1條2級指令N條1級指令1·N·kns=Nkns第3級1條3級指令N條2級指令1·N·N·kns=N2kns第4級1條4級指令N條3級指令1·N·N·N·kns=N3kns1.8.從機(jī)器（匯編）語言程序員看，以下哪些是透明的？指令地址寄存器；指令緩沖器；時標(biāo)發(fā)生器；條件碼寄存器；乘法器；主存地址寄存器；磁盤外設(shè)；先行進(jìn)位鏈；移位器；通用寄存器；中斷字寄存器。第一組區(qū)別，加3位編碼），編碼性能如下表；(4)3/7擴(kuò)展編碼是15/15/15法的變種，第一組3條指令，碼長為2（共有4種組合，其中3種組合分別代表3條指令，留1種組合作為擴(kuò)展前綴標(biāo)志）,第二組7條指令，碼長為5（2位固定的前綴擴(kuò)展標(biāo)志，與第一組區(qū)別，加3位編碼，只用其中7種組合），編碼性能如下表。Huffman編碼2/8擴(kuò)展編碼3/7擴(kuò)展編碼平均碼長L2.993.13.2信息冗余量R1.10%4.61%7.59%2.14一臺模型機(jī)共有7條指令，各指令的使用頻率分別為35%，25%，20%，10%，5%，3%和2%，有8個通用數(shù)據(jù)寄存器，2個變址寄存器。(1)要求操作碼的平均長度最短，請?jiān)O(shè)計(jì)操作碼的編碼，并計(jì)算所設(shè)計(jì)操作碼的平均長度。(2)設(shè)計(jì)8字長的寄存器-寄存器型指令3條，16位字長的寄存器-存儲器型變址尋址方式指令4條，變址范圍不小于±127。請?jiān)O(shè)計(jì)指令格式，并給出各字段的長度和操作碼的編碼。解：(1)要使得到的操作碼長度最短，應(yīng)采用Huffman編碼，構(gòu)造Huffman樹如下：由此可以得到7條指令的編碼分別如下：這樣，采用Huffman編碼法得到的操作碼的平均長度為：H=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35(2)設(shè)計(jì)8位字長的寄存器-寄存器型變址尋址方式指令如下，因?yàn)橹挥?個通用寄存器，所以寄存器地址需3位，操作碼只有兩位，設(shè)計(jì)格式如下：三條指令的操作碼分別為00，01，10設(shè)計(jì)16位字長的寄存器-存儲器型變址尋址方式指令如下：四條指令的操作碼分別為1100，1101，1110，11112.15某處理機(jī)的指令字長為16位，有雙地址指令、單地址指令和零地址指令三類，并假設(shè)每個地址字段的長度均為6位。(1)如果雙地址指令有15條，單地址指令和零地址指令的條數(shù)基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。(2)如果要求三類指令的比例大致為1：9：9，問雙地址指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。解：(1)15條/63條/64條(2)14條/126條/128條(1)根據(jù)指令地址的數(shù)量來決定各種指令在指令空間上的分布：如果我們按照從小到大的順序分配操作碼，這樣，按照指令數(shù)值從小到大的順序，分別為雙地址指令、單地址指令和零地址指令。其次可以根據(jù)指令的條數(shù)來大致的估計(jì)操作碼的長度：雙指令15條，需要4位操作碼來區(qū)分，剩下的12位操作碼平均分給單地址和零地址指令，每種指令可以用6位操作碼來區(qū)分，這樣，各指令的條數(shù)為：雙地址指令15條，操作碼：0000~1110；單地址指令2^6-1=63條，操作碼：1111000000~1111111110；零地址指令64條，操作碼：1111111111000000~1111111111111111。(2)與上面的分析相同，可以得出答案：雙地址指令14條，操作碼：0000~1101；單地址指令2^6x2-2=126條，1110000000~1110111110，1111000000~1111111110；零地址指令128條1110111111000000~1110111111111111,1111111111000000~1111111111111111(2)B雙地址指令同上,14條，操作碼：0000~1101；單地址指令64+62=126條，64條單地址指令操作碼1110000000~1110111111，62條單地址指令操作碼1111000000~1111111101；零地址指令128條1111111110000000~1110111110111111,1111111111000000~1111111111111111：3.9：一個頁式虛擬存儲器的虛存空間大小為4Gb，頁面大小為4KB，每個頁表存儲子要占用4個字節(jié)。計(jì)算這個頁式虛擬存儲器需要采用幾級頁表？答：Log2（4G/4K）/Log2（4K/4）=2.0.取整得2，所以需要2級頁表如果要求頁表所占用的總主存頁面數(shù)最小，請分配每一級頁表的實(shí)際存儲容量各為多少字節(jié)？答：第一季頁表為一個頁面大小，為4kb，第二級頁表被占用1k個頁面，為4mb頁表的哪些部分必須存放在主存中？哪些可以放在輔存中？答：第一級頁表必須放在主存中，二級頁表只需將正在運(yùn)行的程序的相關(guān)頁表放在主存中，其他都可以放在輔存中。3.12一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用戶最多要用1024個頁面，每頁4K字節(jié)，主存容量8M字節(jié)。

（1）寫出多用戶虛地址的格式，并標(biāo)出各字段的長度。

（2）寫出主存地址的格式，并標(biāo)出各字段的長度。

（3）快表的字長為多少位？分幾個字段？各字段的長度為多少位？

（4）慢表的容量是多少個存儲字？每個存儲字的長度為多少位？

答：用戶號：64＝26，虛頁號：1024＝210，頁內(nèi)地址：4K＝212，主存頁數(shù)：8M/4K＝211

（1）多用戶虛地址：

用戶號（6位）＋虛頁號（10位）＋頁內(nèi)地址（12位）

共28位

（2）主存地址：

主存實(shí)頁號（11位）＋頁內(nèi)地址（12位）

共23位

快表字長27位；分3個字段：用戶號6位，虛頁號10位，實(shí)頁號11位

（4）慢表容量為2(6+10)，每個存儲字長為：主存頁號＋1＝12位。3.143.14在頁式虛擬存儲器中，一個程序由P1~P5共5個虛頁組成。在程序執(zhí)行過程中依次訪問到的頁面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假設(shè)系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種替換算法對這三頁主存進(jìn)行調(diào)度。（1） 畫出主存頁面調(diào)入、替換和命中的情況表。（2） 統(tǒng)計(jì)三種頁面替換算法的頁命中率。答案：解：三種替換算法的替換過程：頁地址流232152453252FIFO222255553333命中3次33332222255111444442調(diào)調(diào)命調(diào)替替替命替命替替進(jìn)進(jìn)中進(jìn)換換換中換中換換222152453252LRU33215245325命中5次321524533調(diào)調(diào)命調(diào)替命替命替替命命進(jìn)進(jìn)中進(jìn)換中換中換換中中OPT222222444222命中6次333333333331555555555調(diào)調(diào)命調(diào)替命替命命替命命進(jìn)進(jìn)中進(jìn)換中換中中換中中3.15.一個程序由五個虛頁組成，采用lfu替換算法，在程序中依次訪問的頁地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3可能的最高頁命中率是多少？至少要分配給該程序多少個主存頁面才能獲得最高的命中率?如果在程序中每訪問一個頁面，平均要對該頁面內(nèi)的存儲單元訪問1024次，求訪問單元的命中率？答案：（1）在分配的主存頁面數(shù)目大于等于5的情況下，這時，除了第一次調(diào)入不命中，以后的訪問均命中，可以達(dá)到最高的頁面命中率：實(shí)際命中的次數(shù)為7次，所以可能達(dá)到的最高頁面命中率為：（2）由于在頁面數(shù)大于等于5的情況下，肯定可以達(dá)到最高命中率，所以我們來看頁面數(shù)小于5時能否達(dá)到該命中率：分配的主存頁面數(shù)等于4時，調(diào)度過程如下：LFULFU算法44444*11111*11命中7次

555*55555*555

3333*33*333*3

2222*22222調(diào)入調(diào)入調(diào)入調(diào)入命中調(diào)入命中命中命中命中命中命中此時也可以達(dá)到最高命中率；分配的主存頁面等于3時，調(diào)度過程如下：LFULFU算法444*222*33*333*3命中3次

555*555*222*11

333*1111*555調(diào)入調(diào)入調(diào)入調(diào)入命中調(diào)入調(diào)入調(diào)入命中調(diào)入調(diào)入命中此時不能達(dá)到最高命中率。所以至少應(yīng)該分配4個主存頁面。（3)我們假設(shè)程序每次只訪問一個存儲單元，這樣，對每一個特定頁面的訪問過程可以描述如下：因?yàn)榈谝淮慰偸遣幻械?，而平均起來，隨后的1023次總是命中的，然后再次被調(diào)出主存，并再次重復(fù)先前的過程。所以訪問存儲單元的命中率為：欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關(guān)系。下圖就是“堆棧模擬圖”，其中“√”表示命中。P=453251323513命中次數(shù)4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7(1)Hmax=7/12≈58.3%(2)n=4(3)當(dāng)1次頁面訪問代表連續(xù)1024次該頁內(nèi)存儲單元訪問時，后1023次單元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁命中（折算為7×1024次單元命中），5次頁不命中（折算為5×1023次單元命中，也可寫為5×1024-5），單元訪問總次數(shù)為12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96%3.16.一個程序由1200條指令組成，每條指令的字長均為4B。假設(shè)這個程訪問虛擬存儲器的字地址流為：12，40，260，280，180，800，500，560，600，1100，1200，1000。采用FIFO替換算法，分配給這個程序的主存容量為2048B。

在下列不同的頁面大小情況下，分別寫出該程序執(zhí)行過程中訪存的虛頁地址流，并分別計(jì)算主存命中率。

(1)

頁的大小為1024B。

(2)

頁的大小為512B。

(3)

頁的大小為2048B。

解：(1)

（6分）頁的大小為1

024B，即頁面大小為256字；主存容量為2048B，即分配n=2個實(shí)頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率H1=6／12

=

0．50

（8分）頁的大小為512B，即頁面大小為128字；主存容量為2

048B，即分配n=4個實(shí)頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為H2

=

3／12

=

0．25

頁的大小為2048B，即頁面大小為512字，主存容量為2048B，即分配n=1個實(shí)頁。給定的程序訪存字地址流對主存空間的使用過程如圖所示。主存命中率為H3

=

6／12

=

0．503.19

在一個采用組相聯(lián)映象方式的Cache存儲系統(tǒng)中，主存由B0～B7共8塊組成，Cache有2組，每組2塊，每塊大小為16B。在一個程序執(zhí)行過程中，訪存的主存塊地址流為：B6，B2，B4，B1，B4，B6，B3，B0，B4，B5，B7，B3。

(1)寫出主存地址的格式，并標(biāo)出各字段的長度。

(2)寫出Cache地址的格式，并標(biāo)出各字段的長度。

(3)指出主存與Cache之間各個塊的映象關(guān)系。

(4)若Cache的4個塊號為C0、C1、C2和C3，列出程序執(zhí)行過程中的Cache塊地址流。

(5)若采用FIFO替換算法，計(jì)算Cache的塊命中率。

(6)若采用LRU替換算法，計(jì)算Cache的塊命中率。

(7)若改為全相聯(lián)映象方式，再做(5)和(6)。

(8)若在程序執(zhí)行過程中，每從主存裝入一塊到Cache，平均要對這個塊訪問16次，計(jì)算在這種情況下的Cache命中率。答案：解：（1）（2）采用組相聯(lián)映象時，主存和Cache地址的格式分別為：

主存按Cache的大小分區(qū)，現(xiàn)主存有8個塊，Cache有2×2=4個塊，則主存分為8/4=2個區(qū)，區(qū)號E的長度為1位。又每區(qū)有2個組，則組號G、g的長度都為1位。而每組有2個塊，則塊號B、b的長度又都為1位。每塊大小為16個存儲字，故塊內(nèi)地址W、w的長度都為4位。

（3）根據(jù)組相聯(lián)映象的規(guī)則，主存塊0～7與Cache塊0～3之間的映象關(guān)系為：主存塊0、1、4、5與Cache塊0、1之間全相聯(lián)，主存塊2、3、6、7與Cache塊2、3之間全相聯(lián)。

（4）根據(jù)組相聯(lián)映象的規(guī)則，該主存塊地址流相應(yīng)的一種Cache塊地址流如下表所示（組內(nèi)替換算法為FIFO）。

時間：

1

2

3

4

5

6

7

8

9

10

11

12

主存塊地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache塊地址流：

C2

C3

C0

C1

C0

C2

C2

C0

C0

C0

C3

C（5）組內(nèi)替換算法采用FIFO時，Cache塊0～3的使用過程如下表所示。

時間：

1

2

3

4

5

6

7

8

9

10

11

12

主存塊地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache塊0

Cache塊1

Cache塊2

Cache塊3

命中

命中

命中

可見命中三次，Cache塊命中率為Hi

=

3/12

=

0.25。

組內(nèi)替換算法采用LRU時，Cache塊0～3的使用過程如下表所示。時間：

1

2

3

4

5

6

7

8

9

10

11

12

主存塊地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache塊0

Cache塊1

Cache塊2

Cache塊3

命中

命中

命中

命中

可見命中四次，Cache塊命中率為Hi

=

4/12

=

0.33。

全相聯(lián)映象的規(guī)則是主存塊0～7可裝入Cache塊0～3的任一塊上。

當(dāng)替換算法采用FIFO時，Cache塊0～3的使用過程如下表所示。時間：

1

2

3

4

5

6

7

8

9

10

11

12

主存塊地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B3

Cache塊0

Cache塊1

Cache塊2

Cache塊3

命中

命中

命中

命中

可見命中四次，Cache塊命中率為Hi

=

4/12

=

0.33。

當(dāng)替換算法采用LRU時，Cache塊0～3的使用過程如下表所示。

時間：

1

2

3

4

5

6

7

8

9

10

11

12

主存塊地址流：

B6

B2

B4

B1

B4

B6

B3

B0

B4

B5

B7

B塊0

Cache塊1

Cache塊2

Cache塊3

命中

命中

命中

可見命中三次，Cache塊命中率為Hi

=

3/12

=

0.25。

（8）當(dāng)命中三次時，Cache的命中率為Hi

=

（12×16-9）/（12×16）≈1，當(dāng)命中四次時，Cache的命中率為Hi

=

（12×16-8）/（12×16）≈1。3.203.23對于一個采用組相聯(lián)映象方式和FIFO替換算法的Cache，發(fā)現(xiàn)它的等效訪問時間太長，為此，提出如下建議：

增大主存的容量。答案：基本無關(guān)

（2）

提高主存的速度。

答案：能夠減小等效訪問時間，T=TcH+Tm(1-H),通過減小Tm能夠減小T。（3）

增大Cache的容量

答案：當(dāng)cache比較小時，增大cache對減少等效訪問時間效果明顯；當(dāng)cache容量達(dá)到一定程度時效果逐漸不明顯。（4）

提高Cache的速度。

Cache的總?cè)萘亢徒M大小不變，增大塊的大小。

（6）

Cache的總?cè)萘亢蛪K大小不變，增大組的大小。答案：有一個極大值，在這個極大值點(diǎn)，等效訪問時間最小。

（7）

Cache的總?cè)萘亢蛪K大小不變，增加組數(shù)。

（8）

替換算法由FIFO改為LFU

：4.4有5個中斷源D1、D2、D3、D4和D5，它們的中斷優(yōu)先級從高到低依次是1-5級別。這些中斷源的中斷優(yōu)先級、正常情況下的中斷屏蔽碼和改變后的中斷屏蔽碼如下表所示。每個中斷源有5位中斷屏蔽碼，其中0表示該中斷源開放，1表示該中斷源被屏蔽。(1)當(dāng)使用正常的中斷屏蔽碼時，處理器響應(yīng)各中斷源的中斷請求的先后順序是什么？實(shí)際上中斷處理的先后次序是什么？

(2)當(dāng)使用改變后的中斷屏蔽碼時，處理器響應(yīng)各中斷源的中斷請求的先后順序是什么？實(shí)際上中斷處理的先后次序是什么？

(3)如果采用改變后的中斷屏蔽碼，

D1、D2、D3、D4和D5同時請求中斷時，畫出處理器響應(yīng)各中斷源的中斷請求和實(shí)際運(yùn)行中斷服務(wù)程序過程的示意圖。答案：(1)

當(dāng)使用正常的中斷屏蔽碼時，處理器響應(yīng)各中斷源的中斷請求的先后順序是D1、D2、D3、D4、D5。

實(shí)際上中斷處理的先后次序是D1、D2、D3、D4、D5。

(2)

當(dāng)使用改變后的中斷屏蔽碼時，處理器響應(yīng)各中斷源的中斷請求的先后順序是D1、D2、D3、D4、D5。

實(shí)際上中斷處理的先后次序是D4、D5、D3、D2、D1。

如果采用改變后的中斷屏蔽碼，

D1、D2、D3、D4和D5同時請求中斷時，處理器響應(yīng)各中斷源的中斷請求和實(shí)際運(yùn)行中斷服務(wù)程序過程如下圖所示：4.5某處理機(jī)共有4個中斷源，分別為D1、D2、D3、D4,要求處理機(jī)響應(yīng)中斷源的中斷服務(wù)請求的次序從高到低分別是D1、D2、D3、D4，而處理機(jī)實(shí)際為各中斷源服務(wù)的先后次序?yàn)镈3，D3，D4，D1.每個中斷源有4位中斷屏蔽碼，其中，0表示該中斷源被屏蔽，1表示該中斷源開放。已知中斷服務(wù)次序?yàn)?-2-4-1，。(1)中斷屏蔽字表如下圖；D1D2D3D4D10111D20010D30000D40110(2)中斷過程示意圖如右圖。時間中斷請求 主程序 1級2級3級4級D1，D2D3，D44.74.8一個字節(jié)多路通道連接有4臺外圍設(shè)備，每臺設(shè)備發(fā)出輸入輸出服務(wù)請求的時間間隔，他們的服務(wù)優(yōu)先級和發(fā)出第一次服務(wù)請求的時刻表如下：設(shè)備名稱

D1

D2

D3

D4

發(fā)服務(wù)請求間隔

10μs

75

μs

15

μs

50

μs

服務(wù)優(yōu)先級

1

4

2

3

發(fā)第一次請求時刻

0

μs

70

μs

10

μs

20

μs

（1）計(jì)算這個字節(jié)多路通道的實(shí)際流量和工作周期

（2）在數(shù)據(jù)傳送期間，如果通道選擇一次設(shè)備的時間為3

μs，傳送一個字節(jié)的時間為2

μs，畫出這個字節(jié)多路通道響應(yīng)各設(shè)備請求和為設(shè)備服務(wù)的時間關(guān)系圖。(1)f=2×105字節(jié)/秒，T=5us(2)Ts+Td=5us，通道時間圖如下。作圖時注意：至少要畫到最慢設(shè)備的第二次請求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因?yàn)轫憫?yīng)優(yōu)先級低的設(shè)備較易丟失數(shù)據(jù)）。(3)5，160，20，40；(4)D2丟失第一次請求的數(shù)據(jù)；(5)參見P245。：5.8用一條5個功能段的浮點(diǎn)加法器流水線計(jì)算每個功能段的延遲時間均相等，流水線的輸出端和輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時間完成計(jì)算，畫出流水線時空圖，并計(jì)算流水線的實(shí)際吞吐率、加速比和效率。[解答]首先需要考慮的是，10個數(shù)的的和最少需要做幾次加法。我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：9次；于是我們要盡可能快的完成任務(wù)，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關(guān)。由于加法滿足交換率和結(jié)合率，我們可以調(diào)整運(yùn)算次序如以下的指令序列，我們把中間結(jié)果寄存器稱為R，源操作數(shù)寄存器稱為A，最后結(jié)果寄存器稱為F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下：I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←A9+A10I6： R6←R1+R2I7： R7←R3+R4I8： R8←R5+R6I9： F←R7+R8這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為Δt。時空圖如下，圖中的數(shù)字是指令號。整個計(jì)算過程需要21Δt，所以吞吐率為：加速比為：效率為：5.9一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個功能段的延遲時間均相等。流水線的輸入端與輸出端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器?，F(xiàn)在用這條流水線計(jì)算：畫出流水線時空圖，并計(jì)算流水