《設(shè)備與IO管理》PPT課件.ppt

1、第八章 設(shè)備與I/O管理,設(shè)備及其分類 設(shè)備的物理特性 IO傳輸方式（查詢、中斷、通道、DMA） 設(shè)備分配與去配 設(shè)備驅(qū)動(dòng) 設(shè)備調(diào)度 緩沖技術(shù) 輸入輸出進(jìn)程 RAID技術(shù) 虛擬設(shè)備,8.1 設(shè)備及其分類,用途 存儲(chǔ)型設(shè)備 磁盤，磁帶，光盤 IO型設(shè)備 掃描儀，打印機(jī)，mouse，keyboard，monitor， 網(wǎng)絡(luò)設(shè)備 網(wǎng)卡，交換機(jī)，etc.,8.1 設(shè)備及其分類,管理 共享型設(shè)備（塊型） 多個(gè)進(jìn)程的IO操作以塊為單位可以交叉 獨(dú)占型設(shè)備（塊型） 多個(gè)進(jìn)程的IO操作以塊為單位不宜交叉 獨(dú)占型設(shè)備（字符型） 多個(gè)進(jìn)程的IO操作以字符為單位不能交叉,IO設(shè)備的物理特性 傳輸一字節(jié)發(fā)生一次中斷

2、存儲(chǔ)設(shè)備的物理特性 磁帶的物理特性,8.2 設(shè)備的物理特性,磁盤組的物理特性,盤面0,盤面1,盤面2,盤面m-1,扇區(qū)1,扇區(qū)0,扇區(qū)n-1,柱面0,柱面l-1,.,引臂,柱面號(hào)i 盤面號(hào)j 扇區(qū)號(hào)k,塊號(hào)b（一維地址）,（三維地址）,編址方法：使相鄰塊物理上最近 例子：l=2; m=3; n=3 柱面號(hào)：0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 盤面號(hào)：0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 扇區(qū)號(hào)：0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 塊 號(hào)：0 1 2 3 4 5 6 7 8 9 10 11

3、12 13 14 15 16 17,三維地址一維地址： b=imn+jn+k 一維地址三維地址： i=b(mn) j=b mod (mn) n k=b mod (mn) mod n,未考慮讀寫延遲的扇區(qū)編號(hào)：,考慮讀寫延遲的扇區(qū)編號(hào)(單交錯(cuò))：,考慮讀寫延遲的扇區(qū)編號(hào)(雙交錯(cuò))：,光盤的物理特性: 讀取原理: pit/land 螺旋線,22188圈(展開5.6km), 內(nèi)側(cè)轉(zhuǎn)速:530轉(zhuǎn)/分; 外側(cè)轉(zhuǎn)速:200轉(zhuǎn)/分(密度均勻,讀取速度均勻),14個(gè)bit構(gòu)成一個(gè)symble,42個(gè)symble構(gòu)成一個(gè)frame,98個(gè)frame構(gòu)成一個(gè)sector,Sector 2352bytes,588b

4、its的frame 各包含24字節(jié),Preamble: 16bytes, 前12bytes為: 00FFFFFFFFFFFFFFFFFFFF00 后隨3bytes扇區(qū)編號(hào),最后字節(jié)為mode,2048字節(jié),288字節(jié),8.3 I/O 傳輸方式,IO操作演變歷史 程序查詢方式 (programmed IO) (polling) CPU and Device can not work in parallel 中斷方式 (interrupt) CPU and device can work in parallel, too many interrupts for CPU 通道方式 (channel)

5、 special processor for dealing with io operations 直接內(nèi)存方式 (DMA) DMA controller in charge of block io,8.3.1 程序控制查詢方式,CPU啟動(dòng)設(shè)備,完成,F,T,缺點(diǎn): 處理機(jī)與設(shè)備串行工作; 消耗大量處理機(jī)時(shí)間.,8.3.2 中斷驅(qū)動(dòng)方式,CPU 計(jì)算 啟動(dòng)設(shè)備 計(jì)算 計(jì)算 中斷處理 計(jì)算,設(shè)備:,工作,特點(diǎn): CPU與設(shè)備并行工作 設(shè)備多時(shí)對CPU打擾多,8.3.3 DMA方式, 數(shù)據(jù)傳輸,CPU,DMA 控制器,內(nèi)存,緩沖,磁盤, 中斷, DMA請求,總線,磁盤 控制器, 回答, DMA編程

6、,8.3.3 DMA方式,.,CPU通過設(shè)置DMA控制器實(shí)現(xiàn)DMA編程，同時(shí)啟動(dòng)磁盤控制器由磁盤讀入數(shù)據(jù)至內(nèi)部緩沖區(qū)并進(jìn)行和校驗(yàn)； DMA控制器向磁盤控制器發(fā)出讀請求，并將內(nèi)存地址放在地址總線上； 磁盤控制器將字節(jié)傳到內(nèi)存指定單元； 磁盤控制器向DMA控制器發(fā)送回答； DMA控制器將內(nèi)部地址寄存器加1同時(shí)將記數(shù)減1，重復(fù)上述過程直至計(jì)數(shù)值為0，此時(shí)DMA控制器向CPU發(fā)出中斷信號(hào).,8.3.4 通道方式,通道 負(fù)責(zé)IO操作的處理機(jī) 指令系統(tǒng) 基本操作：讀、寫、控制、轉(zhuǎn)移、結(jié)束 指令格式：（操作碼，傳輸量，特征位，地址） 運(yùn)控部件 CAW，CCW，CSW，CDW 存儲(chǔ)區(qū)域（與CPU共用內(nèi)存,通道

7、內(nèi)有緩沖區(qū)） 通道程序，IO數(shù)據(jù)（channel does have its buffers）,通道程序執(zhí)行過程：,按CAW取通道命令CCW,（CAW）+1 CAW,是通道結(jié)束命令,執(zhí)行此命令,F,向CPU發(fā)中斷,一個(gè)通道程序可以控制若干設(shè)備進(jìn)行多次IO傳輸。,T,通道類型,字節(jié)多路通道(byte multiplexer channel) 多個(gè)非分配型子通道，連接低速外圍設(shè)備 數(shù)組選擇通道(block selector channel) 一個(gè)分配型子通道，連接多臺(tái)高速設(shè)備 數(shù)組多路通道(block multiplexer channel) 多個(gè)非分配型子通道，連接多臺(tái)高速設(shè)備,設(shè)備、通道、內(nèi)存

8、連接,選擇通道,磁盤,字節(jié)多路通道,打印機(jī),輸入機(jī),內(nèi)存儲(chǔ)器,處理機(jī),磁帶,數(shù)組多路通道,8.4 設(shè)備的分配與去配,獨(dú)占型設(shè)備的分配與去配 塊型獨(dú)占 字符型獨(dú)占 共享型設(shè)備的分配與去配 塊型共享,數(shù)據(jù)結(jié)構(gòu) 設(shè)備控制塊(UCB) 通道控制塊(CCB),設(shè)備標(biāo)識(shí) 設(shè)備狀態(tài) 占有設(shè)備進(jìn)程,通道標(biāo)識(shí) 通道狀態(tài) 通道類型 占有通道進(jìn)程,系統(tǒng)設(shè)備表(SDT),設(shè)備類 總數(shù) 設(shè)備等待隊(duì)列 UCB表指針 lp m Sm,UCB UCB UCB, ,獨(dú)占型設(shè)備的分配與去配 用戶使用獨(dú)占型設(shè)備活動(dòng)： 申請，使用，使用，使用，釋放 申請：(1) 根據(jù)設(shè)備類查SDT表 (2) P(Sm) (3) 查UCB表找一空閑設(shè)

9、備并分配 使用：(1) IO傳輸 釋放：(1) 找SDT表對應(yīng)入口 (2) 查UCB表，去配 (3) V(Sm),8.4 設(shè)備的分配與去配,共享型設(shè)備的分配與去配 用戶使用共享型設(shè)備活動(dòng) 使用，使用，使用 特征 來自文件系統(tǒng)； 每次讀（寫）一塊； 通常經(jīng)過緩沖； 排隊(duì)優(yōu)化。 使用 IO操作,8.5 設(shè)備驅(qū)動(dòng),通道程序 CCW指令序列 靜態(tài)編制或動(dòng)態(tài)生成 設(shè)備啟動(dòng) 通道啟動(dòng) 中斷處理 通道向CPU發(fā)的中斷,8.5 設(shè)備驅(qū)動(dòng),設(shè)備,CAW CCW CDW CSW,. 形成通道程序 . 地址CAW . 啟動(dòng)通道 . 中斷處理 .,啟動(dòng),中斷,內(nèi)存,CPU,通道,8.6 設(shè)備調(diào)度,優(yōu)化服務(wù)順序 考慮因

10、素 公平性 防止餓死 高效性 減少磁盤引臂移動(dòng)量,磁盤引臂調(diào)度(disk head scheduling),先到先服務(wù)（FCFS） 請求序列：130，42，180，15，108，68，97,移動(dòng)量: (130-53)+(130-42)+(180-42)+(180-15)+(108-15)+(108-68)+(97-68)=630,磁盤引臂調(diào)度(disk head scheduling),最短尋找時(shí)間優(yōu)先（SSTF） 請求序列：130，42，180，15，108，68，97,移動(dòng)量: (53-42)+(180-42)+(180-15)=314,磁盤引臂調(diào)度(disk head schedulin

11、g),SCAN（LOOK） 請求序列：130，42，180，15，108，68，97,SCAN移動(dòng)量: (53-0)+(180-0)=233 LOOK移動(dòng)量: (53-15)+(180-15)=203,0 15 42 53 68 97 108 130 180 199,Look Scan,磁盤引臂調(diào)度(disk head scheduling),C-SCAN（C-LOOK） 請求序列：130，42，180，15，108，68，97,特點(diǎn)：所有磁道地位最長等待時(shí)間相同,8.7 緩沖技術(shù),設(shè)備處理數(shù)據(jù)到達(dá)與離開速度不一致所采用的技術(shù)。 Buffering vs. Caching buffering:

12、 one data copy caching: multiple data copy (slow多, fast少) 硬緩沖與軟緩沖 硬緩沖區(qū)通常設(shè)在設(shè)備中 軟緩沖區(qū)通常設(shè)在內(nèi)存系統(tǒng)空間中 私用緩沖與公共緩沖 一個(gè)緩沖區(qū)與一個(gè)固定設(shè)備相聯(lián)系，不同設(shè)備使用不同的緩沖區(qū) 利用率低 緩沖區(qū)由系統(tǒng)統(tǒng)一管理，按需要?jiǎng)討B(tài)分派給正在進(jìn)行I/O傳輸?shù)脑O(shè)備,Var buf_num:semaphore; (init n) mutex:semaphore; (init 1) 1. 申請 2. 釋放 (1) P(buf_num) P(mutex) (2) P(mutex) 空緩沖入鏈尾 (3) 取鏈頭空緩沖 V(mut

13、ex) (4) V(mutex) V(buf_num),緩沖池管理,tail,8.7.5 緩沖技術(shù)實(shí)現(xiàn)：輸入設(shè)備,io鏈,進(jìn)程方面：,中斷方面：,IO鏈空,設(shè)備忙,申請空緩沖,啟動(dòng)設(shè)備,等待,由io鏈取一緩沖,信息進(jìn)程空間,釋放空緩沖,緩沖入io鏈,有等待進(jìn)程,喚醒,傳輸完畢,申請空緩沖,啟動(dòng)設(shè)備,F,T,F,T,F,T,T,F,8.7.5 緩沖技術(shù)實(shí)現(xiàn)：輸出設(shè)備,進(jìn)程方面：,中斷方面：,申請一空緩沖,信息緩沖,設(shè)備忙,啟動(dòng)設(shè)備,緩沖入io鏈,傳輸完,T,F,F,T,釋放空緩沖,io鏈空,取一緩沖,啟動(dòng)設(shè)備,T,F,8.7.5 輸入輸出設(shè)備： (磁帶、磁盤),塊型緩沖區(qū)：,進(jìn)程空間,緩沖,IO

14、設(shè)備,緩沖,緩沖,.,io鏈,進(jìn)程方面(輸入)：,進(jìn)程方面(輸出)：,中斷方面：,申請空緩沖,填寫頭部,設(shè)備工作,入io鏈尾,啟動(dòng)設(shè)備,信息進(jìn)程,釋放緩沖,申請空緩沖,填寫頭部,信息緩沖,設(shè)備工作,啟動(dòng)設(shè)備,入io鏈,輸入,喚醒等待者,釋放空緩沖,io鏈空,取一緩沖,啟動(dòng)設(shè)備,F,T,F,T,T,F,F,T,等待,UNIX緩沖,字符型緩沖 100個(gè)緩沖區(qū)，長度8字節(jié)(6字符+2指針) 組成公共緩沖池，所有字符型設(shè)備公用 緩沖區(qū)或?qū)儆赾freelist, 或?qū)儆谀匙址O(shè)備(eg. tty,lp) 塊型緩沖 50個(gè)緩沖區(qū)，長度514字節(jié) 組成公共緩沖池，所有塊型設(shè)備公用 緩沖區(qū)可屬于bfreeli

15、st and/or devtab 預(yù)先讀入的塊(breada) 延遲寫出的塊(bdwrite),字符型設(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 block ,struct buf

16、 /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)

17、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 0,B_READ/B_WRITE,B_DONE,B_ERROR,B_BUSY,B_WANTED,B_RELOC,B_ASYNC,B_DELWRI,b_flag:,struct devta

18、b /設(shè)備IO隊(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 queue ,char buffersNBUF514; /塊型緩沖區(qū) struct buf bfreelist; /緩沖區(qū)頭部的鏈頭,相關(guān)操作：

19、getblk(dev,blkno) /assign a buffer for the given block bread(dev,blkno) /read a block(if necessary), return buf pointer breada(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 release bawrite(bp) /start the

20、io, release buffer, no wait for completion bdwrite(bp) /release buffer, mark it so that if it is grabbed for another purpose, it will be written out before being given up brelse(bp) /release the buffer, with no io implied,getblk(dev,blkno),參數(shù)： dev:設(shè)備號(hào)，blkno: 設(shè)備塊號(hào) 返回：緩沖區(qū)指針bp 步驟： 塊在b鏈中，且當(dāng)前空閑 由av鏈摘除，標(biāo)記

21、BUSY, 返回緩沖塊指針 塊在b鏈中，但BUSY(其它進(jìn)程在用) sleep(空閑事件發(fā)生)，由av鏈摘除，標(biāo)記BUSY, 返回緩沖塊指針 不在b的鏈中，在av鏈上取到延遲寫的塊 寫出該塊，分配下一個(gè)緩沖區(qū) 不在b的鏈中，av鏈已空 等待任意緩沖區(qū)變空閑的事件 不在b的鏈中，在av鏈上得到空緩沖 分配，由av鏈摘除，返回緩沖塊指針,brelse(bp),參數(shù)：bp: 緩沖區(qū)頭指針 返回：無 步驟： 有等待者(b_flag bfreelist上有等待者,喚醒 bp入av鏈,bread(dev,blkno),參數(shù)：dev:設(shè)備號(hào)，blkno: 設(shè)備塊號(hào) 返回：載有信息的緩沖區(qū)bp 步驟： bp=

22、getblk(dev,blkno) if (緩沖區(qū)數(shù)據(jù)有效) return(bp) /在cache中得到 啟動(dòng)磁盤讀(d_actf/d_actl鏈) sleep(等待讀盤完成事件) 中斷 bp入b_forw/b_back鏈, 標(biāo)記BUSY return(bp),breada(dev,blkno,rablkno),參數(shù)：dev:設(shè)備號(hào)，blkno:讀塊號(hào)，rablkno:預(yù)讀塊號(hào) 返回：blk緩沖塊指針rbp 步驟： rbp=getblk(dev,blkno) if(信息無效) 啟動(dòng)設(shè)備讀入(d_actf/d_actl鏈) rabp=getblk(dev,rablkno) if (B_DONE)

23、 /緩沖區(qū)從b鏈得到 brelse(rabp) /入av鏈 else /緩沖區(qū)從av鏈得到 啟動(dòng)設(shè)備讀入(d_actf/d_actl鏈) /中斷時(shí)入b鏈和av鏈 iowait(rbp) return(rbp),bwrite(bp),參數(shù)：bp：緩沖區(qū)指針 步驟： 入設(shè)備d_act隊(duì)列(若設(shè)備不忙啟動(dòng)設(shè)備) if(! B_ASYNC) sleep(等待IO完成事件) 中斷 bp入b鏈, (b_forw/b_back) brelse(bp), (bp入av鏈),bdwrite(bp),參數(shù): bp: 緩沖區(qū)指針 返回: 無 步驟： 標(biāo)記b_flags =| B_DELWRI | B_DONE bp

24、入設(shè)備b_forw/b_back隊(duì)列 brelse(bp), (bp入av鏈),bawrite(bp),參數(shù)：bp: 緩沖區(qū)頭指針 返回：無 步驟： bp-b_flag =| B_ASYNC bwrite(bp) 中斷 (入b_act隊(duì)列) 入av隊(duì)列,8.8 輸入輸出進(jìn)程,專門負(fù)責(zé)IO傳輸?shù)倪M(jìn)程 另外一種IO模式服務(wù)模式 C/S Model 特點(diǎn) 界面清晰,方便使用 兩次進(jìn)程切換,速度問題,8.9 RAID技術(shù),RAID: Redundant Array of Inexpensive Disks compared with SLEDs (Single Large Expensive Disk

25、s) Redundant Array of Independent Disks /獨(dú)立磁盤冗余陣列 Proposed by researchers at UC Berkeley David A. Patterson Background disk access speed increases slowly compared with CPU solution: multiple parallel component Objective enhanced performance high reliability,RAID技術(shù),RAID RAID is a set of physical disk

26、s viewed by the operating system as a single logical drive Data are distributed across an array of physical drives Redundant disk capacity is used to store parity information, which guarantees data recoverability in case of disk failure Hardware RAID vs. Software RAID hardware based: special control

27、ler Windows NT, 2000, UNIX support software RAID SCSI RAID vs. IDE RAID performance: SCSI outperforms IDE price: IDE beats SCSI,8.9.1 RAID級別,How to organize data across multiple disks? Industry standards scheme levels: level 0, , level 5 level 6, level 7 level 01/10 level 03/30 level 05/50 level 15/

28、51,Level 0,Strip(Striping): data are striped and stored on multiple disks high data transfer capacity no fault tolerance,d0,d1,d2,d3,d11,Level 1,Mirror(mirroring) completely duplicated high recoverability expensive,d0,d1,d2,d3,.,Level 0+1,RAID01/10 high reliability high availability expensive,d0,d1,

29、d2,d3,d4,d5,d6,d7,Level 5,Strip + parity safety between 1 and 0 economy between 1 and 0 speed 0, less than 1,JBOD - SPAN,Not a standard RAID level just bundle of disks no performance improvement no safety guarantee,d1,d2,d3,d4,d5,RAID level 0 1 5 N# of disks 2,3,4 2 3,4,5 Capacity SN SN/2 S(N-1) Sto

30、re efficiency 100% 50% (N-1)/N Fault tolerance no 2 3 Availability 1 2 2 Random read 4 3 5 Random write 4 3 2 Sequential read 5 2 4 Sequential write 4 3 3 Cost $ $ $,8.9.2 Remark on Software RAID,Pros: cost less simplicity Cons: performance boot volume limitation /導(dǎo)引卷不能是RAID level support: only 0,1,

31、5 are supported OS compatibility: multiple problem other software compatibility reliability software bugs,Benefit from RAID,Increased read/write speed Improved data reliability Enlarged storage capacity multiple disks viewed as a single volume,8.10 虛擬設(shè)備,概念 利用共享型設(shè)備實(shí)現(xiàn)的數(shù)量較多、速度較快的獨(dú)占型設(shè)備 引入 用戶直接使用獨(dú)占型設(shè)備效率低

32、 實(shí)現(xiàn) 輸入型虛擬設(shè)備 輸出型虛擬設(shè)備 虛擬設(shè)備的例子 SPOOLing輸入 SPOOLing輸出,8.7.1 虛擬設(shè)備引入,用戶使用獨(dú)占型設(shè)備活動(dòng)： 申請，使用，使用，使用，釋放 缺點(diǎn)： 速度：CPU與設(shè)備速度不匹配 設(shè)備利用率：占有期間不一定一直使用,進(jìn)程獨(dú)占此設(shè)備,方法： 在進(jìn)程與獨(dú)占型設(shè)備之間增加共享設(shè)備緩沖,虛擬 設(shè)備,虛擬 設(shè)備,虛擬 設(shè)備,虛擬 設(shè)備,進(jìn)程,獨(dú)占設(shè)備,共享設(shè)備（如磁盤）,間斷傳輸,連續(xù)傳輸,8.10.2 虛擬設(shè)備的實(shí)現(xiàn),輸入型虛擬設(shè)備的實(shí)現(xiàn) 申請： 分配一虛設(shè)備 分配一實(shí)設(shè)備 信息由實(shí)設(shè)備虛設(shè)備 去配該實(shí)設(shè)備 使用： 信息由虛設(shè)備進(jìn)程空間 釋放： 去配虛設(shè)備,輸出型虛擬設(shè)備的實(shí)現(xiàn) 申請： 分配一虛設(shè)備 使用： 信息由進(jìn)程空間虛設(shè)備 釋放： 分配一實(shí)設(shè)備 信息由虛設(shè)備實(shí)設(shè)備 去配實(shí)設(shè)備 去配虛設(shè)備,8.10.2 虛擬設(shè)備的實(shí)現(xiàn),8.10.3 虛擬設(shè)備的例子,SPOOLing輸入 作業(yè)預(yù)輸入（輸入機(jī)輸入井） SPOOLing輸出 作業(yè)緩輸出（輸出井輸出機(jī)） S