第11章 IO管理和磁盤調(diào)度

第五部分I/O與文件

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

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

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