第八章第八章 設(shè)備與設(shè)備與I/O管理管理n設(shè)備及其分類設(shè)備及其分類n設(shè)備的物理特性設(shè)備的物理特性nIO傳輸方式（查詢、中斷、通道、傳輸方式（查詢、中斷、通道、DMA）n設(shè)備分配與去配設(shè)備分配與去配n設(shè)備驅(qū)動(dòng)設(shè)備驅(qū)動(dòng)n設(shè)備調(diào)度設(shè)備調(diào)度n緩沖技術(shù)緩沖技術(shù)n輸入輸出進(jìn)程輸入輸出進(jìn)程nRAID技術(shù)技術(shù)n虛擬設(shè)備虛擬設(shè)備8.1 設(shè)備及其分類設(shè)備及其分類n用途用途n存儲(chǔ)型設(shè)備存儲(chǔ)型設(shè)備n磁盤，磁帶，光盤磁盤，磁帶，光盤nIO型設(shè)備型設(shè)備n掃描儀，打印機(jī)，掃描儀，打印機(jī)，mouse，keyboard，monitor，n網(wǎng)絡(luò)設(shè)備網(wǎng)絡(luò)設(shè)備n網(wǎng)卡，交換機(jī)，網(wǎng)卡，交換機(jī)，etc.8.1 設(shè)備及其分類設(shè)備及其分類n管理管理n共享型設(shè)備（塊型）共享型設(shè)備（塊型）n多個(gè)進(jìn)程的多個(gè)進(jìn)程的IO操作以塊為單位可以交叉操作以塊為單位可以交叉n獨(dú)占型設(shè)備（塊型）獨(dú)占型設(shè)備（塊型）n多個(gè)進(jìn)程的多個(gè)進(jìn)程的IO操作以塊為單位不宜交叉操作以塊為單位不宜交叉n獨(dú)占型設(shè)備（字符型）獨(dú)占型設(shè)備（字符型）n多個(gè)進(jìn)程的多個(gè)進(jìn)程的IO操作以字符為單位不能交叉操作以字符為單位不能交叉IO設(shè)備的物理特性設(shè)備的物理特性傳輸一字節(jié)發(fā)生一次中斷傳輸一字節(jié)發(fā)生一次中斷存儲(chǔ)設(shè)備的物理特性存儲(chǔ)設(shè)備的物理特性磁帶的物理特性磁帶的物理特性頭標(biāo)頭標(biāo) 信息塊信息塊 信息塊信息塊 信息塊信息塊 .尾標(biāo)尾標(biāo)間隙間隙操作：反繞，正向查找，反向查找，讀，寫，操作：反繞，正向查找，反向查找，讀，寫，地址：一維地址：一維文件：順序結(jié)構(gòu)（一個(gè)文件占若干連續(xù)塊）文件：順序結(jié)構(gòu)（一個(gè)文件占若干連續(xù)塊）8.2 設(shè)備的物理特性.磁盤組的物理特性磁盤組的物理特性.盤面盤面0盤面盤面1盤面盤面2盤面盤面m-1扇區(qū)扇區(qū)1扇區(qū)扇區(qū)0扇區(qū)扇區(qū)n-1柱面柱面0柱面柱面l-1.引臂柱面號(hào)柱面號(hào)i盤面號(hào)盤面號(hào)j扇區(qū)號(hào)扇區(qū)號(hào)k塊號(hào)塊號(hào)b（一維地址）一維地址）（三維地址）（三維地址）編址方法：使相鄰塊物理上最近編址方法：使相鄰塊物理上最近例子：例子：l=2;m=3;n=3柱面號(hào)：柱面號(hào)：0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1盤面號(hào)：盤面號(hào)：0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2扇區(qū)號(hào)：扇區(qū)號(hào)：0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2塊塊 號(hào)：號(hào)：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17三維地址三維地址一維地址：一維地址：b=i m n+j n+k一維地址一維地址三維地址：三維地址：i=b(m n)j=b mod(m n)n k=b mod(m n)mod n未考慮讀寫延遲的扇區(qū)編號(hào)：未考慮讀寫延遲的扇區(qū)編號(hào)：扇區(qū)扇區(qū)0扇區(qū)扇區(qū)7扇區(qū)扇區(qū)6扇區(qū)扇區(qū)5扇區(qū)扇區(qū)4扇區(qū)扇區(qū)3扇區(qū)扇區(qū)2扇區(qū)扇區(qū)1扇區(qū)扇區(qū)0扇區(qū)扇區(qū)7扇區(qū)扇區(qū)3扇區(qū)扇區(qū)6扇區(qū)扇區(qū)2扇區(qū)扇區(qū)5扇區(qū)扇區(qū)1扇區(qū)扇區(qū)4考慮讀寫延遲的扇區(qū)編號(hào)考慮讀寫延遲的扇區(qū)編號(hào)(單交錯(cuò)單交錯(cuò))：扇區(qū)扇區(qū)0扇區(qū)扇區(qū)5扇區(qū)扇區(qū)2扇區(qū)扇區(qū)7扇區(qū)扇區(qū)4扇區(qū)扇區(qū)1扇區(qū)扇區(qū)6扇區(qū)扇區(qū)3考慮讀寫延遲的扇區(qū)編號(hào)考慮讀寫延遲的扇區(qū)編號(hào)(雙交錯(cuò)雙交錯(cuò))：光盤的物理特性:讀取原理:pit/land 螺旋線,22188圈(展開5.6km),內(nèi)側(cè)轉(zhuǎn)速:530轉(zhuǎn)/分;外側(cè)轉(zhuǎn)速:200轉(zhuǎn)/分(密度均勻,讀取速度均勻)DataECCP14個(gè)bit構(gòu)成一個(gè)symble42個(gè)symble構(gòu)成一個(gè)frame98個(gè)frame構(gòu)成一個(gè)sectorSector2352bytes588bits的frame各包含24字節(jié)Preamble:16bytes,前12bytes為:00FFFFFFFFFFFFFFFFFFFF00后隨3bytes扇區(qū)編號(hào),最后字節(jié)為mode2048字節(jié)288字節(jié)8.3 I/O 傳輸方式nIO操作演變歷史操作演變歷史n程序查詢方式程序查詢方式 (programmed IO)(polling)nCPU and Device can not work in parallel n中斷方式中斷方式 (interrupt)nCPU and device can work in parallel,too many interrupts for CPUn通道方式通道方式 (channel)nspecial processor for dealing with io operationsn直接內(nèi)存方式直接內(nèi)存方式(DMA)nDMA controller in charge of block io8.3.1 程序控制查詢方式程序控制查詢方式CPU啟動(dòng)設(shè)備啟動(dòng)設(shè)備完成完成FT缺點(diǎn)缺點(diǎn):處理機(jī)與設(shè)備串行工作處理機(jī)與設(shè)備串行工作;消耗大量處理機(jī)時(shí)間消耗大量處理機(jī)時(shí)間.8.3.2 中斷驅(qū)動(dòng)方式中斷驅(qū)動(dòng)方式nCPUn計(jì)算計(jì)算n啟動(dòng)設(shè)備啟動(dòng)設(shè)備n計(jì)算計(jì)算nn計(jì)算計(jì)算n中斷處理中斷處理n計(jì)算計(jì)算設(shè)備設(shè)備:工工作作特點(diǎn)特點(diǎn):CPU與設(shè)備并行工作與設(shè)備并行工作 設(shè)備多時(shí)對(duì)設(shè)備多時(shí)對(duì)CPU打擾多打擾多8.3.3 DMA方式 數(shù)據(jù)傳輸數(shù)據(jù)傳輸CPUDMA控制器控制器內(nèi)存內(nèi)存地地 址址計(jì)計(jì) 數(shù)數(shù)控控 制制緩沖緩沖磁盤磁盤 中斷中斷 DMA請求請求總線總線磁盤磁盤控制器控制器 回答回答 DMA編程編程8.3.3 DMA方式.nCPU通過設(shè)置DMA控制器實(shí)現(xiàn)DMA編程，同時(shí)啟動(dòng)磁盤控制器由磁盤讀入數(shù)據(jù)至內(nèi)部緩沖區(qū)并進(jìn)行和校驗(yàn)；nDMA控制器向磁盤控制器發(fā)出讀請求，并將內(nèi)存地址放在地址總線上；n磁盤控制器將字節(jié)傳到內(nèi)存指定單元；n磁盤控制器向DMA控制器發(fā)送回答；nDMA控制器將內(nèi)部地址寄存器加1同時(shí)將記數(shù)減1，重復(fù)上述過程直至計(jì)數(shù)值為0，此時(shí)DMA控制器向CPU發(fā)出中斷信號(hào).8.3.4 通道方式通道方式n通道通道n負(fù)責(zé)負(fù)責(zé)IO操作的處理機(jī)操作的處理機(jī)n指令系統(tǒng)指令系統(tǒng)n基本操作：讀、寫、控制、轉(zhuǎn)移、結(jié)束基本操作：讀、寫、控制、轉(zhuǎn)移、結(jié)束n指令格式：（操作碼，傳輸量，特征位，地址）指令格式：（操作碼，傳輸量，特征位，地址）n運(yùn)控部件運(yùn)控部件nCAW，CCW，CSW，CDWn存儲(chǔ)區(qū)域（與存儲(chǔ)區(qū)域（與CPU共用內(nèi)存共用內(nèi)存,通道內(nèi)有緩沖區(qū)）通道內(nèi)有緩沖區(qū)）n通道程序，通道程序，IO數(shù)據(jù)（數(shù)據(jù)（channel does have its buffers）通道程序執(zhí)行過程：通道程序執(zhí)行過程：按按CAW取通道命令取通道命令CCW（CAW）+1 CAW是通道結(jié)束命令是通道結(jié)束命令執(zhí)行此命令執(zhí)行此命令F向向CPU發(fā)中斷發(fā)中斷一個(gè)通道程序可以控制若干設(shè)備進(jìn)行多次一個(gè)通道程序可以控制若干設(shè)備進(jìn)行多次IO傳輸。傳輸。T通道類型通道類型n字節(jié)多路通道字節(jié)多路通道(byte multiplexer channel)n 多個(gè)非分配型子通道，連接低速外圍設(shè)備多個(gè)非分配型子通道，連接低速外圍設(shè)備n數(shù)組選擇通道數(shù)組選擇通道(block selector channel)n 一個(gè)分配型子通道，連接多臺(tái)高速設(shè)備一個(gè)分配型子通道，連接多臺(tái)高速設(shè)備n數(shù)組多路通道數(shù)組多路通道(block multiplexer channel)n 多個(gè)非分配型子通道，連接多臺(tái)高速設(shè)備多個(gè)非分配型子通道，連接多臺(tái)高速設(shè)備設(shè)備、通道、內(nèi)存連接設(shè)備、通道、內(nèi)存連接選擇通道選擇通道磁盤字節(jié)多路通道字節(jié)多路通道打印機(jī)打印機(jī)輸入機(jī)輸入機(jī)內(nèi)存儲(chǔ)器內(nèi)存儲(chǔ)器處理機(jī)處理機(jī)磁帶數(shù)組多路通道數(shù)組多路通道8.4 設(shè)備的分配與去配設(shè)備的分配與去配n獨(dú)占型設(shè)備的分配與去配獨(dú)占型設(shè)備的分配與去配n塊型獨(dú)占?jí)K型獨(dú)占n字符型獨(dú)占字符型獨(dú)占n共享型設(shè)備的分配與去配共享型設(shè)備的分配與去配n塊型共享塊型共享數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)設(shè)備控制塊設(shè)備控制塊(UCB)通道控制塊通道控制塊(CCB)設(shè)備標(biāo)識(shí)設(shè)備標(biāo)識(shí)設(shè)備狀態(tài)設(shè)備狀態(tài)占有設(shè)備進(jìn)程占有設(shè)備進(jìn)程通道標(biāo)識(shí)通道標(biāo)識(shí)通道狀態(tài)通道狀態(tài)通道類型通道類型占有通道進(jìn)程占有通道進(jìn)程系統(tǒng)設(shè)備表系統(tǒng)設(shè)備表(SDT)設(shè)備類設(shè)備類 總數(shù)總數(shù) 設(shè)備等待隊(duì)列設(shè)備等待隊(duì)列 UCB表指針表指針 lp m Sm UCBUCBUCB 獨(dú)占型設(shè)備的分配與去配獨(dú)占型設(shè)備的分配與去配用戶使用獨(dú)占型設(shè)備活動(dòng)：用戶使用獨(dú)占型設(shè)備活動(dòng)：申請，使用，使用，申請，使用，使用，使用，釋放，使用，釋放 申請：申請：(1)根據(jù)設(shè)備類查根據(jù)設(shè)備類查SDT表表 (2)P(Sm)(3)查查UCB表找一空閑設(shè)備并分配表找一空閑設(shè)備并分配 使用：使用：(1)IO傳輸傳輸 釋放：釋放：(1)找找SDT表對(duì)應(yīng)入口表對(duì)應(yīng)入口 (2)查查UCB表，去配表，去配 (3)V(Sm)l共享型設(shè)備的分配與去配共享型設(shè)備的分配與去配用戶使用共享型設(shè)備活動(dòng)用戶使用共享型設(shè)備活動(dòng)使用，使用，使用，使用，使用，使用特征特征來自文件系統(tǒng)；來自文件系統(tǒng)；每次讀（寫）一塊；每次讀（寫）一塊；通常經(jīng)過緩沖；通常經(jīng)過緩沖；排隊(duì)優(yōu)化。排隊(duì)優(yōu)化。使用使用IO操作操作8.5 設(shè)備驅(qū)動(dòng)設(shè)備驅(qū)動(dòng)n通道程序通道程序nCCW指令序列指令序列n靜態(tài)編制或動(dòng)態(tài)生成靜態(tài)編制或動(dòng)態(tài)生成n設(shè)備啟動(dòng)設(shè)備啟動(dòng)n通道啟動(dòng)通道啟動(dòng)n中斷處理中斷處理n通道向通道向CPU發(fā)的中斷發(fā)的中斷8.5 設(shè)備驅(qū)動(dòng)設(shè)備驅(qū)動(dòng)設(shè)備設(shè)備CAWCCWCDWCSWCCW1CCW2CCWi.CCWn數(shù)據(jù)區(qū)數(shù)據(jù)區(qū).形成通道程序形成通道程序.地址地址CAW.啟動(dòng)通道啟動(dòng)通道.中斷處理中斷處理.啟動(dòng)啟動(dòng)中斷中斷內(nèi)存內(nèi)存CPU通道通道 8.6 設(shè)備調(diào)度設(shè)備調(diào)度n優(yōu)化服務(wù)順序優(yōu)化服務(wù)順序n考慮因素考慮因素n公平性公平性n防止餓死防止餓死n高效性高效性n減少磁盤引臂移動(dòng)量減少磁盤引臂移動(dòng)量磁盤引臂調(diào)度磁盤引臂調(diào)度(disk head scheduling)n先到先先到先服務(wù)（服務(wù)（FCFS）n請求序列：請求序列：130，42，180，15，108，68，970 15 42 53 68 97 108 130 180 199移動(dòng)量移動(dòng)量:(130-53)+(130-42)+(180-42)+(180-15)+(108-15)+(108-68)+(97-68)=630磁盤引臂調(diào)度磁盤引臂調(diào)度(disk head scheduling)n最短尋找時(shí)間優(yōu)先（最短尋找時(shí)間優(yōu)先（SSTF）n請求序列：請求序列：130，42，180，15，108，68，970 15 42 53 68 97 108 130 180 199移動(dòng)量移動(dòng)量:(53-42)+(180-42)+(180-15)=314lSCAN（LOOK）請求序列：請求序列：130，42，180，15，108，68，97SCAN移動(dòng)量移動(dòng)量:(53-0)+(180-0)=233LOOK移動(dòng)量移動(dòng)量:(53-15)+(180-15)=2030 15 42 53 68 97 108 130 180 199 Look ScanlC-SCAN（C-LOOK）請求序列：請求序列：130，42，180，15，108，68，97特點(diǎn)：所有磁道地位最長等待時(shí)間相同特點(diǎn)：所有磁道地位最長等待時(shí)間相同0 15 42 53 68 97 108 130 180 199 C-Look C-Scan8.7 緩沖技術(shù)n設(shè)備設(shè)備處理數(shù)據(jù)到達(dá)與離開速度不一致所采用的技術(shù)處理數(shù)據(jù)到達(dá)與離開速度不一致所采用的技術(shù)。nBuffering vs.Cachingnbuffering:one data copyncaching:multiple data copy(slow多多,fast少少)n硬緩沖與軟緩沖硬緩沖與軟緩沖 n硬緩沖區(qū)通常設(shè)在設(shè)備中硬緩沖區(qū)通常設(shè)在設(shè)備中 n軟緩沖區(qū)通常設(shè)在內(nèi)存系統(tǒng)空間中軟緩沖區(qū)通常設(shè)在內(nèi)存系統(tǒng)空間中 n私用緩沖與公共緩沖私用緩沖與公共緩沖 n一個(gè)緩沖區(qū)與一個(gè)固定設(shè)備相聯(lián)系，不同設(shè)備使用不同的緩沖區(qū)一個(gè)緩沖區(qū)與一個(gè)固定設(shè)備相聯(lián)系，不同設(shè)備使用不同的緩沖區(qū) n利用率低利用率低 n緩沖區(qū)由系統(tǒng)統(tǒng)一管理，按需要?jiǎng)討B(tài)分派給正在進(jìn)行緩沖區(qū)由系統(tǒng)統(tǒng)一管理，按需要?jiǎng)討B(tài)分派給正在進(jìn)行I/O傳輸?shù)脑O(shè)傳輸?shù)脑O(shè)備備空緩沖空緩沖空緩沖空緩沖空緩沖空緩沖.head共共n個(gè)個(gè)Var buf_num:semaphore;(init n)mutex:semaphore;(init 1)1.申請申請 2.釋放釋放(1)P(buf_num)P(mutex)(2)P(mutex)空緩沖入鏈空緩沖入鏈尾尾(3)取鏈頭空緩沖取鏈頭空緩沖 V(mutex)(4)V(mutex)V(buf_num)緩沖池管理緩沖池管理 tail8.7.5 緩沖技術(shù)實(shí)現(xiàn)：輸入設(shè)備 進(jìn)程空間進(jìn)程空間緩沖緩沖輸入設(shè)備輸入設(shè)備緩沖緩沖緩沖緩沖.io鏈進(jìn)程方面：進(jìn)程方面：中斷方面：中斷方面：IO鏈空鏈空設(shè)備忙設(shè)備忙申請空緩沖申請空緩沖啟動(dòng)設(shè)備啟動(dòng)設(shè)備等待等待由由io鏈取一緩沖鏈取一緩沖信息信息進(jìn)程空間進(jìn)程空間釋放空緩沖釋放空緩沖緩沖入緩沖入io鏈鏈有等待進(jìn)程有等待進(jìn)程喚醒喚醒傳輸完畢傳輸完畢申請空緩沖申請空緩沖啟動(dòng)設(shè)備啟動(dòng)設(shè)備FTFTFTTF8.7.5 緩沖技術(shù)實(shí)現(xiàn)：輸出設(shè)備 進(jìn)程空間進(jìn)程空間緩沖緩沖輸出設(shè)備輸出設(shè)備緩沖緩沖緩沖緩沖.io鏈進(jìn)程方面：進(jìn)程方面：中斷方面：中斷方面：申請一空緩沖申請一空緩沖信息信息緩沖緩沖設(shè)備忙設(shè)備忙啟動(dòng)設(shè)備啟動(dòng)設(shè)備緩沖入緩沖入io鏈鏈傳輸完傳輸完TFFT釋放空緩沖釋放空緩沖io鏈空鏈空取一緩沖取一緩沖啟動(dòng)設(shè)備啟動(dòng)設(shè)備TF8.7.5 輸入輸出設(shè)備：輸入輸出設(shè)備：(磁帶、磁盤磁帶、磁盤)緩沖區(qū)頭緩沖區(qū)頭緩沖區(qū)體緩沖區(qū)體設(shè)備塊號(hào)設(shè)備塊號(hào)IO標(biāo)識(shí)標(biāo)識(shí)等待進(jìn)程等待進(jìn)程塊型緩沖區(qū)：塊型緩沖區(qū)：進(jìn)程空間進(jìn)程空間緩沖緩沖IO設(shè)備設(shè)備緩沖緩沖緩沖緩沖.io鏈鏈進(jìn)程方面進(jìn)程方面(輸入輸入)：進(jìn)程方面進(jìn)程方面(輸出輸出)：中斷方面：中斷方面：申請空緩沖申請空緩沖填寫頭部填寫頭部設(shè)備工作設(shè)備工作入入io鏈尾鏈尾啟動(dòng)設(shè)備信息信息進(jìn)程進(jìn)程釋放緩沖釋放緩沖申請空緩沖申請空緩沖填寫頭部填寫頭部信息信息緩沖緩沖設(shè)備工作設(shè)備工作啟動(dòng)設(shè)備啟動(dòng)設(shè)備入入io鏈鏈輸入輸入喚醒喚醒等待等待者者釋放釋放空緩空緩沖沖io鏈空鏈空取一緩沖取一緩沖啟動(dòng)設(shè)備啟動(dòng)設(shè)備FTFTTFFT等待等待UNIX緩沖緩沖n字符型緩沖字符型緩沖n100個(gè)緩沖區(qū)，長度個(gè)緩沖區(qū)，長度8字節(jié)字節(jié)(6字符字符+2指針指針)n組成公共緩沖池，所有字符型設(shè)備公用組成公共緩沖池，所有字符型設(shè)備公用n緩沖區(qū)或?qū)儆诰彌_區(qū)或?qū)儆赾freelist,或?qū)儆谀匙址O(shè)備或?qū)儆谀匙址O(shè)備(eg.tty,lp)n塊型緩沖塊型緩沖n50個(gè)緩沖區(qū)，長度個(gè)緩沖區(qū)，長度514字節(jié)字節(jié)n組成公共緩沖池，所有塊型設(shè)備公用組成公共緩沖池，所有塊型設(shè)備公用n緩沖區(qū)可屬于緩沖區(qū)可屬于bfreelist and/or devtabn預(yù)先讀入的塊預(yù)先讀入的塊(breada)n延遲寫出的塊延遲寫出的塊(bdwrite)字符型設(shè)備緩沖字符型設(shè)備緩沖struct cblock struct cblock*c_next;char info6;struct cblock*cfreelist;/free c blocks struct clist /associated with a character device int c_cc;/character count int c_cf;/pointer to first block int c_cl;/pointer to last blockstruct buf /actually a buffer header,shared by all mounted disks int b_flags;/BUSY,ASYNC,DELWRI,DONE.struct buf*b_forw;/headed by devtab struct buf*b_back;struct buf*av_forw;/position on free list struct buf*av_back;int b_dev;int b_wcount;/transfer count char *b_addr;/low order core(buffer)address char *b_xmem;/high order core(buffer)address char *b_blkno /block#on device char b_error;char *b_resid;/word not transferred after error bufNBUF塊型設(shè)備緩沖（頭部）15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0B_READ/B_WRITEB_DONEB_ERRORB_BUSYB_WANTEDB_RELOCB_ASYNCB_DELWRIb_flag:struct devtab /設(shè)備設(shè)備IO隊(duì)列隊(duì)列 char d_active;/busy flag char d_errcnt;/error count struct buf *b_forw;/first buffer for this dev struct buf *b_back;/last buffer for this dev struct buf *d_actf;/head of IO queue struct buf *d_actl;/tail of IO queuechar buffersNBUF514;/塊型緩沖區(qū)塊型緩沖區(qū)struct buf bfreelist;/緩沖區(qū)頭部的緩沖區(qū)頭部的鏈頭鏈頭相關(guān)操作：getblk(dev,blkno)/assign a buffer for the given block bread(dev,blkno)/read a block(if necessary),return buf pointerbreada(dev,blkno,rablkno)/read in first block,like read;but also start io on second block bwrite(bp)/write the buffer,wait for completion,then releasebawrite(bp)/start the io,release buffer,no wait for completionbdwrite(bp)/release buffer,mark it so that if it is grabbed for another purpose,it will be written out before being given upbrelse(bp)/release the buffer,with no io impliedgetblk(dev,blkno)n參數(shù)：參數(shù)：dev:設(shè)備號(hào)，設(shè)備號(hào)，blkno:設(shè)備塊號(hào)設(shè)備塊號(hào)n返回：緩沖區(qū)指針返回：緩沖區(qū)指針bpn步驟：步驟：n塊在塊在b鏈中，且當(dāng)前空閑鏈中，且當(dāng)前空閑n由由av鏈摘除，標(biāo)記鏈摘除，標(biāo)記BUSY,返回緩沖塊指針返回緩沖塊指針n塊在塊在b鏈中，但鏈中，但BUSY(其它進(jìn)程在用其它進(jìn)程在用)nsleep(空閑事件發(fā)生空閑事件發(fā)生)，由，由av鏈摘除，標(biāo)記鏈摘除，標(biāo)記BUSY,返回緩返回緩沖塊指針沖塊指針n不在不在b的鏈中，在的鏈中，在av鏈上取到延遲寫的塊鏈上取到延遲寫的塊n寫出該塊，分配下一個(gè)緩沖區(qū)寫出該塊，分配下一個(gè)緩沖區(qū)n不在不在b的鏈中，的鏈中，av鏈已空鏈已空n等待任意緩沖區(qū)變空閑的事件等待任意緩沖區(qū)變空閑的事件n不在不在b的鏈中，在的鏈中，在av鏈上得到空緩沖鏈上得到空緩沖n分配，由分配，由av鏈摘除，返回緩沖塊指針鏈摘除，返回緩沖塊指針brelse(bp)n參數(shù)：參數(shù)：bp:緩沖區(qū)頭指針緩沖區(qū)頭指針n返回：無返回：無n步驟：步驟：nIf 有等待者有等待者(b_flag&B_WANTED!=0),喚醒喚醒;nElsenbfreelist上有等待者上有等待者,喚醒喚醒nbp入入av鏈鏈bread(dev,blkno)n參數(shù)：參數(shù)：dev:設(shè)備號(hào)，設(shè)備號(hào)，blkno:設(shè)備塊號(hào)設(shè)備塊號(hào)n返回：載有信息的緩沖區(qū)返回：載有信息的緩沖區(qū)bpn步驟：步驟：nbp=getblk(dev,blkno)nif(緩沖區(qū)數(shù)據(jù)有效緩沖區(qū)數(shù)據(jù)有效)nreturn(bp)/在在cache中得到中得到n啟動(dòng)磁盤讀啟動(dòng)磁盤讀(d_actf/d_actl鏈鏈)nsleep(等待讀盤完成事件等待讀盤完成事件)n中斷中斷nbp入入b_forw/b_back鏈鏈,標(biāo)記標(biāo)記BUSYnreturn(bp)breada(dev,blkno,rablkno)n參數(shù)：參數(shù)：dev:設(shè)備號(hào)，設(shè)備號(hào)，blkno:讀塊號(hào)，讀塊號(hào)，rablkno:預(yù)讀塊號(hào)預(yù)讀塊號(hào)n返回：返回：blk緩沖塊指針緩沖塊指針rbpn步驟：步驟：nrbp=getblk(dev,blkno)nif(信息無效信息無效)n啟動(dòng)設(shè)備讀入啟動(dòng)設(shè)備讀入(d_actf/d_actl鏈鏈)nrabp=getblk(dev,rablkno)nif(B_DONE)/緩沖區(qū)從緩沖區(qū)從b鏈得到鏈得到nbrelse(rabp)/入入av鏈鏈nelse /緩沖區(qū)從緩沖區(qū)從av鏈得到鏈得到n啟動(dòng)設(shè)備讀入啟動(dòng)設(shè)備讀入(d_actf/d_actl鏈鏈)/中斷時(shí)入中斷時(shí)入b鏈和鏈和av鏈鏈niowait(rbp)nreturn(rbp)bwrite(bp)n參數(shù)：參數(shù)：bp：緩沖區(qū)指針緩沖區(qū)指針n步驟：步驟：n入設(shè)備入設(shè)備d_act隊(duì)列隊(duì)列(若設(shè)備不忙啟動(dòng)設(shè)備若設(shè)備不忙啟動(dòng)設(shè)備)nif(!B_ASYNC)nsleep(等待等待IO完成事件完成事件)n中斷中斷nbp入入b鏈鏈,(b_forw/b_back)nbrelse(bp),(bp入入av鏈鏈)bdwrite(bp)n參數(shù)參數(shù):bp:緩沖區(qū)指針緩沖區(qū)指針n返回返回:無無n步驟：步驟：n標(biāo)記標(biāo)記b_flags=|B_DELWRI|B_DONEnbp入設(shè)備入設(shè)備b_forw/b_back隊(duì)列隊(duì)列nbrelse(bp),(bp入入av鏈鏈)bawrite(bp)n參數(shù)：參數(shù)：bp:緩沖區(qū)頭指針緩沖區(qū)頭指針n返回：無返回：無n步驟：步驟：nbp-b_flag=|B_ASYNCnbwrite(bp)n中斷中斷n(入入b_act隊(duì)列隊(duì)列)n入入av隊(duì)列隊(duì)列8.8 輸入輸出進(jìn)程輸入輸出進(jìn)程n專門負(fù)責(zé)專門負(fù)責(zé)IO傳輸?shù)倪M(jìn)程傳輸?shù)倪M(jìn)程n另外一種另外一種IO模式模式服務(wù)模式服務(wù)模式nC/S Modeln特點(diǎn)特點(diǎn)n界面清晰界面清晰,方便使用方便使用n兩次進(jìn)程切換兩次進(jìn)程切換,速度問題速度問題8.9 RAID技術(shù)nRAID:nRedundant Array of Inexpensive Disksncompared with SLEDs(Single Large Expensive Disks)nRedundant Array of Independent Disks/獨(dú)立磁盤冗余陣列獨(dú)立磁盤冗余陣列nProposed by researchers at UC BerkeleynDavid A.PattersonnBackgroundndisk access speed increases slowly compared with CPUnsolution:multiple parallel componentnObjectivenenhanced performancenhigh reliabilityRAID技術(shù)nRAIDnRAID is a set of physical disks viewed by the operating system as a single logical drivenData are distributed across an array of physical drivesnRedundant disk capacity is used to store parity information,which guarantees data recoverability in case of disk failurenHardware RAID vs.Software RAIDnhardware based:special controller nWindows NT,2000,UNIX support software RAIDnSCSI RAID vs.IDE RAIDnperformance:SCSI outperforms IDEnprice:IDE beats SCSI8.9.1 RAID級(jí)別nHow to organize data across multiple disks?nIndustry standards schemen levels:nlevel 0,level 5nlevel 6,level 7nlevel 01/10nlevel 03/30nlevel 05/50nlevel 15/51Level 0nStrip(Striping):ndata are striped and stored on multiple disksnhigh data transfer capacity nno fault toleranced0d3d6d9disk0d1d4d7d10disk1d2d5d8d11disk2d0,d1,d2,d3,d11Level 1nMirror(mirroring)ncompletely duplicatednhigh recoverabilitynexpensived0d1d2d3disk1d0d1d2d3disk2d0,d1,d2,d3,.Level 0+1nRAID01/10nhigh reliabilitynhigh availabilitynexpensived0d2d4d6disk1d1d3d5d7disk2d0,d1,d2,d3,d4,d5,d6,d7d0d2d4d6disk0d1d3d5d7disk3Level 5nStrip+paritynsafety between 1 and 0neconomy between 1 and 0nspeed 0,less than 1d1d4p3d9disk1d2p1d7d10disk2d0,d1,d2,d3,d4,d5,d6,d7d0d3d6p4disk0p0d5d8d11disk3JBOD-SPANnNot a standard RAID levelnjust bundle of disksnno performance improvementnno safety guaranteed0d1d2d3disk0d4d5disk1disk2d1,d2,d3,d4,d5RAID level 0 1 5N#of disks 2,3,4 2 3,4,5Capacity SN SN/2 S(N-1)Store efficiency 100%50%(N-1)/NFault tolerance no 2 3 Availability 1 2 2Random read 4 3 5Random write 4 3 2Sequential read 5 2 4Sequential write 4 3 3Cost$8.9.2 Remark on Software RAIDnPros:ncost lessnsimplicitynCons:nperformancenboot volume limitation /導(dǎo)引卷不能是RAIDnlevel support:only 0,1,5 are supportednOS compatibility:multiple problemnother software compatibilitynreliabilitynsoftware bugsBenefit from RAIDnIncreased read/write speednImproved data reliabilitynEnlarged storage capacitynmultiple disks viewed as a single volume8.10 虛擬設(shè)備虛擬設(shè)備n概念概念n利用共享型設(shè)備實(shí)現(xiàn)的數(shù)量較多、速度較快的獨(dú)占型設(shè)利用共享型設(shè)備實(shí)現(xiàn)的數(shù)量較多、速度較快的獨(dú)占型設(shè)備備n引入引入n用戶直接使用獨(dú)占型設(shè)備效率低用戶直接使用獨(dú)占型設(shè)備效率低n實(shí)現(xiàn)實(shí)現(xiàn)n輸入型虛擬設(shè)備輸入型虛擬設(shè)備n輸出型虛擬設(shè)備輸出型虛擬設(shè)備n虛擬設(shè)備的例子虛擬設(shè)備的例子nSPOOLing輸入輸入nSPOOLing輸出輸出l用戶使用獨(dú)占型設(shè)備活動(dòng)：用戶使用獨(dú)占型設(shè)備活動(dòng)：申請，使用，使用，申請，使用，使用，使用，釋放，使用，釋放l缺點(diǎn)：缺點(diǎn)：速度：速度：CPU與設(shè)備速度不匹配與設(shè)備速度不匹配設(shè)備利用率：占有期間不一定一直使用設(shè)備利用率：占有期間不一定一直使用進(jìn)程獨(dú)占此設(shè)備進(jìn)程獨(dú)占此設(shè)備l方法：方法：在進(jìn)程與獨(dú)占型設(shè)備之間增加共享設(shè)備緩沖在進(jìn)程與獨(dú)占型設(shè)備之間增加共享設(shè)備緩沖虛擬虛擬設(shè)備設(shè)備虛擬虛擬設(shè)備設(shè)備虛擬虛擬設(shè)備設(shè)備虛擬虛擬設(shè)備設(shè)備進(jìn)程進(jìn)程獨(dú)占設(shè)備獨(dú)占設(shè)備 共享設(shè)備共享設(shè)備（如磁盤）（如磁盤）間斷傳輸間斷傳輸連續(xù)傳輸連續(xù)傳輸l輸入型虛擬設(shè)備的實(shí)現(xiàn)輸入型虛擬設(shè)備的實(shí)現(xiàn)申請：申請：l分配一虛設(shè)備分配一虛設(shè)備l分配一實(shí)設(shè)備分配一實(shí)設(shè)備l信息由實(shí)設(shè)備信息由實(shí)設(shè)備虛設(shè)備虛設(shè)備l去配該實(shí)設(shè)備去配該實(shí)設(shè)備使用：使用：l信息由虛設(shè)備信息由虛設(shè)備進(jìn)程空間進(jìn)程空間釋放：釋放：l去配虛設(shè)備去配虛設(shè)備l輸出型虛擬設(shè)備的實(shí)現(xiàn)輸出型虛擬設(shè)備的實(shí)現(xiàn)申請：申請：l分配一虛設(shè)備分配一虛設(shè)備使用：使用：l信息由進(jìn)程空間信息由進(jìn)程空間虛設(shè)備虛設(shè)備釋放：釋放：l分配一實(shí)設(shè)備分配一實(shí)設(shè)備l信息由虛設(shè)備信息由虛設(shè)備實(shí)設(shè)備實(shí)設(shè)備l去配實(shí)設(shè)備去配實(shí)設(shè)備l去配虛設(shè)備去配虛設(shè)備8.10.3 虛擬設(shè)備的例子虛擬設(shè)備的例子nSPOOLing輸入輸入n作業(yè)預(yù)輸入（輸入機(jī)作業(yè)預(yù)輸入（輸入機(jī)輸入井）輸入井）nSPOOLing輸出輸出n作業(yè)緩輸出（輸出井作業(yè)緩輸出（輸出井輸出機(jī)）輸出機(jī)）nSPOOLingnSimultaneous Peripheral Operation On-Linen由由SPOOLing程序控制通道完成程序控制通道完成.job11job1m.輸入井輸入井預(yù)輸入進(jìn)程預(yù)輸入進(jìn)程輸入機(jī)輸入機(jī)輸入機(jī)輸入機(jī)預(yù)輸入進(jìn)程預(yù)輸入進(jìn)程通道通道通道通道內(nèi)存內(nèi)存.SPOOLing輸入程序（輸入程序（1）vs.SPOOLing輸入進(jìn)程（輸入進(jìn)程（n）有待輸入作業(yè)有待輸入作業(yè) 有空閑作業(yè)表有空閑作業(yè)表等待等待等待等待取一取一“空閑空閑”作業(yè)表為作業(yè)表為JCB作業(yè)狀態(tài)改為作業(yè)狀態(tài)改為“提交提交”申請輸入井空間申請輸入井空間作業(yè)內(nèi)容作業(yè)內(nèi)容輸入井輸入井填寫填寫JCB作業(yè)狀態(tài)改為作業(yè)狀態(tài)改為“后備后備”作業(yè)調(diào)度作業(yè)調(diào)度1等待等待 “后備后備”作作業(yè)業(yè)喚醒喚醒SPOOLing 輸入程序輸入程序FTFTFT.通道通道通道通道job11job1n.輸出井輸出井緩輸出進(jìn)程緩輸出進(jìn)程緩輸出進(jìn)程緩輸出進(jìn)程內(nèi)存內(nèi)存輸出機(jī)輸出機(jī)輸出機(jī)輸出機(jī)SPOOLing輸出程序（輸出程序（1）vs.SPOOLing輸出進(jìn)程輸出進(jìn)程（n）輸出作業(yè)結(jié)果輸出作業(yè)結(jié)果釋放輸出井空間釋放輸出井空間狀態(tài)改為狀態(tài)改為“空空閑閑”有等空閑有等空閑JCB的預(yù)輸入進(jìn)程的預(yù)輸入進(jìn)程喚醒一個(gè)喚醒一個(gè)輸出井有輸出井有“完成完成”作作業(yè)業(yè)取一取一“完成完成”作作業(yè)業(yè)狀態(tài)改為狀態(tài)改為“退出退出”等待等待SPOOLing 輸出程序FTTF8.11 穩(wěn)定存儲(chǔ)器穩(wěn)定存儲(chǔ)器(stable storage)n定義定義n不丟失信息的存儲(chǔ)器稱為穩(wěn)定存儲(chǔ)器不丟失信息的存儲(chǔ)器稱為穩(wěn)定存儲(chǔ)器n實(shí)現(xiàn)實(shí)現(xiàn)n不存在絕對(duì)可靠的存儲(chǔ)介質(zhì)不存在絕對(duì)可靠的存儲(chǔ)介質(zhì)n策略：冗余策略：冗余n在兩種失效獨(dú)立的介質(zhì)上構(gòu)建在兩種失效獨(dú)立的介質(zhì)上構(gòu)建n保存保存n將信息寫到第一個(gè)存儲(chǔ)塊將信息寫到第一個(gè)存儲(chǔ)塊n上述操作成功后，將相同信息寫到第二存儲(chǔ)塊上述操作成功后，將相同信息寫到第二存儲(chǔ)塊n僅當(dāng)?shù)诙蝹鬏斠渤晒r(shí)，整個(gè)保存操作完成僅當(dāng)?shù)诙蝹鬏斠渤晒r(shí)，整個(gè)保存操作完成8.11 穩(wěn)定存儲(chǔ)器穩(wěn)定存儲(chǔ)器(stable storage)n實(shí)現(xiàn)實(shí)現(xiàn)n恢復(fù)恢復(fù)n鑒別兩個(gè)數(shù)據(jù)塊內(nèi)容鑒別兩個(gè)數(shù)據(jù)塊內(nèi)容n一對(duì)信息完全相同，且無檢測到錯(cuò)誤，正常一對(duì)信息完全相同，且無檢測到錯(cuò)誤，正常n其中一塊檢測到錯(cuò)誤，用另一塊取代其中一塊檢測到錯(cuò)誤，用另一塊取代n兩塊均未檢測到錯(cuò)誤，但內(nèi)容不同，用第二塊內(nèi)容取兩塊均未檢測到錯(cuò)誤，但內(nèi)容不同，用第二塊內(nèi)容取代第一塊內(nèi)容代第一塊內(nèi)容8.12 系統(tǒng)舉例系統(tǒng)舉例Linuxn涉及內(nèi)容涉及內(nèi)容n設(shè)備驅(qū)動(dòng)，設(shè)備緩沖，文件管理設(shè)備驅(qū)動(dòng)，設(shè)備緩沖，文件管理n主要特點(diǎn)主要特點(diǎn)n允許系統(tǒng)管理員動(dòng)態(tài)添加或刪除設(shè)備，其相應(yīng)的驅(qū)動(dòng)程序通常允許系統(tǒng)管理員動(dòng)態(tài)添加或刪除設(shè)備，其相應(yīng)的驅(qū)動(dòng)程序通常以以DLL的形式動(dòng)態(tài)加載，設(shè)備驅(qū)動(dòng)程序可以采用高級(jí)語言編寫，的形式動(dòng)態(tài)加載，設(shè)備驅(qū)動(dòng)程序可以采用高級(jí)語言編寫，移植性好移植性好n除除NTFS外，支持多種可裝卸的文件系統(tǒng)，如外，支持多種可裝卸的文件系統(tǒng)，如FAT32、OS/2、HPFS、CDFS等支持映像文件等支持映像文件I/On設(shè)備管理子系統(tǒng)以設(shè)備管理子系統(tǒng)以I/O請求包請求包(I/O Request Package，IRP)方式驅(qū)動(dòng)，每個(gè)方式驅(qū)動(dòng)，每個(gè)I/O請求均以表示為請求均以表示為I/O請求包，請求包，I/O管理器管理器負(fù)責(zé)協(xié)調(diào)所有各組成部分之間的相互作用負(fù)責(zé)協(xié)調(diào)所有各組成部分之間的相互作用n通過系統(tǒng)進(jìn)程通過系統(tǒng)進(jìn)程(線程線程)提供異步提供異步I/O，在，在I/O請求的進(jìn)程請求的進(jìn)程(線程線程)不需要等待不需要等待I/O傳輸結(jié)果的情況下，請求者可以立即返回，具傳輸結(jié)果的情況下，請求者可以立即返回，具體體I/O操作由系統(tǒng)線程負(fù)責(zé)完成異步操作由系統(tǒng)線程負(fù)責(zé)完成異步I/O是通過異步過程調(diào)是通過異步過程調(diào)用用(Asynchronous Procedure Call，APC)實(shí)現(xiàn)的實(shí)現(xiàn)的應(yīng)用程序應(yīng)用程序系統(tǒng)服務(wù)系統(tǒng)服務(wù)IO管理程序文件系統(tǒng)磁盤驅(qū)動(dòng)磁盤驅(qū)動(dòng)光盤驅(qū)動(dòng)光盤驅(qū)動(dòng)磁帶驅(qū)動(dòng)磁帶驅(qū)動(dòng)Windows2000/XP IO子系統(tǒng)