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

I/O管理和磁盤調(diào)度Chapter11主要內(nèi)容教學(xué)目標與要求理解I/O控制方式。掌握I/O緩沖技術(shù)掌握磁盤存儲器的管理教學(xué)重點與難點緩沖技術(shù)，磁盤調(diào)度I/O設(shè)備的種類1、人可讀的適合與計算機用戶通信，如：打印機，終端（顯示器，鍵盤，鼠標）2、機器可讀適合與電子設(shè)備通信，如磁盤驅(qū)動器，傳感器，控制器，執(zhí)行器3、通信適合與遠程設(shè)備通信，如數(shù)字線路驅(qū)動器，調(diào)制解調(diào)器設(shè)備的分類按傳輸速率分低速設(shè)備：每秒幾個到數(shù)百字節(jié)。如調(diào)制解調(diào)器中速設(shè)備：每秒數(shù)千到數(shù)萬字節(jié)。如打印機高速設(shè)備：每秒數(shù)百K到數(shù)兆。如磁盤、磁帶I/O設(shè)備的差別數(shù)據(jù)率數(shù)據(jù)傳送率可能會差別幾個數(shù)量級I/O設(shè)備的差別應(yīng)用用于文件操作的磁盤需要文件管理軟件的支持在虛擬存儲方案中，磁盤用作頁面調(diào)度的后備存儲器，取決于虛存硬件和軟件的使用終端被普通用戶使用和系統(tǒng)管理員使用可能具有不同的特權(quán)級別，從而在OS中有不同的優(yōu)先級I/O設(shè)備的差別控制的復(fù)雜度傳送單位數(shù)據(jù)可以按照字節(jié)流或者字符流的形式傳送（如終端I/O），也可以按照大塊傳送（如磁盤I/O）數(shù)據(jù)表示數(shù)據(jù)編碼方案,包括字符代碼和奇偶約定的差異錯誤條件錯誤的本質(zhì)、報告的方式、后果以及響應(yīng)隨設(shè)備的不同而不同I/O功能的組織常見的三種I/O控制技術(shù)：程序控制I/O處理器代表進程給I/O模塊發(fā)送一個I/O命令，該進程進入忙等待，等待操作的完成，然后才可以繼續(xù)執(zhí)行中斷驅(qū)動I/O處理器代表進程發(fā)送一個I/O命令,然后繼續(xù)執(zhí)行后續(xù)指令，當(dāng)I/O模塊完成工作后，處理器被該模塊中斷。如果該進程不需等待I/O完成，后續(xù)指令可以是該進程中的指令否則，這個進程在這個中斷上被掛起，處理器執(zhí)行其他工作直接存儲器存取(DMA)DMA模塊控制主存和I/O模塊之間的數(shù)據(jù)交換為傳送一塊數(shù)據(jù)，處理器給DMA模塊發(fā)請求，只有當(dāng)整個數(shù)據(jù)塊傳送結(jié)束后，處理器才被中斷輸入輸出功能的發(fā)展I/O功能的發(fā)展階段：處理器直接控制外圍設(shè)備程序控制I/O方式：增加了控制器或I/O模塊處理器使用沒有中斷的程序控制I/O處理器不需要處理外部設(shè)備接口的具體細節(jié)又稱忙--等待方式

輸入輸出功能的發(fā)展中斷驅(qū)動I/O：控制器或I/O模塊采用了中斷處理器不再需要花費時間等待執(zhí)行一個I/O操作DMA控制方式

：I/O模塊通過DMA直接控制存儲器從主存中移出或往主存移入一塊數(shù)據(jù)，不需要處理器參與僅僅在傳送開始和結(jié)束時需要用到處理器輸入輸出功能的發(fā)展I/O通道控制方式

I/O模塊被增強成一個單獨的處理器，又專門為I/O設(shè)計的指令集I/O模塊有自己的局部存儲器I/O模塊本身就是一個計算機也稱作I/O處理器特點：是DMA方式的發(fā)展，它可進一步減少CPU的干預(yù)，即把對一個數(shù)據(jù)塊的讀（或?qū)懀閱挝坏母深A(yù)，減少為對一組數(shù)據(jù)塊的讀（或?qū)懀┘坝嘘P(guān)的控制和管理為單位的干預(yù)。同時，又可實現(xiàn)CPU、通道和I/O設(shè)備三者的并行工作，從而更有效的提高了整個系統(tǒng)的資源利用率。直接存儲器訪問DMA取代處理器控制系統(tǒng)，在系統(tǒng)總線上從存儲器中或者往存儲器中傳送數(shù)據(jù)周期挪用技術(shù)用于在總線上傳送數(shù)據(jù)為了使數(shù)據(jù)能夠傳送，掛起一個指令周期，即CPU暫停一個總線周期整塊數(shù)據(jù)傳送過程中沒有中斷發(fā)生不需要保存進程上下文DMADMA工作流程請求讀/寫操作的信號相關(guān)的I/O設(shè)備地址內(nèi)存起始地址讀/寫的字節(jié)數(shù)DMA機制的配置方法周期挪用技術(shù)導(dǎo)致處理器執(zhí)行得更慢通過DMA和I/O功能集成起來，可以大大的減少所需要的總線周期的數(shù)目DMA模塊和一個或多個I/O模塊之間除了系統(tǒng)總線還存在著路徑DMADMADMA操作系統(tǒng)設(shè)計問題Efficiency（效率）與主存和處理器相比，大多數(shù)I/O設(shè)備都是非常慢速的使用多道程序設(shè)計，可以允許一些進程在等待I/O操作時另一些進程正在執(zhí)行交換技術(shù)用于將額外的就緒進程加載到內(nèi)存，使得處理器保持忙狀態(tài)，但交換本身是一個I/O操作I/O設(shè)計的主要任務(wù)是提供I/O的效率操作系統(tǒng)設(shè)計問題Generality（通用性）為了簡單性和避免錯誤，往往希望能用一種統(tǒng)一的方式處理所有的設(shè)備使用一種層次化的、模塊化的方法設(shè)計I/O功能，在低層例程中隱藏大部分設(shè)備I/O的細節(jié)，使得用戶進程和操作系統(tǒng)高層可以通過一些通用的功能，如read,write,open,close,lock,unlock等來查看I/O設(shè)備一種I/O組織的模型I/O緩沖速度的差異問題計算機系統(tǒng)中的各種設(shè)備(包括中央處理機)的運行速度差異甚大，CPU的運行速度是以納秒計，而設(shè)備的運行速度則是以毫秒甚至以秒計；負荷不均勻問題有時處理機進行大量的計算工作，沒有I/O操作，有時又會進行大量的I/O操作，這兩個極端都會造成系統(tǒng)中的一些設(shè)備過于繁忙，一部分設(shè)備過于空閑，嚴重地影響CPU與外設(shè)的并行工作。緩存cache和緩沖buffer的異同

緩存（cache）是把讀取過的數(shù)據(jù)保存起來，重新讀取時若命中（找到需要的數(shù)據(jù)）就不要去讀硬盤了，若沒有命中就讀硬盤。其中的數(shù)據(jù)會根據(jù)讀取頻率進行組織，把最頻繁讀取的內(nèi)容放在最容易找到的位置，把不再讀的內(nèi)容不斷往后排，直至從中刪除。緩沖（buffer）當(dāng)存儲速度快的設(shè)備與存儲速度慢的設(shè)備進行通信時，存儲慢的設(shè)備先把數(shù)據(jù)存放到buffer，達到一定程度后，存儲快的設(shè)備再讀取buffer的數(shù)據(jù)，在此期間存儲快的設(shè)備CPU可以干其他的事情。緩存cache和緩沖buffer的異同

相同之處：都是為了彌補速度差異，都位于相對較快的設(shè)備上，容量相對較小不同之處：Cache要考慮局部性，重復(fù)使用Buffer有寫“化零為整”和預(yù)讀的作用（writesequencingandreadprefetching)Cache中的內(nèi)容在低速設(shè)備中一定還有一份，從而要考慮同步，相對的Buffer要考慮flush這種區(qū)別并不是絕對的，有時也混用，比如TLB引入緩沖技術(shù)的目的提出用緩沖技術(shù)來匹配CPU與設(shè)備的速度的差異提高處理機與外設(shè)的并行程度。緩沖的實現(xiàn)方式硬件緩沖區(qū)：如設(shè)備控制器中的數(shù)據(jù)寄存器，數(shù)量少軟件緩沖區(qū):內(nèi)存中劃出的一塊專門空間。兩類I/O設(shè)備面向塊的設(shè)備信息保存在固定大小的塊中一次只傳送一塊使用磁盤和磁帶面向流的設(shè)備傳送字節(jié)流數(shù)據(jù)終端,打印機,通信端口,鼠標和其他指示設(shè)備以及大多數(shù)不是輔存的其他設(shè)備，都是面向流的常用的緩沖技術(shù)1、單緩沖2、雙緩沖3、循環(huán)緩沖單緩沖當(dāng)一個用戶進程發(fā)出I/O請求時，操作系統(tǒng)給該操作分配一個位于內(nèi)存中系統(tǒng)部分的緩沖區(qū)CPUCPUTCTCM單緩沖面向塊設(shè)備輸入傳送進入系統(tǒng)緩沖區(qū)當(dāng)傳送完成時，進程把該塊移到用戶空間，并立即請求另一塊稱作預(yù)讀，或者先行輸入用戶進程可以在下一塊數(shù)據(jù)正在讀入時，處理這一塊數(shù)據(jù)由于輸入發(fā)生在系統(tǒng)存儲空間中而不是用戶進程存儲器中，故而操作系統(tǒng)可以把該進程換出操作系統(tǒng)必須知道給用戶進程分配系統(tǒng)緩沖區(qū)的情況單緩沖面向流設(shè)備在每次傳送一行或一個字節(jié)的方式下使用每次傳送一行適合于上卷式終端：用戶每次輸入一行，用回車表示到達行尾，并且輸出到終端時也是類似的每次輸出一行行式打印機每次傳送一個字節(jié)適用于表格型終端，鍵盤、傳感器、控制器對于塊設(shè)備：

設(shè)：數(shù)據(jù)從磁盤—>緩沖區(qū) T數(shù)據(jù)從緩沖區(qū)—>用戶區(qū)MCPU計算時間C則：單緩沖系統(tǒng)對數(shù)據(jù)的處理時間為：max(C,T)+M如無緩沖區(qū)，處理時間為：T+C單緩沖性能無緩沖的數(shù)據(jù)處理時間：T+C單緩沖的數(shù)據(jù)處理時間：Max[C,T]＋M數(shù)據(jù)由I/O控制器到緩沖區(qū)和數(shù)據(jù)由緩沖區(qū)到用戶工作區(qū)，必須串行操作；單緩沖工作時序圖雙緩沖給操作系統(tǒng)指定兩個系統(tǒng)緩沖區(qū)，對單緩沖方案進行改進當(dāng)一個進程往這一個緩沖區(qū)中傳送數(shù)據(jù)（從這個緩沖區(qū)中取數(shù)據(jù)）時，操作系統(tǒng)正在清空（填充）另一個緩沖區(qū)，并行操作TCM雙緩沖性能雙緩沖的數(shù)據(jù)處理時間：Max[C+M,T]雙緩沖工作時序圖20119、某文件占10個磁盤塊，現(xiàn)要把該文件磁盤塊逐個讀入主存緩沖區(qū)，并送用戶區(qū)進行分析。假設(shè)一個緩沖區(qū)與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區(qū)的時間為100μs，將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時間是50μs，CPU對一塊數(shù)據(jù)進行分析的時間為50μs。在單緩沖區(qū)和雙緩沖區(qū)結(jié)構(gòu)下，讀入并分析完該文件的時間分別是（B

）

A、1500μs、1000μsB、1550μs、1100μs

C、1550μs、1550μsD、2000μs、2000μsTCM1005050100*9+20010050501005050循環(huán)緩沖使用多于兩個的緩沖區(qū)其中的每一個緩沖區(qū)是這個循環(huán)緩沖區(qū)的一個單元使相關(guān)I/O操作能夠跟得上這個進程緩沖池環(huán)形緩沖區(qū)一般用于特定的進程，屬于專用緩沖區(qū)，當(dāng)系統(tǒng)較大時，將會有許多這樣的環(huán)形緩沖區(qū)，這不僅要消耗大量的內(nèi)存空間，利用率也不高。為了提高緩沖區(qū)的利用率，目前廣泛流行公用緩沖池，池中的緩沖區(qū)可供多個進程共享。

緩沖池由內(nèi)存中一組大小相等的緩沖區(qū)組成，池中各緩沖區(qū)的大小與用于I/O的設(shè)備的基本信息單位相似，緩沖池屬于系統(tǒng)資源，由系統(tǒng)進行管理。緩沖池中各緩沖區(qū)可用于輸出信息，也可用于輸入信息，并可根據(jù)需要組成各種緩沖區(qū)隊列。

目前，幾乎所有隨機存取的文件，都是存放在磁盤上，磁盤I/O速度的高低將直接影響文件系統(tǒng)的性能。磁盤分為兩種：固定頭磁盤：每個磁道設(shè)置一個磁頭，變換磁道時不需要磁頭的機械移動，速度快但成本高移動頭磁盤：一個盤面只有一個磁頭，變換磁道時需要移動磁頭，速度慢但成本低磁盤概述柱面扇區(qū)磁臂磁頭磁盤側(cè)視圖磁道扇區(qū)磁盤俯視圖信息記錄在磁道上，多個盤片，正反兩面都用來記錄信息，每面一個磁頭所有盤面中處于同一磁道號上的所有磁道組成一個柱面每個扇區(qū)大小為512字節(jié)物理地址形式：柱面號 磁頭號扇區(qū)號柱面、磁頭、扇區(qū)由三個動作組成：尋道：磁頭移動定位到指定磁道旋轉(zhuǎn)延遲：等待指定扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過數(shù)據(jù)傳輸：數(shù)據(jù)在磁盤與內(nèi)存之間的實際傳輸磁盤的訪問過程磁盤I/O傳送的時序磁盤性能參數(shù)為了讀和寫，磁頭必須定位于期望的磁道和該磁道中期望的扇區(qū)的開始處尋道時間磁頭定位磁道所需要的時間當(dāng)代磁盤的平均尋道時間小于10ms旋轉(zhuǎn)延遲扇區(qū)到達磁頭的時間速度為15000r/m，平均旋轉(zhuǎn)延遲為2ms磁盤性能參數(shù)存取時間Accesstime尋道時間和旋轉(zhuǎn)延遲的總和達到讀或?qū)懳恢盟枰臅r間一旦磁頭定位，并且扇區(qū)旋轉(zhuǎn)到磁頭下，就開始執(zhí)行讀或?qū)懖僮鳎@是整個操作的數(shù)據(jù)傳送部分傳送時間總平均存取時間時序比較假設(shè)一磁盤平均尋道時間為4ms，轉(zhuǎn)速為7500rpm，每個磁道500個扇區(qū)，每個扇區(qū)512個字節(jié)。假設(shè)讀取一個包含2500個扇區(qū)、大小為1.28MB的文件，請問估計傳送的總時間？時序比較順序訪問時間總時間=16+(4*12)=64ms=0.064s隨機訪問時間總時間=2,500*8.016=20,040ms=20.04s磁盤調(diào)度策略尋道時間是產(chǎn)生性能差異的原因?qū)τ趩蝹€磁盤，磁盤訪問請求隊列中可能有來自多個進程的許多I/O請求（讀和寫）如果按隨機順序從對列中選擇項目，那么磁道完全是被隨機訪問的，這種情況下的性能最差磁盤調(diào)度策略先進先出(First-in,first-out，F(xiàn)IFO)按訪問請求到達的先后次序服務(wù)優(yōu)點：對于所有的進程都很公平缺點：如果有多個進程競爭一個磁盤，這種技術(shù)在性能上往往接近于隨機調(diào)度。例：表11.2a圖11.7a磁盤調(diào)度策略Priority這種方法并不會優(yōu)化磁盤的使用率，但可以滿足操作系統(tǒng)的其他目標，如：比較短的批作業(yè)和交互作業(yè)比需要較長計算時間的長作業(yè)的優(yōu)先級高可以提供比較好的交互響應(yīng)時間磁盤調(diào)度策略Last-in,first-out取最近請求有利于事務(wù)處理系統(tǒng)把設(shè)備給最近的用戶會導(dǎo)致磁頭臂在一個順序文件中移動時移動的很少，甚至不移動利用這種局部性可以提高吞吐量，減小隊列長度當(dāng)一個作業(yè)往隊列中送入一個I/O請求時，錯過了磁頭位置時，該作業(yè)就可能永遠得不到磁頭而被餓死，除非它前面的隊列變?yōu)榭沾疟P調(diào)度策略最短服務(wù)時間優(yōu)先(ShortestServiceTimeFirst,SSTF)選擇使磁頭臂從當(dāng)前位置開始移動最少的磁盤I/O請求貪心的策略，總是選擇最小尋道時間的請求不能保證平均尋道時間最短能提供比FIFO更好的性能饑餓現(xiàn)象例：表11.2b圖11.7b磁盤調(diào)度策略SCAN（電梯算法）要求磁頭臂僅僅沿一個方向移動，并在途中滿足所有未完成的請求，直到它到達這個方向上的最后一個磁道，或者在這個方向上沒有別的請求為止(可以防止饑餓)后一種改進有時候稱作LOOK策略。然后倒轉(zhuǎn)服務(wù)方向，沿相反方向掃描，同樣按順序完成所有請求在移動方向固定的情況下采用了SSTF，以避免饑餓現(xiàn)象存在請求進程等待延遲現(xiàn)象，最大延遲時間為2t例：表11.2c圖11.7c磁盤調(diào)度策略C-SCAN（循環(huán)掃描）把掃描限定在一個方向當(dāng)沿某個方向訪問到最后一個磁道時，磁頭臂返回到磁盤的另一端，并再次開始掃描請求延遲時間：2tt+Smax，減少了新請求的最大延遲磁盤調(diào)度策略可避免“磁頭臂的粘性（磁臂粘著）”的策略：N-step-SCAN把磁盤請求隊列分成長度為N的子隊列每一次用SCAN處理一個子隊列在處理某一個隊列時，新請求必須添加到其他某個隊列中磁盤調(diào)度策略可避免“磁頭臂的粘性”的策略：FSCAN使用兩個子隊列當(dāng)掃描開始時，所有請求都在一個隊列中，而另一個隊列為空。在掃描過程中，所有新到的請求都被放入另一個隊列中磁盤調(diào)度策略獨立磁盤冗余陣列（RAID）RAID(RedundantArraysofIndependentDisk)。由伯克利提出，廣泛用于大中型計算機和網(wǎng)絡(luò)中。由一臺磁盤陣列控制器控制一組磁盤驅(qū)動器，組成一個高度可靠、快速的大容量磁盤系統(tǒng)。1、并行交叉存取2、RAID分級3、RAID的優(yōu)點1、并行交叉存取加快訪問速度在系統(tǒng)中有多臺磁盤驅(qū)動器（N）。存放數(shù)據(jù)時，將數(shù)據(jù)的第一塊放在第一個磁盤上，第N塊放在第N個磁盤上。這樣可以并行讀寫，極大地提高了速度。2、RAID分級RAID0—RAID7RAID0提供并行交叉存?。]有冗余能力）至少兩個盤RAID1兩個盤，并行交叉存取，并把一個磁盤的數(shù)據(jù)鏡像到另一個磁盤上。利用率50%。比傳統(tǒng)鏡像盤快。RAID2-6:使用某種形式的奇偶計算來實現(xiàn)冗余的RAID0(non-redundant)RAID1(mirrored)通過臨時復(fù)制所有數(shù)據(jù)來實現(xiàn)冗余的RAID2(redundancythroughHammingcode)RAID2-3:并行訪問RAID3(交錯位奇偶校驗)RAID4(塊奇偶校驗)RAID4-6:獨立訪問RAID