【正文】 節(jié) (3)恒置“ 1”法 方法 :在規(guī)定字長(zhǎng)之最低位恒置成“ 1”狀態(tài) 最大誤差：整數(shù)二進(jìn)制為 1，分?jǐn)?shù)為 2m 正負(fù)：有正有負(fù)。 分布：統(tǒng)計(jì)平均誤差接近零，稍偏正，無(wú)法調(diào)節(jié) (4)查表舍入法 方法 :基于存貯邏輯思想，用 ROM或 PLA存放下溢 處理表。當(dāng) k1位全位“ 1”時(shí)，以截?cái)喾ㄌ幚?；其? 以舍入法處理。 最大誤差： 最大為 1 正負(fù)：有正有負(fù) 分布：不均勻，平均誤差為零，可調(diào)節(jié) 2.【 解答 】 (1)極限流量 a)字節(jié)多路通道 :每選一臺(tái)設(shè)備傳送一個(gè)字節(jié) =1/(TS+TD) b)數(shù)組多路通道 :每選一條設(shè)備傳送 K個(gè)字節(jié) =k/(TS+kTD)=1/(TS/k+TD) c)選擇通道 :每選一臺(tái)設(shè)備就把 N個(gè)字節(jié)傳送完 =N/(TS+NTD)=1/(TS/N+TD) (2)實(shí)際最大流量 a)字節(jié)多路通道 : =Σ b)數(shù)組多路通道： =max c)選擇通道： =max (3)滿(mǎn)足式子 = = = i=1 pj i=1 pj i=1 pj 3.【 解答 】 (1)增大輔存容量，對(duì)主存命中率 H不會(huì) 有什么影響。因?yàn)檩o存容量增大，并不是程序空間 的增大，程序空間與實(shí)存空間的容量差并未改變。 所以，增大物理輔存容量，不會(huì)對(duì)主存的命中率 H 有什么影響。 (2)如果主存容量 (頁(yè)數(shù) )增加較多時(shí)，將使主存命 中率有明顯提高的趨勢(shì)。但如果主存容量增加比較 少，命中率 H可能會(huì)略有增大，也可能不變，甚至 還可能會(huì)有少許下降。 這是因?yàn)槠淝疤崾敲新?H太低。如果主存容量 顯著增加，要訪(fǎng)問(wèn)的程序頁(yè)面在主存中的機(jī)會(huì)大大 增加，命中率會(huì)顯著上升。但如果主存容量 (頁(yè)數(shù) ) 增加較少，加上使用的 FIFO算法不是堆棧型替換算 法，所以對(duì)命中率的提高可能不明顯，甚至還可能 有所下降。 (3)因?yàn)榍疤崾侵鞔娴拿新?H很低，在增大主、 輔存的頁(yè)面大小時(shí)，如果增加量較小，主存命中率 可能沒(méi)有太大的波動(dòng)。因?yàn)?FIFO是非堆棧型的替換 算法，主存命中率可能會(huì)有所增加，也可能降低和 不變。而當(dāng)頁(yè)面大小增加量較大時(shí)，可能會(huì)出現(xiàn)兩 種相反的情況。當(dāng)原頁(yè)面大小較小時(shí)，在顯著增大 了頁(yè)面大小之后，一般會(huì)使主存命中率 H有較大提 高。但當(dāng)原頁(yè)面大小已較大時(shí)，再顯著增大頁(yè)面大 小后，由于在主存中的頁(yè)面數(shù)過(guò)少，將會(huì)使主存命 中率繼續(xù)有所下降。 (4)頁(yè)面替換算法由 FIFO改為 LRU后，一般會(huì)使 主存的命中率提高。因?yàn)?LRU替換算法比 FIFO替換 算法能更好地體現(xiàn)出程序工作的局部性特點(diǎn)。然而 主存命中率還與頁(yè)地址流、分配給主存的實(shí)頁(yè)數(shù)多 少等有關(guān)，所以，主存命中率也可能仍然較低，沒(méi) 有明顯改進(jìn)。 (5)頁(yè)面替換算法由 FIFO改為 LRU，同時(shí)增大主 存的容量 (頁(yè)數(shù) )，一般會(huì)使主存命中率有較大的提 高。因?yàn)?LRU替換算法比 FIFO替換算法能更好地體 現(xiàn)出程序工作的局部性，又由于原先主存的命中率 太低，現(xiàn)在增大主存容量，一般會(huì)使主存命中率上 升。如果主存容量增加量大些，主存命中率 H將會(huì) 顯著上升。 (6)FIFO改為 LRU，且增大頁(yè)面大小時(shí)，如果原 先頁(yè)面大小很小，則會(huì)使命中率顯著上升；如果原 先頁(yè)面大小已很大了，因?yàn)橹鞔骓?yè)數(shù)進(jìn)一步減少而 使命中率還會(huì)繼續(xù)有所下降。 三 .計(jì)算題 1.【 解答 】 (1)4位 (2)Huffman樹(shù)如下圖： 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 (3)、 (4)結(jié)果如下： Huffman編碼平均碼長(zhǎng)＝ ∑ pili＝ 擴(kuò)展編碼平均碼長(zhǎng)＝ ∑ pili＝ 使用頻度 Huffman編碼 (不唯一 ) 擴(kuò)展編碼 (不唯一 ) 00 00 0 00 00 1 00 01 01 0 01 1 00 1 10 0 10 1 11 0 11 1 00 00 00 01 00 10 00 11 01 0 01 1 10 0 10 1 11 0 11 1 2.【 解答 】 (1)直接映象 (2)主存地址到 Cache地址變換過(guò)程的示意圖如下圖所示： 主存塊號(hào) 塊內(nèi)地址 主存地址 nm nmb 4位 nmr ncb 4位 ncr Cache地址 nc … 相聯(lián)比較 不等 塊失效 區(qū)號(hào) 4位 … 0 1 15 ? ? 相等 訪(fǎng) Cache (按地址訪(fǎng)問(wèn)存貯器 ) 輔助映象表存貯器用按地址訪(fǎng)問(wèn)的存貯器構(gòu)成， 共 16個(gè)單元，每個(gè)單元 4位寬。 變換過(guò)程：主存地址中截取對(duì)應(yīng) Cache地址部分 的字段來(lái)訪(fǎng) Cache，同時(shí)用區(qū)內(nèi) (Cache)塊號(hào)訪(fǎng)問(wèn)輔 助映象表存貯器，將其內(nèi)容讀出，與主存區(qū)號(hào)字段 進(jìn)行比較。若比較相等，讓訪(fǎng) Cache操作繼續(xù)進(jìn)行 下去，表示 Cache命中；否則，表示訪(fǎng) Cache失效， 由主存中調(diào)塊。 模擬試題二 一 .簡(jiǎn)答題 (40分 ) 、組成與實(shí)現(xiàn)。 ？簡(jiǎn)要解釋并各舉一系統(tǒng)類(lèi)型的例子。 RISC機(jī)器的基本技術(shù)是什么？ Huffman樹(shù)的過(guò)程。 3種類(lèi)型？各適合連接什么類(lèi)型的設(shè)備？滿(mǎn)負(fù)荷時(shí)，設(shè)備對(duì)通道要求的實(shí)際流量與所連的設(shè)備有什么關(guān)系？ 。 Cache時(shí)，會(huì)發(fā)生 Cache與主存的對(duì)應(yīng)副本內(nèi)容不一致的現(xiàn)象，解決這個(gè)問(wèn)題有哪些方法？各需要增加什么開(kāi)銷(xiāo)？ 2種方法？各自的思路是什么？ 二 .問(wèn)答題 (30分 ) “程序的動(dòng)態(tài)再定位”？ ？目的是什么？具體分為哪幾類(lèi)？各自是如何定義的？ 、 LRU替換算法的 Cache存貯器，發(fā)現(xiàn)等效訪(fǎng)問(wèn)速度不高，為此提議： (1)增大主存容量； (2)增大 Cache中的塊數(shù) (塊的大小不變 )； (3)增大組相聯(lián)組的大小 (塊的大小不變 )。 (4)增大塊的大小 (組的大小和 Cache總?cè)萘坎蛔?)。 (5)提高 Cache本身器件的訪(fǎng)問(wèn)速度。 試問(wèn)分別采用上述措施后，對(duì)等效訪(fǎng)問(wèn)速度可能 會(huì)有什么樣的顯著變化？其變化趨勢(shì)如何？如果采 取措施后并未能使等效訪(fǎng)問(wèn)速度有明顯提高的話(huà)， 又是什么原因？ 三 .計(jì)算題 (30分 ) 5級(jí)中斷，中斷響應(yīng)次序?yàn)?1 2 3 4 5，現(xiàn)要求中斷處理次序?yàn)?2 3 1 5 4。 (1)設(shè)計(jì)各級(jí)中斷處理程序的中斷級(jí)屏蔽位的狀態(tài)，令“ 0”表示開(kāi)放，“ 1”表示屏蔽。 (2)若在運(yùn)行用戶(hù)程序時(shí)，同時(shí)發(fā)生第 3級(jí)中斷請(qǐng)求，而在第 1級(jí)中斷未完成時(shí)，又發(fā)生 5級(jí)中斷，請(qǐng)畫(huà)出處理機(jī)執(zhí)行程序的全過(guò)程示意圖(標(biāo)出交換 PSW的時(shí)間 )。 5個(gè)頁(yè)面，其頁(yè)地址流依次為 4， 5， 3， 2， 5， 1， 3， 2， 5， 1， 3用 LRU替換算法。 (1)用堆棧對(duì)該頁(yè)地址流模擬一次，畫(huà)出這一模擬過(guò)程，并標(biāo)出實(shí)頁(yè)數(shù)為 3， 4， 5時(shí)的命中情況。 (2)為獲得最高的命中率，應(yīng)分配給該程序幾個(gè)實(shí)頁(yè)即可？其可能的最高命中率是多少？ 模擬試題二參考答案 一 .簡(jiǎn)答題 1.【 解答 】 (1)系統(tǒng)結(jié)構(gòu)：是對(duì)計(jì)算機(jī)系統(tǒng)中各機(jī)器 之間界面的劃分和定義，以及對(duì)各級(jí)界面上、下的 功能進(jìn)行分配。 (2)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)： 是系統(tǒng)結(jié)構(gòu)中的一部分，指 層次結(jié)構(gòu)中傳統(tǒng)機(jī)器級(jí)的系統(tǒng)結(jié)構(gòu)，其界面之上的 功能包括操作系統(tǒng)級(jí)、匯編語(yǔ)言級(jí)、高級(jí)語(yǔ)言級(jí)和 應(yīng)用語(yǔ)言級(jí)中所有軟件的功能；界面之下的功能包 括所有硬件和固件的功能。因此，這個(gè)界面實(shí)際是 軟件與硬件或固件的分界面。 (3)計(jì)算機(jī)組成：是計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的邏輯實(shí)現(xiàn) ， 包括機(jī)器級(jí)內(nèi)的數(shù)據(jù)流和控制流的組成以及邏輯實(shí) 現(xiàn) 。 (4)計(jì)算機(jī)實(shí)現(xiàn)：指的是計(jì)算機(jī)組成的物理實(shí)現(xiàn) 。 2.【 解答 】 (1)時(shí)間重疊：在并行性中引入時(shí)間因 素 ， 讓多個(gè)處理過(guò)程在時(shí)間上錯(cuò)開(kāi) ， 輪流重復(fù)的使 用同一套硬件設(shè)備的各個(gè)部分 ， 以加快硬件周轉(zhuǎn)而 提高速度 。 例如 ， 流水線(xiàn)處理機(jī) 。 (2)資源重復(fù)：引入空間因素 ， 通過(guò)重復(fù)設(shè)置硬件 資源來(lái)提高可靠性或性能 。 例如 ， 雙工系統(tǒng) 。 (3)資源共享：利用軟件的辦法讓多個(gè)用戶(hù)按一定 時(shí)間順序輪流使用同一套資源 ， 以提高其利用率 ， 這樣可以提高整個(gè)系統(tǒng)的性能 。 例如 ， 多道程序分 時(shí)系統(tǒng) ， 多處理機(jī) ， 分布處理系統(tǒng) ， 計(jì)算機(jī)網(wǎng)絡(luò) 。 3.【 解答 】 (1)遵循 RISC機(jī)器一般原則設(shè)計(jì)的技術(shù) 。 (2)在邏輯上采用硬聯(lián)實(shí)現(xiàn)和微程序固件實(shí)現(xiàn)相結(jié) 合的技術(shù)。 (3)在 CPU中設(shè)置數(shù)量較大的寄存器組，并采用重 疊寄存器窗口的技術(shù)。 (4)指令的執(zhí)行采用流水和延遲轉(zhuǎn)移技術(shù)。 (5)采用認(rèn)真設(shè)計(jì)和優(yōu)化編譯系統(tǒng)設(shè)計(jì)的技術(shù)。 4.【 解答 】 (1)將指令的使用頻度由小到大排序 (2)每次選最小兩個(gè)頻度結(jié)合一個(gè)新節(jié)點(diǎn) (3)再按頻度大小插入余下未結(jié)合的頻度值中 (4)如此重復(fù)直至全部結(jié)合完畢成根節(jié)點(diǎn)“ 1” (5)沿兩個(gè)分支，分別用“ 0”或“ 1”來(lái)表示 這樣，從根節(jié)點(diǎn)開(kāi)始，沿線(xiàn)到達(dá)個(gè)頻度指令的 代碼序列就是該指令的哈夫曼編碼。 5.【 解答 】 通道分為字節(jié)多路通道、數(shù)組多路通道 以及選擇通道 3種。 (1)字節(jié)多路通道適合連接大量低速的字符設(shè)備。 滿(mǎn)負(fù)荷時(shí)，設(shè)備對(duì)通道要求的實(shí)際流量應(yīng)是所連各 設(shè)備的流量之和。 (2)數(shù)組多路通道適合于連接高速的設(shè)備。滿(mǎn)負(fù)荷 時(shí)，設(shè)備對(duì)通道要求的實(shí)際流量應(yīng)是所連各個(gè)設(shè)備 中，流量最大的那個(gè)。 (3)選擇通道適合于連接中、高速的高優(yōu)先級(jí)的設(shè) 備。滿(mǎn)負(fù)荷時(shí)，設(shè)備對(duì)通道要求的實(shí)際流量應(yīng)是所 連各個(gè)設(shè)備中，流量最大的那個(gè)。 6.【 解答 】 (1)總線(xiàn)分配前計(jì)數(shù)器清“ 0”,從“ 0”開(kāi)始查 詢(xún)，優(yōu)先級(jí)排序類(lèi)似串行鏈接。 (2)總線(xiàn)分配前不清“ 0”，從中止點(diǎn)繼續(xù)查詢(xún)，是 循環(huán)優(yōu)先級(jí)，部件使用總線(xiàn)機(jī)會(huì)均等。 (3)總線(xiàn)分配前將計(jì)數(shù)器設(shè)置初值，可以指定某個(gè) 部件為最高優(yōu)先級(jí)。 (4)總線(xiàn)分配前將部件號(hào)重新設(shè)置，可以為各部件 指定任意希望的優(yōu)先級(jí)。 7.【 解答 】 (1) 寫(xiě)回法：在 CPU執(zhí)行寫(xiě)操作時(shí)，只是 把信息寫(xiě)入 Cache，僅當(dāng)需要被替換時(shí)，才將已經(jīng) 被寫(xiě)入過(guò)的 Cache塊先送回主存，然后再調(diào)入新塊 進(jìn)行替換。這種方法要求對(duì)每個(gè) Cache塊增加一個(gè) 修改位的資源開(kāi)銷(xiāo)。 (2)寫(xiě)直達(dá)法：也稱(chēng)為存直達(dá)法，它利用 Cache— —主存存貯層次在處理機(jī)和主存之間的直接通路， 每當(dāng)處理機(jī)寫(xiě)入 Cache的同時(shí)，也通過(guò)此通路直接 寫(xiě)入主存。這種方法要增加寫(xiě)主存的時(shí)間開(kāi)銷(xiāo)。 8.【 解答 】 (1)堆棧法：棧頂恒存放近期最久訪(fǎng)問(wèn)過(guò) 的頁(yè)的頁(yè)號(hào)，而棧底恒存放近期最久沒(méi)有訪(fǎng)問(wèn)過(guò)的 頁(yè)的頁(yè)號(hào)，即準(zhǔn)備被替換掉的頁(yè)的頁(yè)號(hào)。按此思想 組成一個(gè)硬件堆棧。 (2)比較對(duì)法：讓各個(gè)塊成對(duì)組合，用一個(gè)觸發(fā)器 的狀態(tài)來(lái)表示該比較對(duì)內(nèi)兩塊訪(fǎng)問(wèn)的遠(yuǎn)近次序，再 經(jīng)門(mén)電路就可以找到 LRU塊。 二 .問(wèn)答題 1.【 解答 】 程序在實(shí)際主存空間中的位置可以動(dòng)態(tài) 移動(dòng)的定位技術(shù)。一種做法是，在硬件上設(shè)置基址 寄存器和地址加法器，即在程序裝入主存時(shí)，只把 程序裝在主存中的起始地址 (基址 )裝入基址寄存器 中，對(duì)指令各地址字段不作修改；在程序運(yùn)行時(shí)， 由邏輯地址根據(jù)需要，加上基址寄存器中的基址來(lái) 形成訪(fǎng)存有效地址。另一種做法是，設(shè)置邏輯地址 到主存物理有效地址的映象表硬件，即程序裝入主 存時(shí)，在映象表中建立起邏輯地址與主存物理地址 的映象關(guān)系；程序執(zhí)行時(shí)，由邏輯地址查映象表來(lái) 獲得訪(fǎng)主存的物理有效地址。這樣，只需修改基址 寄存器中的基址或地址映象表的內(nèi)容，就可以使程 序在主存中動(dòng)態(tài)改變所存貯的位置。 2.【 解答 】 (1)中斷分類(lèi)的依據(jù)是：把中斷源性質(zhì)相 近、中斷處理過(guò)程類(lèi)似的歸為一類(lèi)。 (2)中斷分類(lèi)的目的是：為了減少中斷處理程序的 入口，每一類(lèi)給一個(gè)中斷服務(wù)程序總?cè)?