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

2、存儲設備的物理特性 磁帶的物理特性,8.2 設備的物理特性,磁盤組的物理特性,盤面0,盤面1,盤面2,盤面m-1,扇區(qū)1,扇區(qū)0,扇區(qū)n-1,柱面0,柱面l-1,.,引臂,柱面號i 盤面號j 扇區(qū)號k,塊號b（一維地址）,（三維地址）,編址方法：使相鄰塊物理上最近 例子：l=2; m=3; n=3 柱面號：0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 盤面號：0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 扇區(qū)號：0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 塊 號：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ū)編號：,考慮讀寫延遲的扇區(qū)編號(單交錯)：,考慮讀寫延遲的扇區(qū)編號(雙交錯)：,光盤的物理特性: 讀取原理: pit/land 螺旋線,22188圈(展開5.6km), 內(nèi)側(cè)轉(zhuǎn)速:530轉(zhuǎn)/分; 外側(cè)轉(zhuǎn)速:200轉(zhuǎn)/分(密度均勻,讀取速度均勻),14個bit構(gòu)成一個symble,42個symble構(gòu)成一個frame,98個frame構(gòu)成一個sector,Sector 2352bytes,588b

4、its的frame 各包含24字節(jié),Preamble: 16bytes, 前12bytes為: 00FFFFFFFFFFFFFFFFFFFF00 后隨3bytes扇區(qū)編號,最后字節(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啟動設備,完成,F,T,缺點: 處理機與設備串行工作; 消耗大量處理機時間.,8.3.2 中斷驅(qū)動方式,CPU 計算 啟動設備 計算 計算 中斷處理 計算,設備:,工作,特點: CPU與設備并行工作 設備多時對CPU打擾多,8.3.3 DMA方式, 數(shù)據(jù)傳輸,CPU,DMA 控制器,內(nèi)存,緩沖,磁盤, 中斷, DMA請求,總線,磁盤 控制器, 回答, DMA編程

6、,8.3.3 DMA方式,.,CPU通過設置DMA控制器實現(xiàn)DMA編程，同時啟動磁盤控制器由磁盤讀入數(shù)據(jù)至內(nèi)部緩沖區(qū)并進行和校驗； DMA控制器向磁盤控制器發(fā)出讀請求，并將內(nèi)存地址放在地址總線上； 磁盤控制器將字節(jié)傳到內(nèi)存指定單元； 磁盤控制器向DMA控制器發(fā)送回答； DMA控制器將內(nèi)部地址寄存器加1同時將記數(shù)減1，重復上述過程直至計數(shù)值為0，此時DMA控制器向CPU發(fā)出中斷信號.,8.3.4 通道方式,通道 負責IO操作的處理機 指令系統(tǒng) 基本操作：讀、寫、控制、轉(zhuǎn)移、結(jié)束 指令格式：（操作碼，傳輸量，特征位，地址） 運控部件 CAW，CCW，CSW，CDW 存儲區(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ā)中斷,一個通道程序可以控制若干設備進行多次IO傳輸。,T,通道類型,字節(jié)多路通道(byte multiplexer channel) 多個非分配型子通道，連接低速外圍設備 數(shù)組選擇通道(block selector channel) 一個分配型子通道，連接多臺高速設備 數(shù)組多路通道(block multiplexer channel) 多個非分配型子通道，連接多臺高速設備,設備、通道、內(nèi)存

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

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

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

11、g),SCAN（LOOK） 請求序列：130，42，180，15，108，68，97,SCAN移動量: (53-0)+(180-0)=233 LOOK移動量: (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,特點：所有磁道地位最長等待時間相同,8.7 緩沖技術(shù),設備處理數(shù)據(jù)到達與離開速度不一致所采用的技術(shù)。 Buffering vs. Caching buffering:

12、 one data copy caching: multiple data copy (slow多, fast少) 硬緩沖與軟緩沖 硬緩沖區(qū)通常設在設備中 軟緩沖區(qū)通常設在內(nèi)存系統(tǒng)空間中 私用緩沖與公共緩沖 一個緩沖區(qū)與一個固定設備相聯(lián)系，不同設備使用不同的緩沖區(qū) 利用率低 緩沖區(qū)由系統(tǒng)統(tǒng)一管理，按需要動態(tài)分派給正在進行I/O傳輸?shù)脑O備,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ù)實現(xiàn)：輸入設備,io鏈,進程方面：,中斷方面：,IO鏈空,設備忙,申請空緩沖,啟動設備,等待,由io鏈取一緩沖,信息進程空間,釋放空緩沖,緩沖入io鏈,有等待進程,喚醒,傳輸完畢,申請空緩沖,啟動設備,F,T,F,T,F,T,T,F,8.7.5 緩沖技術(shù)實現(xiàn)：輸出設備,進程方面：,中斷方面：,申請一空緩沖,信息緩沖,設備忙,啟動設備,緩沖入io鏈,傳輸完,T,F,F,T,釋放空緩沖,io鏈空,取一緩沖,啟動設備,T,F,8.7.5 輸入輸出設備： (磁帶、磁盤),塊型緩沖區(qū)：,進程空間,緩沖,IO

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

15、st and/or devtab 預先讀入的塊(breada) 延遲寫出的塊(bdwrite),字符型設備緩沖 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,塊型設備緩沖（頭部）,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 /設備IO隊列 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:設備號，blkno: 設備塊號 返回：緩沖區(qū)指針bp 步驟： 塊在b鏈中，且當前空閑 由av鏈摘除，標記

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

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

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

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

25、s) Redundant Array of Independent Disks /獨立磁盤冗余陣列 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 /導引卷不能是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 虛擬設備,概念 利用共享型設備實現(xiàn)的數(shù)量較多、速度較快的獨占型設備 引入 用戶直接使用獨占型設備效率低

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