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