資工系網(wǎng)媒所NEWS試驗(yàn)室SSTF磁碟排程RSWiki課件

1、作業(yè)系統(tǒng) 第十五章 大量儲(chǔ)存結(jié)構(gòu)第1頁，共46頁。第十五章 大量儲(chǔ)存結(jié)構(gòu)磁碟排程 磁碟結(jié)構(gòu) FCFS 排程 SSTF 排程 SCAN 與 C-SCAN 排程 LOOK 與 C-LOOK 排程 演算法選擇 磁碟管理 RAID 結(jié)構(gòu) 儲(chǔ)存設(shè)備附加方式 其他儲(chǔ)存議題 摘要第2頁，共46頁。7/29/20222/45磁碟排程磁碟的存取時(shí)間是磁碟的搜尋時(shí)間與旋轉(zhuǎn)延遲之和搜尋時(shí)間是指磁碟臂將磁頭移到目標(biāo)資料磁區(qū)所在的磁柱上所花的時(shí)間旋轉(zhuǎn)延遲是指該資料磁區(qū)旋轉(zhuǎn)到磁頭所花費(fèi)的時(shí)間磁碟排程是降低磁碟平均搜尋時(shí)間最有效的方法第3頁，共46頁。7/29/20223/45磁碟結(jié)構(gòu)磁碟驅(qū)動(dòng)程式將磁碟視為一個(gè)邏輯上的一維

2、區(qū)塊陣列 常線速度 如光碟機(jī)讀取頭在讀取內(nèi)圈資料時(shí)轉(zhuǎn)速較高，而讀取外圈資料時(shí)轉(zhuǎn)速較低，因此每秒鐘讀寫頭所經(jīng)過的面積很接近，所以光碟機(jī)每秒鐘讀取的資料量也會(huì)固定 常角速度 如磁碟機(jī)轉(zhuǎn)動(dòng)磁盤存取資料時(shí)，每秒鐘旋轉(zhuǎn)的角度是固定的 第4頁，共46頁。7/29/20224/45FCFS 排程驅(qū)動(dòng)程式一次只接受一個(gè)要求，並依要求的次序服務(wù)，即先到先做的演算法FCFS 排程雖然簡單公平，卻不能提供最佳化的服務(wù) 第5頁，共46頁。7/29/20225/45FCFS 磁碟排程 0 16 39 55 67 69 100 120 122 181 199佇列 = 10018139120161226769讀寫頭的起始位

3、置55第6頁，共46頁。7/29/20226/45SSTF 排程先讀取最接近目前磁頭位置的磁柱，以減少磁頭的搜尋時(shí)間 SSTF 排程是一種最短工作優(yōu)先的排程，先完成花費(fèi)時(shí)間較少的工作，以降低平均等待時(shí)間第7頁，共46頁。7/29/20227/45 SSTF 磁碟排程 0 16 39 55 67 69 100 120 122 181 199佇列 = 10018139120161226769讀寫頭的起始位置 55第8頁，共46頁。7/29/20228/45SCAN 與 C-SCAN 排程SCAN 排程演算法是讓磁碟臂從磁碟的一端向另一端移動(dòng)，在此移動(dòng)的期間依序服務(wù)每個(gè)磁柱的 I/O 要求；當(dāng)?shù)竭_(dá)磁

4、碟底端時(shí)再反轉(zhuǎn)向另一端前進(jìn)，來回地存取磁碟C-SCAN 排程演算法將磁柱視為一個(gè)循環(huán)串列，即會(huì)由最後一個(gè)磁柱繞回第一個(gè)磁柱第9頁，共46頁。7/29/20229/45SCAN 磁碟排程 0 16 39 55 67 69 100 120 122 181 199佇列 = 10018139120161226769讀寫頭的起始位置55第10頁，共46頁。7/29/202210/45C-SCAN 磁碟排程 0 16 39 55 67 69 100 120 122 181 199佇列 = 10018139120161226769讀寫頭的起始位置55第11頁，共46頁。7/29/202211/45LOOK

5、與 C-LOOK 排程LOOK 排程與 SCAN 排程相似，不同的地方在於 SCAN 會(huì)讓磁碟臂來回於磁碟的兩端，而 LOOK 則是只移動(dòng)到有讀寫要求的最外側(cè)及最內(nèi)側(cè)磁柱C-LOOK 及 LOOK 的差異與 C-SCAN 及 SCAN的差異均為是否將磁柱視為一個(gè)循環(huán)串列第12頁，共46頁。7/29/202212/45LOOK 磁碟排程 0 16 39 55 67 69 100 120 122 181 199佇列 = 10018139120161226769讀寫頭的起始位置55第13頁，共46頁。7/29/202213/45C-LOOK 磁碟排程 0 16 39 55 67 69 100 120

6、 122 181 199佇列 = 10018139120161226769讀寫頭的起始位置55第14頁，共46頁。7/29/202214/45演算法選擇作業(yè)系統(tǒng)大多將演算法寫成一個(gè)獨(dú)立的模組，以便對(duì)不同情況能夠使用不同的磁碟排程演算法有些磁碟製造商已經(jīng)將磁碟演算法實(shí)作在磁碟控制器內(nèi)第15頁，共46頁。7/29/202215/45第十五章 大量儲(chǔ)存結(jié)構(gòu)磁碟排程 磁碟管理 磁碟格式化 啟動(dòng)區(qū)塊 壞損區(qū)塊 RAID 結(jié)構(gòu) 儲(chǔ)存設(shè)備附加方式 其他儲(chǔ)存議題 摘要第16頁，共46頁。7/29/202216/45磁碟格式化低階格式化磁碟在使用前必須先經(jīng)過磁區(qū)的劃分，使得磁碟控制器能夠讀取與寫入這些磁區(qū)磁碟分

7、割 將磁碟分成一個(gè)或多個(gè)磁柱的群組作業(yè)系統(tǒng)會(huì)將這些磁碟分割視為一個(gè)個(gè)獨(dú)立的磁碟 邏輯格式化作業(yè)系統(tǒng)會(huì)儲(chǔ)存初始的檔案系統(tǒng)資料結(jié)構(gòu)於磁碟之中；資料結(jié)構(gòu)中包含未被配置和已配置的空間、及一個(gè)初始的空白目錄第17頁，共46頁。7/29/202217/45啟動(dòng)區(qū)塊電腦的在打開或重置電源之後，需要一個(gè)初始化電腦的啟動(dòng)載入程式，負(fù)責(zé)初始化 CPU 暫存器、裝置控制器、和主要記憶體內(nèi)容，然後執(zhí)行作業(yè)系統(tǒng) 完整的啟動(dòng)載入程式是儲(chǔ)存在一個(gè)特別的磁碟分割中，稱為啟動(dòng)區(qū)塊 第18頁，共46頁。7/29/202218/45MS-DOS 磁碟資料存放方式 啟動(dòng)區(qū)塊FAT根目錄資料區(qū)塊（子目錄）磁區(qū) 0磁區(qū) 1第19頁，共4

8、6頁。7/29/202219/45壞損區(qū)塊MS-DOS 的 format 指令可以在執(zhí)行邏輯格式化時(shí)一併掃描磁碟，如果發(fā)現(xiàn)到一個(gè)壞損磁區(qū)，會(huì)在相對(duì)映的 FAT 紀(jì)錄中寫入一個(gè)特定值，以告知程式不要使用這個(gè)磁區(qū) 若是在使用時(shí)所造成的損毀，則需要以人工方式執(zhí)行一個(gè)特定程式，如 chkdsk，以搜尋磁碟內(nèi)壞損的磁區(qū)、並將它們記錄下來禁止使用 第20頁，共46頁。7/29/202220/45第十五章 大量儲(chǔ)存結(jié)構(gòu)磁碟排程 磁碟管理 RAID 結(jié)構(gòu) 可靠度和效能 RAID 階層 選定 RAID 階層 儲(chǔ)存設(shè)備附加方式 其他儲(chǔ)存議題 摘要第21頁，共46頁。7/29/202221/45RAID 結(jié)構(gòu)將數(shù)個(gè)

9、磁碟串接在一起，並將平行處理的觀念應(yīng)用於 I/O 之上，改善磁碟效能第22頁，共46頁。7/29/202222/45可靠度和效能提高可靠度最簡單的方法就是對(duì)每顆磁碟都再附加一顆額外的磁碟將資料的每個(gè)位元組的各個(gè)位元分散配置於不同的磁碟上，如此在讀取資料時(shí)可以同時(shí)跨過多個(gè)磁碟，分別讀取某個(gè)位元組的不同位元而提高效率資料跨分主要有 2 個(gè)目的 藉由同時(shí)存取多顆磁碟中的跨分資料，以增加產(chǎn)量降低存取大量資料的反應(yīng)時(shí)間第23頁，共46頁。7/29/202223/45RAID 階層 (1)RAID 0：資料以區(qū)塊為單位跨分於多顆磁碟RAID 1：複製所有的磁碟，即磁碟鏡像RAID 2：以位元為跨分單位，加

10、入多個(gè)漢明碼的檢查位元RAID 3：對(duì)區(qū)塊只產(chǎn)生單一個(gè)同位檢查位 元，並將檢查的結(jié)果寫入專門儲(chǔ)存同位檢查位元的磁碟中RAID 4：與 RAID 3 幾乎相同，不過是以區(qū)塊為跨分的單位第24頁，共46頁。7/29/202224/45RAID 階層 (2)RAID 5：不同於 RAID 4 的是 RAID 5 將資料和同位檢查位元資料散佈於所有的磁碟上RAID 6：與 RAID 5 類似， RAID 6 使用Reed-Solomon 編碼方式RAID 0 + 1 / 1 + 0：RAID 0 和 RAID 1 的組合，既可以得到 RAID 0 的效率，也可獲得 RAID 1 的可靠度 第25頁，共

11、46頁。7/29/202225/45RAID 階層 (a) RAID 0(c) RAID 2PPP(d) RAID 3P(e) RAID 4P(f) RAID 5PPPPP(g) RAID 6PPPPPPPPPP(b) RAID 1CCCC：資料磁碟：錯(cuò)誤更正碼磁碟：備份資料磁碟PC第26頁，共46頁。7/29/202226/45RAID 0+1 和 1+0 (b) RAID 1 + 0鏡像鏡像鏡像鏡像跨分(a) RAID 0 + 1鏡像跨分跨分第27頁，共46頁。7/29/202227/45選定 RAID 階層RAID 0 要求在高效率不在乎資料遺失RAID 1 需要高可靠度與快速復(fù)原RAI

12、D 0+1 和 RAID 1+0 可靠度和效率皆重要的環(huán)境RAID 5 適合用於儲(chǔ)存大量資料的環(huán)境下RAID 6 提供比 RAID 5 更佳的可靠度第28頁，共46頁。7/29/202228/45第十五章 大量儲(chǔ)存結(jié)構(gòu)磁碟排程 磁碟管理 RAID 結(jié)構(gòu) 儲(chǔ)存設(shè)備附加方式 主機(jī)附加儲(chǔ)存設(shè)備 網(wǎng)路附加儲(chǔ)存設(shè)備 儲(chǔ)存區(qū)域網(wǎng)路 其他儲(chǔ)存議題 摘要第29頁，共46頁。7/29/202229/45儲(chǔ)存設(shè)備附加方式電腦上附加的儲(chǔ)存設(shè)備，其存取資料的方式主要有 3 種：從本地主機(jī)上經(jīng)由 I/O 埠存取，這種設(shè)備稱為主機(jī)附加儲(chǔ)存設(shè)備經(jīng)由遠(yuǎn)端主機(jī)的分散式檔案系統(tǒng)來存取，這種設(shè)備稱為網(wǎng)路附加儲(chǔ)存設(shè)備儲(chǔ)存區(qū)域網(wǎng)路，是

13、綜合以上兩種方式，加上獨(dú)立的儲(chǔ)存設(shè)備協(xié)定來建構(gòu)有效率的大型網(wǎng)路儲(chǔ)存系統(tǒng)。第30頁，共46頁。7/29/202230/45主機(jī)附加儲(chǔ)存設(shè)備一般電腦所用的儲(chǔ)存設(shè)備都是經(jīng)由 I/O 埠作存取的主機(jī)附加儲(chǔ)存設(shè)備，如 IDE高階工作站和伺服器一般則使用更複雜的架構(gòu)，如 SCSI 或光纖通道第31頁，共46頁。7/29/202231/45網(wǎng)路附加儲(chǔ)存設(shè)備 (1/2)NAS 是特殊目的的網(wǎng)路儲(chǔ)存系統(tǒng)，藉由資料網(wǎng)路作遠(yuǎn)端的資料存取 NAS 在 IP 網(wǎng)路協(xié)定上是使用遠(yuǎn)端程式呼叫，而不是以使用裝置驅(qū)動(dòng)程式的方式來存取儲(chǔ)存設(shè)備 NAS 系統(tǒng)的缺點(diǎn)是，I/O 設(shè)備的操作會(huì)消耗掉資料網(wǎng)路的頻寬，而造成網(wǎng)路通訊的延遲第

14、32頁，共46頁。7/29/202232/45網(wǎng)路附加儲(chǔ)存設(shè)備 (2/2) NAS客戶端NAS客戶端客戶端LAN/WAN第33頁，共46頁。7/29/202233/45儲(chǔ)存區(qū)域網(wǎng)路 (1/2)SAN 是介於伺服器與設(shè)備間的私有網(wǎng)路使用設(shè)備協(xié)定而不是網(wǎng)路傳輸協(xié)定，與連接伺服器及客戶端的區(qū)域網(wǎng)路或廣域網(wǎng)路分離許多 SAN 系統(tǒng)是架構(gòu)在光纖通道迴路或是光纖通道交換式網(wǎng)路上，所以 SAN 系統(tǒng)是架構(gòu)在 IP 網(wǎng)路基礎(chǔ)的設(shè)施上第34頁，共46頁。7/29/202234/45儲(chǔ)存區(qū)域網(wǎng)路 (2/2)RAID資料伺服器磁帶庫伺服器伺服器資料處理中心客戶端客戶端客戶端網(wǎng)頁內(nèi)容提供者 LAN/WANSAN第35

15、頁，共46頁。7/29/202235/45第十五章 大量儲(chǔ)存結(jié)構(gòu)磁碟排程 磁碟管理 RAID 結(jié)構(gòu) 儲(chǔ)存設(shè)備附加方式 其他儲(chǔ)存議題 穩(wěn)定儲(chǔ)存體 第三儲(chǔ)存裝置 作業(yè)系統(tǒng)議題 效能議題 摘要第36頁，共46頁。7/29/202236/45穩(wěn)定儲(chǔ)存體一般磁碟寫入會(huì)有寫入失敗的可能 穩(wěn)定儲(chǔ)存設(shè)備要求寫入一個(gè)區(qū)塊時(shí)，若有錯(cuò)誤發(fā)生，系統(tǒng)必須能夠偵測並執(zhí)行一個(gè)復(fù)原的程序，將這個(gè)區(qū)塊復(fù)原到之前的狀態(tài) 第37頁，共46頁。7/29/202237/45第三儲(chǔ)存裝置第三儲(chǔ)存裝置最大的特性是價(jià)格低第三儲(chǔ)存裝置大多是用可抽換的媒介構(gòu)成的，如：可抽換的磁碟片磁光碟片光碟片相位改變光碟唯讀光碟磁帶 第38頁，共46頁。7/

16、29/202238/45作業(yè)系統(tǒng)議題 (1/2)作業(yè)系統(tǒng)的兩項(xiàng)主要工作管理實(shí)際裝置提供虛擬機(jī)器的抽象層應(yīng)用程式介面作業(yè)系統(tǒng)對(duì)於可抽換磁碟的處理，幾乎都是將它看待為固定式的磁碟來處理 作業(yè)系統(tǒng)通常以裸 I/O 的方式來使用磁帶，磁帶的應(yīng)用程式不是開啟磁帶中的一個(gè)檔案，而是將磁帶當(dāng)成一個(gè)裸磁碟一樣的裸裝置來開啟整個(gè)磁帶 第39頁，共46頁。7/29/202239/45作業(yè)系統(tǒng)議題 (2/2)檔案命名在個(gè)人電腦上檔案名稱是跟隨著路徑名稱和裝置字元所組成在 UNIX 系統(tǒng)上的檔案名稱是以掛載表讓作業(yè)系統(tǒng)發(fā)現(xiàn)檔案是安置在那一個(gè)裝置中 階層式的儲(chǔ)存管理主記憶體、輔助記憶體與第三儲(chǔ)存裝置形成了階層式的儲(chǔ)存系

17、統(tǒng) 第40頁，共46頁。7/29/202240/45效能議題速度承受頻寬是平均資料傳輸率，也就是傳輸位元組的個(gè)數(shù)除以傳輸時(shí)間有效頻寬是指裝置所提供的資料傳輸速率，速率的計(jì)算是整個(gè) I/O 時(shí)間的平均值可靠度固定式磁碟比可抽換式磁碟與磁帶可靠光學(xué)式的儲(chǔ)存裝置比磁碟與磁帶來的可靠成本價(jià)位是決定第三儲(chǔ)存裝置效能的重要因素 第41頁，共46頁。7/29/202241/45DRAM 價(jià)格 220408016032032 MB1 Mb4 MB simm 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 16 Kb64 Kb256 Kb6401.20.85101280$/MB128 MB2GB20080.03第42頁，共46頁。7/29/202242/45硬碟價(jià)格 19 GB128 MB20 MB10 MB1005020520.50.20.050.0040.021.2 GB2 GB45 GB1982 1984 1986 1988 1990 1992 1994 1996 1998 2000$/MB0.00011.5TB2008第43頁，共46頁。7/29/202243/45磁帶驅(qū)動(dòng)裝置價(jià)格 1.2 GB4 GB72 GB1984 1986 1988 1990 1992 1994 1996 1998 2000 年60 MB120 MB402