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