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

2、間隙操作：反繞，正向查找，反向查找，讀，寫，地址：一維文件：順序構(gòu)造一個文件占假設(shè)干延續(xù)塊8.2 設(shè)備的物理特性.磁盤組的物理特性.盤面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

3、11 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ū)0扇區(qū)7扇區(qū)6扇區(qū)5扇區(qū)4扇區(qū)3扇區(qū)2扇區(qū)1.扇區(qū)0扇區(qū)7扇區(qū)3扇區(qū)6扇區(qū)2扇區(qū)5扇區(qū)1扇區(qū)4思索讀寫延遲的扇區(qū)編號(單交錯)：.扇區(qū)0扇區(qū)5扇區(qū)2扇區(qū)7扇區(qū)4扇區(qū)1扇區(qū)6扇區(qū)3思索讀寫延遲的扇區(qū)編號(雙交錯)：.光盤的物理特性: 讀取原理: pit/land 螺旋線,22188圈(展開5.6km), 內(nèi)側(cè)轉(zhuǎn)速:530轉(zhuǎn)/分; 外側(cè)轉(zhuǎn)速:200轉(zhuǎn)/分(密度均勻,讀取速度均勻) Da

4、taECCP14個bit構(gòu)成一個symble42個symble構(gòu)成一個frame98個frame構(gòu)成一個sectorSector2352bytes588bits的frame各包含24字節(jié)Preamble: 16bytes, 前12bytes為: 00FFFFFFFFFFFFFFFFFFFF00后隨3bytes扇區(qū)編號,最后字節(jié)為mode2048字節(jié)288字節(jié).8.3 I/O 傳輸方式IO操作演化歷史程序查詢方式 (programmed IO) (polling)CPU and Device can not work in parallel 中斷方式 (interrupt)CPU and dev

5、ice can work in parallel, too many interrupts for CPU通道方式 (channel)special processor for dealing with io operations直接內(nèi)存方式 (DMA)DMA controller in charge of block io.8.3.1 程序控制查詢方式CPU啟動設(shè)備完成FT缺陷: 處置機與設(shè)備串行任務(wù); 耗費大量處置機時間.8.3.2 中斷驅(qū)動方式CPU計算啟動設(shè)備計算計算中斷處置計算設(shè)備:任務(wù)特點: CPU與設(shè)備并行任務(wù) 設(shè)備多時對CPU打擾多.8.3.3 DMA方式 數(shù)據(jù)傳輸CPUDMA

6、控制器內(nèi)存地 址計 數(shù)控 制緩沖磁盤 中斷 DMA懇求總線磁盤控制器 回答 DMA編程.8.3.3 DMA方式. CPU經(jīng)過設(shè)置DMA控制器實現(xiàn)DMA編程，同時啟動磁盤控制器由磁盤讀入數(shù)據(jù)至內(nèi)部緩沖區(qū)并進展和校驗；DMA控制器向磁盤控制器發(fā)出讀懇求，并將內(nèi)存地址放在地址總線上；磁盤控制器將字節(jié)傳到內(nèi)存指定單元；磁盤控制器向DMA控制器發(fā)送回答；DMA控制器將內(nèi)部地址存放器加1同時將記數(shù)減1，反復(fù)上述過程直至計數(shù)值為0，此時DMA控制器向CPU發(fā)出中斷信號. .8.3.4 通道方式通道擔任IO操作的處置機指令系統(tǒng)根本操作：讀、寫、控制、轉(zhuǎn)移、終了指令格式：操作碼，傳輸量，特征位，地址運控部件CA

7、W，CCW，CSW，CDW存儲區(qū)域與CPU共用內(nèi)存,通道內(nèi)有緩沖區(qū)通道程序，IO數(shù)據(jù)channel does have its buffers.通道程序執(zhí)行過程：按CAW取通道命令CCWCAW+1 CAW是通道終了命令執(zhí)行此命令F向CPU發(fā)中斷一個通道程序可以控制假設(shè)干設(shè)備進展多次IO傳輸。T.通道類型字節(jié)多路通道(byte multiplexer channel) 多個非分配型子通道，銜接低速外圍設(shè)備數(shù)組選擇通道(block selector channel) 一個分配型子通道，銜接多臺高速設(shè)備數(shù)組多路通道(block multiplexer channel) 多個非分配型子通道，銜接多臺高

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

9、 釋放：(1) 找SDT表對應(yīng)入口 (2) 查UCB表，去配 (3) V(Sm) . 8.4 設(shè)備的分配與去配共享型設(shè)備的分配與去配用戶運用共享型設(shè)備活動運用，運用，運用特征來自文件系統(tǒng)；每次讀寫一塊；通常經(jīng)過緩沖；排隊優(yōu)化。運用IO操作.8.5 設(shè)備驅(qū)動通道程序CCW指令序列靜態(tài)編制或動態(tài)生成設(shè)備啟動通道啟動中斷處置通道向CPU發(fā)的中斷.8.5 設(shè)備驅(qū)動設(shè)備CAWCCWCDWCSWCCW1CCW2CCWi.CCWn數(shù)據(jù)區(qū).構(gòu)成通道程序.地址CAW.啟動通道.中斷處置.啟動中斷內(nèi)存CPU通道 .8.6 設(shè)備調(diào)度優(yōu)化效力順序思索要素公平性防止餓死高效性減少磁盤引臂挪動量.磁盤引臂調(diào)度(disk

10、head scheduling)先到先效力FCFS懇求序列：130，42，180，15，108，68，970 15 42 53 68 97 108 130 180 199挪動量: (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，970 15 42 53 68 97 108 130 180 199挪動量: (53-42)+(180-42)+(180-15)=314.磁盤引臂調(diào)度(di

11、sk head scheduling)SCANLOOK懇求序列：130，42，180，15，108，68，97SCAN挪動量: (53-0)+(180-0)=233LOOK挪動量: (53-15)+(180-15)=2030 15 42 53 68 97 108 130 180 199 Look Scan.磁盤引臂調(diào)度(disk head scheduling)C-SCANC-LOOK懇求序列：130，42，180，15，108，68，97特點：一切磁道位置最長等待時間一樣0 15 42 53 68 97 108 130 180 199 C-Look C-Scan.8.7 緩沖技術(shù)設(shè)備處置數(shù)據(jù)

12、到達與分開速度不一致所采用的技術(shù)。Buffering vs. Cachingbuffering: one data copycaching: multiple data copy (slow多, fast少)硬緩沖與軟緩沖 硬緩沖區(qū)通常設(shè)在設(shè)備中 軟緩沖區(qū)通常設(shè)在內(nèi)存系統(tǒng)空間中 私用緩沖與公共緩沖 一個緩沖區(qū)與一個固定設(shè)備相聯(lián)絡(luò)，不同設(shè)備運用不同的緩沖區(qū) 利用率低 緩沖區(qū)由系統(tǒng)一致管理，按需求動態(tài)分派給正在進展I/O傳輸?shù)脑O(shè)備.空緩沖空緩沖空緩沖.head共n個Var buf_num:semaphore; (init n) mutex:semaphore; (init 1)1. 懇求 2. 釋

13、放(1) P(buf_num) P(mutex)(2) P(mutex) 空緩沖入鏈尾(3) 取鏈頭空緩沖 V(mutex)(4) V(mutex) V(buf_num)緩沖池管理 tail.8.7.5 緩沖技術(shù)實現(xiàn)：輸入設(shè)備 進程空間緩沖輸入設(shè)備緩沖緩沖.io鏈.進程方面：中斷方面：IO鏈空設(shè)備忙懇求空緩沖啟動設(shè)備等待由io鏈取一緩沖信息進程空間釋放空緩沖緩沖入io鏈有等待進程喚醒傳輸終了懇求空緩沖啟動設(shè)備FTFTFTTF.8.7.5 緩沖技術(shù)實現(xiàn)：輸出設(shè)備 進程空間緩沖輸出設(shè)備緩沖緩沖.io鏈.進程方面：中斷方面：懇求一空緩沖信息緩沖設(shè)備忙啟動設(shè)備緩沖入io鏈傳輸完TFFT釋放空緩沖io鏈

14、空取一緩沖啟動設(shè)備TF.8.7.5 輸入輸出設(shè)備：(磁帶、磁盤) 緩沖區(qū)頭緩沖區(qū)體設(shè)備塊號IO標識等待進程塊型緩沖區(qū)： 進程空間緩沖IO設(shè)備緩沖緩沖.io鏈.進程方面(輸入)：進程方面(輸出)：中斷方面：懇求空緩沖填寫頭部設(shè)備任務(wù)入io鏈尾啟動設(shè)備信息進程釋放緩沖懇求空緩沖填寫頭部信息緩沖設(shè)備任務(wù)啟動設(shè)備入io鏈輸入喚醒等待者釋放空緩沖io鏈空取一緩沖啟動設(shè)備FTFTTFFT等待.UNIX緩沖字符型緩沖100個緩沖區(qū)，長度8字節(jié)(6字符+2指針)組成公共緩沖池，一切字符型設(shè)備公用緩沖區(qū)或?qū)儆赾freelist, 或?qū)儆谀匙址O(shè)備(eg. tty,lp)塊型緩沖50個緩沖區(qū)，長度514字節(jié)組成公

15、共緩沖池，一切塊型設(shè)備公用緩沖區(qū)可屬于bfreelist 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

16、last block.struct 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

17、 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:.str

18、uct devtab /設(shè)備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 queuechar buffersNBUF514; /塊型緩沖區(qū)struct buf bfreelist; /緩沖區(qū)頭部的鏈頭.

19、相關(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 t

20、he 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 implied.getblk(dev,blkno)參數(shù)： dev:設(shè)備號，blkno: 設(shè)備塊號前往：緩沖區(qū)指針bp步驟：塊在b鏈中，且當前空閑由av鏈摘除，標志BUSY

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

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

23、else(rabp) /入av鏈else /緩沖區(qū)從av鏈得到啟動設(shè)備讀入(d_actf/d_actl鏈) /中斷時入b鏈和av鏈iowait(rbp)return(rbp).bwrite(bp)參數(shù)：bp：緩沖區(qū)指針步驟：入設(shè)備d_act隊列(假設(shè)設(shè)備不忙啟動設(shè)備)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_DONEbp入設(shè)備b_forw/b_back隊列brelse(bp)

24、, (bp入av鏈).bawrite(bp)參數(shù)：bp: 緩沖區(qū)頭指針前往：無步驟：bp-b_flag =| B_ASYNCbwrite(bp)中斷(入b_act隊列)入av隊列.8.8 輸入輸出進程專門擔任IO傳輸?shù)倪M程另外一種IO方式效力方式C/S Model特點界面明晰,方便運用兩次進程切換,速度問題.8.9 RAID技術(shù)RAID: Redundant Array of Inexpensive Diskscompared with SLEDs (Single Large Expensive Disks)Redundant Array of Independent Disks /獨立磁盤冗

25、余陣列Proposed by researchers at UC BerkeleyDavid A. PattersonBackgrounddisk access speed increases slowly compared with CPUsolution: multiple parallel componentObjectiveenhanced performancehigh reliability.RAID技術(shù)RAIDRAID is a set of physical disks viewed by the operating system as a single logical dri

26、veData are distributed across an array of physical drivesRedundant disk capacity is used to store parity information, which guarantees data recoverability in case of disk failureHardware RAID vs. Software RAIDhardware based: special controller Windows NT, 2000, UNIX support software RAIDSCSI RAID vs

27、. IDE RAIDperformance: SCSI outperforms IDEprice: IDE beats SCSI.8.9.1 RAID級別How to organize data across multiple disks? Industry standards scheme levels:level 0, , level 5level 6, level 7level 01/10level 03/30level 05/50level 15/51.Level 0Strip(Striping): data are striped and stored on multiple dis

28、kshigh data transfer capacity no fault toleranced0d3d6d9disk0d1d4d7d10disk1d2d5d8d11disk2d0,d1,d2,d3,d11.Level 1Mirror(mirroring)completely duplicatedhigh recoverabilityexpensived0d1d2d3disk1d0d1d2d3disk2d0,d1,d2,d3,.Level 0+1RAID01/10high reliabilityhigh availabilityexpensived0d2d4d6disk1d1d3d5d7di

29、sk2d0,d1,d2,d3,d4,d5,d6,d7d0d2d4d6disk0d1d3d5d7disk3.Level 5Strip + paritysafety between 1 and 0economy between 1 and 0speed 0, less than 1d1d4p3d9disk1d2p1d7d10disk2d0,d1,d2,d3,d4,d5,d6,d7d0d3d6p4disk0p0d5d8d11disk3.JBOD - SPANNot a standard RAID leveljust bundle of disksno performance improvementn

30、o safety guaranteed0d1d2d3disk0d4d5disk1disk2d1,d2,d3,d4,d5.RAID 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

31、on Software RAIDPros:cost lesssimplicityCons:performanceboot volume limitation /導(dǎo)引卷不能是RAIDlevel support: only 0,1,5 are supportedOS compatibility: multiple problemother software compatibilityreliabilitysoftware bugs.Benefit from RAIDIncreased read/write speedImproved data reliabilityEnlarged storage

32、 capacitymultiple disks viewed as a single volume.8.10 虛擬設(shè)備概念利用共享型設(shè)備實現(xiàn)的數(shù)量較多、速度較快的獨占型設(shè)備引入用戶直接運用獨占型設(shè)備效率低實現(xiàn)輸入型虛擬設(shè)備輸出型虛擬設(shè)備虛擬設(shè)備的例子SPOOLing輸入SPOOLing輸出.8.7.1 虛擬設(shè)備引入用戶運用獨占型設(shè)備活動：懇求，運用，運用，運用，釋放缺陷：速度：CPU與設(shè)備速度不匹配設(shè)備利用率：占有期間不一定不斷運用進程獨占此設(shè)備.方法：在進程與獨占型設(shè)備之間添加共享設(shè)備緩沖虛擬設(shè)備虛擬設(shè)備虛擬設(shè)備虛擬設(shè)備進程獨占設(shè)備 共享設(shè)備如磁盤延續(xù)傳輸延續(xù)傳輸.8.10.2 虛擬設(shè)備的實現(xiàn)輸入型虛擬設(shè)備的實現(xiàn)懇求：分配一虛設(shè)備分配一實設(shè)備信息由實設(shè)備虛設(shè)備去配該實設(shè)備運用：信息由虛設(shè)備進程空間釋放：去配虛設(shè)備.輸出型虛擬設(shè)備的實現(xiàn)懇求：分配一虛設(shè)備運用：信息由進程空間虛設(shè)備釋放：分配一實設(shè)備信息由虛設(shè)備實設(shè)備去配實設(shè)備去配虛設(shè)備8.10.2 虛擬設(shè)備的實現(xiàn).8