【正文】 08 130 180 199 Look Scan 磁盤引臂調(diào)度 (disk head scheduling) ? CSCAN（ CLOOK） – 請求序列： 130， 42， 180， 15， 108， 68， 97 特點：所有磁道地位最長等待時間相同 問題： diskhead stickiness（磁頭粘性） 0 15 42 53 68 97 108 130 180 199 CLook CScan 磁盤引臂調(diào)度 (disk head scheduling) ? Nstep SCAN（ N步掃描） ? 將磁盤請求隊列分為若干個長度為 N的子隊列，每個隊列內(nèi)采用 SCAN算法 ? 例子：磁道由外向內(nèi)編號 099,磁頭當(dāng)前位置 20,向內(nèi)移動 ,N=4 ? 12, 5, 7, 30, 60, 77, 13, 26, 61, 80, 53, 66 ? 20→ 30→ 12→ 7→ 5→ 13→ 26→ 60→ 77→ 80→ 66→ 61 → 53 ? 當(dāng) N很大時，接近 SCAN算法 ? 當(dāng) N=1時，蛻化為 FCFS算法 磁盤引臂調(diào)度 (disk head scheduling) ? FSCAN（ Freezing SCAN，凍結(jié)掃描 ) ? 將磁盤請求分為兩個子隊列， ? 服務(wù)隊列 ? 請求隊列 ? 用 SCAN算法掃描服務(wù)隊列，并為請求服務(wù)，服務(wù)期間新到達的請求入請求隊列 ? 掃描完成后交換兩個隊列的地位 磁盤 I/O參數(shù) ? 首先分析一下讀 /寫一個磁盤塊需要多少時間。 消耗大量處理機時間 . 中斷驅(qū)動方式 ? CPU ? 計算 ? 啟動設(shè)備 ? 計算 ? … ? 計算 ? 中斷處理 ? 計算 設(shè)備 : 工作 特點 : CPU與設(shè)備并行工作 設(shè)備多時對 CPU打擾多 DMA方式 ③ 數(shù)據(jù)傳輸 CPU DMA 控制器 內(nèi)存 地 址 計 數(shù) 控 制 緩沖 磁盤 ⑤ 中斷 ② DMA請求 總線 磁盤 控制器 ④ 回答 ① DMA編程 啟動 中斷 狀態(tài) DMA方式 . ? ① CPU通過設(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ā)出中斷信號 . 通道方式 ? 通道 ? 負(fù)責(zé) IO操作的處理機 ? 指令系統(tǒng) ? 基本操作：控制、讀、寫、轉(zhuǎn)移、結(jié)束 ? 指令格式：（操作碼，傳輸量，特征位，地址） ? 運控部件 ? CAW， CCW， CSW， CDW ? 存儲區(qū)域（與 CPU共用內(nèi)存 ,通道內(nèi)有緩沖區(qū)） ? 通道程序， IO數(shù)據(jù)（ channel does have its buffers） 通道程序執(zhí)行過程： 按 CAW取通道命令 ?CCW （ CAW） +1 ?CAW 是通道結(jié)束命令 執(zhí)行此命令 F 向 CPU發(fā)中斷 一個通道程序可以控制若干設(shè)備進行多次 IO傳輸。 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 12 13 14 15 16 17 三維地址 ?一維地址： b=i?m?n+j?n+k 一維地址 ?三維地址： i=b?(m?n) j=b mod (m?n) ? n k=b mod (m?n) 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圈 (展開 ), 內(nèi)側(cè)轉(zhuǎn)速 :530轉(zhuǎn) /分 。第八章 設(shè)備與 I/O管理 ? 設(shè)備及其分類 ? 設(shè)備的物理特性 ? IO傳輸方式（查詢、中斷、通道、 DMA） ? 設(shè)備分配與去配 ? 設(shè)備驅(qū)動 ? 設(shè)備調(diào)度 ? 緩沖技術(shù) ? 輸入輸出進程 ? RAID技術(shù) ? 虛擬設(shè)備 設(shè)備及其分類 ? 用途 ? 存儲型設(shè)備 ? 磁盤，磁帶，光盤 ? IO型設(shè)備 ? 掃描儀，打印機， mouse， keyboard，monitor， ? 網(wǎng)絡(luò)設(shè)備 ? 網(wǎng)卡，交換機， etc. 設(shè)備及其分類 ? 管理 ? 共享型設(shè)備（塊型） ? 多個進程的 IO操作以塊為單位可以交叉 ? 獨占型設(shè)備（塊型） ? 多個進程的 IO操作以塊為單位不宜交叉 ? 獨占型設(shè)備（字符型） ? 多個進程的 IO操作以字符為單位不能交叉 IO設(shè)備的物理特性 傳輸一字節(jié)發(fā)生一次中斷 存儲設(shè)備的物理特性 磁帶的物理特性 頭標(biāo) 信息塊 信息塊 信息塊 ……………. 尾標(biāo) 間隙 操作：反繞，正向查找，反向查找，讀，寫， … 地址：一維 文件：順序結(jié)構(gòu)（一個文件占若干連續(xù)塊） 設(shè)備的物理特性 ... 磁盤組的物理特性 ... ... … … 盤面 0 盤面 1 盤面 2 盤面 m1 扇區(qū) 1 扇區(qū) 0 扇區(qū) n1 柱面 0 柱面 l1 … ... 引臂 柱面號 i 盤面號 j 扇區(qū)號 k 塊號 b（一維地址） （三維地址） 編址方法：使相鄰塊物理上最近 例子： l=2。 m=3。 外側(cè)轉(zhuǎn)速 :200轉(zhuǎn) /分 (密度均勻 ,讀取速度均勻 ) …… … Data ECC P 14個 bit構(gòu)成一個 symble 42個 symble構(gòu)成一個 frame 98個 frame構(gòu)成一個 sector Sector 2352bytes 588bits的 frame 各包含 24字節(jié) Preamble: 16bytes, 前 12bytes為 : 00FFFFFFFFFFFFFFFFFFFF00 后隨 3bytes扇區(qū)編號 ,最后字節(jié)為 mode 2048字節(jié) 288字節(jié) 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) ? special processor for dealing with io operations ? 直接內(nèi)存方式 (DMA) ? DMA controller in charge of block io 程序控制查詢方式 CPU啟動設(shè)備 完成 F T 缺點 : 處理機與設(shè)備串行工作 。 T 通道類型 ? 字節(jié)多路通道 (byte multiplexer channel) ? 多個非分配型子通道，連接低速外圍設(shè)備 ? 數(shù)組選擇通道 (block selector channel) ? 一個分配型子通道，連接多臺高速設(shè)備 ? 數(shù)組多路通道 (block multiplexer channel) ? 多個非分配型子通道，連接多臺高速設(shè)備 設(shè)備、通道、內(nèi)存連接 選擇通道 磁盤 字節(jié)多路通道 打印機 輸入機 內(nèi)存儲器 處理機 磁帶 數(shù)組多路通道 設(shè)備的分配與去配 ? 獨占型設(shè)備的分配與去配 ? 塊型獨占 ? 字符型獨占 ? 共享型設(shè)備的分配與去配 ? 塊型共享 數(shù)據(jù)結(jié)構(gòu) 設(shè)備控制塊 (UCB) 通道控制塊 (CCB) 設(shè)備標(biāo)識 設(shè)備狀態(tài) 相連通道 占有設(shè)備進程 通道標(biāo)識 通道狀態(tài) 通道類型 占有通道進程 系統(tǒng)設(shè)備表 (SDT) 設(shè)備類 總數(shù) 設(shè)備等待隊列 UCB表指針 … … … … lp m Sm UCB UCB … UCB …