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

精品文檔

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

系別班級姓名學(xué)號

一、填空題（每空1分）

1.按照弗林（Flynn）分類法，計算機系統(tǒng)可以分為4類：SISD計算機、（SIMD計算

機）、（MISD計算機）和（M1MD計算機）。

2.改進之后的馮？諾依曼計算機的只要特點是存儲器為中心，總線結(jié)構(gòu)，分散控制。

3.當(dāng)前計算機系統(tǒng)中的存儲系統(tǒng)是一個層次結(jié)構(gòu)，其各層分別為：（通用寄存器，高速緩存，

主存，輔存，脫機大容量存儲器）。

4.高速緩沖存儲器的地址映象方式有三

種，它們分別是：（全向量方式，直接相聯(lián)方式，組

相聯(lián)方式）。

5.虛擬存儲器的三種管理方式是（段式管理，頁式管理和段頁式管理）。

6.目前計算機中常用數(shù)據(jù)有（用戶定義數(shù)據(jù)，系統(tǒng)數(shù)據(jù)和指令數(shù)據(jù)）三種類型。

7.通常可能出現(xiàn)的流水線的相關(guān)性有（資源相關(guān)，數(shù)據(jù)相關(guān)和控制相關(guān)）。

8.解決中斷引起的流水線斷流的方法有（不精確斷點法和精確斷點法）。

9.目前向量處理機的系統(tǒng)結(jié)構(gòu)有兩種：（存儲器一存儲器型和寄存器一寄存器型）。

10.通用計算機基本指令分為5類，它們分別是：（數(shù)據(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）類型的數(shù)據(jù)相關(guān)。

12.多計算機網(wǎng)絡(luò)中，通常出現(xiàn)的4種通信模式是（單播模式，選播模式，廣播模式和會議模

式）。

13.傳統(tǒng)的馮？諾依曼計算機是以控制驅(qū)動方式工作，以數(shù)據(jù)驅(qū)動方式工作的典型計算機是（數(shù)

據(jù)流計算機），以需求驅(qū)動方式工作的典型計算機是（歸約機），以模式匹配驅(qū)動方式工作

的典型計算機是（人工智能計算機）。

、名詞解釋（每題2分）

1.計算機體系名吉構(gòu)：計算機系統(tǒng)結(jié)構(gòu)就是計算機的機器語言程序員或編譯程序編寫者

所看到的外特性，是硬件子系統(tǒng)的概念結(jié)構(gòu)及其功能特性。

2.系列機：

所謂系列機是指同一廠家生產(chǎn)的具有相同的系統(tǒng)結(jié)構(gòu)，但采取了不同的組成和實現(xiàn)的技術(shù)

方案，形成了不同型號的多種機型。

3.模擬：

模擬是指用軟件的方法在一臺計算機上，實現(xiàn)另一臺計算機的指令系統(tǒng)，被模擬的機器

是不存在的，稱為虛擬機，執(zhí)行模擬程序的機器稱宿主機。

4.程序的局部性原壬里：程序訪問局部性原理說明了計算機在程序執(zhí)行過程中呈現(xiàn)出

的一種規(guī)律，即程序往往重精品文檔

精品文檔

復(fù)使用它剛剛使用過的數(shù)據(jù)和指令。局部性分為時間上的局部性和空間上的局部性兩種。

謂時間局部性是指近期被訪問的代碼，很可能不久又將再次被訪問；空間局部性是指地址上

相鄰近的代碼可能會被連續(xù)地訪問。

5.MIPS：

它表示每秒百萬條指令數(shù)。

6.高速緩沖存儲器：高速緩沖存儲器是

存在于主存與CPU之間的一級存儲器，由靜態(tài)存儲芯片（SRAM）組成，容量比較小但速度比

主存高得多，接近于CPU的速度。

7.虛擬存儲器：

虛擬存儲器是由主存儲器和輔助存儲器組成，通過必須的軟件和硬件的支持，使得CPU

可以訪問的存儲器具有近似于主存的速度和近似于輔存的容量。

8.快表：

為了提高地址轉(zhuǎn)換速度，縮短查表時間，采用一個小容量的、高速的相關(guān)存儲部件，用

來存放當(dāng)前最經(jīng)常用到的那一部分頁表，采取按內(nèi)容相聯(lián)方式進行訪問。這樣，查頁表的時

間就相當(dāng)于訪問小容量的相關(guān)存儲器的時間，從而大大地提高了速度，這個小容量相關(guān)存儲

器稱為快表。

9.程序定位：

把一個程序交給處理機運行，必須首先把這個程序的指令和數(shù)據(jù)裝入到主存儲器中。一

般情況下，程序所分配到的主存物理空間與程序本身的邏輯地址空間是不同的，把指令和數(shù)

據(jù)中的邏輯地址（相對地址）轉(zhuǎn)變成主存物理地址（絕對地址）的過程稱為程序定位。

10.延遲車專移技術(shù)：為了使指令流水線不斷流，在轉(zhuǎn)移指令之后插入一條不相關(guān)的有效

的指令，而轉(zhuǎn)移指令被延遲執(zhí)行，這種技術(shù)稱為延遲轉(zhuǎn)移技術(shù)。

11.窗口重疊技術(shù)：為了能更簡單、更直接地實現(xiàn)過程與過程之間的參數(shù)傳遞，大多數(shù)

RISC機器的CPU中都設(shè)置有數(shù)量較大的寄存器組，讓每個過程使用一個有限數(shù)量的寄存器窗

口，并讓各個過程的寄存器窗口部分重疊，這就是窗口重疊技術(shù)。

12.流水線技術(shù)：

把一個重復(fù)的時序過程分成若干個子過程，每個子過程都可以有效地在其專用功能段上

和其他子過程同時執(zhí)行的一種技術(shù)，稱為流水線技術(shù)。

13.動態(tài)流水線：

動態(tài)流水線在同一時間內(nèi)允許按多種不同運算的聯(lián)結(jié)方式工作。

14.靜態(tài)流水線：

靜態(tài)流水線在同一時間內(nèi)只能按一種運算的聯(lián)結(jié)方式工作。

精品文檔

精品文檔

15.線性流水線:

線性流水線中，從輸入到輸出，每個功能段只允許經(jīng)過一次，不存在反饋回路。

16.非線性流水線：

非線性流水線存在反饋回路，從輸入到輸出過程中，某些功能段將數(shù)次通過流水線，這

種流水線適合于進行線性遞歸的運算。

17.流水線的吞吐率：

流水線單位時間完成的任務(wù)數(shù)。

18.超流水線計算機：超級流水線結(jié)構(gòu)是把每一個流水線(一個周期)分成多個

(例如3個)子流水線，而在每一個子流水線中取出的仍只有一條指令，但總的來看，在

一個周期內(nèi)取出了三條指令。即在一個時鐘周期內(nèi)能夠分時發(fā)射多條指令的處理機。

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ī)則。

答：

(D主存與緩存分成相同大小的數(shù)據(jù)塊。

(2)主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。

3.簡述直接相聯(lián)映象規(guī)則。

答：

(D主存與緩存分成相同大小的數(shù)據(jù)塊。

(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)

與緩存的總塊數(shù)相等。

(3)主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。

精品文檔

精品文檔

4.引起Cache與主存

內(nèi)容不一致的原因是什么？為了保持Cache的一致性，

在單計算機系統(tǒng)中一般采取哪些措施？

答：不一致的原因：

(1)由于CPU寫Cache,沒有立即寫主存

(2)由于I/O處理機或1/0設(shè)備寫主存

采取措施：

(1)全寫法，亦稱寫直達法(WT法一Writethrough)方法：在對Cache進行寫操作的同

時，也對主存該內(nèi)容進行寫入。

(2)寫回法(WB法一Writeback)方法：在CPU執(zhí)行寫操作時，只寫入Cache,不寫入主

存。

5.影響虛擬存儲器命中率的因素有哪些？它們是如何影響的？

答：(1)頁面大?。寒?dāng)頁面比較小時，隨著頁面的增大，命中率明顯提高，但當(dāng)頁面增大到一

定值時，命中率不再增大，而隨著頁面的增大而下降。

(2)主存容量：當(dāng)主存容量增加時，命中率不斷提高；當(dāng)容量增大到一定程度后，命中率的提

高就不大了。

(3)頁面調(diào)度方式：頁面的調(diào)度都是發(fā)生在產(chǎn)生缺頁中斷時進行，因此在程序剛開始運行時命

中率很低，為此可以采用預(yù)取式調(diào)度法，提高命中率。

6.模擬與仿真的主要區(qū)別和適合場合是什么？答：模擬是指用軟件的方法

在一臺計算機上，實現(xiàn)另一臺計算機的指令系統(tǒng)，被模擬的機器是不存在的，稱為虛擬機，

執(zhí)行模擬程序的機器稱宿主機。由于模擬采用純軟件解釋執(zhí)行方法，因此運行速度較慢，實時

性差。因此只適合于移植運行時間短，使用次數(shù)少，而且在時間上沒有約束和限制的軟件。

仿真是指用微程序的方法在一臺計算機上實現(xiàn)另一臺計算機的指令系統(tǒng)。執(zhí)行微程序的

機器為宿主機，被實現(xiàn)的為目標(biāo)機。仿真的運行速度比模擬快，但仿真計算機的系統(tǒng)結(jié)構(gòu)，因

此對于系統(tǒng)結(jié)構(gòu)差別較大的機器難于用仿真的方法實現(xiàn)軟件移植。

7.什么是程序直接定位方式？什么是程序靜態(tài)定位方式？答：⑴

直接定位方式程序員在編寫程序時或編譯程序?qū)υ闯绦蜻M行編譯時，就已經(jīng)確切知道該程序

應(yīng)占用的主存物理空間。因此可以直接使用實際主存物理地址來編寫或編譯程序。目前大多不

用這種方式。

(2)靜態(tài)定位方式專門用裝入程序來完成并要求程序本身可以重定位。在程序裝入主存的

過程中，把那些帶有標(biāo)識的指令或數(shù)據(jù)中的邏輯地址全部變成主存的物理地址，集中一次完

成地址變換，一旦裝入主存就不能再變動了。

8.什么是程序動態(tài)定位方式？

答：動態(tài)定位方式是利用類似變址尋址方法，有硬件支持完成。程序裝入主存時，指令或數(shù)

據(jù)地址不作修改，只把主存的起始地址裝入該程序?qū)?yīng)的基址寄存器中。在程序運行時，利

用地址加法器，指令中的邏輯地址與已經(jīng)存放在基址寄存器中的程序起始地址相加，就形成

了主存的物理地址。指令的地址碼不需全部修改。

精品文檔

精品文檔

9.什么是指令的重疊解釋方式？重疊解釋方式有哪三種？

答：所謂重疊解釋方式，即是在兩條相鄰指令的解釋過程中，某些不同解釋階段在時間上存

在重疊部分。重疊解釋方式分三種：一次重疊、先行控制技術(shù)和多操作部件并行。

10.什么是數(shù)據(jù)相關(guān)，數(shù)據(jù)相關(guān)沖突可分為哪三種類型？答：數(shù)據(jù)相關(guān)是

在幾條相近的指令間共用相同的操作數(shù)時發(fā)生的。例如，指令部件中的某一條指令在進行操

作數(shù)地址計算時要用到一個通用寄存器的內(nèi)容，而這個通用寄存器的內(nèi)容又要由這條指令前的

另一條指令產(chǎn)生，但前面那條指令還未進入執(zhí)行部件，還未產(chǎn)生通用寄存器的內(nèi)容，這時指

令部件中的那條指令只能停下來等待。

數(shù)據(jù)相關(guān)沖突可分為RAW、WAR和WAW三種類型。

11.如有一個經(jīng)解釋實現(xiàn)的計算機，可以按功能劃分成4級。每一級

為了執(zhí)行一

條指令需要下一級的N條指令解釋。若執(zhí)行第一級的一條指令需

K(ns)時間，那

么執(zhí)行第2、3、4級的一條指令各需要用多少時間(ns)?

解：??,第二級的一條指令需第1級的N條指令解釋

.?.第二級的一條指令執(zhí)行時間為NKns;

第三級的一條指令執(zhí)行時間為N2Kns；

第四級的一條指令執(zhí)行時間為N3Knso

12.假設(shè)將某系統(tǒng)的某一部件的處理速度加快到10倍，但該部件的原

處理時間僅

為整個運行時間的40%,則采用加快措施后能使整個系統(tǒng)的性能提高

多少？解：由題意可知fe=0.4,re=10,根據(jù)AmdahI定律

Te11

T?11

M?1.M

,T。(10.4)0.4/100.64

13.若某機要求有：三地址指令4條，單地址指令192條，零地址指

令16條。

設(shè)指令字長為12位，每個地址碼長3位。問能否以擴展操作碼為其

編碼？

精品文檔

精品文檔

14.簡述馮。諾依曼計算機的特征。

答：一般認為其主要特征有以下幾點：

⑴機器以運算器為中心。除了完成運算以外，機器內(nèi)部的數(shù)據(jù)傳輸都經(jīng)過運算器。各部件的操

作以及它們之間的協(xié)調(diào)由控制器集中控制。

⑵存儲器按一維線性編址，順序訪問存儲器地址單元，每個存儲單元的位數(shù)固定。

(3)程序存儲，指令和數(shù)據(jù)無區(qū)別存放在存儲器中，指令和數(shù)據(jù)一樣可以送到運算器中進行

運算，指令與數(shù)據(jù)的區(qū)別主要在于地址區(qū)域不同。

(4)指令在存儲器中按其執(zhí)行順序存放，由一個順序控制器(亦稱程序計數(shù)器或指令計數(shù)器)

指定即將被執(zhí)行的指令地址。每讀取一條指令后，計數(shù)器自動按順序遞增。

⑸指令由操作碼和地址碼組成，操作碼指明操作類型，地址碼指明操作數(shù)的地址和結(jié)果地

址。

(6)數(shù)據(jù)以二進制表示。

15.試述頁式管理虛擬存儲器的工作過程。答：頁式管理是將主存空間與虛存

空間按固定的大小劃分成塊，每塊稱為一頁。頁的大小和劃分與程序的邏輯功能無關(guān)，由操

作系統(tǒng)軟件來執(zhí)行。一般而言，一頁的大小應(yīng)該是512Bit的整數(shù)倍，因為輔助磁盤存儲的

物理塊的大小為512Bito虛頁中的頁稱為虛頁，實存中的各頁稱為實頁，各虛頁與實頁之

間按全相聯(lián)方式映象，也就是虛頁中的一頁，可以存入主存中的任意一頁的位置。當(dāng)CPU給

出所要訪問的虛地址后，根據(jù)用戶號訪問基址寄存器，求得用戶的頁表首地址Pa,然后與虛地

址中的虛頁號P相加，得到該頁的表目，由此表目中得到該頁存入主存中的實頁號為P,將該

頁號讀出與頁內(nèi)地址組裝即可得到主存的實際地址。

16.簡述計算機系統(tǒng)結(jié)構(gòu)用軟件實現(xiàn)和用硬件實現(xiàn)各自的優(yōu)缺點

答：硬件實現(xiàn)：速度快、成本高；靈活性差、占用內(nèi)存少。

軟件實現(xiàn)：速度低、復(fù)制費用低；靈活性好、占用內(nèi)存多。

17.簡述字節(jié)多路、數(shù)組多路和選擇通道的數(shù)據(jù)傳送方式。

精品文檔

精品文檔

答：

(1)字節(jié)多路通道：用于連接多臺慢速外設(shè)，一般采用字節(jié)交叉?zhèn)魉蛿?shù)據(jù)的方式，即連接在通

道上的各個設(shè)備輪流占用一個很短的時間片(通常小于100微秒)傳輸一個字節(jié)。

(2)選擇通道：是指每一個通道連接一臺高速外設(shè)，也可以連接多臺相同的高速外設(shè)，但通道

只能對各臺外設(shè)串行服務(wù)。當(dāng)某一設(shè)備工作時，則通道與該設(shè)備相連，一直到整個數(shù)組傳送

完后，才可能轉(zhuǎn)向為其他設(shè)備服務(wù)。

(3)數(shù)組多路通道：數(shù)組多路通道是字節(jié)多路通道與選擇通道工作方式的綜合，是在數(shù)組傳送

的基礎(chǔ)上，再分時為多個高速外設(shè)服務(wù)。它每次選擇一個高速設(shè)備后傳送一個數(shù)據(jù)塊，并輪流

為多臺外圍設(shè)備服務(wù)。每臺高速外設(shè)，如磁盤，其工作時間有尋址時間與傳送時間之分。而

尋址時間很長，在這段時間中并不需要通道的控制，所以是通道空閑時間，那么通道可以為其

他準(zhǔn)備好的高速外設(shè)服務(wù)。

四'問答與計算題(每題15分)

1.某機主存容量為512KB,Cache的容量為32KB,每塊的大小為

16個字(或

字節(jié))。劃出全相聯(lián)方式主、緩存的地址格式'目錄表格式及其容

量

答：主存塊數(shù)：512K/16=32K=2,5；緩存塊數(shù)：32K/16=2K=2"；塊內(nèi)地址：16=2"

18430

26121110

目錄表主存塊地址緩存塊地址有效位

主存塊號Bi塊內(nèi)地址

14430

緩存塊號Bi塊內(nèi)地址

容量:與緩沖塊數(shù)量相同即2"=2048(或32K/16=2048)(.

2.主存容量為512KB,Cache的容量為32KB,每塊為64個字(或

字節(jié))，緩

存共分128組。劃出組相聯(lián)方式主、緩存的地址格式、目錄表

格式及其容量。答：主存區(qū)數(shù)：512K/32K=16=2"；緩存組數(shù)：128=2'；緩存塊

數(shù)：32K/64=512=2，組內(nèi)塊數(shù)：512/128=4=22；塊內(nèi)地址：64=26

精品文檔

精品文檔

主存地址區(qū)號組號塊號塊內(nèi)地址

1487650

緩存地址組號緩存塊號塊內(nèi)地址

8543210

目錄表區(qū)號塊號緩存塊號有效位

容量：與緩沖塊數(shù)量相同即29=512(或32K/64=512)。

3.什么是方體置換？寫出方體置換函數(shù)的表達式，假設(shè)互聯(lián)網(wǎng)有16

個結(jié)點，請畫出4個方體置換函數(shù)(即CO,C1,C2,03)的

輸入端與輸出端的連接

答：方體置換是實現(xiàn)二進制地址編號中第k位位值不同的輸入端輸出端之間的連接。其表達

式為：Ck(XnlXn2XklXkXklXo)(XnlXn2XklXkXklXo)

CO立方置換函數(shù)：Co(X3X2X1X0)(X3X2X1X°)

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

精品文檔

精品文檔

1111

精品文檔

精品文檔

C1立方置換函數(shù)：G（X3X2X1X。）（X3X2X1X。）

0000--------------S./--------------0000

00010001

00100010

OOH0011

01000100

01010101

OHO0110

0111___________________________________0111

1000-------------X./--------------1000

10011001

10101010

10111011

1100---------------、,----------------1100

1101----------------------------------------------------------1101

mo-------------------------------------------------------------1110

1111_________/1111

C2立方置換函數(shù)：C2(X3X2X1X0)(X3X2X1X0)

0000---------------、/---------------0000

0001---------------/--------------------------------0001

0010------------------------------------------------------0010

0011----0006----0011

0100_________/X/X/vx_________0100

01010101

0110_________//^\\__________0110

0111_________/X__________0111

1000-------------------------------------/-----------------1000

1001---------------//--------------------------------1001

1010-------------------------------------------------------1010

1011----dOOC----1011

1100-----------------1100

1101-----------------1101

1110________//\\----------------1110

精品文檔/\

1111________/X_________1111

精品文檔

C3立方置換函數(shù)：C2(X3X2X|X0)=(X3X2X|XO)0000

00000001

oooi_______AZ_______ooio

工EE

1101—'::

mo-----------!y-----------1111

精品文檔

精品文檔

4.在頁式虛擬存儲器中，一個程序由P1-P5共5個頁面組成。在程序

執(zhí)行過程中依次訪問的頁面如下：P2,P3,P2,P1,P5,P2,P4,P5,

P3,P2,P5,P2

假設(shè)系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LFU

和OPT三種頁面替換算法對這3頁主存進行調(diào)度。

（1）畫出主存頁面調(diào)入'替換和命中的情況表

（2）統(tǒng)計三種頁面替換算法的頁命中率。

解：三種替換算法的替換過程：

頁地址流232152453252

222,*55產(chǎn),?3331*

FIFO333蘆2227*尹55

命中311,*44444*2

調(diào)調(diào)命調(diào)替替替命替命替替

進進中進換換換中換中換換

222152453252

LRU33215245325

命中5>?r*,?苦I*苦1*產(chǎn)

調(diào)調(diào)命調(diào)替命替命替替命命

進進中進換中換中換換中中

2222產(chǎn)?*>*4*222

OPT333333333

命中6，*5555555

調(diào)調(diào)命調(diào)替命替命命替命命

也進市進換市換市中換市市

5.一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用戶最

多要用1024個頁面，每頁4K字節(jié)，主存容量8M字節(jié)。

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

精品文檔

精品文檔

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

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

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

號：64=26,虛頁號：1024=210,頁內(nèi)地址：4K=2",主存頁數(shù)：8M/4K=2"（1）多用戶虛地

址：

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

（2）主存地址：

主存實頁號（11位）+頁內(nèi)地址（12位）共23位

（3）快表字長27位；分3個字段：用戶號6位，虛頁號10位，實頁號11位（4）慢表容

量為2⑻8，每個存儲字長為：主存頁號+1=12位。

6.一個程序由五個虛頁組成，采用LFU替換算法，在程序執(zhí)行過程中依

次訪

問的地址流如下：

4,5,3,2,5,1,3,2,3,5,1,3

1）可能的最高頁命中率是多少？

2）至少要分配給該程序多少個主存頁面才能獲得最高的命中率

3）如果在程序執(zhí)行過程中訪問一個頁面，平均要對該頁面內(nèi)的存儲單

元訪問

1024次，求訪問存儲單元的命中率。

解：（1）由于在頁地址流中互不相同的頁共有5頁，因此最多分配5個主存頁面就可獲

得最高頁中命中率，可能的最高命中率為

,1257

1212

（2）因為LFU替換算法為堆棧型換算法，即隨著分配給該程序的主存頁面數(shù)的減少，其命中

率單調(diào)遞減，所以為獲得最高命中率H=7/12,可采用逐步減少所分配的主存頁

數(shù)的方法來推算，若分配n個主存頁面時可獲得最高命中率，但分配n-1個頁面時命

中率卻減少，則此時我們可以得出這樣的結(jié)論：至少要分配給該程序n個主存頁面才能獲得

最高的命中率。

由表可知，至少要分配給該程序4個主存頁面才能獲得最高的命中率。

精品文檔

精品文檔

頁地址流453251322513

S(1)453251322513

精品文檔

精品文檔

堆S(2)45325133251

棧S(3)4532511325

內(nèi)S(4)443255132

容S(5)4444444

S(6)

n=1H

實n=2H

頁n=3HH

數(shù)n=4HHHHH

n>=5HHHHHH

HH

H

3）訪問存儲單元的命中率為

1024125

H---------------0.99959

102412

值得說明的是，在此例中，盡管LFU屬于堆棧替換算法，但是分配的實際頁數(shù)n也并

不是越多越好，當(dāng)命中率H達到飽和后，實際頁數(shù)n的增加不僅不會提高命中率，反而會使實存的

利用率下降。

8.假設(shè)一臺模型計算機共有10種不同的操作碼，如果采用固定長操作碼

?=1='rtih

而支

4位。已知各種操作碼在程序中出現(xiàn)的概率如下表所示，計算采用

Huffman編碼法的操作碼平均長度，并計算固定長操作碼和Huffman操

作碼的信息冗余量（假

設(shè)最短平均長度H=3.1位）。

指令序號指令序號指令使用頻度Pi

指令使用頻度Pi

精品文檔

精品文檔

110.17I60.09

I20.15I70.08

I30.15I80.07

精品文檔

精品文檔

I40.13I90.03

I50.121100.01

答：構(gòu)造Huffman樹如下:

Huffman編碼如下表：

0.40

><E><3L><0.08^<^09^>〈0.13

指令使指令使

指令號Huffman碼長指令號Huffman碼長

用頻度Pi編碼用頻度Pi碼

110.17102I60.0901104

I20.150003I70.0801114

I30.150013I80.0711104

I40.130103I90.03111105

I50.1211031100.01111115

Huffman編碼的平均碼長為：

10Pil,0.172(0.150.150.130.12)3(0.090.080.07)4(0.03

0.01)5ii

3.15

冗余量=(3.15-3.10)/3.15=1.59%

固定碼長：Iog2"=4

冗余量=(4-3.10)/4=22.5%

8.一臺模型機的各條指令的頻度如下：

ADD（加）：43%SHR（右移）：1%

SUB（減）：13%CLL（循環(huán)左移）：2%

精品文檔

精品文檔

JOM（按頁轉(zhuǎn)移）：CLA（累加器清0）：

6%22%

STO（存）：5%

試設(shè)計這9條指令的哈夫曼編碼的篇馬表示以及2-4等長擴展操作

1.00

碼表示，并計算這兩種表示的平均操作碼長度。

?10.57

答：構(gòu)造Huffman樹如下：022

0.09,0

0.09oo

0.04

01010

Huffman編碼如下表:

指令使用Huffman編2-4擴展

指令碼長碼長

頻度Pi碼碼

ADD0.4301002

CLA0.221003012

SUB0/p>

JMP0.071100410014

JOM0.061101410104

STO0