第一章計算機系統結構的基本概念

從處理數據的角度看，并行級別有位串字串，位并字串，位片串字并，全并行。位串字串和位并字串基本上構成了SIMD。位片串字并的例子有：相聯處理機STARAN，MPP。全并行的例子有：陣列處理機ILLIACIV。

從加工信息的角度看，并行級別有存儲器操作并行，處理器操作步驟并行，處理器操作并行，指令、任務、作業并行。

存儲器操作并行是指可以在一個存儲周期內并行讀出多個CPU字的，采用單體多字、多體單字或多體多字的交叉訪問主存系統，進而采用按內容訪問方式，位片串字并或全并行方式，在一個主存周期內實現對存儲器中大量字的高速并行操作。例子有并行存儲器系統，以相聯存儲器為核心構成的相聯處理機。

處理器操作步驟并行是指在并行性概念中引入時間因素，讓多個處理過程在時間上錯開，輪流重復地執行使用同一套設備的各個部分，加快硬件周轉來贏得速度。例子有流水線處理機。

處理器操作并行是指一個指令部件同時控制多個處理單元，實現一條指令對多個數據的操作。擅長對向量、數組進行處理。例子有陣列處理機。

指令、任務、作業并行是指多個獨立的處理機分別執行各自的指令、任務、作業。例子有多處理機，計算機網絡，分布處理系統。

并行性的開發途徑有時間重疊(TimeInterleaving)，資源重復(ResourceReplication)，資源共享(ResourceSharing)。

時間重疊是指在并行性概念中引入時間因素，讓多個處理過程在時間上錯開，輪流重復地執行使用同一套設備的各個部分，加快硬件周轉來贏得速度。例子有流水線處理機。

資源重復是指一個指令部件同時控制多個處理單元，實現一條指令對多個數據的操作。例子有陣列處理機，相聯處理機。

資源共享是指用軟件方法讓多個用戶按一定時間順序輪流使用同一套資源以提高資源的利用率，從而提高系統性能。例子有多處理機，計算機網絡，分布處理系統。

SISD:一個指令部件控制一個操作部件，實現一條指令對一個數據的操作。例子有傳統的單處理機

SIMD:一個指令部件同時控制多個處理單元，實現一條指令對多個數據的操作。例子有陣列處理機，相聯處理機。

MIMD:多個獨立的處理機分別執行各自的指令、任務、作業，實現指令、任務、作業并行的多機系統，是多個SISD的集合，也稱多倍SISD系統(MSISD)。例子有多處理機，計算機網絡，分布處理系統。

exercises:

1.有一臺經解釋實現的計算機，可以按功能劃分成4級，每一級為了執行一條指令，需要下一級的N條指令來解釋。如果執行第1級的一條指令要Kns時間，那么執行第2、第3和第4級的一條指令各需要用多少時間？

解答：

執行第2、第3和第4級的一條指令各需要KNns、KN^2ns、KN^3ns的時間。1.有一個計算機系統可按功能分成4級，每級的指令互不相同，每一級的指令都比其下一級的指令在效能上強M倍，即第i級的一條指令能完成第i-1級的M條指令的計算量。現若需第i級的N條指令解釋第i+1級的一條指令，而有一段第1級的程序需要運行Ks，問在第2、3和4級上一段等效程序各需要運行多長時間？

答：

第2級上等效程序需運行：(N/M)*Ks。第3級上等效程序需運行：(N/M)*(N/M)*Ks。第4級上等效程序需運行：(N/M)*(N/M)*(N/M)*Ks。

note:

由題意可知：第i級的一條指令能完成第i-1級的M條指令的計算量。而現在第i級有N條指令解釋第i+1級的一條指令，那么，我們就可以用N/M來表示N/M表示第i+1級需(N/M)條指令來完成第i級的計算量。所以，當有一段第1級的程序需要運行Ks時，在第2級就需要(N/M)Ks，以此類推

2.硬件和軟件在什么意義上是等效的？在什么意義上又是不等效的？試舉例說明。

答：軟件和硬件在邏輯功能上是等效的，原理上，軟件的功能可用硬件或固件完成，硬件的功能也可用軟件模擬完成。但是實現的性能價格比，實現的難易程序不同。

在DOS操作系統時代，漢字系統是一個重要問題，早期的漢字系統的字庫和處理程序都固化在漢卡（硬件）上，而隨著CPU、硬盤、內存技術的不斷發展，UCDOS把漢字系統的所有組成部份做成一個軟件。

3.試以實例說明計算機系統結構、計算機組成與計算機實現之間的相互關系與影響。

答：計算機系統結構、計算機組成、計算機實現互不相同，但又相互影響。

（1）計算機的系統結構相同，但可采用不同的組成。如IBM370系列有115、125、135、158、168等由低檔到高檔的多種型號機器。從匯編語言、機器語言程序設計者看到的概念性結構相同，均是由中央處理機/主存，通道、設備控制器，外設4級構成。其中，中央處理機都有相同的機器指令和匯編指令系統，只是指令的分析、執行在低檔機上采用順序進行，在高檔機上采用重疊、流水或其它并行處理方式。

（2）相同的組成可有多種不同的實現。如主存器件可用雙極型的，也可用MOS型的；可用VLSI單片，也可用多片小規模集成電路組搭。

（3）計算機的系統結構不同，會使采用的組成技術不同，反之組成也會影響結構。如為實現A:=B+CD:=E*F,可采用面向寄存器的系統結構，也可采用面向主存的三地址尋址方式的系統結構。要提高運行速度，可讓相加與相乘并行，為此這兩種結構在組成上都要求設置獨立的加法器和乘法器。但對面向寄存器的系統結構還要求寄存器能同時被訪問，而對面向主存的三地址尋址方式的系統結構并無此要求，倒是要求能同時形成多個訪存操作數地址和能同時訪存。又如微程序控制是組成影響結構的典型。通過改變控制存儲器中的微程序，就可改變系統的機器指令，改變結構。如果沒有組成技術的進步，結構的進展是不可能的。

綜上所述，系統結構的設計必須結合應用考慮，為軟件和算法的實現提供更多更好的支持，同時要考慮可能采用和準備采用的組成技術。應避免過多地或不合理地限制各種組成、實現技術的采用和發展，盡量做到既能方便地在低檔機上用簡單便宜的組成實現，又能在高檔機上用復雜較貴的組成實現，這樣，結構才有生命力；組成設計上面決定于結構，下面受限于實現技術。然而，它可與實現折衷權衡。例如，為達到速度要求，可用簡單的組成但卻是復雜的實現技術，也可用復雜的組成但卻是一般速度的實現技術。前者要求高性能的器件，后者可能造成組成設計復雜化和更多地采用專用芯片。

組成和實現的權衡取決于性能價格比等因素；結構、組成和實現所包含的具體內容隨不同時期及不同的計算機系統會有差異。軟件的硬化和硬件的軟件都反映了這一事實。VLSI的發展更使結構組成和實現融為一體，難以分開。

4.什么是透明性概念？對計算機系統結構，下列哪些是透明的？哪些是不透明的？

存儲器的模m交叉存取；浮點數據表示；I/O系統是采用通道方式還是外圍處理機方式；數據總線寬度；字符行運算指令；陣列運算部件；通道是采用結合型還是獨立型；PDP-11系列的單總線結構；訪問方式保護；程序性中斷；串行、重疊還是流水控制方式；堆棧指令；存儲器最小編址單位；Cache存儲器。

答：透明指的是客觀存在的事物或屬性從某個角度看不到。

透明的有：存儲器的模m交叉存取；數據總線寬度；陣列運算部件；通道是采用結合型還是獨立型；PDP-11系列的單總線結構串行、重疊還是流水控制方式；Cache存儲器。

不透明的有：浮點數據表示；I/O系統是采用通道方式還是外圍處理機方式；字符行運算指令；訪問方式保護；程序性中斷；；堆棧指令；存儲器最小編址單位。

5.從機器（匯編）語言程序員看，以下哪些是透明的？

指令地址寄存器；指令緩沖器；時標發生器；條件寄存器；乘法器；主存地址寄存器；磁盤外設；先行進位鏈；移位器；通用寄存器；中斷字寄存器。

答：透明的有：指令緩沖器、時標發生器、乘法器、先進先出鏈、移位器、主存地址寄存器。

6.下列哪些對系統程序員是透明的？哪些對應用程序員是透明的？

系列機各檔不同的數據通路寬度；虛擬存儲器；Cache存儲器；程序狀態字；“啟動I/O”指令；“執行”指令；指令緩沖寄存器。

答：對系統程序員透明的有：系列機各檔不同的數據通路寬度；Cache存儲器；指令緩沖寄存器；

對應用程序員透明的有：系列機各檔不同的數據通路寬度；Cache存儲器；指令緩沖寄存器；虛擬存儲器；程序狀態字；“啟動I/O”指令。

note:系列機各檔不同的數據通路寬度、Cache存貯器、指令緩沖寄存器屬于計算機組成，對系統和程序員和應用程序員都是透明的。

虛擬存貯器、程序狀態字、“啟動I/O”指令，對系統程序員是不透明的，而對應用程序員卻是透明的。

“執行”指令則對系統程序員和應用程序員都是不透明的。

7.想在系列機中發展一種新型號機器，你認為下列哪些設想是可以考慮的，哪些則不行的？為什么？

新增加字符數據類型和若干條字符處理指令，以支持事務處理程序的編譯。

（2）為增強中斷處理功能，將中斷分級由原來的4級增加到5級，并重新調整中斷響應的優先次序。

（3）在CPU和主存之間增設Cache存儲器，以克服因主存訪問速率過低而造成的系統性能瓶頸。

（4）為解決計算誤差較大，將機器中浮點數的下溢處理方法由原來的恒置“1”法，改為用ROM存取下溢處理結果的查表舍入法。

（5）為增加尋址靈活性和減少平均指令字長，將原等長操作碼指令改為有3類不同碼長的擴展操作碼；將源操作數尋址方式由操作碼指明改成如VAX-11那種設尋址方式位字段指明。

（6）將CPU與主存間的數據通路寬度由16位擴展成32位，以加快主機內部信息的傳送。

（7）為減少公用總路線的使用沖突，將單總線改為雙總線。

（8）把原0號通用寄存器改作堆棧指示器。

答：可以考慮的有：1,3,4,6,7。不可以考慮的有：2,5,8。

原則是看改進后能否保持軟件的可移植性。

P.S.為了能使軟件長期穩定，就要在相當長的時期里保證系統結構基本不變，因此在確定系列結構時要非常慎重。其中最主要是確定好系列機的指令系統、數據表示及概念性結構。既要考慮滿足應用的各種需要和發展，又要考慮能方便地采用從低速到高速的各種組成的實現技術，即使用復雜、昂貴的組成實現時，也還能充分發揮該實現方法所帶來的好處。

8.并行處理計算機除分布處理、MPP和機群系統外，有哪4種基本結構？列舉它們各自要解決的主要問題。

答：除了分布處理，MPP和機群系統外，并行處理計算機按其基本結構特征可分為流水線計算機，陣列處理機，多處理機和數據流計算機四種不同的結構。

流水線計算機主要通過時間重疊，讓多個部件在時間上交劃重疊地并行招待運算和處理，以實現時間上的并行。它主要應解決：擁塞控制，沖突防止，流水線調度等問題。

陣列處理機主要通過資源重復實現空間上的并行。它主要應解決：處理單元靈活、規律的互連模式和互連網絡設計，數據在存儲器中的分布算法等問題。

多處理機主要通過資源共享，讓一組計算機在統一的操作系統全盤控制下，實現軟件和硬件各級上的相互作用，達到時間和空間上的異步并行。它主要應解決：處理機間互連等硬件結構，進程間的同上步和通訊，多處理機調度等問題。

數據流計算機設有共享變量的概念，指令執行順序只受指令中數據的相關性制約。數據是以表示某一操作數或參數已準備就緒的數據令牌直接在指令之間傳遞。它主要應解決：研究合適的硬件組織和結構，高效執行的數據流語言等問題。

9.計算機系統的3T性能目標是什么？

答：計算機系統的3T性能目標是1TFLOPS計算能力,1TBYTE主存容量和1TBYTES的I/O帶寬第二章數據表示與指令系統

1.尾數的rm進制數位m'和尾數的二進制數位m的關系

存在m'=m/log2(rm)這種關系是因為，在機器中，一個rm進制的數位是用log2(rm)個機器數位來表示的。

假設rm=8，尾數為20，則m'=2,八進制數20轉換成二進制數為10000，其二進制數位，即機器數位m=5。2=5/log2(8)。

note:這里的等號并不表示純粹數學意義上的“等于”。

2.可表示的尾數個數公式

rm^m'(rm-1)/rm。

對于rm進制的數來說，每個數位均可以有0到rm-1，即rm個碼。m'個rm進制數位共有rm^m'種編碼。但課本中討論的是規格化數，即尾數的小數點后第一個數位不為零的數，所以，應該去掉小數點后第一個數位是0的那些非規格化的數。顯然，非規格化數的個數占了全部尾數編碼總數的1/rm的比例，所以可表示的浮點數規格化的尾數個數應該是：rm^m'（1-1/rm)。

exercises:

1.某模型時機共有7種指令，各指令使用頻率分別為0.35，0.25，0.20，0.10，0.05，0.03，0.02，有8個通用數據寄存器和2個變址寄存器。

（1）要求操作碼的平均長最短，請設計操作碼的編碼，并計算所設計操作碼的平均長。（4分）

（2）設計8位長度的寄存器－寄存器型指令3種，16位長度的寄存器－存儲器變址尋址方式指令4條，變址范圍不小于正、負127。請寫出指令格式，并給出各字段的長度和操作碼編碼。（6分）

解答：

(1)全Huffman編碼的平均碼長是可用的二進制位編碼中平均碼長最短的編碼。

全Huffman編碼的平均碼長=2*(0.35+0.25+0.20)+3*0.10+4*0.05+5*(0.02+0.03)=2.35

(2)由于有8個通用數據寄存器和2個變址寄存器，所以通用寄存器用3位表示，變址寄存器用1位表示,8位的寄存器-寄存器型指令，3個操作碼編碼為00、01、10，16位的寄存器-存儲器變址尋址方式指令，4個操作碼編碼為1100、1101、1110、1111，2位3位3位OPR1R2操作碼寄存器1寄存器24位3位1位8位OPR1Xd操作碼寄存器1變址寄存器相對位移主存邏輯地址1.數據結構和機器的數據表示之間是什么關系？確定和引入數據表示的基本原則是什么？

答：數據表示是能由硬件直接識別和引用的數據類型。數據結構反映各種數據元素或信息單元之間的結構關系。

數據結構要通過軟件映象變換成機器所具有的各種數據表示實現，所以數據表示是數據結構的組成元素。不同的數據表示可為數據結構的實現提供不同的支持，表現在實現效率和方便性不同。數據表示和數據結構是軟件、硬件的交界面。

除基本數據表示不可少外，高級數據表示的引入遵循以下原則：

（1）看系統的效率有否提高，是否養活了實現時間和存儲空間。

（2）看引入這種數據表示后，其通用性和利用率是否高。

2.標志符數據表示與描述符數據表示有何區別？描述符數據表示與向量數據表示對向量數據結構所提供的支持有什么不同？

答：標志符數據表示與描述符數據表示的差別是標志符與每個數據相連，合存于同一存儲單元，描述單個數據的類型特性;描述符是與數據分開存放，用于描述向量、數組等成塊數據的特征。

描述符數據表示為向量、數組的的實現提供了支持，有利于簡化高級語言程序編譯中的代碼生成，可以比變址法更快地形成數據元素的地址。但描述符數據表示并不支持向量、數組數據結構的高效實現。而在有向量、數組數據表示的向量處理機上，硬件上設置有豐富的賂量或陣列運算指令，配有流水或陣列方式處理的高速運算器，不僅能快速形成向量、數組的元素地址，更重要的是便于實現把向量各元素成塊預取到中央處理機，用一條向量、數組指令流水或同時對整個向量、數組高速處理．如讓硬件越界判斷與元素運算并行。這些比起用與向量、陣列無關的機器語言和數據表示串行實現要高效的多。

3.堆棧型機器與通用寄存器型機器的主要區別是什么？堆棧型機器系統結構為程序調用的哪些操作提供了支持？

答：通用寄存器型機器對堆棧數據結構實現的支持是較差的。表現在：(1)堆棧操作的指令少，功能單一；(2)堆棧在存儲器內，訪問堆棧速度低；(3)堆棧通常只用于保存于程序調用時的返回地址，少量用堆棧實現程序間的參數傳遞。

而堆棧型機器則不同，表現在：(1)有高速寄存器組成的硬件堆棧，并與主存中堆棧區在邏輯上組成整體，使堆棧的訪問速度是寄存器的，容量是主存的；(2)豐富的堆棧指令可對堆棧中的數據進行各種運算和處理；(3)有力地支持高級語言的編譯；(4)有力地支持子程序的嵌套和遞歸調用。

堆棧型機器系統結構有力地支持子程序的嵌套和遞歸調用。在程序調用時將返回地址、條件碼、關鍵寄存器的內容等全部壓入堆棧，待子程序返回時，再從堆棧中彈出。

4.設某機階值6位、尾數48位，階符和數符不在其內，當尾數分別以2、8、16為基時，在非負階、正尾數、規格化數情況下，求出其最小階、最大階、階的個數、最小尾數值、最大尾數值、可表示的最小值和最大值及可表示的規格化數的總個數。

解：

依題意知：p=6m=48rm=2,8,16，m'=m/log2(rm)，列下表：p=6,m=48,rm=2(m'=48)p=6,m=48,rm=8(m'=16)p=6,m=48,rm=16(m'=12)最小階(非負階，最小為0)000最大階(2^p-1)2^6-12^6-12^6-1最小尾數值(rm^(-1))1/21/81/16最大尾數值(1-rm^(-m'))1-2^(-48)1-8^(-16)，即(1-2^(-48))1-16^(-12)，即(1-2^(-48))可表示的最小值1/21/81/16可表示的最大值2^63*(1-2^(-48))8^63*(1-8^(-16))16^63*(1-16^(-12))階的個數(2^p)2^62^62^6可表示的尾數的個數2^48*(2-1)/28^16*(8-1)/816^12*(16-1)/16可表示的規格化數的個數2^6*2^48*(2-1)/22^6*8^16*(8-1)/82^6*16^12*(16-1)/16note:

可表示的最小值=rm^(最小階)*最小尾數值=rm^0*rm^(-1)=rm^(-1);

可表示的最大值=rm^(最大階)*最大尾數值=rm^(2^p-1)*(1-rm^(-m'));

可表示的尾數的個數=rm^m'*(rm-1)/rm;

可表示的規格化數的個數=階的個數*尾數的個數=2^p*rm^m'*(rm-1)/rm。

5.（1）浮點數系統使用的階基rp=2,階值位數p=2,尾數基值rm=10，以rm為基的尾數位數m''=1,按照使用的倍數來說，等價于m=4,試計算在非負階、正尾數、規格化情況下的最小尾數值、最大尾數值、最大階值、可表示的最小值和最大值及可表示數的個數。

（2）對于rp=2,p=2,rm=4,m'=2,重復以上計算。

解：

依題意列下表：p=2,rm=10,m'=1p=2,rm=4,m'=2最小尾數值10^-1=0.14^-1=0.25最大尾數值1-10^-1=0.91-4^-2=15/16最大階值2p^-1=33可表示的最小值0.10.25可表示的最大值10^3*0.9=9004^3*15/16=60可表示數的個數3648

題中“按照使用的倍數來說，等價于m=4,”這個m=4,因為2^3<10<2^4,等價為實際要4個二進制位，表示RM=10為基的一位

6.由4位數（其中最低位為下溢附加位）經ROM查表舍入法，下溢處理成3位結果，設計使下溢處理平均誤差接近于零的ROM表，列出ROM編碼表地址與內容的對應關系。

解：

ROM編碼表地址與內容的對應關系地址0000000100100011010001010110011110001001101010111100110111101111內容0000010010100100110111001001011011101101111111117.變址尋址和基址尋址各適用于何種場合？設計一種只用6位地址碼就可指向一個大地址空間中任意64個地址之一的尋址機構。

答：基址尋址是對邏輯地址空間到物理地址空間變換的支持，以利于實現程序的動態再定位。變址尋址是對數組等數據塊運算的支持，以利于循環。將大地址空間64個地址分塊，用基址寄存器指出程序所在塊號，用指令中6位地址碼表示該塊內64個地址之一，這樣基址和變址相結合可訪問大地址任意64個地址之一。比如地址空間很大，為0-1023，只用6位地址碼就可以指向這1024個地址中的任意64個。

剖析：比如地址空間很大，1024，就是分成16個塊，塊號放在寄存器中，塊內地址放在地址位中，寄存器內容和地址位結合，就能達到要求了。

8.經統計，某機器14條指令的使用頻度分別為：0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14,0.11,0.03。分別求出用等長碼、Huffman碼、只有兩種碼長的擴展操作碼3種編碼方式的操作碼平均碼長。

解：等長操作碼的平均碼長=4位;Huffman編碼的平均碼長=3.38位;只有兩種碼長的擴展操作碼的平均碼長=3.4位。

9.若某機要求：三地址指令4條，單地址指令255條，零地址指令16條。設指令字長為12位．每個地址碼長為3位。問能否以擴展操作碼為其編碼?如果其中單地址指令為254條呢?說明其理由。

答：

①不能用擴展碼為其編碼。

∵指令字長12位，每個地址碼占3位；

∴三地址指令最多是2^(12-3-3-3)=8條，現三地址指令需4條,

∴可有4條編碼作為擴展碼，

∴單地址指令最多為4×2^3×2^3=2^8=256條，

現要求單地址指令255條，∴可有一條編碼作擴展碼

∴零地址指令最多為1×2^3＝8條

不滿足題目要求

∴不可能以擴展碼為其編碼。

②若單地址指令254條，可以用擴展碼為其編碼。

∵依據①中推導，單地址指令中可用2條編碼作為擴展碼

∴零地址指令為2×2^3＝16條，滿足題目要求

note:三地址指令格式：操作碼地址碼地址碼地址碼3位3位3位3位單地址指令格式：操作碼地址碼9位3位

所以前面9位由于三地址指令用了最前面3位，還有中間6位可作為編碼（也就是總共可以有9位作為單地址指令的指令操作碼的編碼）。減去3地址指令的4條，有4*2^6=256條，但由于韙目要求要有255條，所以剩下一個編碼，已經用了9位的全部編碼，最后零地址指令（全部12位都可作為操作碼的編碼）還有1*2^3=8(這是12位編碼中最后三位的）若只要求254種，則可以有（256-254）*2^3=16條

10.某機指令字長16位。設有單地址指令和雙地址指令兩類。若每個地址字段為6位.且雙地址指令有X條。問單地址指令最多可以有多少條?

答：

單地址指令最多為(16-X)×2^6

P.S.雙地址指令最多是2^(16-6-6)=2^4=16條，現雙地址指令有X條,

∴可有(16-X)條編碼作為擴展碼，

∴單地址指令最多為(16-X)×2^6=256條

11.何謂指令格式的優化?簡要列舉包括操作碼和地址碼兩部分的指令格式優化可采用的各種途徑和思路。

答：

指令格式的優化指如何用最短位數表示指令的操作信息和地址信息，使程序中指令的平均字長最短。

①操作碼的優化

采用Huffman編碼和擴展操作碼編碼。

②對地址碼的優化：

采用多種尋址方式;

采用0、1、2、3等多種地址制;

在同種地址制內再采用多種地址形式，如寄存器-寄存器型、寄存器-主存型、主存-主存型等;

在維持指令字在存儲器內按整數邊界存儲的前提下，使用多種不同的指令字長度。

12.某模型機9條指令使用頻率為：ADD(加)30%SUB(減)24%JOM(按負轉移)6%STO(存)7%JMP(轉移)7%SHR(右移)2%CIL(循環)3%CLA(清加)20%STP(停機)1%要求有兩種指令字長，都按雙操作數指令格式編排，采用擴展操作碼，并限制只能有兩種操作碼碼長。設該機有若干通用寄存器，主存為16位寬，按字節編址，采用按整數邊界存儲。任何指令都在一個主存周期中取得，短指令為寄存器-寄存器型，長指令為寄存器-主存型，主存地址應能變址尋址。(1)僅根據使用頻率，不考慮其它要求，設計出全Huffman操作碼，計算其平均碼長;(2)考慮題目全部要求，設計優化實用的操作形式，并計算其操作碼的平均碼長;

(3)該機允許使用多少可編址的通用寄存器？

(4)畫出該機兩種指令字格式，標出各字段之位數;

(5)指出訪存操作數地址尋址的最大相對位移量為多少個字節？

解：

第(1)和(2)中Huffman和擴展操作碼的編碼及平均碼長如下表：指令Ii使用頻度PiHuffman編碼擴展操作碼編碼I1

I2

I3

I4

I5

I6

I7

I8

I930%

24%

20%

7%

7%

6%

3%

2%

1%10

00

01

1100

1101

1110

11110

111110

11111100

01

10

11000

11001

11010

11011

11100

11101西個馬pili2.612.78

(3)8個。

(4)兩種指令格式如下圖所示：2位3位3位OPR1R2操作碼寄存器1寄存器25位3位3位5位OPR1Xd操作碼寄存器1變址寄存器相對位移主存邏輯地址(5)訪存操作數地址尋址的最大相對位移量為32個字節。

13.設計RISC機器的一般原則及可采用的基本技術有那些?

答：

一般原則：

(1)確定指令系統時，只選擇使用頻度很高的指令及少量有效支持操作系統，高級語言及其它功能的指令；

(2)減少尋址方式種類，一般不超過兩種；

(3)讓所有指令在一個機器周期內完成；

(4)擴大通用寄存器個數，一般不少于32個，盡量減少訪存次數；

(5)大多數指令用硬聯實現，少數用微程序實現；

(6)優化編譯程序，簡單有效地支持高級語言實現。

基本技術：

(1)按RISC一般原則設計，即確定指令系統時，選最常用基本指令，附以少數對操作系統等支持最有用的指令，使指令精簡。編碼規整，尋址方式種類減少到1、2種。

(2)邏輯實現用硬聯和微程序相結合。即大多數簡單指令用硬聯方式實現，功能復雜的指令用微程序實現。

(3)用重疊寄存器窗口。即：為了減少訪存，減化尋址方式和指令格式，簡單有效地支持高級語言中的過程調用，在RISC機器中設有大量寄存囂，井讓各過程的寄存器窗口部分重疊。

(4)用流水和延遲轉移實現指令，即可讓本條指令執行與下條指令預取在時間上重疊。另外，將轉移指令與其前面的一條指令對換位置，讓成功轉移總是在緊跟的指令執行之后發生，使預取指令不作廢，節省一個機器周期。

(5)優化設計編譯系統。即盡力優化寄存器分配，減少訪存次數。不僅要利用常規手段優化編譯，還可調整指令執行順序，以盡量減少機器周期等。

14.簡要比較CISC機器和RISC機器各自的結構特點，它們分別存在哪些不足和問題?為什么說今后的發展應是CISC和RISC的結合?

答：CISC結構特點：機器指令系統龐大復雜。

RISC結構特點：機器指令系統簡單，規模小，復雜度低。

CISC的問題：

(1)指令系統龐大，一般200條以上；

(2)指令操作繁雜，執行速度很低；

(3)難以優化生成高效機器語言程序，編譯也太長，太復雜；

(4)由于指令系統龐大，指令的使用頻度不高，降低系統性能價格比，增加設計人員負擔。

RISC的問題；

(1)由于指令少，在原CISC上一條指令完成的功能現在需多條RISC指令才能完成，加重匯編語言程序設計負擔，增加了機器語言程序長度，加大指令信息流量。

(2)對浮點運算和虛擬存儲支持不很強。

(3)RISC編譯程序比CISC難寫。

由于RISC和CISC各有優缺點,在設計時，應向著兩者結合，取長補短方向發展。第三章總線、中斷與輸入輸出系統

中斷嵌套的原則：在處理某級中斷請求時，只能比它的中斷處理級別高的中斷請求才能中斷其處理，等呼應和處理完后再繼續處理原先的那個中斷請求。

為了領會中斷響應排隊器對中斷響應優先次序是用硬件固定的，以及通過由操作系統給各中斷級服務程序現行程序狀態字中的中斷級屏蔽位設置不同的狀態，可以改變中斷處理(完)的次序這兩個要點，下圖給出了一個中斷響應硬件部分的簡單邏輯原理示意圖。圖中略去了某些實現上的具體細節，因為這些已不是本課程要討論的內容。

中斷級屏蔽位是程序狀態字中的一個組成部分。程序狀態字是將散布于系統各部分，反映程序工作時某些關鍵性硬件的狀態，組合在一起所構成的字，有的計算機也稱其為處理器狀態字或程序換道區。每類程序均在主存中指定一個區域來放置其程序狀態字。運行一個程序或進程時，就會將其程序狀態字從主存指定單元或區域取出送到分散于系統各部分的寄存器或計數器中，建立起運行此程序或進程的環境。一個程序或進程在退出運行時，也會將反映該程序狀態的這些寄存器或計數器內容組拼成程序狀態字，存回該程序或進程在主存中的指定單元或區域里。因此，程序或進程的切換，只需要通過硬件啟動的交換新舊程序狀態字的內容即可快速完成。例如，在IBM370系列機上，程序狀態字為64位，等于它的長字，交換程序狀態字只需硬件啟動寫長字和讀長字兩次訪存即可完成。盡管中斷請求是隨機發出的，為了便于精確保存中斷的斷點以及在中斷處理完后又能返回到原中斷處，中斷響應排隊器總是在每條指令執行到最后一個機器周期的最后一個時鐘周期時，對目前到達中斷響應排隊器入口的所有中斷請求排一次隊，擇優進行響應。在中斷響應排隊器相應的輸出端產生出響應信號。此信號經中斷級服務程序入口地址形成硬件，生成出該級中斷服務程序的程序狀態字在內存區中所存放的地址。同時，經中斷響應控制信號啟動，進行新舊程序狀態字的交換，完成程序的切換。被中斷的程序的斷點地址(即程序計數器的內容)，由硬件自動壓入返回地址堆棧，予以保存。系統切換到新的程序或進程后，繼續運行下去。如果新的程序或進程是一個中斷服務程序，在運行結束，執行到中斷返回指令時，就會從堆棧中彈出所保存的返回地址，再次交換程序狀態字，系統又重新返回到原被中斷的程序，恢復運行。

1.如何設置中斷級屏蔽位寄存器中的中斷屏蔽碼？

設中斷級屏蔽位“1”對應于開放，“0”對應于屏蔽。

第i級中斷處理程序級別的各級中斷級屏蔽位中應有i-1位設為“1”。舉例來說，第1級中斷處理程序級別的各級中斷級屏蔽位均應設為“0”。

響應級別為n的中斷處理程序的n級中斷級屏蔽位應設為“0”。

設第i2級中斷處理程序級別的中斷處理級別高于第i1級中斷處理程序級別，根據中斷嵌套的原則，第i1級中斷處理程序級別的第i2級中斷級屏蔽位應設為“1”,從而實現對第i2級中斷處理程序級別的開放。

2.對3.3.1中中斷級屏蔽位舉例1的解釋

*1，2，3，4中斷同時出現，進行排隊器；

*按中斷響應優先級，1最高，響應；

*1的屏蔽字為0000，所以1中斷執行到結束，回用戶程序；

*剩下的2優先級高，2響應，但其屏蔽字為1011，允許響應1、3、4，3的響應優先級高，所以；

*2被中斷，3響應，但其屏蔽字為1001，允許響應1、4，所以；

*4響應，執行到結束，回3；

*3執行到結束，回2；

*2執行到結束，回用戶程序。

3.怎樣題目中沒有說明的通道屬于哪一類型？

有的題目中沒有說明談及的通道的類型，這種情況下，一般是指字節多路通道。1.簡要舉出集中式串行鏈接，定時查詢和獨立請求3種總線控制方式的優缺點。同時分析硬件產生故障時通訊的可靠性。

答：控制方式優點缺點串行鏈接(1)選擇算法簡單。

(2)控制線數少，只需要3根，且不取決于部件數量。

(3)可擴充性好。(1)對“總線可用”線及其有關電路失效敏感。

(2)靈活性差，如果高優先級的部件頻繁要求使用總線，離總線控制器遠的部件就難以獲得總線使用權。

(3)“總線可用”信號順序脈動地通過各個部件，總線的分配速度慢。

(4)受總線長度的限制，增減和移動部件受限制。定時查詢(1)靈活性強，部件的優先次序由程序控制。

(2)可靠性高，不會因某個部件失效而影響其它部件使用總線。(1)總線的分配速度不能很高。

(2)控制較為復雜。

(3)控制線數多，需要2+log2N根。

(4)可擴充性差。獨立請求(1)靈活性強，部件的優先次序由程序控制。

(2)能方便地隔離失效部件的請求。

(3)總線的分配速度快。(1)控制較為復雜。

(2)控制線數多，要控制N個設備，需要有2N+1根控制線。

2.設中斷級屏蔽位“1”對應于開放，“0”對應于屏蔽，各級中斷處理程序的中斷級屏蔽位設置如下：中斷處理程序級別中斷級屏蔽位1級2級3級4級第1級0000第2級1010第3級1000第4級1010

(1)當中斷響應優先次序為1→2→3→4時，其中斷處理次序是什么?

(2)如果所有的中斷處理都各需3個單位時間，中斷響應和中斷返回時間相對中斷處理時間少得多。當機器正在運行用戶程序時，同時發生第2，3級中斷請求，過兩個單位時間，又同時發生第1，4級中斷請求，試畫出程序運行過程示意圖。

答：

(1)當中斷響應優先次序為1→2→3→4時，其中斷處理次序為1→3→4→2。

(2)

3.若機器共有5級中斷,中斷響應優先次序為1→2→3→4→5,現要求其實際的中斷處理次求序1→4→5→2→3。

(1)設計各級中斷處理程序的中斷級屏蔽位(令“1”對應于開放，“0”對應于屏蔽);

(2)若在運行用戶程序時，同時出現第4，2級中斷請求，而在處理第2級中斷未完成時，又同時出現第1，3，5級中斷請求，請畫出此程序運行過程示意圖。

答：

(1)中斷級屏蔽位設置如下圖：中斷處理程序級別中斷級屏蔽位1級2級3級4級5級第1級11111第2級01100第3級00100第4級01111第5級01101

(2)中斷過程示意圖：如圖

2、4中斷同時出現，進行排隊器。

首先響應第2級中斷請求，屏蔽字為01100，表明其對第4級中斷請求開放，所以轉去響應第4級中斷請求并進行處理。

響應4，中斷4運行結束，回2。

1、3、5進入排隊器。

第2級中斷請求的處理請求被中斷，轉去響應第1級中斷請求并進行處理。

響應第5級中斷請求并進行處理。

繼續響應并處理第2級中斷處理請求，結束后返回用戶程序。

最后處理第3級中斷請求。

4.簡述字節多路，數組多路和選擇通道的數據傳送方式。

答:

字節多路通道適用于連接大量的像光電機等字符類低速設備。這些設備傳送一個字符(字節)的時間很短，但字符(字節)間的等待時間很長。通道“數據寬度”為單字節，以字節交叉方式輪流為多臺設備服務，使效率提高。字節多路通道可有多個子通道，同時執行多個通道程序。

數組多路通道適合于連接多臺象磁盤等高速設備。這些設備的傳送速率很高，但傳送開始前的尋址輔助操作時間很長。通道“數據寬度”為定長塊，多臺設備以成組交叉方式工作，以充分利用并盡可能重疊各臺高速設備的輔助操作時間。傳送完K個字節數據，就重新選擇下個設備。數組多路通道可有多個子通道，同時執行多個通道程序。

選擇通道適合于連接象磁盤等優先級高的高速設備，讓它獨占通道，只能執行一道通道程序。通道“數據寬度”為可變長塊，一次將N個字節全部傳送完，在數據傳送期只選擇一次設備。

5.如果通道在數據傳送期中，選擇設備需9.8μs，傳送一個字節數據需0.2μs。某低速設備每隔500μs發出一個字節數據傳送請求，問至多可接幾臺這種低速設備?對于如下A～F6種高速設備，一次通訊傳送的字節數不少于1024個字節，問哪些設備可以掛在此通道上?哪些則不能?其中A—F設備每發出一個字節數據傳送請求的時間間隔分別為(單位為μs)：

表3-5設備ABCDEF發申請間隔(μs)0.20.250.50.190.40.21

答:

(1)至多可連接50臺低速的外設。

剖析：

根據題意可知：低速設備應掛接在字節多路通道上，字節多路通道的通道極限流量為：

fmax.byte=1/(TS+TD)>=fbyte

通道極限流量應大于或等于設備對通道要求的流量fbyte。

如果字節多路通道上所掛設備臺數為m,設備的速率為fi，為了不丟失信息，應滿足：

1/(TS+TD)>=m*fi

fi也就是設備發出字節傳送請求間隔時間(500μs)的倒數，所以：

m<=1/((TS+TD)*f)=500/(9.8+0.2)=50(臺)

(2)設備B,C,E,F可以掛在此通道上，設備A,D則不能。

剖析：

思路一：從傳送字節速率上入手。

A~F是高速設備，應掛接在選擇通道上，選擇通道的極限流量為：

fmax.select=N/(TS+N*TD)=1/((TS/N)+TD)=1/((9.8/1024)+0.2)=1/0.21(約)

通道上所掛設備的最大速率fi.max應小于或等于通道的極限流量。

由表3-5可得出設備ABCDEF傳送速率(B/μs)1/0.21/0.251/0.51/0.191/0.41/0.21

所以，B、C、E、F可掛在該通道上。A、D不能。

思路二：從傳送字節時間上入手。

對于高速設備，由于一次傳送字節數不少于1024byte

∴該通道一次傳送數據的時間為9.8μs+1024×0.2μs＝214.6μs

由表3-5可得出每臺設備發送1024字節的時間間隔分別為:設備ABCDEF傳送時間(μs)204.8256512194.56409.6215.04

∴為使數據不丟失，B、C、E、F可掛在該通道上。A、D不能。

6.某字節多路通道連接6臺外設，某數據傳送速率分別如表中所列。設備123456傳送速率(KB/s)5015100254020

(1)計算所有設備都工作時的通道實際最大流量：

(2)如果設計的通道工作周期使通道極限流量恰好與通道最大流量相等，以滿足流量設計的基本要求，同時讓速率越高的設備被響應的優先級越高。當6臺設備同時發出請求開始，畫出此通道在數據傳送期內響應和處理各外設請求的時間示意圖。由此你發現了什么問題?

(3)在(2)的基礎上，在哪臺設備內設置多少個字節的緩沖器就可以避免設備信息丟失?那么，這是否說書中關于流量設計的基本要求是沒有必要的了呢?為什么?

解：

(1)實際最大流量＝50+15+l00+25+40+20＝250KB/S。

(2)通道響應和處理各設備請求的時間示意圖

由此發現由于高速設備的響應優先級高，使低速設備2造成數據丟失。

(3)在2中各設兩個字節的緩沖區即可。這并不說明流量設計的基本條件是不必要的，因為若基本條件不滿足，無論設備優先級如何確定總有設備的信息會丟失。

剖析：

(2)由各設備的傳送字節速率可解其連續發出傳送請求的時間間隔分別為：設備123456發申請間隔(μs)2067(約)10402550

7.通道型I/O系統由一個字節多路通道A(其中包括兩個子通道Al和A2)，兩個數組多路通道B1和B2及一個選擇通道C構成，各通道所接設備和設備的數據傳送速率如表所示。

(1)分別求出各通道應具有多大設計流量才不會丟失信息；

(2)設I/O系統流量占主存流量的1/2時才算流量平衡，則主存流量應達到多少?通道號所接設備的數據傳送速率(KB/s)字節多路通道子通道A15035202050352020子通道A25035202050352020數組多路通道B1500400350250數組多路通道B2500400350250選擇通道C500400350250

解：

(1)要不丟失信息，各通道需要達到的流量：字節多路通道子通道A1:0.25KB/S;字節多路通道子通道A2:0.25KB/S;數組多路通道B1:500KB/s;數組多路通道B2:500KB/s;選擇通道C:500KB/s。

(2)主存流量應達到4MB/S。

剖析:

(1)設備要求字節多路通道或其子通道的實際最大流量，是該通道所接各設備的字節傳送速率之和;

設備要求數組多路通道或選擇通道的實際最大流量，是該通道所接各設備的字節傳送速率中的最大者。

(2)I/O系統中，各種通道和子通道可以并行工作，因此，I/O系統的最大流量應等于各通道最大流量之和。第四章存儲體系

解決Cache的透明性所帶來的問題，和中央處理機寫Cache，使主存內容跟不上Cache內對應內容的變化造成的不一致的問題的關鍵是選擇好更新主存內容的算法，一般有兩種寫直達法(存直達法)和寫回法(即抵觸修改法)兩種。

寫直達法，又稱存直達法，是指在CPU對Cache進行寫操作時，如果命中Cache，不僅將數據寫入Cache，而且寫入主存，使兩者的對應內容統一起來，這樣，當Cache中的塊被替換時，就不必再花時間寫回主存了。

寫回法，又稱抵觸修改法，是指在CPU對Cache進行寫操作時，如果命中Cache，就只將數據寫入Cache，而暫時不寫入主存，只有當變化了的Cache塊被替換時，才花一個主存周期，將其寫回主存相應的位置上，使兩者的對應內容統一起來。

Cache采用按需取進算法和預取進算法來提高Cache的命中率。

按需取進算法是指在Cache塊失效時才將要訪問的字所在的塊取進Cache。預取進算法是指在用到某Cache塊之前就將該塊預取進Cache。

預取進算法包括恒預取進算法和不命中時預取進算法。

恒預取進算法是指訪問主存第i塊時，不論其是否在Cache中命中，恒將主存第i+1塊預取進Cache。不命中時預取進算法是指訪問到主存第i塊的信息時，只有當其不在Cache中時，才將主存第i+1塊預取進Cache。

1.按位編址和按字編址？

現在從內存中讀數據都是按字節為單位。

P86第二段第一行：“目前不少機器的指令地址碼已達24-32位，相當于每個用戶的程序空間已達16MB-8192MB”。這里有一層隱含的意思，就是地址碼一般是按字節編碼。

2.相等比較電路的個數=組內塊數？

我不知道是不是可以這么理解，遇到過一道題，其中存在這種關系，不知道是不是巧合？

一個采用位選擇組相聯映象方式的Cache，要求Cache的每一塊在主存周期內取得。主存采用4個存儲體的低位交叉方式訪問，每個存儲體的字長為4個字節，總容量為256MB，Cache的容量為512KB,每一組內有4塊。采用按地址訪問存儲器構成相聯目錄表，實現主存地址到Cache地址的變換，采用4個相等比較電路。

(1)設計主存地址格式，并標出各字段的長度。(5分)

(2)設計Cache的地址格式，并標出各字段的長度。(5分)

(3)設計相聯目錄表結構，并求出該表的行數及每一行的格式。(5分)

(4)畫出實現位選擇組相聯地址變換的邏輯示意圖。(5分)

3.采用多級狀態位技術、比較對法實現LRU算法時需要比較對觸發器的個數

設組內有b塊，每組g群，每群p對，每對l行。

每組g群，組中選群需C2(g)個比較對觸發器。

每群p對，群中選對需gC2(p)個比較對觸發器。

每對l行，對中選行需gpC2(l)個比較對觸發器。

共需C2(g)+gC2(p)+gpC2(l)個比較對觸發器。1.在一個頁式虛擬存儲器中，虛地址空間為4G字節，頁大小為1K字節，頁表項的大小為4字節。試問：

(1)共需要多少個頁表項？

(2)每個頁面可存放多少個頁表項？

(3)需要幾級頁表構成表層次？

解答：

(1)2^22個或4M個

(2)1024/4=256個

(3)3級

第四章存儲體系

1.設二級虛擬存儲器的TA1=10-7s、TA2=10-2s,為使存儲層次的訪問效率e達到最大值的80%以上，命中率H至少要求達到多少？實際上這樣高的命中率是很難達到的，那么從存儲層次上如何改進？

解：

e=TA1/TA=TA1/(H*TA1+(1-H)*TA2)≥80%，H≥(10^5-5/4)/(10^5-1)。

這樣的命中率很難達到。為了降低對H的要求，可以選擇高命中率的算法，可以減少相鄰兩級的訪問速度差和容量差(這樣做不利于降低存儲器的平均每位價格)，可在主、輔存儲器間加一層電子磁盤，使存儲體系中相鄰兩級的訪問時間比不太大。

2、程序存放在模32單字交叉存儲器中，設訪存申請隊的轉移概率λ為25%,求每個存儲周期能訪問到的平均字數。當模數為16呢？由此你可得到什么結論？解：B=[1-(1-λ)^m]/λ

解：

由λ=0.25,m=32求得：B=4-4*(3/4)^32

同理，m=16時,B=4-4*(3/4)^16

可得出，在λ=0.25時，m=32的平均訪問字數大于m=16時的平均訪問字數。

3、設主存每個分體的存取周期為2μs，寬度為4個字節。采用模m多分體交叉存取，但實際頻寬只能達到最大頻寬的0.6倍。現要求主存實際頻寬為4MB/S,問主存模數m應取多少方能使兩者速度基本適配？其中m取2的冪。

解：

m=4

剖析：

根據題意，模m多分體交叉的最大頻寬為：分體數*單體頻寬=m*分體的寬度/分體的存取周期=m*4B/2μs，所以有0.6*m*4/2>=4。

4.某虛擬存儲器共8個頁面，每頁1024個字，實際主存為4096個字，采用頁表法進行地址映象。映象表的內容如下表所示。虛頁號01234567實頁號31232100裝入位11001010注：我把虛頁號加上了。

(1)列出會發生頁面失效的全部虛頁號；

(2)按以下虛地址計算主存實地址：0，3728，1023，1024，2055，7800，4096，6800。

解:

(1)會發生頁面失效的全部虛頁號為：2,3,5,7。

(2)虛地址虛頁號頁內位移裝入位實頁號頁內位移實地址0001303072327836560頁面失效頁面失效無102301023131023409510241011010242055270頁面失效頁面失效無780076320頁面失效頁面失效無40964012020486800665610656656剖析：(1)根據頁表法列出表2，當裝入位為0時，即為頁面失效，再找出相對應的虛頁號即可。

(2)虛頁號=虛地址/頁面大小

頁內位移量=虛地址－虛頁號*頁面大小

實地址＝實頁號*頁面大小＋頁內位移量

由于可以用替換算法解決頁面失效的問題，所以，發生頁面失效的虛頁2,3,5,7仍然可以有相應的實地址，但這樣要在頁表中建立新的虛實地址對應關系，新的虛實地址對應關系和原來的對應關系相同的可能性就很小了。

5、一個段頁式虛擬存儲器。虛地址有2位段號、2位頁號、11位頁內位移（按字編址），主存容量為32K字。每段可有訪問方式保護，其頁表和保護位如下表所示。段號0123訪問方式只讀可讀/執行可讀/寫/執行可讀/寫虛頁0所在位置實頁9在輔存上頁表不在主存內實頁14虛頁1所在位置實頁3實頁0頁表不在主存內實頁1虛頁2所在位置在輔存上實頁15頁表不在主存內實頁6虛頁3所在位置實頁12實頁8頁表不在主存內在輔存上

(1)此地址空間中共有多少個虛頁？

(2)當程序中遇到下列情況時方式段頁頁內位移取數

取數

取數

存數

存數

存數

轉移至此

取數

取數

轉移至此0

1

3

0

2

1

1

0

2

31

1

3

1

1

0

3

2

0

01

10

2047

4

2

14

100

50

5

60寫出由虛地址計算出實地址。說明哪個會發生段失效、頁面或保護失效失效。

解答:1)該地址空間中共有16個虛頁。

(2)程序中遇到上表中各情況時，是否會發生段失效、頁失效或保護失效及相應的主存實地址的情況如下表所示：方式段頁頁內位移段失效頁失效實頁號實地址保護失效取數

取數

取數

存數

存數

存數

轉移至此

取數

取數

轉移至此0

1

3

0

2

1

1

0

2

31

1

3

1

1

0

3

2

0

01

10

2047

4

2

14

100

50

5

60無

無

無

無

有

無

無

無

有

無無

無

有

無

/

有

無

有

/

無3

0

無

3

無

無

8

無

無

146145

10

無

6184

無

無

16484

無

無

28732無

無

/

有

/

/

無

/

/

有

剖析：

(1)虛地址中段號有2位，頁號有2位，也就是每個程序最多只能有2^2=4個段，每個段至多只能有2^2=4頁，所以該地址空間中共有4*4=16個虛頁。

(2)先從題意得知：

實地址：15位，其中實頁號4位，頁內位移11位

頁大小為2K字（由頁內位移得知）

6.設某程序包含5個虛頁，其頁地址為4，5，3，2，5，1，3，2，2，5，1，3。當使用LRU算法替換時，為獲得最高命中率，至少應分配給該程序幾個實頁？其可能的最高命中率為多少？

7.采用頁式管理的虛擬存儲器，分時運行兩道程序。其中，程序X為DO50I=1,3B(I)=A(I)-C(I)IF(B(I)·LE·0)GOTO40D(I)=2*C(I)-A(I)IF(D(I)·EQ·0)GOTO5040E(I)=050CONTINUEData:A=(-4,+2,0)C=(-3,0,+1)每個數組分別放在不同的頁面中;而程序Y在運行過程中，其數組將依次用到程序空間的第3,5,4,2,5,3,1,3,2,5,1,3,1,5,2頁。如果采用LRU算法，實存卻只有8頁位置可供存放數組之用。試問為這兩首程序的數組分別分配多少個實頁最為合適？為什么？

解答：

分別分配給程序X和Y的數組4個實頁最為合適。

根據題意，程序X依次調用數組A,C,B,B,E,A,C,B,B,C,A,D,D,E,A,C,B,B,E中的數據。

設程序X中的數組A,B,C,D,E分別存放于程序空間的第1,2,3,4,5頁，則程序的頁地址流為：1，3，2，2，5，1，3，2，2，3，1，4，4，5，1，3，2，2，5。

分析使用LRU算法對程序X的頁地址流進行堆棧處理的過程可知，分配給程序X的數組5個實頁最為合適;分析使用LRU算法對程序Y的頁地址流進行堆棧處理的過程可知，分配給程序Y的數組4個實頁最為合適。

但實存只有8頁位置可供存放數組之用，所以，分別分配給程序X和Y的數組4個實頁。

note:

分時運行在微觀上是串行的，就是說，分時運行時把時間劃分為若干時間片，每個程序輪流占用時間片;在宏觀上是并行的，就是說，每個程序在一個時間片內并不能運行完。總的來看，是同時運行的，所以兩個程序分配的實頁和不能大于8。

我不了解FORTRAN，找朋友把上面的源代碼轉成C了：main(){intA[]={-4,2,0};intC[]={-3,0,1};for(i=0,i<>0)E[i]=0;};};}8.設一個按位編址的虛擬存儲器，它應可對應1K個任務，但在一段較長時間內，一般只有4個任務在使用，故用容量為4行的相聯寄存器組硬件來縮短被變換的虛地址中的用戶位位數；每個任務的程序空間最大可達4096頁，每頁為512個字節，實主存容量為2＾20位；設快表用按地址訪問存儲器構成，行數為32，快表的地址是經散列形成；為減少散列沖突，配有兩套獨立相等比較電路。請設計該地址變換機構，內容包括：

(1)畫出其虛、實地址經快表變換之邏輯結構示意圖；

(2)相聯寄存器組中每個寄存器的相聯比較位數；

(3)相聯寄存器組中每個寄存器的總位數；

(4)散列變換硬件的輸入位數和輸出位數；

(5)每個相等比較器的位數；

(6)快表的總容量（以位為單位）。

解:

(1)依題意得知：

虛地址為34位，其中用戶號為10位（對應1K的任務）、虛頁號12位（每個任務4096頁）、頁內位移12位（每頁512字節，512字節=512*8=1024*4=2^12）

實地址為20位，其中實頁號8位，頁內位移12位（與虛頁頁內位移對應）

相聯寄存器的作用：把10位的用戶號轉換為2位的ID（因為一般只有4個任務在使用），并把ID與虛地址的虛頁號合并到快表中查實頁號。

快表的作用：相當于頁表，即虛頁號對實頁號的對應關系。但又有所簡化（原因是如果用用戶號和虛頁號與實頁號對應，前者就有22位，現改進后虛頁號只有14位了）

(2)相聯寄存器組中每個寄存器的相聯比較位數為10（與虛地址中的用戶號寬度對應）

(3)相聯寄存器組中每個寄存器的總數為12（用戶號寬度+ID寬度）

(4)散列變換硬件的輸入位數為14位（虛頁號寬度+相聯寄存器中ID的寬度），輸出位數為8位（與主存中的實頁號寬度對應）

(5)每個相等比較器的位數=ID+用戶虛頁號nv'=2+12=14(位)。

(6)快表的總容量：32行*（14(輸入位數)+8（輸出位數））*2=32*22*2

9.考慮一個920個字的程序，其訪問虛存的地址流為20，22，208，214，146，618，370，490，492，868，916，728。

(1)若頁面大小為200字，主存容量為400字，采用FIFO替換算法，請按訪存的各個時刻，寫出其虛頁地址流，計算主存的命中率；

(2)若頁面大小為100字，再做一遍；

(3)若頁面大小為400字，再做一遍；

(4)由(1)、(2)、(3)的結果可得出什么結論？

(5)若把主存容量增加到800字，按第(1)小題再做一遍，又可得出什么結論？

解：

(1)主存容量400字，頁面大小200字，所以主存實頁數為2；

把地址流轉換為頁地址流，以第一個虛地址流轉換為頁地址流為例說明：求模公式為：INT（地址/頁面大小），就是把地址整除于頁面大小，得INT（20/200）=0，下同，所以頁地址流為：0,0,1,1,0,3,1,2,2,4,4,3

按FIFO算法得出替換過程為：0（調入），0（命中），1（調入），1（命中），0（命中），3（替換0，0比1先入隊，所以被替換，下同），1（命中），2（替換1），2（命中），4（替換3），4（命中），3（替換2），所以總共命中6次。

故命中率H=6/12=50%

(2)方法同（1）H=25%

(3)H=50%

(4)由以上結論可得，FIFO算法的條件下，當頁面大小發生變化時，其命中率變化是：一開始隨頁面大小增大命中率（第一步與第二步比較），但當頁面大小增到一定時，命中率不再增加（第一步與第三步比較）。

(5)命中率為58%，結論是如果分配給主存容量增加時可以搞高命中率。

10.在一個頁式二級虛擬存儲器中，采用FIFO算法進行頁面替換，發現命中率H太低，因此有下列建議：

(1)增大輔存容量;

(2)增大主存容量(頁數);

(3)FIFO改為LRU;

(4)FIFO改為LRU，并增大主存容量(頁數);

(5)FIFO改為LRU，并增大頁面大小。

試分析上述各建議對命中率的影響情況。

解答：

(1)增大輔存容量，對命中率H無影響。

(2)增大主存容量(頁數)，可普遍提高命中率。

(3)FIFO改為LRU，一般可提高命中率。

(4)FIFO改為LRU，并增大主存容量(頁數)，一般可使命中率有較大提高。

(5)FIFO改為LRU，并增大頁面大小，如果原來頁面很小，則會使命中率顯著上升，如果原來頁面很大，則會使命中率下降。

11.采用組相聯映象的Cache存儲器，Cache為1KB，要求Cache的每一塊在一個主存周期內能從主存取得。主存模4交叉，每個分體寬為32位，總容量為256KB。用按地址訪問存儲器構成相聯目錄表實現主存地址到Cache地址的變換，并約定用4個外相等比較電路。請設計此相聯目錄表，求出該表之行數、總位數及每個比較電路的位數。

解答：

設Cache地址中的組內塊號為s，相聯目錄表的行數是2^(13-s)，總位數是(8+2s)*2^(15-s)，每個比較電路的位數為8+s。

剖析：

在一個主存周期內主存能訪問到的字節數為mW=4*32/8=16(Byte)。要求Cache的每一塊在一個主存周期內能從主存取得，所以，Cache中每塊的塊內字數不能大于16Bytes。為了加速調塊，一般讓每塊的大小等于在一個主存周期內主存能訪問到的字數，即16Bytes。

設Cache地址中的組內塊號為s，相聯目錄表的行數=Cache地址內的組數Q=Cache容量/(每組塊數*每塊大小)=1KB/(S*4*32)=2^13/(2^s*2^7)=2^(6-s)。

主存塊數/Cache塊數=256=2*8，所以，主存地址中的區號nd=8。每個比較電路的位數=nd+s'=nd+s=8+s。

相聯目錄表的總位數=表中子目錄表的個數*每個子目錄表的位數*相聯目錄表的行數=4*(nd+s'+s)*Q=4*(8+2s)*2^(6-s)=(8+2s)*2^(8-s)。

note：

若認為相等比較電路的個數=組內塊數，則相聯目錄表的行數=2^4，每個比較電路的位數=10，相聯目錄表的總位數=12*2^6。

12.有一個Cache存儲器。主存共分8個塊(0~7),Cache為4個塊(0~3),采用組相聯映象，組內塊數為2塊，替換算法為近期最少使用算法(LRU)。

(1)畫出主存、Cache地址的各字段對應關系(標出位數)圖;

(2)畫出主存、Cache空間塊的映象對應關系示意圖;(3)對于如下主存塊地址流：1,2,4,1,3,7,0,1,2,5,4,6,4,7,2,如主存中內容一開始未裝入Cache中，請列出Cache中各塊隨時間的使用狀況;

(4)對于(3),指出塊失效又發生塊爭用的時刻;

(5)對于(3),求出此期間Cache的命中率。

解答：

(1)主存地址、Cache地址的各字段的位數及其對應關系如下圖所示

(2)主存塊、Cache塊的映象對應關系如下圖所示

(3)Cache中各塊隨時間的使用狀況如下圖所示。圖中標*號的是候選替換塊的塊號，H：命中;R：替換;L：失效。

(4)發生塊失效又發生塊爭用的時刻有6、7、9、10、11、12、14、15。

(5)Cache的塊命中率Hc=3/15=0.2。

剖析：

由于主存塊、Cache塊之間存在上述的映象對應關系，主存的第0、1、4、5塊只能映象裝入或替換物理Cache的第0、1塊;主存的第2、3、6、7塊只能映象裝入或替換物理Cache的第2、3塊。

13.采用組相聯映象，LRU替換算法的Cache存儲器，發現等效訪問速度不高，為此建議：

(1)增大主存容量;

(2)增大Cache的塊數(塊的大小不變);

(3)增大組相聯組的大小(塊的大小不變);

(4)增大塊的大小(組的大小和Cache總容量不變);

(5)提高Cache本身器件的訪問速度。

解答：

(1)增大主存容量對Cache的訪問時間ta基本不影響，從而對Cache的等效訪問速度基本不影響。

(2)增大Cache的塊數(塊的大小不變)一般將使Cache的命中率Hc上升，從而使ta下降，從而提高Cache的等效訪問速度。

(3)增大組相聯組的大小(塊的大小不變)一般將使Cache的命中率Hc上升，從而使ta下降，從而提高Cache的等效訪問速度。

(4)增大塊的大小(組的大小和Cache總容量不變)一般將使ta下降，從而提高Cache的等效訪問速度。

(5)提高Cache本身器件的訪問速度一般將縮短ta，從而提高Cache的等效訪問速度。

14.你對Cache存儲器的速度不滿，于是申請到一批有限的經費，為能發揮其最大經濟效益，有人建議你再買一些同樣速度的Cache片子以擴充其容量;而另有人建議你干脆去買更高速的Cache片子將現有的低速Cache片子全部換掉。你認為哪種建議可取？你如何做決定？為什么？

解答：

Cache本身的速度與容量都會影響Cache存儲器的等效訪問速度。如果對Cache存儲器的等效訪問速度不滿，需要改進的話，就要作具體分析，看看現在Cache存儲器的等效訪問速度是否已接近于Cache本身的速度。如果差得較遠，說明Cache的命中率低，應從提高Cache命中率著手，包括調整組的大小、塊的大小、替換算法以及增大Cache容量等。如果Cache存儲器的等效訪問速度已經非常接近于Cache本身的速度還不能滿足需要，就應該更換更高速的Cache片子。

第五章重疊、流水和向量處理機

因機器語言程序中鄰近指令之間出現了關聯，為防止出錯不讓它們同時被解釋的現象，稱為相關。數據相關是指相鄰指令的數據地址之間有關聯。指令相關是因為指令在程序的執行過程中允許被修改造成的。

多功能靜態流水線，在同一時間段內該流水線的各功能段之間只能按一種功能進行聯接，只有等流水線全部流空后，才能切換成按另一種功能進行聯接。

多功能動態流水線，在同一時間段內該流水線的各功能段之間可以按多種不同的功能進行聯接。

中斷和轉移一樣，會引起流水線斷流。由于發生中斷的概率遠低于條件轉移，且中斷又是隨機發生的，所以，流水機器處理中斷的關鍵在于如何處理好斷點現場的保存和恢復，而不是如何縮短流水線的斷流時間。

設在執行指令i時有中斷，斷點本應是在指令i執行結束，指令i+1尚未開始執行的地方，但由于流水機器是同時解釋多條指令，后續指令i+1,i+2,...可能已進入流水線并被解釋。對于采用異步流動方式的流水線，這些后續指令中的一些可能已經流到指令i前面去了。

早期的流水機器多采用不精確斷點法。不論指令i在流水線的哪一段發生中斷，未進入流水線的后續指令不再進入，已在流水線的指令繼續流完，再轉入中斷處理程序。這樣斷點就不一定是指令i，而可能是指令i+1,i+2,...即斷點是不精確的。僅當指令i在流水線的第一段呼應中斷時，斷點才是精確的。采用不精確斷點法，硬件開銷少，控制簡單，不利于編程和程序的排錯。

后來的流水機器多采用精確斷點法。不論指令i在流水線的哪一段發生中斷，中斷處理程序的現場都是對應于指令i的。如果在執行第i條指令時發生了程序性錯誤或故障，那么斷點就是i。最壞的情況是指令i執行到流水線的最后一個功能段時才發生程序性錯誤或故障，為此，需設置很多后援寄存器，以保證流