計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)前四章習(xí)題參考答案98

1、?計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)?前四章習(xí)題參考答案第二章習(xí)題：教材pp91-93:第2、6、9、12、15、20題第2題：數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示是軟件和硬件之間的交界面。數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的組成元素，數(shù)據(jù)結(jié)構(gòu)要通過軟件映像變換成機(jī)器所具有的各種數(shù)據(jù)表示來實(shí)現(xiàn)。不同的數(shù)據(jù)表示可為數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)提供不同的支持，但在實(shí)現(xiàn)效率和方便性上有所不同。確定和引入數(shù)據(jù)表示的根本原那么是：1系統(tǒng)效率有無提高？包括實(shí)現(xiàn)的時(shí)間主要看主存和處理機(jī)之間傳送的信息量和存儲(chǔ)空間有無減少；2引入這種數(shù)據(jù)表示的通用性和利用率如何。第6題：階碼6位，即階碼局部除去階符外剩下的階碼值局部p=6位；尾數(shù)48位，即尾數(shù)的二進(jìn)制位位數(shù)m=48位。當(dāng)尾數(shù)基

2、值為rm時(shí)，尾數(shù)每一個(gè)rm進(jìn)制數(shù)位需用log2rm個(gè)二進(jìn)位表示。尾數(shù)基值為rm的尾數(shù)位數(shù)m=m/log2rm。對(duì)于rm為2、8、16時(shí)，m分別為48、16、12位。此題的計(jì)算結(jié)果如下表所示：第9題：變址尋址適合在標(biāo)量計(jì)算機(jī)中，通過循環(huán)程序修改變址值來對(duì)向量或數(shù)組等數(shù)據(jù)結(jié)構(gòu)中的元素進(jìn)行訪問和處理。基址尋址主要用于程序的邏輯地址空間到物理地址空間進(jìn)行變換場合，以支持動(dòng)態(tài)重定位技術(shù)的使用。第二問中隱含著指令中為尋找該操作數(shù)的地址碼只有六位，用來表示這64個(gè)地址中的某一個(gè)。設(shè)計(jì)方法一：采用隱含尋址。程序執(zhí)行過程中，每當(dāng)要訪問存儲(chǔ)器時(shí)，可以經(jīng)硬件加法器將隱含存放器的基址值與指令中給出的6位相對(duì)位移量相加

3、來形成其訪問單元的物理地址。設(shè)計(jì)方法二：基點(diǎn)地址采用程序計(jì)數(shù)器PC，通過無條件轉(zhuǎn)移指令來修改PC的內(nèi)容，實(shí)現(xiàn)在一個(gè)大的地址空間中的訪問PC自相對(duì)尋址。即：通過將PC的內(nèi)容和指令中所提供的6位相對(duì)位移量相加來形成主存單元的物理地址。第12題：分析：等長操作碼的意思是不管其指令的頻度如何，都用同樣長度的二進(jìn)制碼位數(shù)來對(duì)指令操作碼編碼。當(dāng)指令條數(shù)為n時(shí)，等長操作碼的二進(jìn)制碼位數(shù)應(yīng)當(dāng)是Huffman編碼是用Huffman算法構(gòu)造出Huffman樹來得到的,它的平均碼長可用計(jì)算出來。只有兩種碼長的擴(kuò)展操作碼編碼，需要對(duì)指令使用頻度進(jìn)行大小分類。高頻的指令放在同一類中，對(duì)其用短的操作碼編碼；低頻指令放在另

4、一類中，用長操作碼編碼。每一類都用等長操作碼編碼。另外，為了能唯一解碼和立即解碼，在短操作碼中要使用某些碼作為擴(kuò)展成長操作碼的擴(kuò)展標(biāo)志碼。使平均碼長盡可能短，來定好長，短碼的碼長組配關(guān)系。從而，再用來求得平均碼長。解答：14條指令的等長操作碼的平均碼長是，即4位。Huffman編碼可先用Huffman算法構(gòu)造出Huffman樹。此題Huffman樹如以下圖所示。采用兩種碼長的擴(kuò)展操作碼，可根據(jù)14條指令所給的使用頻度分成兩類。使用頻度較高的6種指令用3位操作碼編碼表示。如：用000101分別表示使用頻度為0.15,0.15,0.14,0.13,0.12,0.11的指令的操作碼。留下110和11

5、1兩個(gè)3位碼作為長碼的擴(kuò)展標(biāo)志，擴(kuò)展出2位碼。從而用5位碼就可以各擴(kuò)展出4條使用頻度較低的指令。這樣，共有8條使用頻度較低的指令符合題目的要求。第15題：此題依據(jù)于擴(kuò)展碼中的短碼不能是長碼前綴的概念來答。依題意，雙地址指令格式為： 4位 6位 6位 操作碼 地址碼1 地址碼2 16位 其操作碼占了4位，這樣，共有16種短操作碼?，F(xiàn)雙地址指令有x條，已占用了4位操作碼中16種組合中的x個(gè)碼點(diǎn)，所以剩下16x個(gè)碼點(diǎn)可用作擴(kuò)展標(biāo)志。單地址指令的格式為： 10位 6位 擴(kuò)展操作碼 地址碼1因此，16x個(gè)擴(kuò)展標(biāo)志中的每一個(gè)碼均可擴(kuò)展出6位操作碼來，所以，單地址指令最多可以有16x*第20題：僅根據(jù)9條指

6、令給出的使用頻度，不考慮其他要求，設(shè)計(jì)全Huffman操作碼，只需對(duì)此9條指令的頻度，用Huffman算法，構(gòu)造Huffman樹，就可以得到Huffman操作碼的編碼。其平均碼長可由公式求得?？紤]題目的全部要求，設(shè)計(jì)優(yōu)化實(shí)用的操作碼和指令字格式，只要先將兩種指令字的格式及其各字段的位數(shù)定下來，其他小題就可解答了。依題意容易得出，短指令字只能是8位，長指令字只能是16位。操作碼 存放器號(hào)存放器號(hào)指令按雙操作數(shù)格式編排，短指令為存放器存放器型，可得到短指令格式為：長指令為存放器主存型，主存地址應(yīng)能變址尋址，就可得出長指令格式為： 操作碼 存放器號(hào)變址存放器號(hào)相對(duì)位移一般計(jì)算機(jī)中，變址存放器用的是通

7、用存放器中某一個(gè)。所以，變址存放器號(hào)字段的位數(shù)與存放器號(hào)字段的位數(shù)相同。依題意，指令用擴(kuò)展操作碼編碼，并限制只能有兩種操作碼的碼長。據(jù)Huffman壓縮的概念，讓使用頻度高的指令用短操作碼表示，使用頻度低的指令用長操作碼表示。這樣，從指令使用頻度分布來看，使用頻度相對(duì)較高的指令只有ADD 30，SUB 24，CLA 20 3條，余下6條指令的頻度相對(duì)較低。因此，短操作碼宜取2位長，它有4各編碼，除了3個(gè)碼用于表示這3條高頻指令外，還可提供一個(gè)長操作碼的擴(kuò)展標(biāo)志。所以，短指令用于尋址兩個(gè)操作數(shù)的存放器號(hào)的時(shí)候就都用3位碼編碼。要想表示余下的6條頻度低的指令，就需要用擴(kuò)展標(biāo)準(zhǔn)再擴(kuò)展出3位操作碼來，

8、從而使操作碼為5位。這樣，主存邏輯地址中的相對(duì)位移地址字段就剩了5位。如果相對(duì)位移量用補(bǔ)碼表示，可表示相對(duì)于變址存放器給出的變址值為16到15個(gè)字節(jié)的范圍，就是說，相對(duì)位移可表示的地址變化范圍有32個(gè)字節(jié)。Huffman樹的形式如以下圖所示： 由圖可得Huffman編碼為： ADD 30% 01SUB 24%11CLA20%10JOM6% 0001STO7%0011JMP7%0010SHR2% 000001CIL3%00001STP1%000000 因此，操作碼的平均碼長為： 2.61位 2采用25擴(kuò)展的操作碼編碼為：ADD 30% 00SUB 24%01CLA20%10JOM6% 11000

9、STO7%11001JMP7%11010SHR2% 11011CIL3%11100STP1%11101 這樣，平均碼長為2.78位 3該機(jī)允許使用的可編址的通用存放器個(gè)數(shù)為 8 個(gè)。4短指令格式為： 2位 3位 3位OP R1 R2 操作碼 存放器1 存放器2 長指令格式為： 5位 3位 3位 5位 OP R1 X d 操作碼 存放器1 變址存放器 相對(duì)位移 5訪主存操作數(shù)地址的最大相對(duì)位移量為32個(gè)字節(jié)。第三章習(xí)題：教材pp117-118: 第2、4、5、8、9、10題第2題：隨著計(jì)算機(jī)系統(tǒng)的不斷開展和應(yīng)用領(lǐng)域的進(jìn)一步擴(kuò)大，要求輸入輸出的數(shù)據(jù)量在迅速增大，對(duì)數(shù)據(jù)傳送的速度要求在明顯增長，輸入

10、輸出設(shè)備的種類和數(shù)量也在日益增多。因而，輸入輸出系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的好壞會(huì)直接影響到計(jì)算機(jī)系統(tǒng)的性能，不僅會(huì)影響到輸入輸出的速度和各個(gè)用戶從程序輸入到運(yùn)算結(jié)果輸出所需的時(shí)間長短，也會(huì)影響到CPU和主存的利用率。此外，還會(huì)影響到整個(gè)I/O系統(tǒng)的兼容能力，可擴(kuò)展能力，綜合處理能力和性能價(jià)格比等。 第4題：分析：據(jù)此題所給出的各級(jí)中斷處理程序?qū)χ袛嗥帘挝辉O(shè)置的狀況，很容易得出其中斷處理完的次序應(yīng)當(dāng)是134-2。因?yàn)檎幚?級(jí)的中斷處理程序時(shí)，現(xiàn)行程序狀態(tài)字中的中斷級(jí)屏蔽位為0000，在其執(zhí)行期間，任何新的同級(jí)和低級(jí)的中斷請(qǐng)求都不可能進(jìn)入中斷響應(yīng)排隊(duì)起進(jìn)行排隊(duì)，所以，1級(jí)中斷處理程序一定會(huì)先處理完。當(dāng)執(zhí)行3

11、級(jí)中斷效勞程序時(shí)，由于現(xiàn)行程序狀態(tài)字中的中斷級(jí)屏蔽位為1000，即對(duì)1級(jí)中斷請(qǐng)求是“開放的，而對(duì)其它各級(jí)中斷請(qǐng)求那么處于“屏蔽狀態(tài)，所以，只要此時(shí)發(fā)生1級(jí)中斷請(qǐng)求，它就能進(jìn)入中斷響應(yīng)排隊(duì)器去排隊(duì)。從而在中斷請(qǐng)求排隊(duì)的微操作發(fā)出時(shí)，就可打斷3級(jí)中斷效勞程序的執(zhí)行，交換程序狀態(tài)字，轉(zhuǎn)去執(zhí)行1級(jí)中斷處理程序，使之被優(yōu)先處理完。而在執(zhí)行3級(jí)中斷效勞程序時(shí)，由于現(xiàn)行程序狀態(tài)字對(duì)2，3，4級(jí)的中斷請(qǐng)求處于被“屏蔽的狀態(tài)，所以，它們都不能打斷正在執(zhí)行的3級(jí)中斷處理程序。其他情況可依次類推。當(dāng)中斷響應(yīng)優(yōu)先次序?yàn)椋?1-2-3-4時(shí)，中斷處理的次序?yàn)椋?-3-4-2。由題目所給出的條件，其CPU運(yùn)行程序的過程示

12、意圖如以下圖所示。圖中，粗短線局部代表進(jìn)行交換程序狀態(tài)字的時(shí)間，t為1個(gè)單位時(shí)間。第5題：中斷級(jí)屏蔽位“1”對(duì)應(yīng)于屏蔽，“0”對(duì)應(yīng)于開放。正在處理某級(jí)中斷效勞程序時(shí)，與其同級(jí)的新的中斷請(qǐng)求是不能被響應(yīng)的，應(yīng)當(dāng)予以屏蔽，因?yàn)橛脴觾?yōu)先級(jí)，那么先來的應(yīng)該先得到響應(yīng)并被處理。根據(jù)所要求的中斷處理的次序，各級(jí)中斷處理程序現(xiàn)行狀態(tài)字中各中斷屏蔽位的狀態(tài)很容易被設(shè)置出來。各級(jí)中斷處理程序中的中斷級(jí)屏蔽位的設(shè)置，如下表所示。中斷處理程序級(jí)別 中斷級(jí)屏蔽位 1 2 3 4 5 1 11111 201100 3 00100 401111 501101由條件可得程序運(yùn)行過程示意圖如以下圖所示。圖中，粗短線表示交換程

13、序狀態(tài)字的時(shí)間。 第8題：1 字節(jié)多路通道選擇好一臺(tái)設(shè)備后，設(shè)備與通道只傳送一個(gè)字節(jié)就釋放總線。某臺(tái)設(shè)備要想傳送n個(gè)字節(jié)，需要經(jīng)n次申請(qǐng)使用通道總線才行。數(shù)組多路通道選擇好一臺(tái)設(shè)備后，連續(xù)傳送完固定K個(gè)字節(jié)的成 組數(shù)據(jù)后，才釋放總線，通道再選擇下一臺(tái)設(shè)備繼續(xù)傳送K個(gè)字節(jié)。選擇通道每選擇一臺(tái)設(shè)備，就讓其獨(dú)占通道，直到它把數(shù)據(jù)傳送完畢，因此，每臺(tái)設(shè)備只需申請(qǐng)一次就可傳送任意多字節(jié)。(2 )根據(jù)第一個(gè)問題，掛低速設(shè)備的通道應(yīng)該按字節(jié)多路通道方式工作。字節(jié)多路通道的通道極限流量是：1/+各設(shè)備啟動(dòng)后，假設(shè)想不喪失設(shè)備信息，通道極限流量應(yīng)大于等于設(shè)備對(duì)通道要求的流量，即應(yīng)滿足：=在字節(jié)多路通道上，設(shè)備對(duì)

14、通道要求的流量應(yīng)是所掛全部設(shè)備的速率之和。假設(shè)所掛設(shè)備臺(tái)數(shù)為m，設(shè)備速度fi實(shí)際就是設(shè)備發(fā)出字節(jié)傳送請(qǐng)求的間隔時(shí)間的倒數(shù)，m臺(tái)相同速率的設(shè)備其速率之和為m*fi，這樣，為不喪失信息，應(yīng)滿足：1/+ = m*于是可求得在字節(jié)多路通道上能掛的設(shè)備臺(tái)數(shù)m應(yīng)滿足： m = * 從而可確定哪些設(shè)備能掛，哪些不能。選擇通道在宏觀上要不喪失設(shè)備信息，就要限制在通道上所掛設(shè)備的速率不能超過一個(gè)限值。在字節(jié)多路通道方式工作時(shí)，限制所掛設(shè)備的臺(tái)數(shù)為：m = 1B/(9.8us/n + 0.2us)，其中n=1024個(gè)字節(jié)。所以限制通道上所掛的設(shè)備速率=(1/e - / ) / (1-/) 將= s,= s 和 e

15、=80%代入上式，可得：H=(1/e - / ) / (1-/) = 0.999 999 975 實(shí)際上，這樣的命中率極難到達(dá)，為此需要減少相鄰兩級(jí)的訪問速度差距，或減少相鄰兩級(jí)存儲(chǔ)器的容量差。除此之外，可考慮在主存和輔存之間增加一級(jí)存儲(chǔ)器，讓其速度界于主存和輔存之間的某個(gè)值。如：讓主存與中間級(jí)的訪問時(shí)間比為1：100，中間級(jí)與輔存間的訪問時(shí)間比為1：1000，將它們配置上相應(yīng)的輔助軟，硬件，組成一個(gè)三級(jí)存儲(chǔ)層次。這樣，可讓第1級(jí)主存的命中率降低。 第8題： 要找出方生頁面失效的全部虛頁號(hào)，關(guān)鍵是搞清頁表法進(jìn)行地址映象所用的虛頁表的構(gòu)成。虛頁表是記錄程序虛頁是否裝入內(nèi)存，已經(jīng)如果已裝入主存時(shí)，

16、是裝在主存的哪個(gè)實(shí)存頁面位置的一個(gè)表。表的行數(shù)為虛頁的頁數(shù)，用相對(duì)于表首偏移的行號(hào)來代表程序虛頁的頁數(shù)，即第1行對(duì)應(yīng)于虛頁0的裝入情況，第2行對(duì)應(yīng)于虛頁是否已裝入主存。 要由虛地址計(jì)算出主存的實(shí)地址，首先應(yīng)據(jù)題意將虛，實(shí)地址中各個(gè)自動(dòng)及其位數(shù)確定。虛地址字段為： 虛頁號(hào) 頁內(nèi)偏移 3位 10位 由虛擬存儲(chǔ)器共有8個(gè)頁面，每個(gè)頁面大小為1024個(gè)字，可知，虛頁號(hào)字段為3位二進(jìn)制位，頁內(nèi)位移字段為10為二進(jìn)制位。由于虛，實(shí)頁面大小是一樣的，實(shí)際主存為4096個(gè)字，因此，實(shí)地址中，實(shí)頁號(hào)字段為2位，頁內(nèi)位移字段為10位，即實(shí)際地址字段為： 實(shí)頁號(hào) 頁內(nèi)偏移 2位 10位這樣，由題中所給虛地址，就可用

17、以下公式計(jì)算出虛頁頁號(hào)和頁內(nèi)位移量。虛頁頁號(hào)為： 虛地址/頁面大小頁內(nèi)偏移為： 虛地址虛頁號(hào)*頁面大小根據(jù)所求得的虛頁號(hào)來查頁表。如果裝入位為“0，為頁失效，不可能變換出主存實(shí)地址，這是因?yàn)檠b入位為“0時(shí)，封鎖了頁表中實(shí)頁號(hào)字段內(nèi)容的取出。只有裝入位為“1時(shí)，才能將頁表中的實(shí)頁號(hào)字段內(nèi)容取出，去拼接上虛存地址中的頁內(nèi)位移量，得到相應(yīng)的主存實(shí)地址。主存實(shí)地址為： 實(shí)頁號(hào)*頁面大小 頁面位移量發(fā)生頁面失效的全部虛頁號(hào)就是頁映象表中所有裝入位為“0的行所對(duì)應(yīng)的虛頁號(hào)的集合。此題為2，3，5，7。由虛地址計(jì)算主存實(shí)地址的情況見下表： 虛地址虛頁號(hào) 頁內(nèi)位移 裝入位實(shí)頁號(hào) 頁內(nèi)位移實(shí)地址 00 0 13

18、 0307237283 656 0 頁面失效無10230 1023 13 1023409510241 0 11 0102420552 7 0 頁面失效無78007 632 0 頁面失效無40964 0 12 0204368006 656 10 656656第9題：段頁式虛擬存儲(chǔ)器是把實(shí)存機(jī)械等分成相同大小的頁。程序按模塊分成段，每個(gè)段又分成與主存頁面大小相同的頁。由此可知，總虛頁數(shù)為段數(shù)*每段頁數(shù)由題意，我們知道程序的虛地址和主存實(shí)地址中各字段的位數(shù)對(duì)應(yīng)為：程序虛地址：段號(hào)頁號(hào) 頁內(nèi)位移 2位 2位11位主存實(shí)地址：頁號(hào) 頁內(nèi)位移 4位11位程序通過一個(gè)段表和相應(yīng)的一組頁表來進(jìn)行定位。如果某段

19、的頁表未裝入主存，訪問該段時(shí)，會(huì)引起段失效故障，請(qǐng)求到輔存中去將頁表調(diào)入主存。自然就不能計(jì)算出主存實(shí)地址。對(duì)此題，如：訪問到程序第2段時(shí)，由于頁表不在主存內(nèi)，就會(huì)發(fā)生段失效故障。每一個(gè)段有有一個(gè)頁表，頁表中各行對(duì)應(yīng)記錄此段各虛頁是否已裝入主存。假設(shè)未裝入主存，訪問該虛頁時(shí)會(huì)發(fā)生頁面失效。假設(shè)已裝入主存，那么記錄有該程序的虛頁裝入定位于主存中的實(shí)頁號(hào)。對(duì)此題，如：訪問程序第0段第2頁時(shí)，由于是“在輔存上，會(huì)發(fā)生頁面失效故障，需要去輔存中將該程序虛頁調(diào)入主存。有關(guān)訪問方式保護(hù)是為了對(duì)所存放的指令，數(shù)據(jù)等進(jìn)行訪問方式的管理。如果程序的訪問方式不符合段映象對(duì)應(yīng)規(guī)定的訪問方式要求，系統(tǒng)會(huì)加以拒絕，以保護(hù)

20、信息。這樣才能保證程序運(yùn)行平安可靠。此題給出的訪問方式有“取數(shù)，“存數(shù)，“轉(zhuǎn)移至此等。不同方式對(duì)存儲(chǔ)單元的操作不同。據(jù)此，可確定程序?qū)δ男┐鎯?chǔ)單元訪問時(shí)，因方式不當(dāng)而發(fā)生保護(hù)失效。在既無段失效，又無頁面失效的情況下，只需要將頁表中所記錄的實(shí)頁號(hào)取出來，再拼接上程序虛地址的頁內(nèi)位移量，即可求得主存的實(shí)地址。此時(shí)，主存實(shí)地址為： 實(shí)頁號(hào) * 頁面大小 頁內(nèi)位移量虛地址空間有2位段號(hào)，即共有4個(gè)段；有2位頁號(hào)，即每個(gè)段有4個(gè)頁。所以程序最多可有4*416個(gè)虛頁。發(fā)生段失效，頁面失效，保護(hù)失效及相應(yīng)主存實(shí)地址情況見下表：表中實(shí)地址 實(shí)頁號(hào)* 頁內(nèi)位移方式段頁頁內(nèi)位移段失效頁失效實(shí)頁號(hào)實(shí)地址保護(hù)失效取數(shù)

21、011無無36145無取數(shù)1110無無010無取數(shù)332047無有無無/存數(shù)014無無36148有存數(shù)212有/無無/存數(shù)1014無有無無/轉(zhuǎn)移13100無無816484無取數(shù)0250無有無無/取數(shù)205有/無無/轉(zhuǎn)移3060無無1428732有第14題：此題首先應(yīng)由虛存地址流中的每個(gè)虛地址按頁面大小，確定出它們各自所在的虛頁號(hào)。根據(jù) 虛頁號(hào) 計(jì)算得到訪問過程中的虛頁地址流后，就可用FIFO替換算法對(duì)虛頁訪問，畫出各頁實(shí)際裝入主存和進(jìn)行頁面替換的過程圖。從而可以求出相應(yīng)的命中率。主存容量，根據(jù)所用的頁面大小，可以用：實(shí)存頁面數(shù) 主存容量/頁面大小求得相應(yīng)的實(shí)存頁面數(shù)1頁面大小為200字，主存容

22、量為400字，可知實(shí)存頁數(shù)為2頁。其虛頁地址流為： 0，0，1，1，0，3，1，2，2，4，4，3 以下圖給出了采用FIFO替換算法時(shí)實(shí)際裝入和替換過程。其中，“*標(biāo)記的是候選的虛頁頁號(hào)，H表示命中。 由圖計(jì)算可得主存的命中率H=6/12=0.52頁面大小為100字，主存容量為400字，可知，實(shí)存頁面數(shù)為4頁。其虛頁地址流為：0，0，2，2，1，6，3，4，4，8，9，7可據(jù)此畫出頁面裝入和替換的全過程，進(jìn)而得出主存的命中率為：H=3/12 = 0.253頁面大小為400字，主存容量為400字，可知，實(shí)存頁面數(shù)為1頁，虛地址流為： 0，0，0，0，0，1，0，1，1，2，2，1 主存命中率為： H=6/12=0.54由上面結(jié)果可知，再分配給程序的實(shí)存容量一定400字的條件下，頁面大小過小時(shí)，命中率較低；頁面大小增大后，兩個(gè)地址在同頁內(nèi)的時(shí)機(jī)增大，使命中率有所上升；由于指令之間因遠(yuǎn)距離的跳轉(zhuǎn)引起命中率下降的