【正文】 38 39 55 58 90 100 150 160 184 請求次序 4 8 3 1 2 5 開始 7 6 9 平均尋道長度 : (45+3+19+21+72+70+10+112+146)/9= 103 第五章 設 備 管 理 1. 先來先服務 FCFS ? 公平，簡單。 ? I/O負載較輕且每次讀寫多個連續(xù)扇區(qū)時，性能較好。 ? 適用于 I/O進程較少的場合。 (從 100號磁道開始 ) 被訪問的下 一個磁道號 移動距離 （磁道數(shù)） 55 58 39 18 90 160 150 38 184 45 3 19 21 72 70 10 112 146 平均尋道長度： 104 第五章 設 備 管 理 2. 最短尋道時間優(yōu)先 SSTF 磁道號 18 38 39 55 58 90 100 150 160 184 請求次序 4 8 3 1 2 5 開始 7 6 9 平均尋道長度 : (10+32+3+16+1+20+132+10+24)/9= 105 第五章 設 備 管 理 2. 最短尋道時間優(yōu)先 SSTF ? 磁頭移動距離最近，時間最少。 ? 不能保證平均尋道時間最短。 ? 可能會有進程處于“ 饑餓 ”狀態(tài)。 (從 100號磁道開始 ) 被訪問的下 一個磁道號 移動距離 （磁道數(shù)） 90 58 55 39 38 18 150 160 184 10 32 3 16 1 20 132 10 24 平均尋道長度： 106 第五章 設 備 管 理 3. 掃描 (SCAN)算法 磁道號 18 38 39 55 58 90 100 150 160 184 請求次序 4 8 3 1 2 5 開始 7 6 9 107 第五章 設 備 管 理 3. 掃描 (SCAN)算法 ? 電梯調度算法。 ? 防止 “饑餓 ”現(xiàn)象。 ? 被廣泛應用。 ? 磁頭剛剛越過了某一磁道，恰好又有一進程請求訪問此磁道，該進程長時間等待。 (從 100號磁道開始，向磁道號增加的方向訪問 ) 被訪問的下 一個磁道號 移動距離 （磁道數(shù)） 150 160 184 90 58 55 39 38 18 50 10 24 94 32 3 16 1 20 平均尋道長度： 108 第五章 設 備 管 理 4. 循環(huán)掃描 (CSCAN)算法 磁道號 18 38 39 55 58 90 100 150 160 184 請求次序 4 8 3 1 2 5 開始 7 6 9 109 第五章 設 備 管 理 4. 循環(huán)掃描 (CSCAN)算法 ? 磁頭單向移動。 ? 該算法在中負載或重負載時，性能比掃描算法好。 (從 100號磁道開始，向磁道號增加的方向訪問 ) 被訪問的下 一個磁道號 移動距離 （磁道數(shù)） 150 160 184 18 38 39 55 58 90 50 10 24 166 20 1 16 3 32 平均尋道長度： 110 第五章 設 備 管 理 5. NStepSCAN算法 ? 在高密度磁盤上容易出現(xiàn)“磁臂粘著”情況。 ? 將磁盤請求隊列分成若干個長度為 N的子隊列。 ? 隊列之間使用 FCFS算法。 ? 隊列內部使用 SCAN算法。 ? 新的 I/O請求，放入其他隊列，避免粘著現(xiàn)象。 ? 當 N值很大時，性能接近于 SCAN算法。 ? 當 N=1時，蛻化為 FCFS算法。 111 第五章 設 備 管 理 6. FSCAN算法 ? 是 N步 SCAN算法的簡化。 ? 磁盤請求隊列分成兩個子隊列： ? 一個是由當前所有請求磁盤 I/O的進程形成的隊列，按 SCAN算法進行處理。 ? 新出現(xiàn)的所有請求磁盤 I/O的進程， 放入另一個等待處理的請求隊列，推遲到下一次掃描時處理。 112 第五章 設 備 管 理 磁盤高速緩存 (Disk Cache) ? 引入目的：提高磁盤的 I/O速度。 ? 實現(xiàn)：利用內存中的存儲空間，暫存從磁盤中讀出的數(shù)據(jù)。 ? 邏輯上屬于磁盤，物理上是駐留在內存。 ? 高速緩存在內存中可分成兩種形式。 ? 內存中開辟一個單獨的存儲空間。 ? 把所有未利用的內存空間變?yōu)橐粋€緩沖池，供請求分頁系統(tǒng)和磁盤 I/O時共享。 113 第五章 設 備 管 理 磁盤高速緩存 (Disk Cache) ? 數(shù)據(jù)交付方式： ? 數(shù)據(jù)交付 ：將磁盤高速緩存中的數(shù)據(jù)傳送給請求進程。 ? 指針交付 ：只將指向高速緩存中某區(qū)域的指針交付給請求者進程，傳送數(shù)據(jù)量少，節(jié)省時間。 114 第五章 設 備 管 理 磁盤高速緩存 (Disk Cache) ? 常用置換算法 ? LRU， NRU， LFU ? 所應考慮的問題 ? 訪問頻率 ? 可預見性 ? 數(shù)據(jù)的一致性 115 第五章 設 備 管 理 磁盤高速緩存 (Disk Cache) ? 周期性地寫回磁盤 ? UNIX系統(tǒng)中專門增設了一個修改程序，間隔 30 s將高速緩存中已修改的盤塊數(shù)據(jù)寫回磁盤。 ? MSDOS采用的方法是：只要高速緩存中的數(shù)據(jù)被修改，便立即寫回磁盤 。 幾乎不會造成數(shù)據(jù)丟失，但須頻繁啟動磁盤。 116 第五章 設 備 管 理 提高磁盤 I/O速度的其它方法 ? 提前讀（基于文件的順序訪問方式） ? 延遲寫 ? 優(yōu)化物理塊的分布 ? 虛擬盤 117 第五章 設 備 管 理 廉價磁盤冗余陣列 ? 并行交叉存取 1 2 3…N118 第五章 設 備 管 理 廉價磁盤冗余陣列 ? RAID的分級 ? RAID 0級 ? RAID 1級 ? RAID 3級 ? RAID 5級 ? RAID 6級和 RAID 7級 ? RAID的優(yōu)點 ? 可靠性高 ? 磁盤 I/O速度高 ? 性能 /價格比高 119 第五章 設 備 管 理 本章小結 ? 設備的分類 ? 設備控制器 ? I/O通道，瓶頸問題 ? I/O控制方式（四種）： ? DMA控制器；通道程序 ? 緩沖管理（四種） ? 設備分配的數(shù)據(jù)結構；設備獨立性 ? SPOOLING技術 ? 設備驅動程序 ? 磁盤訪問時間；磁盤調度算法 120 第五章 設 備 管 理 利用緩沖寄存器實現(xiàn)緩沖 1 位 緩沖送內存8 位緩沖寄存器8 位緩沖寄存器送內存(a)(b)(c)位位緩沖寄存器位緩沖寄存器返回 121 第五章 設 備 管 理 中斷現(xiàn)場保護示意圖 122 第五章 設 備 管 理 基本的 設備分配流程 進程 P提出所需的 I/O設備 根據(jù)物理設備名 ， 從 SDT中找出該設備的 DCT 由 DCT的設備狀態(tài)字段 ， 檢查該設備是否忙 ？ 將該進程的 PCB插入到 該設備的等待隊列中 檢查本次設備分配是否安全 ？ 將此設備分配給該進程 從其 DCT中找出與該設備連接的控制器的 COCT， 檢查該控制器是否忙 ？ 將該進程的 PCB插入到 該控制器的的等待隊列中 將該控制器分配給進程 從 COCT中找到與該控制器連接的通道的 CHCT， 檢查該通道是否忙 ？ 將該進程的 PCB插入到 該通道的的等待隊列中 將該通道分配給進程 至此，設備、控制器和通道三者都已分配成功 啟動 I/O設備，進行具體的 I/O操作 不忙 不忙 不忙 忙 忙 安全 不安全 忙 123 第五章 設 備 管 理 現(xiàn)代磁盤扇區(qū)結構示意圖 124 第五章 設 備 管 理 磁盤性能簡述 ? 磁盤的低級格式化（溫盤） Gap 1 0 2 0 3 1 29 2 29 3 Field Gap Field Gap Gap Field Gap Field Gap 17 7 41 515 20 17 7 41 515 20 ID Data ID Data Gap 1 29 2 29 3 Field Gap Field 17 7 41 515 20 ID Data Sector Physical Sector 0 Physical Sector 1 Physical Sector 29 Bytes Synch Byte Track Head Sector Bytes 1 2 1 1 CRC 3 Synch Byte Data CRC 1 512 2 600 Bytes/Sector Gap 125