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

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

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

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

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

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

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

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

）

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

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

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

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