I／O管理與磁盤調(diào)度第一頁，共77頁。第11章

輸入輸出與磁盤調(diào)度主要內(nèi)容：I/O設備I/O功能的組織操作系統(tǒng)的I/O設計I/O緩沖磁盤調(diào)度磁盤高速緩存Unix/Linux/Windows的I/O2第二頁，共77頁。I/O的特點I/O性能經(jīng)常成為系統(tǒng)性能的瓶頸I/O是導致操作系統(tǒng)龐大復雜的原因之一種類繁多、結構各異、速度差異大理解I/O的工作過程與結構是理解操作系統(tǒng)的工作過程與結構的關鍵與操作系統(tǒng)的其他功能（特別是文件系統(tǒng)）聯(lián)系密切3第三頁，共77頁。11.1I/O設備分類：人可讀的（humanreadable）——與用戶交互打印機終端：顯示器+鍵盤（+鼠標+觸摸屏+手寫筆+……）機器可讀（machinereadable）——與電子設備通信磁盤驅(qū)動器固態(tài)硬盤/U盤/閃存盤（SolidStateDisk/USBkey/

USBflashdrive）傳感器（sensor）控制器（controller）執(zhí)行機構/驅(qū)動器/傳動器（actuator）通信（communication）——與遠程設備通信數(shù)字線路驅(qū)動器（digitallinedriver）調(diào)制解調(diào)器（modem）4第四頁，共77頁。I/O設備的差異數(shù)據(jù)傳送速率：5第五頁，共77頁。I/O設備的差異（續(xù)）應用程序用于存儲文件的磁盤需要文件管理軟件支持用于存儲虛擬內(nèi)存頁面的磁盤需要特定軟硬件支持系統(tǒng)管理員使用的終端可能擁有高優(yōu)先級控制的復雜性傳送單位——字節(jié)（如鍵盤）/塊（磁盤）數(shù)據(jù)表示——編碼方案（字符編碼、奇偶校驗）錯誤條件——不同的設備以不同的方式響應錯誤6第六頁，共77頁。設備組成I/O設備一般由機械和電子兩部分組成：機械部分：設備本身（物理裝置）電子部分：稱作設備控制器（devicecontroller）或適配器（adapter），在小型和微型機中常采用印刷電路卡插入計算機（接口）中OS差不多總是跟控制器而不是設備本身打交道，即控制器完成設備與主機間的連接和通訊第七頁，共77頁。設備組成（續(xù)）控制器卡上通常有一個可插接的連接器，通過電纜與設備內(nèi)部相連控制器與設備之間的接口常常是一個低級接口（如指定具體參數(shù)對磁盤進行格式化）從設備驅(qū)動器出來的是位流（比特流），控制器的任務是把串行的位流轉換為字節(jié)塊，并進行必要的校驗工作后送到內(nèi)存第八頁，共77頁。11.2I/O功能的組織控制設備和內(nèi)存或CPU之間的數(shù)據(jù)傳送的方式（在第1章中已經(jīng)講過）：程序控制（programmedI/O）由用戶進程直接控制（如發(fā)出啟動命令）I/O操作完成前CPU處于忙等待狀態(tài)（不停檢測是否完成）中斷驅(qū)動方式(interrupt-drivenI/O)操作系統(tǒng)將I/O命令（帶參數(shù)）寫入控制器寄存器中CPU可以轉去執(zhí)行其他運算I/O操作完成時控制器產(chǎn)生一個中斷DMA(DirectMemoryAccess，直接內(nèi)存訪問)由DMA模塊控制內(nèi)存和I/O設備之間的數(shù)據(jù)交換CPU僅僅在整個數(shù)據(jù)塊的傳送都完成時才被中斷9第九頁，共77頁。I/O傳送控制方式的發(fā)展過程CPU直接控制外圍設備引入了控制器或I/O模塊，使用程序控制方式中斷控制方式I/O模塊通過DMA直接控制內(nèi)存I/O模塊有獨立的處理器（有專門的指令集）（I/O通道）I/O模塊進一步發(fā)展成專用I/O計算機（I/O處理器，或I/O通道）10第十頁，共77頁。中斷使用中斷方式的一次磁盤讀過程：操作系統(tǒng)將（帶參數(shù)的）I/O命令寫入控制器寄存器控制器從磁盤驅(qū)動器串行地一位一位地讀一個塊，直到將整塊信息放入控制器的內(nèi)部緩沖區(qū)中控制器做和校驗計算，以核實無讀錯誤發(fā)生，然后控制器產(chǎn)生一個中斷CPU響應中斷，控制轉給操作系統(tǒng)操作系統(tǒng)重復地從控制器緩沖區(qū)中一次一個字節(jié)或一個字地讀這個磁盤塊的信息，并將其送入內(nèi)存中第十一頁，共77頁。DMA使用DMA方式的一次磁盤讀過程：CPU提供被讀取塊磁盤地址、目標存儲地址、要讀取的字節(jié)數(shù)控制器將整塊數(shù)據(jù)讀進緩沖區(qū)，并進行核準校驗控制器按照指定存儲器地址，把指定字節(jié)數(shù)數(shù)據(jù)送入主存（每傳送一個字節(jié)計數(shù)器值減1）控制器引發(fā)中斷，通知操作系統(tǒng)，操作完成12第十二頁，共77頁。DMA框圖13第十三頁，共77頁。DMA與中斷DMA方式與中斷方式的主要區(qū)別：設備與內(nèi)存之間的數(shù)據(jù)傳送的控制者不同中斷方式中是由CPU控制完成的DMA方式中則是由DMA控制器完成的（傳送時不需要占用CPU時間）DMA控制器從CPU中奪取系統(tǒng)控制權，用來在系統(tǒng)總線上與內(nèi)存進行數(shù)據(jù)交換——周期竊取技術(cyclestealing)14第十四頁，共77頁。DMA的周期竊取技術指令周期被掛起CPU暫停一個總線周期，但并不是中斷（不用保存執(zhí)行上下文）15第十五頁，共77頁。DMA的配置方式單總線，分離DMA所有I/O模塊共享一個系統(tǒng)總線DMA模塊代理處理器，使用可編程I/O開銷小但低效一個字節(jié)的傳送需要兩個總線周期（傳送請求+傳送）單總線，I/O集成DMADMA模塊與I/O模塊的數(shù)據(jù)交換脫離系統(tǒng)總線DMA模塊接口多樣I/O總線DMA模塊與I/O模塊的數(shù)據(jù)交換脫離系統(tǒng)總線DMA模塊接口單一，便于擴展16第十六頁，共77頁。DMA的配置方式（續(xù)）17第十七頁，共77頁。11.3操作系統(tǒng)設計問題主要內(nèi)容：I/O機制的設計目標效率——最重要（I/O瓶頸），最關注的是磁盤I/O通用性——統(tǒng)一處理方式，困難處理器看待I/O設備的方式操作系統(tǒng)管理I/O設備和I/O操作的方式邏輯結構——層次結構、模塊化I/O緩沖——為減小系統(tǒng)開銷和提高操作效率，在I/O請求發(fā)出之前/后，就/才開始執(zhí)行數(shù)據(jù)傳送磁盤調(diào)度——磁盤比內(nèi)存慢4個數(shù)量級，磁盤性能與文件系統(tǒng)關系密切18第十八頁，共77頁。I/O軟件設計目標效率（efficiency）與處理器和主存相比，大多數(shù)I/O設備的速度都相當慢多道程序允許在一些進程等待I/O時運行其他進程I/O仍然可能跟不上處理器的速度虛擬內(nèi)存可解決多道程序設計中的內(nèi)存不足問題，但是頁面交換本身又是I/O操作提高效率技術：I/O緩沖、磁盤調(diào)度、磁盤陣列、磁盤高速緩沖等通用性（generality）希望以統(tǒng)一的方式處理所有I/O設備低層例程隱藏設備I/O的大部分細節(jié)，向進程和高層提供使用設備的通用方式，如read,write,open,close,lock,unlock等——采用層次結構和模塊化設計19第十九頁，共77頁。I/O軟件的層次邏輯結構20第二十頁，共77頁。OS設計層次層次名稱對象示例操作13外殼(shell)用戶編程環(huán)境shell語句12用戶進程用戶進程退出、終止、掛起、恢復11目錄目錄創(chuàng)建、刪除、連接、分離、查找、列表10設備外設（如顯示器、鍵盤）打開、關閉、讀、寫9文件系統(tǒng)文件創(chuàng)建、刪除、打開、關閉、讀、寫8通信管道創(chuàng)建、刪除、打開、關閉、讀、寫7虛擬存儲器段、頁讀、寫、取6本地輔存數(shù)據(jù)塊、設備通道讀、寫、分配、空閑5原始進程進程、信號量、就緒列表掛起、恢復、等待、發(fā)信號4中斷中斷處理程序調(diào)用、屏蔽、去屏蔽、重試3過程過程、調(diào)用棧、顯示標記棧、調(diào)用、返回2指令集計算棧、微程序解釋器、標量與數(shù)組數(shù)據(jù)加載、保存、加、減、分支1電路寄存器、門、總線等清空、傳送、激活、求反外部邏輯對象內(nèi)部資源硬件21第二十一頁，共77頁。用戶空間的I/O軟件庫過程中的I/O系統(tǒng)調(diào)用輸入，如gets輸出，如printfSPOOLing系統(tǒng)：用共享設備(如磁盤)模擬獨占設備(如打印機)打印精靈網(wǎng)絡傳輸精靈22第二十二頁，共77頁。假脫機技術SPOOL（SimultaneousPeripheralOperationsOnLine，外部設備同時聯(lián)機操作/假脫機）技術也稱為虛擬設備技術引入：在多道批處理系統(tǒng)中，專門利用一道程序（SPOOLing程序）來完成對設備的I/O操作,而無需使用外圍I/O處理機23第二十三頁，共77頁。假脫機技術（續(xù)）原理：設置兩級緩沖區(qū)：內(nèi)存緩沖區(qū)和快速外存上的緩沖池，后者可以暫存多批I/O操作的較多數(shù)據(jù)應用程序進行I/O操作時，只是和SPOOLing程序交換數(shù)據(jù)，稱為“虛擬I/O”——實際上是對SPOOLing程序的緩沖池進行I/O操作SPOOLing程序和外設進行數(shù)據(jù)交換，稱為“實際I/O”——可以緩沖24第二十四頁，共77頁。假脫機技術（續(xù)）優(yōu)點：高速虛擬I/O操作實現(xiàn)對獨享設備的共享舉例：打印機設備和可由打印機管理器管理的打印作業(yè)隊列。在Windows中，應用程序直接向針式打印機輸出需要15分鐘，而向打印作業(yè)隊列輸出只需要1分鐘，此后用戶可以關閉應用程序而轉入其他工作，在以后適當?shù)臅r候由打印機管理器完成15分鐘的打印輸出而無需用戶干預25第二十五頁，共77頁。邏輯I/O（設備無關的I/O軟件）大部分I/O軟件是與設備無關的設備驅(qū)動程序與設備無關軟件的確切界限依賴于具體系統(tǒng)設備無關I/O軟件的常見功能：設備驅(qū)動程序的統(tǒng)一接口：實現(xiàn)一般設備都需要的I/O功能，向用戶層軟件提供統(tǒng)一接口設備命名：把設備的符號名映射到相應的設備驅(qū)動程序上設備保護：防止無權限用戶訪問/存取設備提供一個與設備無關的塊大小：屏蔽“不同設備基本單位可以不同”這一事實（不同的磁盤扇區(qū)尺寸可以不同，不同的字符設備傳輸單位也可以不同），向較高層軟件提供統(tǒng)一塊大小的抽象設備26第二十六頁，共77頁。邏輯I/O（續(xù)）緩沖：通過緩沖區(qū)來協(xié)調(diào)設備的讀寫速度和用戶進程的讀寫速度塊設備的存儲分配：磁盤空閑塊管理分配和釋放獨占設備：對獨占設備的使用請求進行檢查錯誤報告：報告設備驅(qū)動程序無法處理的出錯信息設備I/O邏輯設備與物理設備間的過渡協(xié)調(diào)機構用戶命令到設備操作序列的轉換I/O緩沖：提高I/O效率27第二十七頁，共77頁。調(diào)度和控制物理設備控制實體，直接面對硬件設備的控制細節(jié)通常體現(xiàn)為設備驅(qū)動程序并發(fā)I/O訪問調(diào)度設備控制和狀態(tài)維護中斷處理設備驅(qū)動程序處理一種或一類設備類型只存在細微差別的不同品牌終端可使用同一個終端驅(qū)動程序性能差別很大的終端應該使用不同的終端驅(qū)動程序28第二十八頁，共77頁。調(diào)度和控制（續(xù)）設備驅(qū)動程序工作過程：接收來自邏輯I/O軟件的抽象請求（如“讀第n塊”），將其轉換成具體的形式（如計算第n塊的實際位置、檢查磁頭臂等）執(zhí)行這個請求，即通過設備控制器中的寄存器向控制器發(fā)出I/O命令并監(jiān)督執(zhí)行在I/O操作完成后（阻塞或不阻塞），進行錯誤檢查，若無錯則將數(shù)據(jù)傳送到與設備無關的軟件層，否則出錯處理（重試、忽略或報警等）返回狀態(tài)信息第二十九頁，共77頁。I/O軟件的層次邏輯結構30第三十頁，共77頁。11.4I/O緩沖緩沖的原因：進程必須要等待I/O操作完成才能繼續(xù)（執(zhí)行速度慢）執(zhí)行I/O操作期間一些頁面必須保留在主存（干擾了OS的交換決策）緩沖技術可提高外設利用率，盡可能使外設處于忙狀態(tài)限制：進程的I/O請求不能超過外設的處理能力緩沖區(qū)位置：內(nèi)存、控制器或外設——多級緩沖機制31第三十一頁，共77頁。I/O緩沖面向塊的（block-oriented）設備信息保存在固定大小的塊中傳送必須以塊為單位如磁盤、固態(tài)硬盤、U盤面向流的（stream-oriented）設備信息以字節(jié)流的形式傳送如終端、打印機、通信端口、鼠標及多數(shù)的其他非輔存設備32第三十二頁，共77頁。I/O緩沖單方向緩沖單緩沖(singlebuffer)

雙緩沖(doublebuffer)環(huán)形緩沖(circularbuffer)雙方向緩沖緩沖池(bufferpool)33第三十三頁，共77頁。單緩沖(SingleBuffer)OS為一個I/O請求在內(nèi)存分配一個緩沖區(qū)面向塊的：輸入傳送到緩沖區(qū)需要時緩沖區(qū)中的塊被移到用戶空間再移入另外一塊到緩沖區(qū)——預讀(readahead)面向流的：每次傳送一行/字節(jié)（緩沖區(qū)用來保存一行/字節(jié)的輸入/輸出）用戶每次輸入一行/字節(jié)，并以回車表示一行/字節(jié)的結束到終端的輸出一次一行/字節(jié)34第三十四頁，共77頁。雙緩沖（DoubleBuffer）使用兩個而不是一個系統(tǒng)緩沖區(qū)OS清空或填充一個緩沖區(qū)時，進程可以傳送數(shù)據(jù)到另外一個緩沖區(qū)（或從另外一個緩沖區(qū)取數(shù)據(jù)）循環(huán)緩沖（CircularBuffer）使用超過兩個的緩沖區(qū)每個緩沖區(qū)是循環(huán)緩沖區(qū)的一個單元使I/O操作能跟上（可能爆發(fā)式地執(zhí)行大量I/O的）進程的速度有限緩沖區(qū)的生產(chǎn)者/消費者模型35第三十五頁，共77頁。緩沖池(bufferpool)緩沖區(qū)隊列：空閑緩沖區(qū)輸入緩沖區(qū)輸出緩沖區(qū)操作：設備輸入、CPU讀入，CPU寫出、設備輸出這些操作互斥訪問各個緩沖區(qū)隊列緩沖區(qū)整體利用率高36第三十六頁，共77頁。11.5磁盤調(diào)度磁盤的物理結構磁盤是將若干個涂有鐵磁的圓形金屬或塑料片組合在一起構成的盤組，每個圓盤有上下兩個盤面每個盤面有一個讀寫磁頭，讀寫磁盤時，磁頭通過存取臂在盤面上移動，而盤體繞中心軸高速旋轉37第三十七頁，共77頁。磁盤硬件盤組旋轉一周，相對固定的磁頭在盤面上的移動軌跡稱為磁道（一個圓），各個盤面上半徑相同的磁道合起來構成一個柱面一個磁道又被分成許多扇區(qū)，一般每條磁道上扇區(qū)數(shù)目在8至32之間，每個扇區(qū)的字節(jié)數(shù)相同（一般為512）38第三十八頁，共77頁。磁盤硬件讀寫一個磁盤塊：移臂/尋道（將存取臂移動到相應柱面上）旋轉（等待相應扇區(qū)旋轉到磁頭下）實際傳輸尋道時間占一次磁盤讀寫時間的大部分磁盤的一個重要特性：控制器是否支持重疊尋道（overlappedseeks），即是否可以同時控制兩個或多個存取臂驅(qū)動器同時進行尋道39第三十九頁，共77頁。11.5磁盤調(diào)度尋道時間是影響磁盤性能最主要的因素當一個磁盤有多個I/O請求時，可按一定的調(diào)度算法對這些請求的服務順序進行調(diào)整，以減少平均尋道時間，同時也要遵循“公平”的原則等待設備等待通道尋道旋轉延遲數(shù)據(jù)傳送40第四十頁，共77頁。磁盤調(diào)度算法先進先出（FIFO=first-in-first-out）按訪問請求到達的先后次序服務簡單，公平一般效率不高，多個進程時性能接近隨機調(diào)度（randomscheduling，RS）相鄰兩次請求可能會造成最內(nèi)到最外的柱面尋道，使磁頭反復移動，增加了服務時間，對機械也不利41第四十一頁，共77頁。磁盤調(diào)度算法（續(xù)）先進先出（FIFO）示例假設磁頭初始位置是100，磁盤訪問請求柱面序列：55、58、39、18、90、160、150、38、184磁頭移動總距離（道數(shù)）：45+3+19+21+72+70+10+112+146=498平均尋道長度：498/9=55.3342第四十二頁，共77頁。磁盤調(diào)度算法（續(xù)）優(yōu)先級（Priority,PRI）目標并不在于優(yōu)化磁盤效率而是滿足操作系統(tǒng)的其他目的短的批作業(yè)可能具有較高優(yōu)先級，從而提供較小的交互響應時間長作業(yè)可能要等待過長時間后進先出（Last-in,first-out，LIFO）有利于事務處理系統(tǒng)設備被分配給最近的使用者，因此移臂幅度可能非常小（局部性原理）可能產(chǎn)生餓死（作業(yè)可能永遠都不能處于隊列頭）43第四十三頁，共77頁。磁盤調(diào)度算法（續(xù)）最短服務時間優(yōu)先（Shortest-Service-Time-First，SSTF）優(yōu)先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優(yōu)先改善了磁盤平均服務時間可能造成某些訪問請求長期等待得不到服務44第四十四頁，共77頁。磁盤調(diào)度算法（續(xù)）最短服務時間優(yōu)先（SSTF）示例順序：90、58、55、39、38、18、90、150、160、184磁頭移動總距離（道數(shù)）：10+32+3+16+1+20+132+10+24=248平均尋道長度：248/9=27.5545第四十五頁，共77頁。磁盤調(diào)度算法（續(xù)）電梯算法/掃描算法（SCAN）當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務，然后判斷該方向上是否還有訪問請求，如果有則繼續(xù)掃描；否則改變移動方向，并為經(jīng)過的訪問請求服務，如此反復克服了最短服務時間優(yōu)先（請求可能會長期等待）的缺點存在偏愛靠內(nèi)&外道服務的缺點46第四十六頁，共77頁。磁盤調(diào)度算法（續(xù)）掃描算法（SCAN）示例順序：150、160、184、90、58、55、39、38、18，假設原方向是磁道遞增方向磁頭移動總距離（道數(shù)）：50+10+24+94+32+3+16+1+20=250平均尋道長度：250/9=27.7847第四十七頁，共77頁。磁盤調(diào)度算法單向掃描算法（C-SCAN=circularSCAN，循環(huán)掃描）從有讀寫請求的最低編號柱面開始遞增掃描，途中按照柱面次序處理訪問請求；處理完最高編號柱面上的請求后，存取臂立即帶動讀寫磁頭快速返回到有讀寫請求的最低編號柱面，返回時不處理任何訪問請求；返回后可再次遞增掃描克服了SCAN偏愛靠里、外服務的缺點中負載或重負載時性能比掃描算法好磁盤調(diào)度算法（續(xù)）48第四十八頁，共77頁。磁盤調(diào)度算法（續(xù)）單向掃描算法（C-SCAN）示例順序：150、160、184、18、38、39、55、58、90，假設原方向是磁道遞增方向磁頭移動總距離（道數(shù)）：50+10+24+166+20+1+16+3+32=322平均尋道長度：322/9=35.7849第四十九頁，共77頁。磁盤調(diào)度算法N步掃描算法（N-step-SCAN）將磁盤請求隊列分成若干個長度為N的子隊列每一次SCAN處理一個子隊列新來的請求必須加入到?jīng)]在處理的子隊列中克服了SCAN偏愛最近作業(yè)（磁頭臂粘性）的缺點特例：FSCAN兩個隊列開始時所有請求在一個隊列中，另一個隊列用來添加新請求磁盤調(diào)度算法（續(xù)）50第五十頁，共77頁。11.6RAIDRAID

(RedundantArrayofIndependent/InexpensiveDisks，獨立/廉價磁盤冗余陣列)，分為7個級別（RAID0至6）一般特點：把多個物理磁盤組織在一起，作為一個邏輯驅(qū)動器→提供磁盤跨越功能數(shù)據(jù)分成多個數(shù)據(jù)塊，分布在陣列的各個物理磁盤上→可以并行寫入/讀出多個磁盤，提高訪問磁盤的速度利用磁盤冗余可進行鏡像或校驗操作等→提高意外恢復能力51第五十一頁，共77頁。RAID0整個邏輯盤的數(shù)據(jù)被分散分布（通過陣列管理軟件）在多個(至少兩個)物理盤上，并行讀寫沒有冗余能力【注】strip(條帶)可以是物理塊、扇區(qū)或其他單位52第五十二頁，共77頁。RAID1把一個磁盤的數(shù)據(jù)鏡像到另一個磁盤上，可從任一磁盤讀數(shù)據(jù)，數(shù)據(jù)同時更新到兩個磁盤兩個盤上實施，數(shù)據(jù)冗余，數(shù)據(jù)安全性最好磁盤利用率最低（50%）第五十三頁，共77頁。RAID2并行讀寫：所有磁盤都參與每一次I/O請求（所有磁頭任何時刻都處于同一位置）通過漢明碼（Hammingcode，一位糾錯，兩位檢錯）實現(xiàn)數(shù)據(jù)冗余（需要的磁盤數(shù)少于RAID1）僅用于錯誤率高的環(huán)境中（不太實用）54第五十四頁，共77頁。RAID3只采用一個冗余磁盤存儲校驗數(shù)據(jù)校驗數(shù)據(jù)：P(b)=b0⊕b1⊕b2⊕b3丟失數(shù)據(jù)可從校驗數(shù)據(jù)及其他數(shù)據(jù)恢復：b1=b0⊕P(b)⊕b2⊕b3數(shù)據(jù)速率高，但同時只能處理一個I/O請求55第五十五頁，共77頁。RAID4獨立讀寫：陣列中每個磁盤的存取各自獨立進行，從而可同時處理多個I/O請求校驗基于數(shù)據(jù)塊進行（假設更新B1）：P(B0~3)=B0⊕B1⊕B2⊕B3P(B0~3)’=B0⊕B1’⊕B2⊕B3=B0⊕B1’⊕B2⊕B3⊕B1⊕B1=P(B0~3)⊕B1⊕B1’56第五十六頁，共77頁。RAID5類似RAID4，但校驗數(shù)據(jù)分布在各個磁盤上可避免RAID4中可能出現(xiàn)的瓶頸——校驗磁盤57第五十七頁，共77頁。RAID6采用兩種不同的數(shù)據(jù)校驗方法可以處理有兩個磁盤出錯的情形數(shù)據(jù)可靠性極高寫性能損失嚴重58第五十八頁，共77頁。RAID級別的比較類別級別說明磁盤需求數(shù)據(jù)可用性大I/O數(shù)據(jù)量傳輸能力小I/O請求率條帶0非冗余N低于單個磁盤很高讀寫都高鏡像1被鏡像2N高于2~5、低于6讀高于0，寫與0相近讀為0的2倍，寫~0并行訪問2漢明碼冗余N+m高于0可比最高0的2倍3交錯位奇偶N+1獨立訪問4交錯塊奇偶N+1讀與0相近，寫（4明顯）慢于0讀與0相近，寫（4明顯）慢于05交錯塊分布式奇偶校驗N+16交錯塊雙重分布式奇偶N+2最高讀與0相近，寫慢于5讀與0相近，寫明顯慢于559第五十九頁，共77頁。11.7磁盤高速緩存(DiskCache)磁盤緩存：內(nèi)存中的磁盤緩沖區(qū)，是磁盤中某些扇區(qū)的副本處理一個請求：若數(shù)據(jù)在cache中，則不需要磁盤數(shù)據(jù)傳輸，從cache傳送給調(diào)用程序（復制或使用共享存儲空間）若數(shù)據(jù)不在cache中，則從磁盤讀并添加到cache中60第六十頁，共77頁。磁盤緩沖替換算法替換策略LRU(LeastRecentlyUsed，最近最少使用)：替換cache中未被訪問的時間最長的塊，最常用cache是一個棧，最近訪問過的塊在棧頂（通過棧指針實現(xiàn)塊的移動）LFU(LeastFrequentlyUsed，最不常用)：替換被訪問次數(shù)最少的塊cahce中的每個塊關聯(lián)一個計數(shù)器，替換計數(shù)器最小的塊壞置換算法（局部性原理）基于頻率的替換算法（frequency-basedreplacement）及其改進61第六十一頁，共77頁。磁盤緩沖替換算法（續(xù)）磁盤訪問的特征——密集性/集中性可能有些塊在短期內(nèi)被訪問很多次，而之后則再也用不著，則計數(shù)器的變化就不能反映當前的引用情況需要考慮磁盤訪問的這種密集特征，對密集引用計數(shù)——基于頻率的替換LRU算法

LFU算法基于頻率的替換62第六十二頁，共77頁。基于頻率的替換第一個版本：把LRU算法中的特殊棧分成二部分：新區(qū)、老區(qū)每個塊增加一個引用計數(shù)器，其中，新加進來的塊計數(shù)器count=1cache命中：把對應的塊移到新區(qū)前端；若原來在新區(qū)，計數(shù)器不變；若原來在老區(qū)，則count加1cache失誤：替換老區(qū)中count最小的塊63第六十三頁，共77頁。基于頻率的替換（續(xù)）第一個版本存在問題：一個短期內(nèi)頻繁訪問的塊留在新區(qū)內(nèi)，且count一直是1轉到老區(qū)后，這個塊將很快被替換掉64第六十四頁，共77頁。基于頻率的替換（續(xù)）第二個版本：使用三個區(qū)：新區(qū)、中間區(qū)、老區(qū)塊的年齡變化：新區(qū)－>中間區(qū)—>老區(qū)中間區(qū)避免新讀入的緩存塊在第一次出新區(qū)域時馬上被置換，有一個過渡期65第六十五頁，共77頁。RAM盤RAM(RandomAccessMemory，隨機存取存儲器)盤即是用一部分內(nèi)存模擬的磁盤具有立即存取的優(yōu)點，對于頻繁讀取磁盤的應用程序及文件（如字庫文件、圖形圖像程序文件、字處理程序等），將信息存儲在RAM盤上能起到加速工作的效果例，在config.sys中設置RAM盤：如：DEVICE=C:\DOS\RAMDRIVE.sys/E1024為了提高RAM盤使用效率，可以改變一個環(huán)境變量TEMP，將它設為RAM的目錄RAM盤存在于內(nèi)存之中，使用中注意存盤66第六十六頁，共77頁。11.8UnixSVR4I/O每個I/O設備關聯(lián)一個特殊文件(/dev/xxx)使用普通read/write命令訪問設備設備分為字符設備和塊設備兩類I/O類型有緩沖——系統(tǒng)緩沖區(qū)高速緩存——本質(zhì)上是一個磁盤高速緩存，與用戶進程空間的數(shù)據(jù)傳送通常使用DMA字符隊列——似生產(chǎn)者/消費者模型，字符隊列只能被讀一次無緩沖（包括DMA機制）——在I/O模塊和進程之間直接傳送進程被鎖定在內(nèi)存而不能換出I/O設備被進程綁定而不能被其他進程使用67第六十七頁，共77頁。UnixI/O為管理緩沖區(qū)高速緩存，需維護：自由列表——高速緩存中所有可用于分配的存儲槽（緩沖區(qū)，可保存一個磁盤扇區(qū)）設備列表——列出當前與每個磁盤關聯(lián)的緩沖區(qū)驅(qū)動程序I/O隊列——正在某個特定設備上進行或等待I/O的緩沖區(qū)68第六十八頁，共77頁。Unix中的設備I/O設備類型無緩沖I/O緩沖區(qū)高速緩存字符隊列磁盤驅(qū)動器√√磁帶驅(qū)動器√√終端√通信線路√打印機√√69第六十九頁，共77頁。11.9LinuxI/OI/O核心機制的實現(xiàn)似UnixSRV4每個I/O設備關聯(lián)一個特殊文件設備分為：塊設備、字符設備、網(wǎng)絡設備磁盤調(diào)度算法電梯調(diào)度程序（elevatorscheduler）——2.4（2001.1.4）默認，排序隊列與合并功能最后期限調(diào)度程序（deadlineI/Oscheduler）——2.6（2003.12.17）新增，使用三個隊列預期I/O調(diào)度程序（anticipatoryI/Oscheduler）——2.6新增，對最后期限調(diào)度的補充，在請求被分派前，增加延遲以符合局部性原理70第七十頁，共77頁。Linux頁面緩存2.2（1999.1.25）及早期版本內(nèi)核維護一個頁面緩存，用于普通文件系統(tǒng)中的讀寫緩存或虛擬內(nèi)存中的頁面緩存內(nèi)核還維護了一個單獨的緩沖區(qū)高速緩存，用于塊I/O2.4及以后版本，頁面高速緩存用于所有的磁盤與內(nèi)存間的數(shù)據(jù)交換頁面緩存的優(yōu)勢在需要將修改過的“臟”頁面寫回磁盤時，可以適當排序臟頁面，以提高寫回的效率“臟”頁面寫回條件空閑內(nèi)存低于指定閾值（內(nèi)核會減少頁面緩存）“臟”頁面駐留時間高于指定閾值71第七十一頁，共77頁。11.10WindowsI/OWindows中I/O管理程序（manager）負責處理所有系統(tǒng)I/O并提供（驅(qū)動程序調(diào)用的）統(tǒng)一接口基本I/O機制——I/O管理程序與如下4種類型的內(nèi)核組件緊密協(xié)調(diào)工作：高速緩存管理程序文件系統(tǒng)驅(qū)動程序網(wǎng)絡驅(qū)動程序硬件設備驅(qū)動程序72第七十二頁，共77頁。Windows的I/O操作模式異步操作模式——用于優(yōu)化