第11章 IO管理和磁盤調度

第五部分I/O與文件

之設備管理2第11章I/O管理和磁盤調度311.1I/O設備I/O設備的三種類別人可讀：適用于同計算機用戶之間的交互打印機、顯示器、鍵盤、鼠標機器可讀：適用于與電子設備通信磁盤、磁帶、傳感器、控制器通信：適用于與遠程設備通信數字線路驅動器、調制解調器I/O設備的差異主要包括：數據傳送速率（見下頁圖）支持的應用程序設備控制的復雜性數據傳送單位（字節(jié)流、字符流、塊）數據表示（編碼方式）錯誤條件411.1I/O設備典型的I/O設備數據率511.2I/O功能的組織三種I/O通信技術（P25圖1.19）可編程I/O中斷驅動I/O直接存儲器訪問（DMA）6I/O模塊執(zhí)行請求的動作，而非處理器。I/O處理模塊設置I/O狀態(tài)寄存器中相應的位。I/O處理模塊不通知處理器，也不中斷處理器。處理器定期檢測I/O模塊狀態(tài)，直到操作結束。處理器不斷詢問I/O模塊的狀態(tài)，嚴重降低了系統(tǒng)的性能。11.2I/O功能的組織711.2I/O功能的組織當I/O模塊準備好要交換的數據時，中斷處理器。處理器保存正在執(zhí)行程序的上下文，然后開始進行中斷處理。沒有不必要的等待。由于每個字的讀寫都需要通過處理器進行，消耗了大量的處理器時間。811.2I/O功能的組織傳送的為塊數據。傳送完成時，產生中斷。處理器委托DMA模塊，由該模塊負責處理數據傳送。處理器不干預傳送，而繼續(xù)其它工作?？删幊毯椭袛囹寗覫/O缺點：I/O傳送速度受限于處理器測試設備和提供服務的速度。處理器忙于管理I/O的傳送工作。處理器必須執(zhí)行很多指令以完成I/O傳送。911.2I/O功能的組織10DMA配置：單總線，集成的DMA-I/O11.2I/O功能的組織DMA配置：單總線，分離的DMA11DMA配置：I/O總線11.2I/O功能的組織1211.3操作系統(tǒng)設計問題設計目標效率和主存相比，大多數I/O設備非常慢使用多道程序設計技術，可使一些進程在等待I/O設備，而其它進程在執(zhí)行I/O也無法跟上處理器的速度交換技術用于將就緒進程加載到內存是一個I/O操作通用性用一種統(tǒng)一的方式處理所有設備屏蔽底層細節(jié)高層可通過讀、寫、打開、關閉、鎖定、解鎖等一些通用的功能來操作I/O1311.3.2I/O功能的邏輯結構1411.4I/O緩沖采用緩沖的原因進程必須等待I/O操作完成后才能繼續(xù)執(zhí)行如果使用分頁機制，那么至少需要將包括目標地址單元的頁鎖定在主存中可能出現單進程死鎖進程發(fā)送I/O命令并被掛起在I/O操作開始之前被換出進程阻塞，等待I/O事件I/O阻塞，等待進程被換入在進程發(fā)出I/O請求之前，鎖定I/O操作所涉及的存儲空間在輸入請求發(fā)出前就開始執(zhí)行輸入傳遞在輸出請求發(fā)出一段時間之后才開始執(zhí)行輸出傳送緩沖技術（面向塊的I/O設備和面向流的I/O設備）1511.4I/O緩沖面向塊的I/O設備信息存儲在固定大小的塊中一次傳送一塊磁盤、磁帶面向流的I/O設備以字節(jié)流的形式傳送信息打印機、鼠標1611.4.1單緩沖區(qū)OS給一個I/O請求分配一個位于主存中系統(tǒng)部分的緩沖區(qū)面向塊輸入傳送的數據被放到系統(tǒng)緩沖區(qū)中傳送完成時，進程把塊移動到用戶空間進程請求另外一塊在下一塊數據正在讀取的時候，用戶進程可以處理一塊數據可以換出進程輸入是發(fā)生在系統(tǒng)內存，而非用戶內存1711.4.1單緩沖區(qū)面向流每次傳送一行或一個字節(jié)一次一行：適用于滾動方式的終端，用戶輸入一行后回車。行式打印機。假定，一塊數據從外部設備輸入到內存所花費的時間為T，在內存中移動所花費的時間為M，被用戶進程加工處理所花費的時間為C，那么在沒有使用I/O緩沖區(qū)的情況下，平均每塊數據的處理時間近似為：T+C在使用單I/O緩沖區(qū)的情況下，平均每塊數據的處理時間近似為：max(T,C)+M相對于沒有I/O緩沖區(qū)的情形，單I/O緩沖區(qū)能提高用戶進程的運行效率。如果用戶進程在對有關數據進行加工處理時不釋放I/O緩沖區(qū)，那么用戶進程的性能并不能得到改善。如果T遠遠大于C，即外部設備的I/O速度比用戶進程的計算速度慢得多，那么，單I/O緩沖區(qū)不會顯著改善用戶進程的性能。2011.4.2雙緩沖區(qū)使用兩個系統(tǒng)緩沖區(qū)一個進程往一個緩沖區(qū)中傳送數據（或從這個緩沖區(qū)中取數據）的同時，OS正在清空（或者填充）另外一個緩沖區(qū)增加一個緩沖區(qū)，兩個緩沖區(qū)可以交替使用。當數據從緩沖區(qū)復制到用戶進程空間時，輸入設備不必等待，可立即開始向另一個緩沖區(qū)輸入數據。因此，增加了一個緩沖區(qū)后，前述的平均工作時間可近似為：max(T,C)。另外，若用戶進程陣發(fā)性I/O的數據超過一個緩沖區(qū)而不滿兩個緩沖區(qū)，雙緩沖使進程不會在I/O數據期間被阻塞。2211.4.3循環(huán)緩沖多于兩個的緩沖區(qū)每個緩沖區(qū)是循環(huán)緩沖區(qū)中的單元用于使得I/O操作跟上進程速度2311.5磁盤調度磁盤速度小于內存速度，如何提高磁盤性能是關鍵？2411.5磁盤調度25 為了讀寫磁盤，磁頭必須定位于指定的磁道和該磁道中指定的扇區(qū)的開始處。

磁盤性能參數：尋道時間（Seektime）磁頭定位到磁道所需要的時間旋轉延遲（Rotationaldelayorrotationallatency）磁頭到達扇區(qū)開始位置的時間存取時間（Accesstime）尋道時間+旋轉延遲磁頭達到讀或寫的位置所需要的時間11.5.1磁盤性能參數2611.5.1磁盤性能參數傳送時間（TransferTime）傳送數據所需要的時間一旦磁頭定位，磁頭就通過下面旋轉的扇區(qū)，開始執(zhí)行讀操作或寫操作T=b/(rN)T:傳送時間b:要傳送的字節(jié)數r:旋轉速度，轉/秒N:一個磁道中的字節(jié)數總的平均存取時間2711.5.1磁盤性能參數 一個典型的磁盤，平均尋道時間為4ms，轉速為7500r/m，每個磁道有500個扇區(qū)，每個扇區(qū)512個字節(jié)。希望讀取一個包含2500扇區(qū)，大小為1.28MB的文件。估計傳送需要的總時間？順序組織（所有數據緊湊地保存在磁盤上，共5個磁道）讀第一個500扇區(qū)的時間=平均尋道4ms+旋轉延遲4ms+傳送時間8ms=16ms隨后不需要尋道。總時間=16+（4+8）*4=64ms隨機讀取讀一個扇區(qū)的時間=4ms+4ms+0.016ms=8.016ms總時間=8.016*2500=20040ms從磁盤讀扇區(qū)的順序對I/O的性能影響很大2811.5.2磁盤調度產生性能差異的原因可以追溯到尋道時間一個磁盤可能有多個I/O請求如果按照隨機調度，性能將很差調度算法先進先出FIFO優(yōu)先級PRI后進先出LIFO最短服務時間優(yōu)先SSTF選擇使磁頭臂從當前位置開始移動最少的磁盤I/O請求2911.5.2磁盤調度調度算法SCAN磁頭臂僅僅沿一個方向移動，并在途中滿足所有未完成的請求到達最后一個磁道或該方向上沒有其它請求，停止反向移動C-SCAN循環(huán)SCANN-step-SCAN和FSCANN-Step-SCAN把隊列分成長度為N的子隊列，每次用SCAN掃描一子隊列，在掃描期間，新請求必須加到其它隊列中FSCAN分成兩個子隊列，開始時候，所有請求在一個隊列中，掃描時，新請求入另外一個隊列3011.5.2磁盤調度例子：假設磁盤有200個磁道，磁盤請求隊列中是一些隨機請求，順序為：55、58、39、18、90、160、150、38、184，磁盤初始位于100處3111.5.2磁盤調度：例子3211.5.2磁盤調度：例子3311.6獨立磁盤冗余陣列（RAID）磁盤傳送速度低，如何提高？

通過多個磁盤，多個獨立的I/O請求可以并行地進行處理，只要它們所需要的數據駐留在不同的磁盤中或者所訪問的數據塊分布在多個磁盤中。獨立磁盤的冗余整列RAID（標準方案）OS把物理磁盤集合看成一個邏輯磁盤數據分布在物理驅動器陣列中使用冗余的磁盤容量保存奇偶校驗信息一個磁盤失敗時，數據具有可恢復性提高可靠性RAID0–RAID63411.6獨立磁盤冗余陣列（RAID）3511.6獨立磁盤冗余陣列（RAID）3611.6獨立磁盤冗余陣列（RAID）3711.7磁盤高速緩沖主存中為磁盤扇區(qū)設置的一個緩沖區(qū)包含有磁盤中某些扇區(qū)的副本I/O請求時，先查看是否在磁盤高速緩沖中在，則直接從緩沖區(qū)讀取否則從磁盤讀入緩沖區(qū)，然后從緩沖區(qū)讀取383811.7磁盤高速緩沖之替換策略最近最少使用算法(LRU-LeastRecentlyUsed)替換在高速緩沖區(qū)中未被訪問的時間最長的塊緩沖區(qū)由一個關于塊的棧組成最近訪問的塊位于棧頂當高速緩沖中的一個塊被訪問到時，它從棧中當前位置移動到棧頂當新的塊需要空間，把位于棧底的塊移出塊在內存中不需要真正移動使用棧指針實現393911.7磁盤高速緩沖之替換策略最不常用算法（LFU：LeastFrequentlyUsed）替換集合中被訪問次數最少的塊每個塊需要一個計數器當塊被訪問時，計數器+1計算器值最少的塊被替換40作業(yè)復習題：11.4、11.5、11.7習題：11.1