計(jì)算機(jī)體系結(jié)構(gòu)期末復(fù)習(xí)題答案

1、計(jì)算機(jī)體系結(jié)構(gòu)期末復(fù)習(xí)題答案系別 _ 班級(jí) _ 姓名_ 學(xué)號(hào)_一、 填空題（每空1分）1.按照弗林（Flynn）分類(lèi)法，計(jì)算機(jī)系統(tǒng)可以分為4類(lèi)：SISD計(jì)算機(jī)、（SIMD計(jì)算機(jī)）、（MISD計(jì)算機(jī)）和（MIMD計(jì)算機(jī)）。2. 改進(jìn)之后的馮諾依曼計(jì)算機(jī)的只要特點(diǎn)是存儲(chǔ)器為中心，總線結(jié)構(gòu)，分散控制。3. 當(dāng)前計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)系統(tǒng)是一個(gè)層次結(jié)構(gòu)，其各層分別為：（通用寄存器，高速緩存，主存，輔存，脫機(jī)大容量存儲(chǔ)器）。4.高速緩沖存儲(chǔ)器的地址映象方式有三種，它們分別是：（全向量方式，直接相聯(lián)方式，組相聯(lián)方式）。5.虛擬存儲(chǔ)器的三種管理方式是（段式管理，頁(yè)式管理和段頁(yè)式管理）。6.目前計(jì)算機(jī)中常用數(shù)據(jù)有

2、（用戶定義數(shù)據(jù)，系統(tǒng)數(shù)據(jù)和指令數(shù)據(jù)）三種類(lèi)型。7.通?？赡艹霈F(xiàn)的流水線的相關(guān)性有（資源相關(guān)，數(shù)據(jù)相關(guān)和控制相關(guān)）。8.解決中斷引起的流水線斷流的方法有（不精確斷點(diǎn)法和精確斷點(diǎn)法）。9.目前向量處理機(jī)的系統(tǒng)結(jié)構(gòu)有兩種：（存儲(chǔ)器存儲(chǔ)器型和寄存器寄存器型）。10.通用計(jì)算機(jī)基本指令分為5類(lèi)，它們分別是：（數(shù)據(jù)傳送類(lèi)，運(yùn)算類(lèi)，程序控制類(lèi)，輸入輸出類(lèi)，處理機(jī)控制和調(diào)試類(lèi)）。11執(zhí)行指令x1=x2+x3；x4=x1-x5會(huì)引起（RAW）類(lèi)型的數(shù)據(jù)相關(guān)，執(zhí)行指令x5=x4*x3；x4=x0+x6會(huì)引起（WAR）類(lèi)型的數(shù)據(jù)相關(guān)，執(zhí)行指令x6=x1+x2；x6=x4*x5會(huì)引起（WAW）類(lèi)型的數(shù)據(jù)相關(guān)。12多計(jì)

3、算機(jī)網(wǎng)絡(luò)中，通常出現(xiàn)的4種通信模式是（單播模式，選播模式，廣播模式和會(huì)議模式）。13.傳統(tǒng)的馮諾依曼計(jì)算機(jī)是以控制驅(qū)動(dòng)方式工作，以數(shù)據(jù)驅(qū)動(dòng)方式工作的典型計(jì)算機(jī)是（數(shù)據(jù)流計(jì)算機(jī)），以需求驅(qū)動(dòng)方式工作的典型計(jì)算機(jī)是（歸約機(jī)），以模式匹配驅(qū)動(dòng)方式工作的典型計(jì)算機(jī)是（人工智能計(jì)算機(jī)）。二、名詞解釋?zhuān)款}2分）1.計(jì)算機(jī)體系結(jié)構(gòu)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)就是計(jì)算機(jī)的機(jī)器語(yǔ)言程序員或編譯程序編寫(xiě)者所看到的外特性，是硬件子系統(tǒng)的概念結(jié)構(gòu)及其功能特性。2.系列機(jī)： 所謂系列機(jī)是指同一廠家生產(chǎn)的具有相同的系統(tǒng)結(jié)構(gòu)，但采取了不同的組成和實(shí)現(xiàn)的技術(shù)方案，形成了不同型號(hào)的多種機(jī)型。3.模擬: 模擬是指用軟件的方法在一臺(tái)計(jì)算機(jī)上

4、，實(shí)現(xiàn)另一臺(tái)計(jì)算機(jī)的指令系統(tǒng)，被模擬的機(jī)器是不存在的，稱(chēng)為虛擬機(jī)，執(zhí)行模擬程序的機(jī)器稱(chēng)宿主機(jī)。4.程序的局部性原理: 程序訪問(wèn)局部性原理說(shuō)明了計(jì)算機(jī)在程序執(zhí)行過(guò)程中呈現(xiàn)出的一種規(guī)律，即程序往往重復(fù)使用它剛剛使用過(guò)的數(shù)據(jù)和指令。局部性分為時(shí)間上的局部性和空間上的局部性兩種。所謂時(shí)間局部性是指近期被訪問(wèn)的代碼，很可能不久又將再次被訪問(wèn)；空間局部性是指地址上相鄰近的代碼可能會(huì)被連續(xù)地訪問(wèn)。5.MIPS：它表示每秒百萬(wàn)條指令數(shù)。6.高速緩沖存儲(chǔ)器: 高速緩沖存儲(chǔ)器是存在于主存與CPU之間的一級(jí)存儲(chǔ)器，由靜態(tài)存儲(chǔ)芯片（SRAM）組成，容量比較小但速度比主存高得多，接近于CPU的速度。7.虛擬存儲(chǔ)器: 虛

5、擬存儲(chǔ)器是由主存儲(chǔ)器和輔助存儲(chǔ)器組成，通過(guò)必須的軟件和硬件的支持，使得CPU可以訪問(wèn)的存儲(chǔ)器具有近似于主存的速度和近似于輔存的容量。8.快表: 為了提高地址轉(zhuǎn)換速度，縮短查表時(shí)間，采用一個(gè)小容量的、高速的相關(guān)存儲(chǔ)部件，用來(lái)存放當(dāng)前最經(jīng)常用到的那一部分頁(yè)表，采取按內(nèi)容相聯(lián)方式進(jìn)行訪問(wèn)。這樣，查頁(yè)表的時(shí)間就相當(dāng)于訪問(wèn)小容量的相關(guān)存儲(chǔ)器的時(shí)間，從而大大地提高了速度，這個(gè)小容量相關(guān)存儲(chǔ)器稱(chēng)為快表。9.程序定位： 把一個(gè)程序交給處理機(jī)運(yùn)行，必須首先把這個(gè)程序的指令和數(shù)據(jù)裝入到主存儲(chǔ)器中。一般情況下，程序所分配到的主存物理空間與程序本身的邏輯地址空間是不同的，把指令和數(shù)據(jù)中的邏輯地址(相對(duì)地址)轉(zhuǎn)變成主存

6、物理地址(絕對(duì)地址)的過(guò)程稱(chēng)為程序定位。10.延遲轉(zhuǎn)移技術(shù)：為了使指令流水線不斷流，在轉(zhuǎn)移指令之后插入一條不相關(guān)的有效的指令，而轉(zhuǎn)移指令被延遲執(zhí)行，這種技術(shù)稱(chēng)為延遲轉(zhuǎn)移技術(shù)。11.窗口重疊技術(shù)： 為了能更簡(jiǎn)單、更直接地實(shí)現(xiàn)過(guò)程與過(guò)程之間的參數(shù)傳遞，大多數(shù)RISC機(jī)器的CPU中都設(shè)置有數(shù)量較大的寄存器組，讓每個(gè)過(guò)程使用一個(gè)有限數(shù)量的寄存器窗口，并讓各個(gè)過(guò)程的寄存器窗口部分重疊，這就是窗口重疊技術(shù)。12.流水線技術(shù)： 把一個(gè)重復(fù)的時(shí)序過(guò)程分成若干個(gè)子過(guò)程，每個(gè)子過(guò)程都可以有效地在其專(zhuān)用功能段上和其他子過(guò)程同時(shí)執(zhí)行的一種技術(shù)，稱(chēng)為流水線技術(shù)。13.動(dòng)態(tài)流水線： 動(dòng)態(tài)流水線在同一時(shí)間內(nèi)允許按多種不同運(yùn)

7、算的聯(lián)結(jié)方式工作。14.靜態(tài)流水線： 靜態(tài)流水線在同一時(shí)間內(nèi)只能按一種運(yùn)算的聯(lián)結(jié)方式工作。15.線性流水線： 線性流水線中，從輸入到輸出，每個(gè)功能段只允許經(jīng)過(guò)一次，不存在反饋回路。16.非線性流水線： 非線性流水線存在反饋回路，從輸入到輸出過(guò)程中，某些功能段將數(shù)次通過(guò)流水線，這種流水線適合于進(jìn)行線性遞歸的運(yùn)算。17.流水線的吞吐率： 流水線單位時(shí)間完成的任務(wù)數(shù)。18.超流水線計(jì)算機(jī)： 超級(jí)流水線結(jié)構(gòu)是把每一個(gè)流水線(一個(gè)周期)分成多個(gè)(例如3個(gè))子流水線，而在每一個(gè)子流水線中取出的仍只有一條指令，但總的來(lái)看，在一個(gè)周期內(nèi)取出了三條指令。即在一個(gè)時(shí)鐘周期內(nèi)能夠分時(shí)發(fā)射多條指令的處理機(jī)。19.向量

8、的分段開(kāi)采技術(shù)： 當(dāng)向量的長(zhǎng)度大于向量寄存器的長(zhǎng)度時(shí)，必須把長(zhǎng)向量分成長(zhǎng)度固定的段，采用循環(huán)結(jié)構(gòu)處理這個(gè)長(zhǎng)向量，這種技術(shù)稱(chēng)為向量循環(huán)開(kāi)采技術(shù)，也稱(chēng)為向量分段開(kāi)采技術(shù)。三、簡(jiǎn)答題（每題5分）1.什么是存儲(chǔ)系統(tǒng)？答：存儲(chǔ)系統(tǒng)是兩個(gè)或兩個(gè)以上的速度、容量、價(jià)格不同的存儲(chǔ)器采用硬件，軟件或軟、硬件結(jié)合的辦法聯(lián)結(jié)成一個(gè)系統(tǒng)，使得整個(gè)系統(tǒng)看起來(lái)象一個(gè)存儲(chǔ)器，其速度接近其中最快的一個(gè)，容量接近其中最大的一個(gè)，價(jià)格接近其中最便宜的一個(gè)。 2.簡(jiǎn)述全相聯(lián)映象規(guī)則。答：（1）主存與緩存分成相同大小的數(shù)據(jù)塊。（2）主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。3.簡(jiǎn)述直接相聯(lián)映象規(guī)則。答：（1）主存與緩存分成相同大

9、小的數(shù)據(jù)塊。（2）主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。 （3）主存中某區(qū)的一塊存入緩存時(shí)只能存入緩存中塊號(hào)相同的位置。4.引起Cache與主存內(nèi)容不一致的原因是什么？為了保持Cache的一致性，在單計(jì)算機(jī)系統(tǒng)中一般采取哪些措施？答：不一致的原因：(1) 由于CPU寫(xiě)Cache，沒(méi)有立即寫(xiě)主存(2) 由于I/O處理機(jī)或I/O設(shè)備寫(xiě)主存采取措施：（1）全寫(xiě)法，亦稱(chēng)寫(xiě)直達(dá)法(WT法Write through)方法：在對(duì)Cache進(jìn)行寫(xiě)操作的同時(shí)，也對(duì)主存該內(nèi)容進(jìn)行寫(xiě)入。（2）寫(xiě)回法（WB法Write back）方法：在CPU執(zhí)行寫(xiě)操作時(shí),

10、只寫(xiě)入Cache,不寫(xiě)入主存。5影響虛擬存儲(chǔ)器命中率的因素有哪些？它們是如何影響的？答：（1）頁(yè)面大小：當(dāng)頁(yè)面比較小時(shí)，隨著頁(yè)面的增大，命中率明顯提高，但當(dāng)頁(yè)面增大到一定值時(shí)，命中率不再增大，而隨著頁(yè)面的增大而下降。（2）主存容量：當(dāng)主存容量增加時(shí)，命中率不斷提高；當(dāng)容量增大到一定程度后，命中率的提高就不大了。（3）頁(yè)面調(diào)度方式：頁(yè)面的調(diào)度都是發(fā)生在產(chǎn)生缺頁(yè)中斷時(shí)進(jìn)行，因此在程序剛開(kāi)始運(yùn)行時(shí)命中率很低，為此可以采用預(yù)取式調(diào)度法，提高命中率。6.模擬與仿真的主要區(qū)別和適合場(chǎng)合是什么？答：模擬是指用軟件的方法在一臺(tái)計(jì)算機(jī)上，實(shí)現(xiàn)另一臺(tái)計(jì)算機(jī)的指令系統(tǒng)，被模擬的機(jī)器是不存在的，稱(chēng)為虛擬機(jī)，執(zhí)行模擬程

11、序的機(jī)器稱(chēng)宿主機(jī)。由于模擬采用純軟件解釋執(zhí)行方法，因此運(yùn)行速度較慢，實(shí)時(shí)性差。因此只適合于移植運(yùn)行時(shí)間短，使用次數(shù)少，而且在時(shí)間上沒(méi)有約束和限制的軟件。仿真是指用微程序的方法在一臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)另一臺(tái)計(jì)算機(jī)的指令系統(tǒng)。執(zhí)行微程序的機(jī)器為宿主機(jī)，被實(shí)現(xiàn)的為目標(biāo)機(jī)。仿真的運(yùn)行速度比模擬快，但仿真計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)，因此對(duì)于系統(tǒng)結(jié)構(gòu)差別較大的機(jī)器難于用仿真的方法實(shí)現(xiàn)軟件移植。7.什么是程序直接定位方式？什么是程序靜態(tài)定位方式？答：(1)直接定位方式 程序員在編寫(xiě)程序時(shí)或編譯程序?qū)υ闯绦蜻M(jìn)行編譯時(shí)，就已經(jīng)確切知道該程序應(yīng)占用的主存物理空間。因此可以直接使用實(shí)際主存物理地址來(lái)編寫(xiě)或編譯程序。目前大多不用這種

12、方式。 (2)靜態(tài)定位方式 專(zhuān)門(mén)用裝入程序來(lái)完成并要求程序本身可以重定位。在程序裝入主存的過(guò)程中，把那些帶有標(biāo)識(shí)的指令或數(shù)據(jù)中的邏輯地址全部變成主存的物理地址，集中一次完成地址變換，一旦裝入主存就不能再變動(dòng)了。8.什么是程序動(dòng)態(tài)定位方式？答：動(dòng)態(tài)定位方式是利用類(lèi)似變址尋址方法，有硬件支持完成。程序裝入主存時(shí)，指令或數(shù)據(jù)地址不作修改，只把主存的起始地址裝入該程序?qū)?yīng)的基址寄存器中。在程序運(yùn)行時(shí)，利用地址加法器，指令中的邏輯地址與已經(jīng)存放在基址寄存器中的程序起始地址相加，就形成了主存的物理地址。指令的地址碼不需全部修改。9什么是指令的重疊解釋方式？重疊解釋方式有哪三種？答：所謂重疊解釋方式，即是在

13、兩條相鄰指令的解釋過(guò)程中，某些不同解釋階段在時(shí)間上存在重疊部分。重疊解釋方式分三種：一次重疊、先行控制技術(shù)和多操作部件并行。10.什么是數(shù)據(jù)相關(guān)，數(shù)據(jù)相關(guān)沖突可分為哪三種類(lèi)型？答：數(shù)據(jù)相關(guān)是在幾條相近的指令間共用相同的操作數(shù)時(shí)發(fā)生的。例如，指令部件中的某一條指令在進(jìn)行操作數(shù)地址計(jì)算時(shí)要用到一個(gè)通用寄存器的內(nèi)容，而這個(gè)通用寄存器的內(nèi)容又要由這條指令前的另一條指令產(chǎn)生，但前面那條指令還未進(jìn)入執(zhí)行部件，還未產(chǎn)生通用寄存器的內(nèi)容，這時(shí)指令部件中的那條指令只能停下來(lái)等待。數(shù)據(jù)相關(guān)沖突可分為RAW、WAR和WAW三種類(lèi)型。 11.如有一個(gè)經(jīng)解釋實(shí)現(xiàn)的計(jì)算機(jī)，可以按功能劃分成4級(jí)。每一級(jí)為了執(zhí)行一條指令需要

14、下一級(jí)的N條指令解釋。若執(zhí)行第一級(jí)的一條指令需K(ns)時(shí)間，那么執(zhí)行第2、3、4級(jí)的一條指令各需要用多少時(shí)間(ns)?解： 第二級(jí)的一條指令需第1級(jí)的N條指令解釋 第二級(jí)的一條指令執(zhí)行時(shí)間為NKns； 第三級(jí)的一條指令執(zhí)行時(shí)間為N2Kns； 第四級(jí)的一條指令執(zhí)行時(shí)間為N3Kns。12.假設(shè)將某系統(tǒng)的某一部件的處理速度加快到10倍，但該部件的原處理時(shí)間僅為整個(gè)運(yùn)行時(shí)間的40%，則采用加快措施后能使整個(gè)系統(tǒng)的性能提高多少？解：由題意可知 fe=0.4, re=10, 根據(jù)Amdahl定律13.若某機(jī)要求有：三地址指令4條，單地址指令192條，零地址指令16條。設(shè)指令字長(zhǎng)為12位，每個(gè)地址碼長(zhǎng)3位

15、。問(wèn)能否以擴(kuò)展操作碼為其編碼？14.簡(jiǎn)述馮。諾依曼計(jì)算機(jī)的特征。答：一般認(rèn)為其主要特征有以下幾點(diǎn)：(1)機(jī)器以運(yùn)算器為中心。除了完成運(yùn)算以外，機(jī)器內(nèi)部的數(shù)據(jù)傳輸都經(jīng)過(guò)運(yùn)算器。各部件的操作以及它們之間的協(xié)調(diào)由控制器集中控制。(2)存儲(chǔ)器按一維線性編址，順序訪問(wèn)存儲(chǔ)器地址單元，每個(gè)存儲(chǔ)單元的位數(shù)固定。 (3)程序存儲(chǔ)，指令和數(shù)據(jù)無(wú)區(qū)別存放在存儲(chǔ)器中，指令和數(shù)據(jù)一樣可以送到運(yùn)算器中進(jìn)行運(yùn)算，指令與數(shù)據(jù)的區(qū)別主要在于地址區(qū)域不同。(4)指令在存儲(chǔ)器中按其執(zhí)行順序存放，由一個(gè)順序控制器（亦稱(chēng)程序計(jì)數(shù)器或指令計(jì)數(shù)器）指定即將被執(zhí)行的指令地址。每讀取一條指令后，計(jì)數(shù)器自動(dòng)按順序遞增。 (5)指令由操作碼和地

16、址碼組成，操作碼指明操作類(lèi)型，地址碼指明操作數(shù)的地址和結(jié)果地址。(6)數(shù)據(jù)以二進(jìn)制表示。15.試述頁(yè)式管理虛擬存儲(chǔ)器的工作過(guò)程。答：頁(yè)式管理是將主存空間與虛存空間按固定的大小劃分成塊，每塊稱(chēng)為一頁(yè)。頁(yè)的大小和劃分與程序的邏輯功能無(wú)關(guān)，由操作系統(tǒng)軟件來(lái)執(zhí)行。一般而言，一頁(yè)的大小應(yīng)該是512Bit的整數(shù)倍，因?yàn)檩o助磁盤(pán)存儲(chǔ)的物理塊的大小為512Bit。虛頁(yè)中的頁(yè)稱(chēng)為虛頁(yè)，實(shí)存中的各頁(yè)稱(chēng)為實(shí)頁(yè)，各虛頁(yè)與實(shí)頁(yè)之間按全相聯(lián)方式映象，也就是虛頁(yè)中的一頁(yè)，可以存入主存中的任意一頁(yè)的位置。當(dāng)CPU給出所要訪問(wèn)的虛地址后，根據(jù)用戶號(hào)訪問(wèn)基址寄存器，求得用戶的頁(yè)表首地址Pa，然后與虛地址中的虛頁(yè)號(hào)P相加，得到該頁(yè)

17、的表目，由此表目中得到該頁(yè)存入主存中的實(shí)頁(yè)號(hào)為p，將該頁(yè)號(hào)讀出與頁(yè)內(nèi)地址組裝即可得到主存的實(shí)際地址。 16.簡(jiǎn)述計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)用軟件實(shí)現(xiàn)和用硬件實(shí)現(xiàn)各自的優(yōu)缺點(diǎn)。答：硬件實(shí)現(xiàn):速度快、成本高；靈活性差、占用內(nèi)存少。 軟件實(shí)現(xiàn):速度低、復(fù)制費(fèi)用低;靈活性好、占用內(nèi)存多。17.簡(jiǎn)述字節(jié)多路、數(shù)組多路和選擇通道的數(shù)據(jù)傳送方式。答：（1）字節(jié)多路通道：用于連接多臺(tái)慢速外設(shè)，一般采用字節(jié)交叉?zhèn)魉蛿?shù)據(jù)的方式，即連接在通道上的各個(gè)設(shè)備輪流占用一個(gè)很短的時(shí)間片（通常小于100微秒）傳輸一個(gè)字節(jié)。 （2）選擇通道：是指每一個(gè)通道連接一臺(tái)高速外設(shè)，也可以連接多臺(tái)相同的高速外設(shè)，但通道只能對(duì)各臺(tái)外設(shè)串行服務(wù)。當(dāng)某一

18、設(shè)備工作時(shí)，則通道與該設(shè)備相連，一直到整個(gè)數(shù)組傳送完后，才可能轉(zhuǎn)向?yàn)槠渌O(shè)備服務(wù)。（3）數(shù)組多路通道：數(shù)組多路通道是字節(jié)多路通道與選擇通道工作方式的綜合，是在數(shù)組傳送的基礎(chǔ)上，再分時(shí)為多個(gè)高速外設(shè)服務(wù)。它每次選擇一個(gè)高速設(shè)備后傳送一個(gè)數(shù)據(jù)塊，并輪流為多臺(tái)外圍設(shè)備服務(wù)。每臺(tái)高速外設(shè)，如磁盤(pán)，其工作時(shí)間有尋址時(shí)間與傳送時(shí)間之分。而尋址時(shí)間很長(zhǎng)，在這段時(shí)間中并不需要通道的控制，所以是通道空閑時(shí)間，那么通道可以為其他準(zhǔn)備好的高速外設(shè)服務(wù)。四、問(wèn)答與計(jì)算題（每題15分）1. 某機(jī)主存容量為512KB，Cache的容量為32KB，每塊的大小為16個(gè)字（或字節(jié)）。劃出全相聯(lián)方式主、緩存的地址格式、目錄表格式

19、及其容量。答：主存塊數(shù)：512K/1632K215；緩存塊數(shù)：32K/162K211；塊內(nèi)地址：1624容量：與緩沖塊數(shù)量相同即2112048(或32K/162048)。 主存塊號(hào)Bi 塊內(nèi)地址 18 4 3 0 主存地址 緩存塊號(hào)Bi 塊內(nèi)地址 14 4 3 0 緩存地址 主存塊地址 緩存塊地址 有效位 26 12 11 1 0 目錄表 2. 主存容量為512KB，Cache的容量為32KB，每塊為64個(gè)字（或字節(jié)），緩存共分128組。劃出組相聯(lián)方式主、緩存的地址格式、目錄表格式及其容量。答：主存區(qū)數(shù)：512K/32K1624；緩存組數(shù)：12827； 緩存塊數(shù)：32K/6451229；組內(nèi)塊

20、數(shù)：512/128422； 塊內(nèi)地址：6426容量：與緩沖塊數(shù)量相同即29512(或32K/64512)。 區(qū)號(hào) 塊號(hào) 緩存塊號(hào) 有效位 8 5 4 3 2 1 0 目錄表 組號(hào) 緩存塊號(hào) 塊內(nèi)地址 14 8 7 6 5 0 緩存地址 區(qū)號(hào) 組號(hào) 塊號(hào) 塊內(nèi)地址 18 15 14 8 7 6 5 0 主存地址 3. 什么是方體置換？寫(xiě)出方體置換函數(shù)的表達(dá)式，假設(shè)互聯(lián)網(wǎng)有16個(gè)結(jié)點(diǎn)，請(qǐng)畫(huà)出4個(gè)方體置換函數(shù)（即C0，C1，C2，C3）的輸入端與輸出端的連接關(guān)系。答：方體置換是實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第k位位值不同的輸入端輸出端之間的連接。其表達(dá)式為： C0立方置換函數(shù)：1000100110101011

21、1100110111101111100010011010101111001101111011110000000100100011010001010110011100000001001000110100010101100111 C1立方置換函數(shù)：00000000000100100011010001010110011100010010001101000101011001111001101010111100110111101111100110101011110011011110111110001000C2立方置換函數(shù)：10001001101010111100110111101111100010011

22、010101111001101111011110000000100100011010001010110011100000001001000110100010101100111C3立方置換函數(shù)：100010011010101111001101111011111000100110101011110011011110111100000001001000110100010101100111000000010010001101000101011001114. 在頁(yè)式虛擬存儲(chǔ)器中，一個(gè)程序由P1P5共5個(gè)頁(yè)面組成。在程序執(zhí)行過(guò)程中依次訪問(wèn)的頁(yè)面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P

23、2，P5，P2 假設(shè)系統(tǒng)分配給這個(gè)程序的主存有3個(gè)頁(yè)面，分別采用FIFO、LFU和OPT三種頁(yè)面替換算法對(duì)這3頁(yè)主存進(jìn)行調(diào)度。（1）畫(huà)出主存頁(yè)面調(diào)入、替換和命中的情況表。（2）統(tǒng)計(jì)三種頁(yè)面替換算法的頁(yè)命中率。解：三種替換算法的替換過(guò)程：頁(yè)地址流232152453252 FIFO命中3次223232*3153*1521*5*245*2432*432*4354*3*52調(diào)進(jìn)調(diào)進(jìn)命中調(diào)進(jìn)替換替換替換命中替換命中替換替換LRU命中5次22323123*512*251*425*542*354*235*523*253*調(diào)進(jìn)調(diào)進(jìn)命中調(diào)進(jìn)替換命中替換命中替換替換命中命中OPT命中6次22323231*23*5

24、2*354*354*354*3523*5235235調(diào)進(jìn)調(diào)進(jìn)命中調(diào)進(jìn)替換命中替換命中命中替換命中命中5. 一個(gè)有快表和慢表的頁(yè)式虛擬存儲(chǔ)器，最多有64個(gè)用戶，每個(gè)用戶最多要用1024個(gè)頁(yè)面，每頁(yè)4K字節(jié)，主存容量8M字節(jié)。（1）寫(xiě)出多用戶虛地址的格式，并標(biāo)出各字段的長(zhǎng)度。（2）寫(xiě)出主存地址的格式，并標(biāo)出各字段的長(zhǎng)度。（3）快表的字長(zhǎng)為多少位？分幾個(gè)字段？各字段的長(zhǎng)度為多少位？（4）慢表的容量是多少個(gè)存儲(chǔ)字？每個(gè)存儲(chǔ)字的長(zhǎng)度為多少位？答：用戶號(hào)：6426，虛頁(yè)號(hào)：1024210，頁(yè)內(nèi)地址：4K212，主存頁(yè)數(shù)：8M/4K211（1）多用戶虛地址： 用戶號(hào)（6位）虛頁(yè)號(hào)（10位）頁(yè)內(nèi)地址（12位）

25、 共28位（2）主存地址： 主存實(shí)頁(yè)號(hào)（11位）頁(yè)內(nèi)地址（12位） 共23位（3）快表字長(zhǎng)27位；分3個(gè)字段：用戶號(hào)6位，虛頁(yè)號(hào)10位，實(shí)頁(yè)號(hào)11位（4）慢表容量為2（6+10），每個(gè)存儲(chǔ)字長(zhǎng)為：主存頁(yè)號(hào)112位。6. 一個(gè)程序由五個(gè)虛頁(yè)組成，采用LFU替換算法，在程序執(zhí)行過(guò)程中依次訪問(wèn)的地址流如下： 4，5，3，2，5，1，3，2，3，5，1，3（1）可能的最高頁(yè)命中率是多少？（2）至少要分配給該程序多少個(gè)主存頁(yè)面才能獲得最高的命中率。（3）如果在程序執(zhí)行過(guò)程中訪問(wèn)一個(gè)頁(yè)面，平均要對(duì)該頁(yè)面內(nèi)的存儲(chǔ)單元訪問(wèn)1024次，求訪問(wèn)存儲(chǔ)單元的命中率。 解：（1）由于在頁(yè)地址流中互不相同的頁(yè)共有5頁(yè)，因

26、此最多分配5個(gè)主存頁(yè)面就可獲得最高頁(yè)中命中率，可能的最高命中率為（2）因?yàn)長(zhǎng)FU替換算法為堆棧型換算法，即隨著分配給該程序的主存頁(yè)面數(shù)的減少，其命中率單調(diào)遞減，所以為獲得最高命中率H7/12，可采用逐步減少所分配的主存頁(yè)數(shù)的方法來(lái)推算，若分配n個(gè)主存頁(yè)面時(shí)可獲得最高命中率，但分配n1個(gè)頁(yè)面時(shí)命中率卻減少，則此時(shí)我們可以得出這樣的結(jié)論：至少要分配給該程序n個(gè)主存頁(yè)面才能獲得最高的命中率。由表可知，至少要分配給該程序4個(gè)主存頁(yè)面才能獲得最高的命中率。頁(yè)地址流453251322513 S(1)堆 S(2)棧 S(3)內(nèi) S(4)容 S(5) S(6)4543542354523415234315242

27、315423154523141523431524 n=1實(shí) n=2頁(yè) n=3數(shù) n=4 n>=5HHHHHHHHHHHHHHHHHH（3）訪問(wèn)存儲(chǔ)單元的命中率為值得說(shuō)明的是，在此例中，盡管LFU屬于堆棧替換算法，但是分配的實(shí)際頁(yè)數(shù)n也并不是越多越好，當(dāng)命中率H達(dá)到飽和后，實(shí)際頁(yè)數(shù)n的增加不僅不會(huì)提高命中率，反而會(huì)使實(shí)存的利用率下降。7. 假設(shè)一臺(tái)模型計(jì)算機(jī)共有10種不同的操作碼，如果采用固定長(zhǎng)操作碼需要4位。已知各種操作碼在程序中出現(xiàn)的概率如下表所示，計(jì)算采用Huffman編碼法的操作碼平均長(zhǎng)度，并計(jì)算固定長(zhǎng)操作碼和Huffman操作碼的信息冗余量（假設(shè)最短平均長(zhǎng)度H3.1位）。指令序號(hào)

28、指令使用頻度Pi指令序號(hào)指令使用頻度PiI10.17I60.09I20.15I70.08I30.15I80.07I40.13I90.03I50.12I100.01答：構(gòu)造Huffman樹(shù)如下：Huffman編碼如下表：指令號(hào)指令使用頻度PiHuffman編碼碼長(zhǎng)指令號(hào)指令使用頻度PiHuffman碼碼長(zhǎng)I10.17102I60.0901104I20.150003I70.0801114I30.150013I80.0711104I40.130103I90.03111105I50.121103I100.01111115Huffman編碼的平均碼長(zhǎng)為： 冗余量（3.153.10）/3.151.59%固定碼長(zhǎng)：log2104冗余量（43.10）/422.5%8一臺(tái)模型機(jī)的各條指令的頻度如下：ADD（加）：43% SHR（右移）：1%SUB（減）：13% CLL（循環(huán)左移）：2%JOM（按頁(yè)轉(zhuǎn)移）：6% CLA（累加器清0）：22%STO（存）：5% STP（停機(jī)）：1%JMP（轉(zhuǎn)移）：7 試設(shè)計(jì)這9條指令的哈夫曼編碼的操作碼表示以及