【正文】 時間優(yōu)先 SSTF168。掃描算法 SCAN（磁盤電梯調(diào)度算法）n 循環(huán)掃描算法 CSCANn NStepSCAN算法n FSCAN算法2/8/2023 76① FCFSn 多個進程的磁盤 I/O請求構成一個隨機分布的請求隊列。n 磁盤 I/O執(zhí)行順序按磁盤請求的先后順序。設開始位置為 532/8/2023 77② 最短尋道時間優(yōu)先 SSTFn 選擇從當前磁頭位置出發(fā)移動最少的磁盤 I/O請求168。 使每次磁頭移動時間最少。168。 不一定是最短平均柱面定位時間，但比 FIFO算法有更好的性能。168。 對中間的磁道有利，但可能會有進程處于饑餓狀態(tài)（ I/O請求總不被執(zhí)行）。2/8/2023 78FCFS SSTF訪問的下一磁道號移動距離（磁道數(shù)）55 4558 339 1918 2190 72160 70150 1038 112184 146平均尋道長度 訪問的下一磁道號移動距離（磁道數(shù)）90 1058 3255 339 1638 118 20150 132160 10184 24平均尋道長度 設當前在 100磁道上；進程要求的訪問順序： 55， 58， 39， 18， 90， 160， 150， 38， 1842/8/2023 79③ 掃描算法 SCAN（磁盤電梯調(diào)度算法）nSSTF會導致 “饑餓 ”現(xiàn)象168?？傔x擇最近的磁道訪問，遠磁道請求的進程會長時間得不到執(zhí)行。n改進：168?？紤]距離的同時，更優(yōu)先考慮方向uSCAN算法168。規(guī)定磁頭移動方向：自里向外，再自外向里移動。168。后續(xù)的 I/O磁道請求，哪個在規(guī)定方向上距離最近，就先執(zhí)行哪個。168。如當前為 100，后續(xù)要求 55， 86， 95， 180， 165， 105n先由內(nèi)向外：選最近的 105執(zhí)行，再判斷剩余的，選165， 180。n再由外向內(nèi)： 95， 86， 55對對 55號磁道請求的進程相對號磁道請求的進程相對 “饑餓饑餓 ”很久很久2/8/2023 80u 循環(huán)掃描 CSCANn SCAN的錯過問題：168。 容易錯過與當前磁道距離近，但方向不一致的磁道。n 修改：將 SCAN規(guī)定的移動方向改為 “單向移動 ”168。 由里向外后，再由里向外。n NStepSCANn 前述算法共同問題：168。 “磁臂粘著 ”—— 磁頭靜止在一個磁道上，導致其它進程無法及時進行磁盤 I/O。（高密度盤，某一進程的讀寫可能集中在某一磁道）n 改進：168。 將磁盤請求隊列分成長為 N 的子隊列168。 按 FCFS選擇子隊列。隊列內(nèi)又按 SCAN算法。168。 處理子隊列過程中產(chǎn)生的新 I/O請求放入其他隊列。168。 N=1時，就是 FCFS， N很大時就是 SCAN。2/8/2023 81uFSCANn NStepSCAN的簡化：168。請求隊列只分為兩個子隊列168。當前一個隊列，按 SCAN算法執(zhí)行；168。掃描期間新生成的組成一個隊列，等待被掃描。2/8/2023 823）磁盤高速緩存）磁盤高速緩存n 內(nèi)存中劃出，對外存磁盤讀寫進行緩存的內(nèi)存中劃出，對外存磁盤讀寫進行緩存的區(qū)域。區(qū)域。4）其他提速方法）其他提速方法n 提前讀提前讀n 延遲寫延遲寫n 優(yōu)化物理塊分布優(yōu)化物理塊分布n 虛擬盤虛擬盤n 磁盤冗余陣列（高速、大容量磁盤系統(tǒng)）磁盤冗余陣列（高速、大容量磁盤系統(tǒng)）自學自學2/8/2023 83要點1. 虛擬設備是指：通過虛擬技術將一臺獨占設備改造成若干臺邏輯設備，供若干個用戶進程同時使用。2. 按信息交換單位分類，可將設備分為：塊設備和字符設備。3. 通道是：負責 I/O的處理機。4. 字節(jié)多路通道主要用作：連接大量的低速 I/O設備。2/8/2023 845. 從資源分配的角度看，操作系統(tǒng)將外部設備分為：獨占型設備、共享型設備、虛擬設備。6. 根據(jù)信息交換方式的不同，可以將通道分為：字節(jié)多路通道、數(shù)據(jù)選擇通道、數(shù)據(jù)多路通道。7. 設備獨占性是指：應用程序獨立于具體使用的物理設備。8. 緩沖技術中的緩沖池在：主存中。2/8/2023 859. 進行設備分配時所需要的數(shù)據(jù)表格主要有：設備控制表、設備控制器控制表、通道控制表和系統(tǒng)設備表。10. 如果有多個中斷同時發(fā)生，系統(tǒng)將根據(jù)中斷優(yōu)先級響應優(yōu)先級最高的中斷請求。若要調(diào)整中斷事件的響應次序，可以利用：中斷屏蔽。11. 在操作系統(tǒng)中，一種用空間換取時間的資源轉(zhuǎn)換技術是：Spooling。12. 大多數(shù)低速設備都屬于：獨享設備。2/8/2023 8613. 為了實現(xiàn) CPU與外設的并行工作，系統(tǒng)引入了：中斷和通道硬件機制。14. 在操作系統(tǒng)中，用戶在使用 I/O設備時，通常采用：邏輯設備名。15. Spooling系統(tǒng)是由：磁盤中的輸入井和輸出井、內(nèi)存中的輸入緩沖區(qū)和輸出緩沖區(qū)以及輸入進程和輸出進程組成。16. 引起中斷發(fā)生的事件稱為：中斷源。2/8/2023 8717. 設備與內(nèi)存之間的傳輸方式有：程序直接控制方式、中斷控制方式、通道控制方式和DMA控制方式，其中通道方式占用 CPU時間最短。18. 設備分配中的安全性是指：設備分配應保證不會引起進程死鎖。19. Spooling技術是指：在共享設備上模擬獨占設備。由預輸入程序?qū)⒆鳂I(yè)執(zhí)行中需訪問的數(shù)據(jù)預先讀入到輸入井中，緩輸出程序則負責將輸出井中的信息在輸出設備上輸出。20. 發(fā)生中斷時，剛執(zhí)行完的那條指令所在的單元號稱為： 斷點，斷點的邏輯后繼指令的單元號稱為：恢復點。2/8/2023 88練習1. 如何將獨占型輸入設備改造成可共享使用的虛擬設備？2. 為什么要設置內(nèi)存 I/O緩沖區(qū)？通常有哪幾類緩沖區(qū)？3. 什么是設備驅(qū)動程序？其功能是什么？4. 在設備管理中，何為設備獨立性？如何實現(xiàn)設備獨立性？5. 試給出常用的 I/O調(diào)度算法。6. 為什么要引入 Spooling系統(tǒng)？ Spooling系統(tǒng)可帶來哪些好處？7. DMA控制方式與通道控制方式有什么不同？8. 設備分配時為什么要考慮安全性和設備的無關性？2/8/2023 89訪問磁盤過程n 對磁盤的訪問總是由缺頁引起的：168。 CPU給出地址，需要訪問某存儲單元；168。 并行進行 TLB查找和 cache查找；168。 TLB查找后申明沒有找到；168。 停止并行查找，并通知操作系統(tǒng)處理；168。 操作系統(tǒng)檢查頁表，發(fā)現(xiàn)該頁不在內(nèi)存中，需要從硬盤調(diào)入。應該如何進行呢？2/8/2023 90l 操作系統(tǒng)從主存中選擇一頁準備換出，為調(diào)入的頁安排存放空間；l 若被換出的頁是 “臟 ”頁，需要將其寫回磁盤存儲；l 操作系統(tǒng)申請 I/O總線；l 獲得批準后，發(fā)送寫命令給 I/O 設備（磁盤）。 緊跟著傳送需要寫回的頁的全部數(shù)據(jù)。l I/O控制器發(fā)現(xiàn)發(fā)給自己的寫命令 ，加入到握手協(xié)議，并接受數(shù)據(jù)。l 根據(jù)數(shù)據(jù)要寫入的地址，讀 /寫頭移動到正確的柱面，同時，將數(shù)據(jù)接收到緩沖區(qū)。l 尋道結束后，等待相應的扇區(qū)旋轉(zhuǎn)到磁頭下面，將數(shù)據(jù)寫入扇區(qū)中。 l 在寫入數(shù)據(jù)間隙，計算校驗碼并寫入扇區(qū)中。訪問磁盤過程（續(xù)）訪問磁盤過程（續(xù)）2/8/2023 91訪問磁盤過程（續(xù)）n 下一步，操作系統(tǒng)繼續(xù)申請總線（如果還保持總線控制權，則不必申請）。n 得到授權后，向磁盤發(fā)出讀命令。 n 然后，磁盤識別地址，并轉(zhuǎn)換為相應的地址段。 n 尋道，將讀 /寫頭移動到指定位置。n 從指定扇區(qū)中讀去數(shù)據(jù)，并進行校驗。n 磁盤申請 I/O總線。n 得到授權后，將數(shù)據(jù)通過總線送到內(nèi)存。2/8/2023 92演講完畢，謝謝觀看！