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

精品文檔

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

系別班級(jí)姓名學(xué)號(hào)

一、填空題（每空1分）

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

機(jī)）、（MISD計(jì)算機(jī)）和（M1MD計(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ù)有（用戶定義數(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)有兩種：（存儲(chǔ)器一存儲(chǔ)器型和寄存器一寄存器型）。

10.通用計(jì)算機(jī)基本指令分為5類，它們分別是：（數(shù)據(jù)傳送類，運(yùn)算類，程序控制類，輸入

輸出類，處理機(jī)控制和調(diào)試類）。

11.執(zhí)行指令x1=x2+x3；x4=x1-x5會(huì)引起（RAW）類型的數(shù)據(jù)相關(guān)，執(zhí)行指令x5=x4*x3；

x4=x0+x6會(huì)引起（WAR）類型的數(shù)據(jù)相關(guān)，執(zhí)行指令x6=x1+x2；x6=x4*x5會(huì)引起

（WAW）類型的數(shù)據(jù)相關(guān)。

12.多計(jì)算機(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ī)）。

、名詞解釋（每題2分）

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

所看到的外特性，是硬件子系統(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ī)上，實(shí)現(xiàn)另一臺(tái)計(jì)算機(jī)的指令系統(tǒng)，被模擬的機(jī)器

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

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

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

精品文檔

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

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

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

5.MIPS：

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

6.高速緩沖存儲(chǔ)器：高速緩沖存儲(chǔ)器是

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

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

7.虛擬存儲(chǔ)器：

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

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

8.快表：

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

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

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

器稱為快表。

9.程序定位：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

精品文檔

精品文檔

15.線性流水線:

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

16.非線性流水線：

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

種流水線適合于進(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.向量的分段開采技術(shù)：

當(dāng)向量的長(zhǎng)度大于向量寄存器的長(zhǎng)度時(shí)，必須把長(zhǎng)向量分成長(zhǎng)度固定的段，采用循環(huán)結(jié)

構(gòu)處理這個(gè)長(zhǎng)向量，這種技術(shù)稱為向量循環(huán)開采技術(shù)，也稱為向量分段開采技術(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ī)則。

答：

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

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

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

答：

(D主存與緩存分成相同大小的數(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寫Cache,沒有立即寫主存

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

采取措施：

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

時(shí)，也對(duì)主存該內(nèi)容進(jìn)行寫入。

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

存。

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)行，因此在程序剛開始運(yùn)行時(shí)命

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

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

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

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

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

仿真是指用微程序的方法在一臺(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)定位方式？答：⑴

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

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

用這種方式。

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

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

成地址變換，一旦裝入主存就不能再變動(dòng)了。

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

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

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

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

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

精品文檔

精品文檔

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

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

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

10.什么是數(shù)據(jù)相關(guān)，數(shù)據(jù)相關(guān)沖突可分為哪三種類型？答：數(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三種類型。

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

為了執(zhí)行一

條指令需要下一級(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í)間為N3Knso

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

處理時(shí)間僅

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

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

Te11

T?11

M?1.M

,T。(10.4)0.4/100.64

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

令16條。

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

編碼？

精品文檔

精品文檔

14.簡(jiǎn)述馮。諾依曼計(jì)算機(jī)的特征。

答：一般認(rèn)為其主要特征有以下幾點(diǎn)：

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

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

⑵存儲(chǔ)器按一維線性編址，順序訪問存儲(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è)順序控制器(亦稱程序計(jì)數(shù)器或指令計(jì)數(shù)器)

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

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

址。

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

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

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

作系統(tǒng)軟件來(lái)執(zhí)行。一般而言，一頁(yè)的大小應(yīng)該是512Bit的整數(shù)倍，因?yàn)檩o助磁盤存儲(chǔ)的

物理塊的大小為512Bito虛頁(yè)中的頁(yè)稱為虛頁(yè)，實(shí)存中的各頁(yè)稱為實(shí)頁(yè)，各虛頁(yè)與實(shí)頁(yè)之

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

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

址中的虛頁(yè)號(hào)P相加，得到該頁(yè)的表目，由此表目中得到該頁(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)某一設(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è)，如磁盤，其工作時(shí)間有尋址時(shí)間與傳送時(shí)間之分。而

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

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

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

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

16個(gè)字(或

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

量

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

18430

26121110

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

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

14430

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

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

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

字節(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ū)號(hào)組號(hào)塊號(hào)塊內(nèi)地址

1487650

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

8543210

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

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

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

個(gè)結(jié)點(diǎn)，請(qǐng)畫出4個(gè)方體置換函數(shù)(即CO,C1,C2,03)的

輸入端與輸出端的連接

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

式為：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.在頁(yè)式虛擬存儲(chǔ)器中，一個(gè)程序由P1-P5共5個(gè)頁(yè)面組成。在程序

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

P3,P2,P5,P2

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

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

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

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

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

頁(yè)地址流232152453252

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

FIFO333蘆2227*尹55

命中311,*44444*2

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

進(jìn)進(jìn)中進(jìn)換換換中換中換換

222152453252

LRU33215245325

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

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

進(jìn)進(jìn)中進(jìn)換中換中換換中中

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

OPT333333333

命中6，*5555555

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

也進(jìn)市進(jìn)換市換市中換市市

5.一個(gè)有快表和慢表的頁(yè)式虛擬存儲(chǔ)器，最多有64個(gè)用戶，每個(gè)用戶最

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

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

精品文檔

精品文檔

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

（3）快表的字長(zhǎng)為多少位？分幾個(gè)字段？各字段的長(zhǎng)度為多少位？

（4）慢表的容量是多少個(gè)存儲(chǔ)字？每個(gè)存儲(chǔ)字的長(zhǎng)度為多少位？答：用戶

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

址：

用戶號(hào)（6位）+虛頁(yè)號(hào)（10位）+頁(yè)內(nèi)地址（12位）共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⑻8，每個(gè)存儲(chǔ)字長(zhǎng)為：主存頁(yè)號(hào)+1=12位。

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

次訪

問的地址流如下：

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

1）可能的最高頁(yè)命中率是多少？

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

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

元訪問

1024次，求訪問存儲(chǔ)單元的命中率。

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

得最高頁(yè)中命中率，可能的最高命中率為

,1257

1212

（2）因?yàn)長(zhǎng)FU替換算法為堆棧型換算法，即隨著分配給該程序的主存頁(yè)面數(shù)的減少，其命中

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

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

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

最高的命中率。

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

精品文檔

精品文檔

頁(yè)地址流453251322513

S(1)453251322513

精品文檔

精品文檔

堆S(2)45325133251

棧S(3)4532511325

內(nèi)S(4)443255132

容S(5)4444444

S(6)

n=1H

實(shí)n=2H

頁(yè)n=3HH

數(shù)n=4HHHHH

n>=5HHHHHH

HH

H

3）訪問存儲(chǔ)單元的命中率為

1024125

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

102412

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

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

利用率下降。

8.假設(shè)一臺(tái)模型計(jì)算機(jī)共有10種不同的操作碼，如果采用固定長(zhǎng)操作碼

?=1='rtih

而支

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

Huffman編碼法的操作碼平均長(zhǎng)度，并計(jì)算固定長(zhǎng)操作碼和Huffman操

作碼的信息冗余量（假

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

指令序號(hào)指令序號(hào)指令使用頻度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

指令使指令使

指令號(hào)Huffman碼長(zhǎng)指令號(hào)Huffman碼長(zhǎng)

用頻度Pi編碼用頻度Pi碼

110.17102I60.0901104

I20.150003I70.0801114

I30.150013I80.0711104

I40.130103I90.03111105

I50.1211031100.01111115

Huffman編碼的平均碼長(zhǎng)為：

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%

固定碼長(zhǎng)：Iog2"=4

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

8.一臺(tái)模型機(jī)的各條指令的頻度如下：

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

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

精品文檔

精品文檔

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

6%22%

STO（存）：5%

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

1.00

碼表示，并計(jì)算這兩種表示的平均操作碼長(zhǎng)度。

?10.57

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

0.09,0

0.09oo

0.04

01010

Huffman編碼如下表:

指令使用Huffman編2-4擴(kuò)展

指令碼長(zhǎng)碼長(zhǎng)

頻度Pi碼碼

ADD0.4301002

CLA0.221003012

SUB0/p>

JMP0.071100410014

JOM0.061101410104

STO0