操作系統(tǒng)：13第十四章 操作系統(tǒng)理

1、第十四章 操作系統(tǒng)理論操作系統(tǒng)理論模型：自動機模型 描述進程與資源建立操作系統(tǒng)形式化理論14.1 預備知識例14-1 自動駕駛的汽車汽車工作的抽象描述: 有限個狀態(tài): 直行、停止、左轉(zhuǎn)、右轉(zhuǎn); 有限個命令: 啟動、停止、左轉(zhuǎn)、右轉(zhuǎn); 有限控制器: 汽車在某狀態(tài)下接受某個命令 轉(zhuǎn)換到相應的狀態(tài)。a b c d （汽車）有限控制器(汽車)單帶有限自動機14.1 預備知識例14-2 郵局單人電話間汽車工作的抽象描述: 有限個狀態(tài): 直行、停止、左轉(zhuǎn)、右轉(zhuǎn); 有限個命令: 啟動、停止、左轉(zhuǎn)、右轉(zhuǎn); 有限控制器: 汽車在某狀態(tài)下接受某個命令 轉(zhuǎn)換到相應的狀態(tài)。a b c d （汽車）有限控制器單帶有限自

2、動機8.2.2 存儲設備的物理特性卷頭標信息塊信息塊信息塊.卷尾標規(guī) 格: 1 in, 16磁道; 0.5 in, 9磁道(現(xiàn)可達18磁道); 每磁道一個磁頭。操 作: 反繞, 正向查找, 反向查找, 讀, 寫, 地 址: 一維文 件: 順序結(jié)構(gòu) (一個文件占若干連續(xù)磁帶塊 )存放信息: 記錄信息和控制信息。磁頭間隙磁帶的物理特性: 啟停型、順序訪問型設備8.2.2 存儲設備的物理特性(Cont.)磁盤的物理特性: 旋轉(zhuǎn)型設備移動臂(頭)磁盤組的物理結(jié)構(gòu)盤面 0盤面 2盤面 1盤面 m-1柱面 0柱面 l-1柱面 1扇區(qū) 0扇區(qū) 1扇區(qū)n-1引 臂柱面號i盤面號j扇區(qū)號k塊號b (一維地址)三

3、維地址 編址方法: 使相鄰塊物理上最近例子: 柱面數(shù)l=2, 盤面數(shù)m=2, 扇區(qū)數(shù)n=4柱面號：0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1盤面號：0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1扇區(qū)號：0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3塊 號: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 158.2.2 存儲設備的物理特性(Cont.) 最上、最下為伺侯面, 不存放信息, 用于磁頭定位; 若盤片數(shù)為 S，盤面數(shù)m2S-2=2(S-1); 每個盤面被分成2i個扇區(qū), 每個扇區(qū)含多個磁道。 存儲容量磁頭數(shù)磁道

4、(柱面)數(shù)每道扇區(qū)數(shù)每扇區(qū)字節(jié)數(shù) 三維數(shù)組柱面數(shù),盤面數(shù),扇區(qū)數(shù)按行存儲的數(shù)組元素的順序號就是磁盤的塊號。三維地址(i , j , k) 一維地址b： b=i m n + j n + k = (i m + j) n + k 一維地址b 三維地址(i , j , k) ： i=b (mn) j=b mod (mn) n k=b mod (mn) mod n其中：m為盤面數(shù), n為扇區(qū)數(shù)8.2.2 存儲設備的物理特性(Cont.)扇區(qū)0扇區(qū)7扇區(qū)6扇區(qū)5扇區(qū)4扇區(qū)3扇區(qū)2扇區(qū)1未考慮讀寫延遲的扇區(qū)編號(無交錯):8.2.2 存儲設備的物理特性(Cont.)扇區(qū)0扇區(qū)7扇區(qū)3扇區(qū)6扇區(qū)2扇區(qū)5扇區(qū)1

5、扇區(qū)4考慮讀寫延遲的扇區(qū)編號(單交錯)：8.2.2 存儲設備的物理特性(Cont.)扇區(qū)0扇區(qū)5扇區(qū)2扇區(qū)7扇區(qū)4扇區(qū)1扇區(qū)6扇區(qū)3考慮讀寫延遲的扇區(qū)編號(雙交錯)：8.2.2 存儲設備的物理特性(Cont.)8.3 數(shù)據(jù)傳輸方式程序查詢方式 (programmed I/O) (polling) CPU and Device can not work in parallel 中斷驅(qū)動方式 (interrupt) CPU and device can work in parallel, too many interrupts for CPU直接內(nèi)存方式 (DMA)DMA controller i

6、n charge of block I/O通道方式 (channel)special processor for dealing with I/O operations8.3.1 程序控制查詢方式缺 點: 處理機與設備串行工作; 消耗大量處理機時間。內(nèi)存映射輸入輸出: 將設備地址映射為內(nèi)存地址空間一部分, 硬件提供專用的輸入輸出指令。F查詢方式完成CPU啟動設備結(jié)束8.3.2 中斷驅(qū)動方式CPU計算啟動設備計算計算中斷處理計算設備工作特點: CPU與設備并行工作 設備多時對CPU打擾多8.3.3 DMA方式設備操作碼內(nèi)存地址計數(shù)器忙碌標志狀態(tài)寄存器緩沖區(qū)DMA控制器opcodeoperands

7、busystatusCPU123內(nèi)存45678.3.3 DMA方式(Cont.). CPU將操作數(shù)送入operands寄存器; CPU將操作碼送入opcode寄存器并啟動DMA控制器; DMA將busy置位, 不接受新命令, CPU可做其它操作; DMA控制設備與其緩沖區(qū)的數(shù)據(jù)傳輸; DMA控制設備其緩沖區(qū)與內(nèi)存的數(shù)據(jù)傳輸; DMA控制器將內(nèi)存地址寄存器加1同時將記數(shù)器減1，若計數(shù)器不為0, 則轉(zhuǎn); DMA復位busy寄存器, 并向CPU發(fā)中斷”傳輸完”; CPU讀入status, 確認操作成功。8.3.4 通道方式指令系統(tǒng)基本操作: 讀、寫、控制、轉(zhuǎn)移、結(jié)束指令格式: 運控部件通道地址字CA

8、W: 存放下一條通道指令地址;通道命令字CCW: 存放當前正在執(zhí)行的通道指令;通道狀態(tài)字CSW: 存放通道、控制器、設備的狀態(tài); 包括I/O完成信息、出錯信息、復執(zhí)次數(shù)等;通道數(shù)據(jù)字CDW: 暫存設備與內(nèi)存之間的I/O數(shù)據(jù)。存儲區(qū)域 (與CPU共用內(nèi)存)通道程序，I/O數(shù)據(jù)操作碼傳輸字節(jié)數(shù)特征位地址信息通 道: 負責I/O操作的處理器。 以內(nèi)存為中心, 支持塊傳輸。8.3.4 通道方式(Cont.)通道程序執(zhí)行過程通道程序執(zhí)行流程按CAW取通道指令CCW(CAW)+1CAWCCW是結(jié)束指令向主機發(fā)中斷請求結(jié) 束F執(zhí)行CCW一個通道程序可以控制傳輸多組數(shù)據(jù)。通道類型字節(jié)多路通道(byte mul

9、tiplexer channel)多個非分配型子通道，連接低速外圍設備數(shù)組選擇通道(block selector channel)一個分配型子通道，連接多臺高速設備數(shù)組多路通道(block multiplexer channel) 多個非分配型子通道，連接多臺高速設備8.3.4 通道方式(Cont.)設備、通道、內(nèi)存連接數(shù)組選擇通道磁盤字節(jié)多路通道打印機輸入機內(nèi)存處理器磁帶數(shù)組多路通道8.3.4 通道方式(Cont.)8.4 設備分配與去配獨占型設備的分配與去配 塊型獨占 字符型獨占共享型設備的分配與去配 塊型共享8.4.1 獨占型設備的分配與去配 數(shù)據(jù)結(jié)構(gòu)設備控制塊(UCB)設備標識(設備號

10、)設備狀態(tài)相連通道占有設備進程通道控制塊(CCB)通道標識通道類型等待隊列占有通道進程系統(tǒng)設備表(SDT)設備名設備數(shù)等待隊列UCB表指針printermSmPtr打印機的UCB表UCB1(printer1)UCB2(printer2)UCBm(printerm)8.4.1 獨占型設備的分配與去配 用戶使用獨占型設備活動： 申請，使用，使用，使用，釋放 申請: 根據(jù)設備名查SDT表； P(Sm)； 查UCB表找一空閑設備并分配。 使用: 分配通道(若通道占用則等待); IO數(shù)據(jù)傳輸; 去配通道。 釋放: 根據(jù)釋放設備名找SDT表對應入口; 根據(jù)設備號查UCB表，找到該設備去配; V(Sm) 8

11、.4.2 共享型設備的分配與去配 用戶使用共享型設備活動： 使用，使用，使用 特征： 來自文件系統(tǒng)、虛擬存儲系統(tǒng)、 輸入/輸出管理程序; 每次讀寫一塊； 通常經(jīng)過緩存； 排隊優(yōu)化。 使用： IO傳輸8.5 設備驅(qū)動8.5.1 通道程序通道指令序列所構(gòu)成的程序;靜態(tài)編制或根據(jù)I/O要求動態(tài)生成;執(zhí)行1次I/O, 或多次I/O;可與處理器的操作并行;多個通道程序可以并行。8.5.2 設備啟動通道程序形成后:處理器將通道程序起始地址放到內(nèi)存指定單元;運行通道啟動指令啟動通道;由指定內(nèi)存單元取通道程序起始地址CAW;執(zhí)行通道程序。 8.5.3 中斷處理.形成通道程序.啟動通道.中斷處理.CPUCCW1

12、CCW2CCWi.CCWn數(shù)據(jù)區(qū)設備內(nèi)存通道程序通道CAWCCWCSWCDW中 斷8.6 設備調(diào)度優(yōu)化服務順序考慮因素公平性：防止餓死高效性：減少磁盤引臂移動量8.6.1 磁盤I/O參數(shù)讀/寫一個磁盤塊需要時間Ta 的計算 一般由如下三個因素確定：尋道時間(seek time) 將磁盤引臂移動到指定柱面所需要的時間;旋轉(zhuǎn)延遲(rotational delay) 指定扇區(qū)旋轉(zhuǎn)到磁頭下的時間;傳輸時間(transfer time) 讀/寫一個扇區(qū)的時間。8.6.1 磁盤I/O參數(shù)尋道時間Ts 計算公式如下:Ts = mn +s其中 n 為跨越磁道數(shù), m 為跨越一個磁道所用時間, s 為啟動時間。

13、旋轉(zhuǎn)延遲Tr 計算公式如下:Tr = 1/(2 r )其中, r 為磁盤轉(zhuǎn)速(單位: 周/分鐘)。該公式給出的是平均旋轉(zhuǎn)延遲,它是磁盤旋轉(zhuǎn)一周時間的一半,即旋轉(zhuǎn)半周所花費的時間。8.6.1 磁盤I/O參數(shù)傳輸時間Tt 計算公式如下：Tt =b/( r N )其中，b 為讀/寫字節(jié)數(shù), r 為磁盤轉(zhuǎn)速, N 為一條磁道上的字節(jié)數(shù)。 8.6.1 磁盤I/O參數(shù)因此，可將訪問b個字節(jié)的時間Ta表示為:Ta=Ts+Tr+Tt =mn+s+1/(2r)+b/(rN)訪問磁盤通常是以扇區(qū)(塊)為單位的， 令M 為一個磁道上扇區(qū)的個數(shù), 則 每扇區(qū)的字節(jié)數(shù)=每磁道字節(jié)數(shù)/每磁道扇區(qū)數(shù) =N/M 則一個扇區(qū)的

14、訪問時間為：Ta=Ts+Tr+Tt =mn+s+1/(2r)+1/(rM)8.6.2 磁盤引臂調(diào)度算法磁盤引臂調(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)=6300 15 42 53 68 97 108 130 180 199最短查找時間優(yōu)先(SSTF) 請求序列: 130, 42, 180, 15, 108, 68, 970 15 42 53 68 97 108

15、130 180 199移動量: (53-42)+(180-42)+(180-15)=314問題: 存在饑餓和餓死問題。8.6.2 磁盤引臂調(diào)度算法掃描算法(SCAN) 不停地雙向往復掃描磁道到盡頭, 雙向響應路徑請求。 請求序列: 130, 42, 180, 15, 108, 68, 97移動量: (53-0)+(180-0)=2330 15 42 53 68 97 108 130 180 1998.6.2 磁盤引臂調(diào)度算法LOOK算法: 又稱電梯算法 前進方向有請求, 則響應; 若前方?jīng)]請求且反向有請求, 則改變方向響應請求。 否則, 停止。 請求序列: 130, 42, 180, 15,

16、108, 68, 97移動量: (53-15)+(180-15)=2030 15 42 53 68 97 108 130 180 1998.6.2 磁盤引臂調(diào)度算法循環(huán)掃描(C-SCAN) 單方向掃描響應路徑請求; 到頭后快速移動到另一頭繼續(xù)掃描。 請求序列: 130, 42, 180, 15, 108, 68, 97移動量=(199-53)+(199-0)+(42-0)=387特點：所有磁道地位、最長等待時間相同。0 15 42 53 68 97 108 130 180 1998.6.2 磁盤引臂調(diào)度算法C-LOOK算法 前進方向有請求, 則響應; 若前方?jīng)]請求且反向有請求, 則移到反向最遠

17、端請求位置繼續(xù)沿原方向掃描響應請求。 否則, 停止。 請求序列: 130, 42, 180, 15, 108, 68, 97移動量=(180-53)+(180-15)+(42-15)=3190 15 42 53 68 97 108 130 180 1998.6.2 磁盤引臂調(diào)度算法SCAN和LOOK存在”磁頭粘性”(arm stickiness)問題。N-step SCAN和凍結(jié)掃描(Freezing SCAN)N步掃描 將磁盤請求隊列分為若干個長度為N的子隊列, 每個隊列內(nèi)采用SCAN算法。例: 磁道由外向內(nèi)編號099, 磁頭當前位置20,向內(nèi)移動,N=4請求序列:12, 5, 7, 30,

18、 60, 77, 13, 26, 61, 80, 53, 66響應序列:2030127513266077806661 53 當N很大時, 接近SCAN算法 當N=1時, 蛻化為FCFS算法8.6.2 磁盤引臂調(diào)度算法FSCAN: 請求隊列被”凍結(jié)”。 將磁盤請求分為兩個子隊列: 服務隊列 請求隊列 用SCAN算法掃描服務隊列, 并為請求服務, 服務期間新到達的請求入請求隊列; 掃描完成后交換兩個隊列的地位。8.6.2 磁盤引臂調(diào)度算法例8-3： 設有一個單磁頭的磁盤, 磁道由外向內(nèi)編號 0、1、2、199。 磁頭移動一個扇區(qū)(柱面?)所需時間為 1ms ; 每個磁道有 100 個扇區(qū); 磁盤轉(zhuǎn)

19、速 6000r/min。 當前引臂位置處于第100磁道 , 當前移動方向由外向內(nèi)， 并規(guī)定引臂向內(nèi)掃描時為路徑請求服務。 對于如下磁道請求 120、85、70、30，每個請求訪問對應磁道上 的一個扇區(qū)。采用C-LOOK引臂調(diào)度算法，問：(1) 給出引臂移動序列，計算引臂移動量和尋道時間， 忽略啟動時間；(2) 計算平均旋轉(zhuǎn)延遲時間；(3) 計算傳輸時間；(4) 計算所有訪問處理時間。8.6.3 磁盤訪問舉例解答：(1)磁盤引臂移動序列為: 100120307085， 跨越磁道數(shù)：20+90+40+15=165。 共需尋道時間1651ms=165ms.(2) 1次訪盤的旋轉(zhuǎn)延遲為：Tr=1/(2

20、r)=1/(2(6000/m)=1/(2(100/s)=5ms，4次訪盤的旋轉(zhuǎn)延遲為 45ms=20ms.(3) 1次訪盤的傳輸時間為：Tt=1/(rM)=1/(6000/m)100)=1/(100/s)100)=0.1ms， 4次訪盤的傳輸時間為40.1ms=0.4ms.(4)所有訪問處理時間=165+20+0.4=185.4(ms)。8.6.3 磁盤訪問舉例8.7 緩沖技術(shù)8.7.1 緩沖技術(shù)的引入 緩沖技術(shù): 處理數(shù)據(jù)到達與離開速度 不一致所采用的技術(shù)。Buffering vs. Cachingbuffering: one data copycaching: multiple data

21、copy8.7.2 硬緩沖與軟緩沖 硬緩沖區(qū)通常設在設備中, 由硬件實現(xiàn)；軟緩沖區(qū)通常設在內(nèi)存系統(tǒng)空間中, 由軟件實現(xiàn)。8.7.3 私用緩沖與公共緩沖 私用緩沖 一個緩沖區(qū)與一個固定設備相聯(lián)系, 不同設備使用不同的緩沖區(qū); 公共緩沖 緩沖區(qū)由系統(tǒng)統(tǒng)一管理, 所有緩沖區(qū)構(gòu)成緩沖池, 按需要動態(tài)分派給正在進行I/O傳輸?shù)脑O備。8.7.4 單緩沖、雙緩沖與循環(huán)緩沖緩沖技術(shù)分為: 單緩沖、雙緩沖、多緩沖以及緩沖池4種。 單緩沖: 設備與進程之間設一個緩沖區(qū); 數(shù)據(jù)傳輸模式為”進程緩沖區(qū)設備”; 處理器與設備對緩沖區(qū)的操作是串行; 雙緩沖: 設備與進程之間設置兩個緩沖區(qū); 數(shù)據(jù)傳輸時, 兩個緩沖區(qū)交替使

22、用; 提高處理器與設備之間的并行性。循環(huán)緩沖: 設備與進程之間設置多個緩沖區(qū), 并鏈成環(huán)形。 設置輸入指針in和輸出指針out。semaphore buf_avaiable; (init n)semaphore mutex; (init 1)1. 申 請 2. 釋 放 P(buf_avaiable) P(mutex) P(mutex) 空緩區(qū)如沖入緩沖池鏈頭 取緩沖池鏈頭空緩沖區(qū) V(mutex) V(mutex) V(buf_avaiable) 返回空緩沖區(qū)指針 緩沖池管理 8.7.5 緩沖池及其管理.head共 n 個空緩沖區(qū)空緩沖區(qū)空緩沖區(qū)8.7.6 緩沖技術(shù)的實現(xiàn)每個設備一個緩沖隊列,

23、 隊列的每塊緩沖區(qū)動態(tài)向系統(tǒng)申請。 輸入型設備輸入設備緩沖區(qū)緩沖區(qū)緩沖區(qū)進程空間I/O鏈通道程序操作系統(tǒng)輸入型設備緩沖示圖進程方面I/O鏈空設備忙申請空緩沖啟動設備由I/O鏈取一緩沖信息進程空間釋放空緩沖結(jié) 束TTFF等待 中斷方面緩沖入I/O鏈有等待進程TF喚醒傳輸完畢申請空緩沖啟動設備F結(jié) 束T輸入型設備緩沖技術(shù)的實現(xiàn)8.7.6 緩沖技術(shù)的實現(xiàn) 輸出型設備輸出設備緩沖區(qū)緩沖區(qū)緩沖區(qū)進程空間I/O鏈通道程序操作系統(tǒng)輸出型設備緩沖示圖8.7.6 緩沖技術(shù)的實現(xiàn)輸出型設備緩沖技術(shù)的實現(xiàn)進程方面申請空緩沖信息緩沖結(jié) 束TTFF中斷方面釋放空緩沖區(qū)I/O鏈空F由I/O鏈取一緩沖啟動設備傳輸結(jié) 束T設

24、備忙緩沖入I/O鏈啟動設備傳輸完8.7.6 緩沖技術(shù)的實現(xiàn) 輸入輸出設備(磁帶、磁盤)輸出/輸入設備緩沖區(qū)緩沖區(qū)緩沖區(qū)進程空間I/O鏈通道程序操作系統(tǒng)輸入輸出型設備緩沖示圖緩沖區(qū)頭設備物理塊號I/O方向標識等待進程緩沖區(qū)體緩沖區(qū)格式8.7.6 緩沖技術(shù)的實現(xiàn)進程輸入申請空緩沖信息進程空間填寫頭部設備工作緩沖區(qū)入I/O鏈尾啟動設備等待釋放空緩沖區(qū)結(jié) 束FTF中斷方面輸 入喚醒等待者釋放空緩沖TFI/O鏈空由I/O鏈取一緩沖啟動設備傳輸結(jié) 束T進程輸出申請空緩沖填寫頭部設備工作緩沖區(qū)入I/O鏈尾啟動設備T信息緩沖結(jié) 束F8.7.6 緩沖技術(shù)的實現(xiàn)UNIX緩沖(P300303)字符型緩沖100個緩沖

25、區(qū), 長度8字節(jié)(6字符+2指針);組成公共緩沖池, 所有字符型設備公用;緩沖區(qū)或?qū)儆赾freelist, 或?qū)儆谀匙址O備(eg. tty,lp)塊型緩沖50個緩沖區(qū), 長度514字節(jié);組成公共緩沖池, 所有塊型設備公用;緩沖區(qū)可屬于bfreelist 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

26、 device int c_cc; /character count int c_cf; /pointer to first block int c_cl; /pointer to 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; /posit

27、ion 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塊型設備緩沖(頭部)15 14 13 12 1

28、1 10 9 8 7 6 5 4 3 2 1 0B_READ/B_WRITEB_DONEB_ERRORB_BUSYB_WANTEDB_RELOCB_ASYNCB_DELWRIb_flag:struct devtab /設備I/O隊列 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 I/O que

29、ue struct buf *d_actl; /tail of I/O queuechar buffersNBUF514; /塊型緩沖區(qū)struct buf bfreelist; /緩沖區(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

30、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 buffe

31、r, with no io impliedgetblk(dev,blkno)參數(shù)： dev:設備號，blkno: 設備塊號返回：緩沖區(qū)指針bp步驟：塊在b鏈中，且當前空閑由av鏈摘除，標記BUSY, 返回緩沖塊指針塊在b鏈中，但BUSY(其它進程在用)sleep(空閑事件發(fā)生)，由av鏈摘除，標記BUSY, 返回緩沖塊指針不在b的鏈中，在av鏈上取到延遲寫的塊寫出該塊，分配下一個緩沖區(qū)不在b的鏈中，av鏈已空等待任意緩沖區(qū)變空閑的事件不在b的鏈中，在av鏈上得到空緩沖分配，由av鏈摘除，返回緩沖塊指針brelse(bp)參數(shù)：bp: 緩沖區(qū)頭指針返回：無步驟：有等待者(b_flag&B_WAN

32、TED!=0),喚醒;bfreelist上有等待者,喚醒bp入av鏈bread(dev,blkno)參數(shù)：dev:設備號，blkno: 設備塊號返回：載有信息的緩沖區(qū)bp步驟：bp=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:設備號，blkno:讀塊號，rablkno:預讀塊號返回：blk緩沖塊指針rbp步驟：rbp=getblk

33、(dev,blkno)if(信息無效)啟動設備讀入(d_actf/d_actl鏈)rabp=getblk(dev,rablkno)if (B_DONE) /緩沖區(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

34、(bp)參數(shù): bp: 緩沖區(qū)指針返回: 無步驟：標記b_flags =| B_DELWRI | B_DONEbp入設備b_forw/b_back隊列brelse(bp), (bp入av鏈)bawrite(bp)參數(shù)：bp: 緩沖區(qū)頭指針返回：無步驟：bp-b_flag =| B_ASYNCbwrite(bp)中斷(入b_act隊列)入av隊列8.8 輸入輸出進程 自主I/O方式: 進程執(zhí)行I/O操作; 專門負責I/O傳輸?shù)倪M程另外一種I/O模式服務模式;C/S ModelI/O實現(xiàn): 進程向I/O進程發(fā)消息;特 點界面清晰, 方便使用;兩次進程切換, 速度問題;8.9 RAID技術(shù)RAIDR

35、edundant Array of Inexpensive Disks compared with SLEDs (Single Large Expensive Disks)Redundant Array of Independent Disks /獨立磁盤冗余陣列Proposed by researchers at UC Berkeley David A. PattersonBackgrounddisk access speed increases slowly compared with CPUsolution: multiple parallel componentObjectiveenh

36、anced performancehigh reliabilityRAIDRAID is a set of physical disks viewed by the operating system as a single logical drive;Data are distributed across an array of physical drivesRedundant disk capacity is used to store parity information, which guarantees data recoverability in case of disk failu

37、re.Hardware RAID vs. Software RAIDhardware based: special controller;Windows NT, 2000, UNIX support software RAID.SCSI RAID vs. IDE RAIDperformance: SCSI outperforms IDE;price: IDE beats SCSI.8.9 RAID技術(shù)(Cont.)8.9.1 RAID級別RAID級別: 行業(yè)標準規(guī)定的 數(shù)據(jù)在多個磁盤上的存放方法。 常見RAID級別: level0, , level5; RAID分條(stripping)數(shù)據(jù)存

38、儲方式位級分條(bit-level stripping)塊級分條(block-level strpping)RAID衡量指標速 度: 是否支持多個訪問同時進行;可靠性: 是否能夠發(fā)現(xiàn)和改正錯誤;成 本: 是否有額外的開銷和開銷的大小。8.9.1 RAID級別(Cont.)Level0 (分條) : 數(shù)據(jù)分條以塊為單位 連續(xù)的數(shù)據(jù)條循環(huán)存放在多個磁盤上。訪問速度快； 經(jīng)濟，空間利用率100；無容錯能力，可靠性差。block0block4block8Disk1block1block5block9Disk2block2block6block10Disk3block3block7block11Disk

39、4控 制 器(4,5)(2,3)讀請求寫請求8.9.1 RAID級別(Cont.)Level1 (鏡像): 數(shù)據(jù)分條以塊為單位 采用分布鏡像(mirroring)方式存儲, 即完全相同的數(shù)據(jù)重復存放在兩個盤上。block0block3block6Disk1block1block4block7Disk2block2block5block8Disk3控 制 器(3,4)(8)讀請求寫請求block0block3block6Disk4block1block4block7Disk5block2block5block8Disk6訪問速度快; 讀一個盤、寫兩個盤;可靠性高;費用高, 是無鏡像磁盤數(shù)的2倍,

40、 空間利用率50。8.9.1 RAID級別(Cont.)Level2 (位級漢明糾錯碼奇偶校驗與恢復): 數(shù)據(jù)以位(bit)為單位分條, 分布存放在多個數(shù)據(jù)磁盤上; 漢明糾錯碼存放在糾錯磁盤上。bit0Disk1bit1Disk2bit2Disk3控 制 器(3,4,5)寫請求bit3Disk4bit4Disk5bit5Disk6bit6Disk78.9.1 RAID級別(Cont.)糾錯能力強, 可靠性高;需要較多糾錯盤存放漢明糾錯碼, 成本較高;不能同時為多個請求服務, 速度較慢:讀操作: 所有磁盤同時訪問, 數(shù)據(jù)與錯誤校驗碼被送到磁盤陣列控制器;寫操作: 必須同時訪問所有數(shù)據(jù)盤和糾錯盤。

41、8.9.1 RAID級別(Cont.)Level3 (位級單個奇偶校驗): 數(shù)據(jù)以位(bit)為單位分條, 分布存放在多個數(shù)據(jù)磁盤上; 只用一個冗余磁盤存放奇偶校驗位。bit0Disk1bit1Disk2bit2Disk3bit3Disk4奇偶校驗Disk5有一定容錯能力;存儲代價較低;讀寫需要訪問所有盤, 多個讀寫不能并行?？?制 器(0,1)等待(3)寫請求寫請求8.9.1 RAID級別(Cont.)Level4 (塊級異或校驗): 數(shù)據(jù)分條以塊為單位, 用異或運算產(chǎn)生校驗信息, 校驗信息保存在單獨的磁盤上。block0block4block8Disk1block1block5block9

42、Disk2block2block6block10Disk3block3block7block11Disk4P0-3P4-7P8-11Disk5控 制 器(5,6)(11)讀請求讀請求8.9.1 RAID級別(Cont.)讀操作不進行異或校驗, 可以并行;寫操作要更新異或校驗信息, 都訪問校驗盤, 不能并行; 寫操作時校驗信息更新: P47=(block4 xor block4)xor p47異或校驗信息用于磁盤發(fā)生故障時數(shù)據(jù)塊的恢復。 例如: 若block7所在的Disk4發(fā)生故障, 要恢復block7。 p47= block4 XOR block5 XOR block6 XOR block7

43、 則 p47 XOR (block4 XOR block5 XOR block6) =全0 XOR block7=block7 所以 block7= p47 XOR (block4 XOR block5 XOR block6) 8.9.1 RAID級別(Cont.)Level5 (塊級分布式異或校驗): 數(shù)據(jù)分條以塊為單位, 異或校驗信息分散循環(huán)保存在各磁盤上。block0block4block8block12P1619Disk1控 制 器(1)(6)寫請求寫請求block1block5block9P1215block16Disk2block2block6P811block13block17D

44、isk3block3P4-7block10block14block18Disk4P03block7block11block15block19Disk58.9.1 RAID級別(Cont.)磁盤數(shù)量至少為3個;讀操作可并行;不涉及相同數(shù)據(jù)盤和校驗盤的寫操作可以并行;對于單盤容量為S、數(shù)量為N的磁盤陣列, 有效存儲容量為: S(N-1) 磁盤利用率為: (N-1)/N任意磁盤發(fā)生故障, 均可根據(jù)其它N-1個磁盤恢復;8.9.1 RAID級別(Cont.)表8-1 RAID 級別的比較Level分條粒度讀并發(fā)性寫并發(fā)性冗余(容錯/開銷)0塊支持支持無1塊支持不支持鏡像2位不支持不支持漢明糾錯碼奇偶校

45、驗與恢復3位不支持不支持單個奇偶校驗4塊支持不支持塊級異或校驗5塊支持支持塊級分布式異或校驗8.9.2 硬件RAID與軟件RAID硬件RAID是RAID技術(shù)主流, 需RAID控制器、價格貴;軟件RAID不需專用RAID器, 成本低、性價比高; 軟件RAID問題:速度、可靠性不如硬件RAID; 系統(tǒng)兼容性: 同一臺機器的不同操作系統(tǒng)的軟件RAID的識別問題; 操作系統(tǒng)的引導問題。8.10 虛擬設備概 念：利用共享型設備 實現(xiàn)的數(shù)量較多、速度較快的獨占型設備。引 入：用戶直接使用獨占型設備效率低。實 現(xiàn) 輸入型虛擬設備 輸出型虛擬設備 虛擬設備的例子SPOOLing輸入SPOOLing輸出用戶使用獨占型設備活動：申請，使用，使用，使用，釋放進程獨占此設備8.10.1 虛擬設備的引入缺點:速 度: CPU與設備速度不匹配;設備利用率: 占有期間不一定一直使用。8.10.1 虛擬設備的引入(Cont.)方法: 在進程與