【文章內(nèi)容簡(jiǎn)介】 K12K15K（2）最佳適應(yīng)算法請(qǐng)求隊(duì)列最佳適應(yīng)算法初始10K4K20K18K7K9K12K15K12K10K4K20K18K7K9K015K10K04K20K18K7K9K015K9K04K20K18K7K0015K（3）最壞適應(yīng)算法請(qǐng)求隊(duì)列最壞適應(yīng)算法初始10K4K20K18K7K9K12K15K12K10K4K8K18K7K9K12K15K10K10K4K8K8K7K9K12K15K9K10K4K8K8K7K9K12K6K可見(jiàn)，分配算法不同，選擇的分配對(duì)象也不一樣。2．系統(tǒng)內(nèi)存被劃分成8塊，每塊4KB。某作業(yè)的虛擬地址空間共劃分成16個(gè)頁(yè)面。當(dāng)前在內(nèi)存的頁(yè)與內(nèi)存塊的對(duì)應(yīng)關(guān)系如下表所示，未列出的頁(yè)表示不在內(nèi)存。頁(yè) 號(hào)塊 號(hào)頁(yè) 號(hào)塊 號(hào)02441153269530117試指出對(duì)應(yīng)于下列虛擬地址的絕對(duì)地址：（a）20 （b）4100 （c）8300解：（a）虛擬地址20對(duì)應(yīng)的頁(yè)號(hào)是0，頁(yè)內(nèi)位移是20。用0去查頁(yè)表，知道第0頁(yè)現(xiàn)在存放在內(nèi)存的第2塊。由于每塊的長(zhǎng)度是4KB，所以第2塊的起始地址為8192。因此，虛擬地址20所對(duì)應(yīng)的絕對(duì)地址是： 8192+20=8212（b）虛擬地址4100對(duì)應(yīng)的頁(yè)號(hào)是： 4100/4096=1（“/”是整除運(yùn)算符）對(duì)應(yīng)的頁(yè)內(nèi)位移是： 4100%4096=4（“%”是求余運(yùn)算符）用1去查頁(yè)表，知道第1頁(yè)現(xiàn)在存放在內(nèi)存的第1塊。第1塊的起始地址為4096。因此，虛擬地址4100所對(duì)應(yīng)的絕對(duì)地址是： 4096+4=4100（c）虛擬地址8300對(duì)應(yīng)的頁(yè)號(hào)是： 8300/4096=2（“/”是整除運(yùn)算符）對(duì)應(yīng)的頁(yè)內(nèi)位移是： 8300%4096=108（“%”是求余運(yùn)算符）用2去查頁(yè)表，知道第2頁(yè)現(xiàn)在存放在內(nèi)存的第6塊。第6塊的起始地址為 64K=24576因此，虛擬地址8300所對(duì)應(yīng)的絕對(duì)地址是 24576+108=246843．某請(qǐng)求分頁(yè)式存儲(chǔ)管理系統(tǒng)，接收一個(gè)共7頁(yè)的作業(yè)。作業(yè)運(yùn)行時(shí)的頁(yè)面走向如下： 1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6若采用最近最久未用（LRU）頁(yè)面淘汰算法，作業(yè)在得到2塊和4塊內(nèi)存空間時(shí)，各會(huì)產(chǎn)生出多少次缺頁(yè)中斷？如果采用先進(jìn)先出（FIFO）頁(yè)面淘汰算法時(shí)，結(jié)果又如何？解：（1）采用最近最久未用（LRU）頁(yè)面淘汰算法，作業(yè)在得到2塊內(nèi)存空間時(shí)所產(chǎn)生的缺頁(yè)中斷次數(shù)為18次，如圖33（a）所示；在得到4塊內(nèi)存空間時(shí)所產(chǎn)生的缺頁(yè)中斷次數(shù)為10次，如圖33（b）所示。圖33 LRU時(shí)的情形（2）采用先進(jìn)先出（FIFO）頁(yè)面淘汰算法，作業(yè)在得到2塊內(nèi)存空間時(shí)所產(chǎn)生的缺頁(yè)中斷次數(shù)為18次，如圖34（a）所示；在得到4塊內(nèi)存空間時(shí)所產(chǎn)生的缺頁(yè)中斷次數(shù)為14次，如圖34（b）所示。圖34 FIFO時(shí)的情形關(guān)于先進(jìn)先出（FIFO）頁(yè)面淘汰算法，在給予作業(yè)更多的內(nèi)存塊時(shí)，缺頁(yè)中斷次數(shù)有可能上升，這是所謂的異常現(xiàn)象。但要注意，并不是在任何情況下都會(huì)出現(xiàn)異常。是否出現(xiàn)異常，取決于頁(yè)面的走向。本題所給的頁(yè)面走向，在FIFO頁(yè)面淘汰算法下，并沒(méi)有引起異常：2塊時(shí)缺頁(yè)中斷次數(shù)為18次，4塊時(shí)缺頁(yè)中斷次數(shù)為14次。4．在一個(gè)分段式存儲(chǔ)管理中，有段表如下：段號(hào)段長(zhǎng)基址02105001235020210090313505904193895試求邏輯地址[0，430]、[1，10]、[2，500]、[3，400]、[4，112]、[5，32]所對(duì)應(yīng)的物理地址。 解：（1）邏輯地址[0，430]的物理地址是210+430=640； （2）邏輯地址[1，10]的物理地址是2350+10=2360； （3）由于第2段的基址是100，段長(zhǎng)是90，所以邏輯地址[2，500]為非法； （4）邏輯地址[3，400]的物理地址是1350+400=1750； （5）由于第4段的基址是1938，段長(zhǎng)是95，所以邏輯地址[4，112]為非法； （6）由于該作業(yè)不存在第5段，所以邏輯地址[5，32]為非法。第4章習(xí)題解答一、填空1．磁帶、磁盤(pán)這樣的存儲(chǔ)設(shè)備都是以 塊 為單位與內(nèi)存進(jìn)行信息交換的。2．根據(jù)用戶(hù)作業(yè)發(fā)出的磁盤(pán)I/O請(qǐng)求的柱面位置，來(lái)決定請(qǐng)求執(zhí)行順序的調(diào)度，被稱(chēng)為 移臂 調(diào)度。3．DMA控制器在獲得總線控制權(quán)的情況下能直接與 內(nèi)存儲(chǔ)器 進(jìn)行數(shù)據(jù)交換，無(wú)需CPU介入。4．在DMA方式下，設(shè)備與內(nèi)存儲(chǔ)器之間進(jìn)行的是 成批 數(shù)據(jù)傳輸。5．通道程序是由 通道 執(zhí)行的。6．通道是一個(gè)獨(dú)立與CPU的、專(zhuān)門(mén)用來(lái)管理 輸入/輸出操作 的處理機(jī)。7．緩沖的實(shí)現(xiàn)有兩種方法：一種是采用專(zhuān)門(mén)硬件寄存器的硬件緩沖，一種是在內(nèi)存儲(chǔ)器里開(kāi)辟一個(gè)區(qū)域，作為專(zhuān)用的I/O緩沖區(qū)，稱(chēng)為 軟件緩沖 。8．設(shè)備管理中使用的數(shù)據(jù)結(jié)構(gòu)有系統(tǒng)設(shè)備表（SDT）和 設(shè)備控制塊（DCB） 。9．基于設(shè)備的分配特性，可以把系統(tǒng)中的設(shè)備分為獨(dú)享、共享和 虛擬 三種類(lèi)型。10．引起中斷發(fā)生的事件稱(chēng)為 中斷源 。 二、選擇1．在對(duì)磁盤(pán)進(jìn)行讀/寫(xiě)操作時(shí)，下面給出的參數(shù)中， C 是不正確的。A． 柱面號(hào) B．磁頭號(hào) C．盤(pán)面號(hào) D．扇區(qū)號(hào)2．在設(shè)備管理中，是由 B 完成真正的I/O操作的。A．輸入/輸出管理程序 B．設(shè)備驅(qū)動(dòng)程序C．中斷處理程序 D．設(shè)備啟動(dòng)程序3．在下列磁盤(pán)調(diào)度算法中，只有 D 考慮I/O請(qǐng)求到達(dá)的先后次序。A．最短查找時(shí)間優(yōu)先調(diào)度算法 B．電梯調(diào)度算法C．單向掃描調(diào)度算法 D．先來(lái)先服務(wù)調(diào)度算法4．下面所列的內(nèi)容里， C 不是DMA方式傳輸數(shù)據(jù)的特點(diǎn)。A．直接與內(nèi)存交換數(shù)據(jù) B．成批交換數(shù)據(jù)C．與CPU并行工作 D．快速傳輸數(shù)據(jù)5．在CPU啟動(dòng)通道后，由 A 執(zhí)行通道程序，完成CPU所交給的I/O任務(wù)。A． 通道 B．CPU C．設(shè)備 D．設(shè)備控制器6．利用SPOOL技術(shù)實(shí)現(xiàn)虛擬設(shè)備的目的是 A 。A．把獨(dú)享的設(shè)備變?yōu)榭梢怨蚕? B．便于獨(dú)享設(shè)備的分配C．便于對(duì)獨(dú)享設(shè)備的管理 D．便于獨(dú)享設(shè)備與CPU并行工作7．通常，緩沖池位于 C 中。A．設(shè)備控制器 B．輔助存儲(chǔ)器 C．主存儲(chǔ)器 D．寄存器8． B 是直接存取的存儲(chǔ)設(shè)備。A．磁帶 B．磁盤(pán) C．打印機(jī) D．鍵盤(pán)顯示終端9．SPOOLING系統(tǒng)提高了 A 的利用率。A．獨(dú)享設(shè)備 B．輔助存儲(chǔ)器 C．共享設(shè)備 D．主存儲(chǔ)器10．按照設(shè)備的 D 分類(lèi)，可將系統(tǒng)中的設(shè)備分為字符設(shè)備和塊設(shè)備兩種。A．從屬關(guān)系 B．分配特性 C．操作方式 D．工作特性三、問(wèn)答1．基于設(shè)備的從屬關(guān)系，可以把設(shè)備分為系統(tǒng)設(shè)備與用戶(hù)設(shè)備兩類(lèi)。根據(jù)什么來(lái)區(qū)分一個(gè)設(shè)備是系統(tǒng)設(shè)備還是用戶(hù)設(shè)備呢？答：所謂“系統(tǒng)設(shè)備”，是指在操作系統(tǒng)生成時(shí)就已被納入系統(tǒng)管理范圍的設(shè)備；所謂“用戶(hù)設(shè)備”是指在完成應(yīng)用任務(wù)過(guò)程中，用戶(hù)特殊需要的設(shè)備。因此，判定一個(gè)設(shè)備是系統(tǒng)設(shè)備還是用戶(hù)設(shè)備，依據(jù)是它在系統(tǒng)生成時(shí)，是否已經(jīng)納入了系統(tǒng)的管理范圍。如果是，它就是系統(tǒng)設(shè)備；如果不是，它就是用戶(hù)設(shè)備。2．設(shè)備管理的主要功能是什么？答：設(shè)備管理的主要功能是：（1）提供一組I/O命令，以便用戶(hù)進(jìn)程能夠在程序中提出I/O請(qǐng)求，這是用戶(hù)使用外部設(shè)備的“界面”；（2）記住各種設(shè)備的使用情況，實(shí)現(xiàn)設(shè)備的分配與回收；（3）對(duì)緩沖區(qū)進(jìn)行管理，解決設(shè)備與設(shè)備之間、設(shè)備與CPU之間的速度匹配問(wèn)題；（4）按照用戶(hù)的具體請(qǐng)求，啟動(dòng)設(shè)備，通過(guò)不同的設(shè)備驅(qū)動(dòng)程序，進(jìn)行實(shí)際的I/O操作；I/O操作完成之后，將結(jié)果通知用戶(hù)進(jìn)程，從而實(shí)現(xiàn)真正的I/O操作。3．試分析最短查找時(shí)間優(yōu)先調(diào)度算法的“不公平”之處。例如例41里，原來(lái)磁臂移到16柱面后，下一個(gè)被處理的I/O請(qǐng)求是柱面1。假定在處理16柱面時(shí)，到達(dá)一個(gè)對(duì)柱面8的I/O新請(qǐng)求，那么下一個(gè)被處理的就不是柱面1而是柱面8了。這有什么弊端存在？答：最短查找時(shí)間優(yōu)先調(diào)度算法，只考慮各I/O請(qǐng)求之間的柱面距離，不去過(guò)問(wèn)這些請(qǐng)求到達(dá)的先后次序。這樣一來(lái)，可能會(huì)出現(xiàn)的弊端是磁頭總是關(guān)照鄰近的I/O請(qǐng)求，冷待了早就到達(dá)的、位于磁盤(pán)兩頭的I/O請(qǐng)求。這對(duì)于它們來(lái)說(shuō)，當(dāng)然是“不公平”的。4．總結(jié)設(shè)備和CPU在數(shù)據(jù)傳輸?shù)?種方式中，各自在“啟動(dòng)、數(shù)據(jù)傳輸、I/O管理以及善后處理”各個(gè)環(huán)節(jié)所承擔(dān)的責(zé)任。答：使用“程序循環(huán)測(cè)試”的方式來(lái)進(jìn)行數(shù)據(jù)傳輸，不僅啟動(dòng)、I/O管理和善后處理等工作要由CPU來(lái)承擔(dān)，即使在數(shù)據(jù)傳輸時(shí)，CPU也要做諸如從控制器的數(shù)據(jù)寄存器里取出設(shè)備的輸入信息，送至內(nèi)存；將輸出的信息，從內(nèi)存送至控制器的數(shù)據(jù)寄存器，以供設(shè)備輸出等工作。因此，在這種方式下，CPU不僅要花費(fèi)大量時(shí)間進(jìn)行測(cè)試和等待，并且只能與設(shè)備串行工作，整個(gè)計(jì)算機(jī)系統(tǒng)的效率發(fā)揮不出來(lái)。使用“中斷”的方式來(lái)進(jìn)行數(shù)據(jù)傳輸，啟動(dòng)、I/O管理以及善后處理等工作仍然要由CPU來(lái)承擔(dān)，但在設(shè)備進(jìn)行數(shù)據(jù)傳輸時(shí)，CPU和外部設(shè)備實(shí)行了并行工作。在這種方式下，CPU的利用率有了一定的提高。使用“直接存儲(chǔ)器存取（DMA）”的方式來(lái)進(jìn)行數(shù)據(jù)傳輸，I/O的啟動(dòng)以及善后處理是CPU的事情，數(shù)據(jù)傳輸以及I/O管理等事宜均由DMA負(fù)責(zé)實(shí)行。不過(guò)，DMA方式是通過(guò)“竊取”總線控制權(quán)的辦法來(lái)工作的。在它工作時(shí)，CPU被掛起，所以并非設(shè)備與CPU在并行工作。因此，在一定程度上影響了CPU的效率。使用“通道”方式來(lái)進(jìn)行數(shù)據(jù)傳輸，在用戶(hù)發(fā)出I/O請(qǐng)求后，CPU就把該請(qǐng)求全部交由通道去完成。通道在整個(gè)I/O任務(wù)結(jié)束后，才發(fā)出中斷信號(hào)，請(qǐng)求CPU進(jìn)行善后處理。這時(shí)CPU對(duì)I/O請(qǐng)求只去做啟動(dòng)和善后處理工作，輸入/輸出的管理以及數(shù)據(jù)傳輸?shù)仁乱耍坑赏ǖ廓?dú)立完成，并且真正實(shí)現(xiàn)了CPU與設(shè)備之間的并行操作。5．用戶(hù)程序中采用“設(shè)備類(lèi)，相對(duì)號(hào)”的方式使用設(shè)備有什么優(yōu)點(diǎn)？答：在用戶(hù)程序中采用“設(shè)備類(lèi)，相對(duì)號(hào)”的方式使用設(shè)備的優(yōu)點(diǎn)是：第一，用戶(hù)不需要記住系統(tǒng)中每一臺(tái)設(shè)備的具體設(shè)備號(hào)，這是非常麻煩的事情；第二，在多道程序設(shè)計(jì)環(huán)境下，用戶(hù)并不知道當(dāng)前哪一臺(tái)設(shè)備已經(jīng)分配，哪一臺(tái)設(shè)備仍然空閑。通過(guò)“設(shè)備類(lèi)，相對(duì)號(hào)”來(lái)提出對(duì)設(shè)備的使用請(qǐng)求，系統(tǒng)就可以根據(jù)當(dāng)前的具體情況來(lái)分配，從而提高設(shè)備的使用效率；第三，用戶(hù)并不知道設(shè)備的好壞情況。如果是用“絕對(duì)號(hào)”指定具體的設(shè)備，而該設(shè)備正好有故障時(shí)，這次I/O任務(wù)就不可能完成，程序也就無(wú)法運(yùn)行下去。但通過(guò)“設(shè)備類(lèi)，相對(duì)號(hào)”來(lái)提出對(duì)設(shè)備的使用請(qǐng)求，系統(tǒng)就可以靈活處理這種情況，把好的設(shè)備分配出去。6．啟動(dòng)磁盤(pán)執(zhí)行一次輸入/輸出操作要花費(fèi)哪幾部分時(shí)間？哪個(gè)時(shí)間對(duì)磁盤(pán)的調(diào)度最有影響？答：執(zhí)行一次磁盤(pán)的輸入/輸出操作需要花費(fèi)的時(shí)間包括三部分：（1）查找時(shí)間；（2）等待時(shí)間；（3）傳輸時(shí)間。在這些時(shí)間中，傳輸時(shí)間是設(shè)備固有的特性，無(wú)法用改變軟件的辦法將它改進(jìn)。因此，要提高磁盤(pán)的使用效率，只能在減少查找時(shí)間和等待時(shí)間上想辦法，它們都與I/O在磁盤(pán)上的分布位置有關(guān)。由于磁臂的移動(dòng)是靠控制電路驅(qū)動(dòng)步進(jìn)電機(jī)來(lái)實(shí)現(xiàn)，它的運(yùn)動(dòng)速度相對(duì)于磁盤(pán)軸的旋轉(zhuǎn)來(lái)講較緩慢。因此，查找時(shí)間對(duì)磁盤(pán)調(diào)度的影響更為主要。7．解釋通道命令字、通道程序和通道地址字。答：所謂“通道命令字”，是指通道指令系統(tǒng)中的指令。只是為了與CPU的指令相區(qū)別，才把通道的指令改稱(chēng)為“通道命令字”。若干條通道命令字匯集在一起，就構(gòu)成了一個(gè)“通道程序”，它規(guī)定了設(shè)備應(yīng)該執(zhí)行的各種操作和順序。通常，通道程序存放在通道自己的存儲(chǔ)部件里。當(dāng)通道中沒(méi)有存儲(chǔ)部件時(shí)，就存放在內(nèi)存儲(chǔ)器里。這時(shí)，為了使通道能取得通道程序去執(zhí)行，必須把存放通道程序的內(nèi)存起始地址告訴通道。存放這個(gè)起始地址的內(nèi)存固定單元，被稱(chēng)為“通道地址字”。8．何為DMA？通道與DMA有何區(qū)別？答：所謂“DMA”，是指“直接存儲(chǔ)器存取”的數(shù)據(jù)傳輸方式，其最大特點(diǎn)是能使I/O設(shè)備直接和內(nèi)存儲(chǔ)器進(jìn)行成批數(shù)據(jù)的快速傳輸。適用于一些高速的I/O設(shè)備，如磁帶、磁盤(pán)等。通道方式與DMA方式之間的區(qū)別如下。（1）在DMA方式下，數(shù)據(jù)傳輸?shù)姆较?、傳輸長(zhǎng)度和地址等仍然需要由CPU來(lái)控制。但在通道方式下，所需的CPU干預(yù)大大減少。（2）在DMA方式下，每臺(tái)設(shè)備要有一個(gè)DMA控制器。當(dāng)設(shè)備增加時(shí)，多個(gè)DMA控制器的使用，顯然不很經(jīng)濟(jì)；但在通道方式下，一個(gè)通道可以控制多臺(tái)設(shè)備，這不僅節(jié)省了費(fèi)用，而且減輕了CPU在輸入/輸出中的負(fù)擔(dān)。（3）在DMA方式下傳輸數(shù)據(jù)時(shí)，是采用“竊取”總線控制權(quán)的辦法來(lái)工作的。因此，CPU與設(shè)備之間并沒(méi)有實(shí)現(xiàn)真正的并行工作；在通道方式下，CPU把I/O任務(wù)交給通道后，它就與通道就真正并行工作。9．解釋記錄的成組與分解。為什么要這樣做？答：往磁帶、磁盤(pán)上存放信息時(shí)，經(jīng)常是把若干個(gè)記錄先在內(nèi)存緩沖區(qū)里拼裝成一塊，然后再寫(xiě)到磁帶或磁盤(pán)上。存儲(chǔ)設(shè)備與內(nèi)存儲(chǔ)器進(jìn)行信息交換時(shí)，就以塊為單位。這個(gè)把記錄拼裝成塊的過(guò)程，被稱(chēng)為是“記錄的成組”。從磁帶、磁盤(pán)上讀取記錄時(shí)，先是把含有那個(gè)記錄的塊讀到內(nèi)存的緩沖區(qū)中，在那里面挑選出所需要的記錄，然后把它送到內(nèi)存存放的目的地。這個(gè)把記錄從緩沖區(qū)里挑選出來(lái)的過(guò)程，被稱(chēng)為是“記錄的分解”。之所以這樣做，一是為了提高存儲(chǔ)設(shè)備的存儲(chǔ)利用率；二是減少內(nèi)、外存之間信息交換次數(shù)，提高系統(tǒng)的效率。10．試述SPOOL系統(tǒng)中的3個(gè)組成軟件模塊各自的作用。答：SPOOLING系