【正文】 I/O請求 ? 使每次磁頭移動時間最少。 ? 不一定是最短平均柱面定位時間，但比 FIFO算法有更好的性能。 ? 對中間的磁道有利，但可能會有進程處于饑餓狀態(tài)（ I/O請求總不被執(zhí)行）。 2/8/2023 86 FCFS SSTF 訪問的 下一磁道號 移動距離 （磁道數(shù)） 55 45 58 3 39 19 18 21 90 72 160 70 150 10 38 112 184 146 平均尋道長度 訪問的 下一磁道號 移動距離 （磁道數(shù)） 90 10 58 32 55 3 39 16 38 1 18 20 150 132 160 10 184 24 平均尋道長度 設當前在 100磁道上； 進程要求的訪問順序： 55， 58， 39， 18， 90， 160， 150， 38， 184 2/8/2023 87 ③掃描算法 SCAN（磁盤電梯調(diào)度算法） Circular SCAN ?SSTF會導致“饑餓”現(xiàn)象 ?總選擇最近的磁道訪問，遠磁道請求的進程會長時間得不到執(zhí)行。 ?改進： ?考慮距離的同時，更優(yōu)先考慮方向 ?SCAN算法 ?規(guī)定磁頭移動方向：自里向外，再自外向里移動。 ?后續(xù)的 I/O磁道請求，哪個在規(guī)定方向上距離最近，就先執(zhí)行哪個。 ?如當前為 100，后續(xù)要求 55， 86， 95， 180， 165， 105 ?先由內(nèi)向外：選最近的 105執(zhí)行，再判斷剩余的，選165， 180。 ?再由外向內(nèi)： 95， 86， 55 反方向較近的 55號磁道請求的進程相對“饑餓”很久 2/8/2023 88 ?循環(huán)掃描 CSCAN ? SCAN的錯過問題： ?容易錯過與當前磁道距離近，但方向不一致的磁道。 ? 修改：將 SCAN規(guī)定的移動方向改為“單向移動” ?由里向外后，再由里向外。 ? NStepSCAN ? 前述最近尋道算法共同問題： ?“磁臂粘著” —— 磁頭靜止在一個磁道上，導致其它進程無法及時進行磁盤 I/O。（因：高密度盤，進程的讀寫可能集中在某一磁道） ?如現(xiàn)有一系列請求： 3 3 5 2 3 3 3 2 3 3 2 3 3 4 4 5 2 3 3 3 4 4 2 3 3 3 2 2 2 3 不管哪種算法，從 3開始向下執(zhí)行會是 3 3 3 3 3 3 3 3 3 3….2 2 2 2 2 2 … 4 4 …. 2/8/2023 89 ? 改進： ?將磁盤請求隊列分成長為 N 的子隊列 ?按 FCFS選擇子隊列。隊列內(nèi)又按 SCAN算法。 3 3 5 2 |3 3 3 2| 3 3 2 3| 3 4 4 5| 2 3 ….2 3 ?處理子隊列過程中產(chǎn)生的新 I/O再依次排隊列。 ? N=1時，就是 FCFS， N很大時就是 SCAN。 ? FSCAN ? NStepSCAN的簡化： ?請求隊列只分為兩個子隊列 ?當前一個隊列，按 SCAN算法執(zhí)行； ?掃描期間新生成的組成一個隊列，等待被掃描。 2/8/2023 90 ? 假設一個活動頭磁盤有２００道，編號從０－１９９。 當前 磁頭正在１５５道上服務，并且在此 之前 完成的是１７３道的訪盤請求。 現(xiàn)有如下訪盤請求序列（磁盤號）：７５，１６８，８１，１３８，８７，１４３，１８７，１２９，１９８，４４。試給出采用下列算法后磁頭移動的順序和移動總量 (總磁道數(shù) )。 （ SSTF）磁盤調(diào)度算法。 （ SCAN）磁盤調(diào)度算法（假設沿磁頭移動方向不再有訪問請求時 , 磁頭就沿相反方向移動。 44到 0磁道的移動忽略不計 ） 答： ： １５５，１４３，１３８，１２９，１６８，１８７，１９８，８７，８１，７５，４４ 三段（１５５～１２９，１２９～１９８，１９８～４４） 移動總量 =15５ 1２９ +1９８ １２９ +1９８ ４４ =2４９ ： １５５，１４３，１３８，１２９，８７，８１，７５，４４，１６８，１８７，１９８ 兩段（ 1５５～４４，４４～１９８） 移動總量 =1５５ 4４ +1９８ ４４ =２６５ 2/8/2023 91 ? （ 8分）若干個等待訪問磁盤者依次要訪問的柱面為 20， 44， 40， 4， 80， 12， 76，假設每移動一個柱面需要 3毫秒時間，移動臂當前位于 40號柱面，請按下列算法分別計算為完成上述各次訪問總共花費的尋找時間。 （ 1）先來先服務算法 （ 2）最短尋找時間優(yōu)先算法。 Fcfs： 4020+4420+444+804+8012+7612=292 Sstf： 40,44,20,12,4,76,80 4410+444+804=150 2/8/2023 92 3）磁盤高速緩存 ? 內(nèi)存中劃出，對外存磁盤讀寫進行緩存的區(qū)域。 4）其他提速方法 ? 提前讀 ? 延遲寫 ? 優(yōu)化物理塊分布 ? 虛擬盤 ? 磁盤冗余陣列（高速、大容量磁盤系統(tǒng)） 閱讀 2/8/2023 93 練習 1. 虛擬設備是指： 通過虛擬技術將一臺獨占設備改造成若干臺邏輯設備，供若干個用戶進程同時使用。 2. 按信息交換單位分類，可將設備分為： 塊設備和字符設備。 3. 通道是： 一種負責 I/O的處理機。 4. 字節(jié)多路通道主要用作： 連接大量的低速 I/O設備。 2/8/2023 94 5. 從資源分配的角度看，操作系統(tǒng)將外部設備分為： 獨占型設備、共享型設備、虛擬設備。 6. 根據(jù)信息交換方式的不同，可以將通道分為： 字節(jié)多路通道、數(shù)據(jù)選擇通道、數(shù)據(jù)多路通道。 7. 設備獨占性是指： 應用程序獨立于具體使用的物理設備。 8. 緩沖技術中的緩沖池在： 主存中。 2/8/2023 95 9. 進行設備分配時所需要的數(shù)據(jù)表格主要有： 設備控制表、設備控制器控制表、通道控制表和系統(tǒng)設備表。 10. 如果有多個中斷同時發(fā)生，系統(tǒng)將根據(jù)中斷優(yōu)先級響應優(yōu)先級最高的中斷請求。若要調(diào)整中斷事件的響應次序，可以利用： 中斷屏蔽。 11. 在操作系統(tǒng)中，一種用空間換取時間的資源轉換技術是： Spooling。 12. 大多數(shù)低速設備都屬于： 獨享設備。 2/8/2023 96 13. 為了實現(xiàn) CPU與外設的并行工作，系統(tǒng)引入了： 中斷和通道硬件機制。 14. 在操作系統(tǒng)中，用戶在使用 I/O設備時，通常采用： 邏輯設備名。 15. Spooling系統(tǒng)是由： 磁盤中的輸入井和輸出井、內(nèi)存中的輸入緩沖區(qū)和輸出緩沖區(qū)以及輸入進程和輸出進程組成。 16. 引起中斷發(fā)生的事件稱為： 中斷源。 2/8/2023 97 17. 設備與內(nèi)存之間的傳輸方式有： 程序直接控制方式、中斷控制方式、通道控制方式和DMA控制方式，其中通道方式占用 CPU時間最短。 18. 設備分配中的安全性是指： 設備分配應保證不會引起進程死鎖。 19. Spooling技術是指： 在共享設備上模擬獨占設備。由預輸入程序將作業(yè)執(zhí)行中需訪問的數(shù)據(jù)預先讀入到輸入井中，緩輸出程序則負責將輸出井中的信息在輸出設備上輸出。 20. 發(fā)生中斷時，剛執(zhí)行完的那條指令所在的單元號稱為： 斷點，斷點的邏輯后繼指令的單元號稱為： 恢復點。 2/8/2023 98 練習 1. 如何將獨占型輸入設備改造成可共享使用的虛擬設備？ 2. 為什么要設置內(nèi)存 I/O緩沖區(qū)？通常有哪幾類緩沖區(qū)？ 3. 什么是設備驅動程序？其功能是什么？ 4. 在設備管理中，何為設備獨立性？如何實現(xiàn)設備獨立性？ 5. 試給出常用的 I/O調(diào)度算法。 6. 為什么要引入 Spooling系統(tǒng)？ Spooling系統(tǒng)可帶來哪些好處？ 7. DMA控制方式與通道控制方式有什么不同？ 8. 設備分配時為什么要考慮安全性和設備的無關性？ 2/8/2023 99 訪問磁盤過程 ? 對磁盤的訪問總是由缺頁引起的： ? CPU給出地址，需要訪問某存儲單元； ? 并行進行 TLB查找和 cache查找； ? TLB查找后申明沒有找到； ? 停止并行查找，并通知操作系統(tǒng)處理； ? 操作系統(tǒng)檢查頁表，發(fā)現(xiàn)該頁不在內(nèi)存中，需要從硬盤調(diào)入。應該如何進行呢？ 2/8/2023 100 ? 操作系統(tǒng)從主存中選擇一頁準備換出，為調(diào)入的頁安排存放空間； ? 若被換出的頁是“臟”頁，需要將其寫回磁盤存儲； ? 操作系統(tǒng)申請 I/O總線； ? 獲得批準后，發(fā)送寫命令給 I/O 設備（磁盤）。 緊跟著傳送需要寫回的頁的全部數(shù)據(jù)。 ? I/O控制器發(fā)現(xiàn)發(fā)給自己的寫命令 ，加入到握手協(xié)議，并接受數(shù)據(jù)。 ? 根據(jù)數(shù)據(jù)要寫入的地址，讀 /寫頭移動到正確的柱面，同時，將數(shù)據(jù)接收到緩沖區(qū)。 ? 尋道結束后，等待相應的扇區(qū)旋轉到磁頭下面，將數(shù)據(jù)寫入扇區(qū)中。 ? 在寫入數(shù)據(jù)間隙，計算校驗碼并寫入扇區(qū)中。 訪問磁盤過程（續(xù)） 2/8/2023 101 訪問磁盤過程（續(xù)） ? 下一步，操作系統(tǒng)繼續(xù)申請總線（如果還保持總線控制權，則不必申請）。 ? 得到授權后，向磁盤發(fā)出讀命令。 ? 然后，磁盤識別地址，并轉換為相應的地址段。 ? 尋道，將讀 /寫頭移動到指定位置。 ? 從指定扇區(qū)中讀去數(shù)據(jù)，并進行校驗。 ? 磁盤申請 I/O總線。 ? 得到授權后，將數(shù)據(jù)通過總線送到內(nèi)存。 2/8/2023 102 演講完畢，謝謝觀看！