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

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

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

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

4、(柱面)數(shù)每道扇區(qū)數(shù)每扇區(qū)字節(jié)數(shù) 三維數(shù)組柱面數(shù),盤(pán)面數(shù),扇區(qū)數(shù)按行存儲(chǔ)的數(shù)組元素的順序號(hào)就是磁盤(pán)的塊號(hào)。三維地址(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為盤(pán)面數(shù), n為扇區(qū)數(shù)8.2.2 存儲(chǔ)設(shè)備的物理特性(Cont.)扇區(qū)0扇區(qū)7扇區(qū)6扇區(qū)5扇區(qū)4扇區(qū)3扇區(qū)2扇區(qū)1未考慮讀寫(xiě)延遲的扇區(qū)編號(hào)(無(wú)交錯(cuò)):8.2.2 存儲(chǔ)設(shè)備的物理特性(Cont.)扇區(qū)0扇區(qū)7扇區(qū)3扇區(qū)6扇區(qū)2扇區(qū)5扇區(qū)1

5、扇區(qū)4考慮讀寫(xiě)延遲的扇區(qū)編號(hào)(單交錯(cuò))：8.2.2 存儲(chǔ)設(shè)備的物理特性(Cont.)扇區(qū)0扇區(qū)5扇區(qū)2扇區(qū)7扇區(qū)4扇區(qū)1扇區(qū)6扇區(qū)3考慮讀寫(xiě)延遲的扇區(qū)編號(hào)(雙交錯(cuò))：8.2.2 存儲(chǔ)設(shè)備的物理特性(Cont.)8.3 數(shù)據(jù)傳輸方式程序查詢方式 (programmed I/O) (polling) CPU and Device can not work in parallel 中斷驅(qū)動(dòng)方式 (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 程序控制查詢方式缺 點(diǎn): 處理機(jī)與設(shè)備串行工作; 消耗大量處理機(jī)時(shí)間。內(nèi)存映射輸入輸出: 將設(shè)備地址映射為內(nèi)存地址空間一部分, 硬件提供專用的輸入輸出指令。F查詢方式完成CPU啟動(dòng)設(shè)備結(jié)束8.3.2 中斷驅(qū)動(dòng)方式CPU計(jì)算啟動(dòng)設(shè)備計(jì)算計(jì)算中斷處理計(jì)算設(shè)備工作特點(diǎn): CPU與設(shè)備并行工作 設(shè)備多時(shí)對(duì)CPU打擾多8.3.3 DMA方式設(shè)備操作碼內(nèi)存地址計(jì)數(shù)器忙碌標(biāo)志狀態(tài)寄存器緩沖區(qū)DMA控制器opcodeoperands

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

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

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

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

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

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

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

14、訪問(wèn)時(shí)間為：Ta=Ts+Tr+Tt =mn+s+1/(2r)+1/(rM)8.6.2 磁盤(pán)引臂調(diào)度算法磁盤(pán)引臂調(diào)度(disk head scheduling)先到先服務(wù)(FCFS) 請(qǐng)求序列: 130, 42, 180, 15, 108, 68, 97移動(dòng)量: (130-53)+(130-42)+(180-42)+(180-15)+ (108-15)+(108-68)+(97-68)=6300 15 42 53 68 97 108 130 180 199最短查找時(shí)間優(yōu)先(SSTF) 請(qǐng)求序列: 130, 42, 180, 15, 108, 68, 970 15 42 53 68 97 108

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

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

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

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

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

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

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

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

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

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

25、區(qū), 長(zhǎng)度8字節(jié)(6字符+2指針);組成公共緩沖池, 所有字符型設(shè)備公用;緩沖區(qū)或?qū)儆赾freelist, 或?qū)儆谀匙址O(shè)備(eg. tty,lp)塊型緩沖50個(gè)緩沖區(qū), 長(zhǎng)度514字節(jié);組成公共緩沖池, 所有塊型設(shè)備公用;緩沖區(qū)可屬于bfreelist and/or devtab預(yù)先讀入的塊(breada)延遲寫(xiě)出的塊(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字符型設(shè)備緩沖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塊型設(shè)備緩沖(頭部)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 /設(shè)備I/O隊(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 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:設(shè)備號(hào)，blkno: 設(shè)備塊號(hào)返回：緩沖區(qū)指針bp步驟：塊在b鏈中，且當(dāng)前空閑由av鏈摘除，標(biāo)記BUSY, 返回緩沖塊指針塊在b鏈中，但BUSY(其它進(jìn)程在用)sleep(空閑事件發(fā)生)，由av鏈摘除，標(biāo)記BUSY, 返回緩沖塊指針不在b的鏈中，在av鏈上取到延遲寫(xiě)的塊寫(xiě)出該塊，分配下一個(gè)緩沖區(qū)不在b的鏈中，av鏈已空等待任意緩沖區(qū)變空閑的事件不在b的鏈中，在av鏈上得到空緩沖分配，由av鏈摘除，返回緩沖塊指針brelse(bp)參數(shù)：bp: 緩沖區(qū)頭指針?lè)祷兀簾o(wú)步驟：有等待者(b_flag&B_WAN

32、TED!=0),喚醒;bfreelist上有等待者,喚醒bp入av鏈bread(dev,blkno)參數(shù)：dev:設(shè)備號(hào)，blkno: 設(shè)備塊號(hào)返回：載有信息的緩沖區(qū)bp步驟：bp=getblk(dev,blkno)if (緩沖區(qū)數(shù)據(jù)有效)return(bp) /在cache中得到啟動(dòng)磁盤(pán)讀(d_actf/d_actl鏈)sleep(等待讀盤(pán)完成事件)中斷bp入b_forw/b_back鏈, 標(biāo)記BUSYreturn(bp) breada(dev,blkno,rablkno)參數(shù)：dev:設(shè)備號(hào)，blkno:讀塊號(hào)，rablkno:預(yù)讀塊號(hào)返回：blk緩沖塊指針rbp步驟：rbp=getblk

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

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

35、edundant Array of Inexpensive Disks compared with SLEDs (Single Large Expensive Disks)Redundant Array of Independent Disks /獨(dú)立磁盤(pán)冗余陣列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級(jí)別RAID級(jí)別: 行業(yè)標(biāo)準(zhǔn)規(guī)定的 數(shù)據(jù)在多個(gè)磁盤(pán)上的存放方法。 常見(jiàn)RAID級(jí)別: level0, , level5; RAID分條(stripping)數(shù)據(jù)存

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

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

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

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

42、Disk2block2block6block10Disk3block3block7block11Disk4P0-3P4-7P8-11Disk5控 制 器(5,6)(11)讀請(qǐng)求讀請(qǐng)求8.9.1 RAID級(jí)別(Cont.)讀操作不進(jìn)行異或校驗(yàn), 可以并行;寫(xiě)操作要更新異或校驗(yàn)信息, 都訪問(wèn)校驗(yàn)盤(pán), 不能并行; 寫(xiě)操作時(shí)校驗(yàn)信息更新: P47=(block4 xor block4)xor p47異或校驗(yàn)信息用于磁盤(pán)發(fā)生故障時(shí)數(shù)據(jù)塊的恢復(fù)。 例如: 若block7所在的Disk4發(fā)生故障, 要恢復(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級(jí)別(Cont.)Level5 (塊級(jí)分布式異或校驗(yàn)): 數(shù)據(jù)分條以塊為單位, 異或校驗(yàn)信息分散循環(huán)保存在各磁盤(pán)上。block0block4block8block12P1619Disk1控 制 器(1)(6)寫(xiě)請(qǐng)求寫(xiě)請(qǐng)求block1block5block9P1215block16Disk2block2block6P811block13block17D

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

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