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

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

2、前計(jì)算機(jī)中常用數(shù)據(jù)有（用戶定義數(shù)據(jù)，系統(tǒng)數(shù)據(jù)和指令數(shù)據(jù)）三種類型。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)有兩種：（存儲器存儲器型和寄存器寄存器型）。10.通用計(jì)算機(jī)基本指令分為5類，它們分別是：（數(shù)據(jù)傳送類，運(yùn)算類，程序控制類，輸入輸出類，處理機(jī)控制和調(diào)試類）。11執(zhí)行指令x1=x2+x3；x4=x1-x5會引起（RAW）類型的數(shù)據(jù)相關(guān)，執(zhí)行指令x5=x4*x3；x4=x0+x6會引起（WAR）類型的數(shù)據(jù)相關(guān)，執(zhí)行指令x6=x1+x2；x6=x4*x5會引起（WAW）類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、頁號P相加，得到該頁的表目，由此表目中得到該頁存入主存中的實(shí)頁號為p，將該頁號讀出與頁內(nèi)地址組裝即可得到主存的實(shí)際地址。 16.簡述計(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é)多路、數(shù)組多路和選擇通道的數(shù)據(jù)傳送方式。答：（1）字節(jié)多路通道：用于連接多臺慢速外設(shè)，一般采用字節(jié)交叉?zhèn)魉蛿?shù)據(jù)的方式，即連接在通道上的各個設(shè)備輪流占用一個很短的時間片（通常小于100微秒）傳輸一個字節(jié)。 （2）選擇通道：是指每一個通道連接一臺高速外設(shè)，也可以連接多臺相同的高速外設(shè)，但通道只能對各臺

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

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

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

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

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

23、P4，P5，P3，P2，P5，P2 假設(shè)系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LFU和OPT三種頁面替換算法對這3頁主存進(jìn)行調(diào)度。（1）畫出主存頁面調(diào)入、替換和命中的情況表。（2）統(tǒng)計(jì)三種頁面替換算法的頁命中率。解：三種替換算法的替換過程：頁地址流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次223

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

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

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

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

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