《磁盤存儲器管理》PPT課件.ppt

1、內容 磁盤I/O 外存分配方法 空閑存儲空間的管理 磁盤容錯技術 文件系統(tǒng)性能的改善 數(shù)據(jù)一致性控制,第九章 磁盤存儲器管理,提高I/O速度的主要途徑： 選擇性能好的磁盤 采用適當?shù)恼{度算法 設置磁盤高速緩沖區(qū) 9.1.1 磁盤性能簡述 9.1.2 磁盤調度算法,9.1 磁盤I/O,數(shù)據(jù)的組織 盤片（Platter ） 磁盤最基本的組成部分是由堅硬金屬材料制成的涂以磁 性介質的盤片，不同容量硬盤的盤片數(shù)不等。每個盤片有兩 面，都可記錄信息。 磁道 (Tracks) 盤片表面上以盤片中心為圓心，不同半徑的同心圓稱為 磁道。 扇區(qū)(Sectors) 盤片被分成許多扇形的區(qū)域，每個區(qū)域叫一個扇區(qū)，硬

2、 盤每個扇區(qū)可存儲512字節(jié)信息。FAT32模式下，每個扇區(qū)的 容量為4KB。每個扇區(qū)的大小相當與一個盤塊。 磁頭(Heads) 每個盤片的每一面都會有一個讀寫頭（read-write head ），來讀取相應盤面的內容。習慣用磁頭號來區(qū)分。,9.1.1 磁盤性能簡述,9.1.1 磁盤性能簡述,柱面 (Cylinders) 不同盤片相同半徑的磁道所組成的圓柱稱為柱面。磁道 與柱面都是表示不同半徑的圓，在許多場合，磁道和柱面 可以互換使用。 扇區(qū)，磁道（或柱面）和磁頭數(shù)構成了硬盤結構的基本 參數(shù)，幫這些 參數(shù)可以得到硬盤的容量，基計算公式為： 存儲容量磁頭數(shù)磁道（柱面）數(shù)每道扇區(qū)數(shù)每扇區(qū)字節(jié)數(shù)

3、1.44M =28018512,磁盤的類型 固定頭磁盤 每條磁道上都有一個讀/寫磁頭，所有的磁頭被裝入一個磁臂 通過這些磁頭可以訪問所有磁道，并進行并行讀寫 主要用于大容量磁盤 移動頭磁盤 每個盤面僅有一個磁頭，被裝入一個磁臂中 為能訪問盤面上的所有磁道，該磁頭必須移動以進行尋道 只能串行讀/寫，致使I/O速度較慢 結構簡單，廣泛應用中、小型磁盤，微機上的硬盤和軟盤，都采 用移動磁頭結構,9.1.1 磁盤性能簡述,磁盤訪問時間 尋道時間（seek time）Ts 把磁頭從當前位置移到指定磁道所經(jīng)歷的時間，一般為230毫秒，平均約為10毫秒。 Ts=m*n+s s-磁盤的啟動時間,大約3ms；

4、m-每移動一條磁道所經(jīng)歷的時間，對一般磁盤：m0.3ms，對高速磁盤：m0.1ms； n-移動的磁道數(shù)目；,9.1.1 磁盤性能簡述,旋轉延遲時間（rotational latency time）Tr 指定扇區(qū)移動到磁頭下所經(jīng)歷的時間。 Tr=1/2r （平均情況下，需要旋轉半圈） r磁盤以秒計的旋轉速度 一個7200（轉/每分鐘）的硬盤，則旋轉延遲時間為 601000720024.17毫秒。 一個5400（轉/每分鐘）的硬盤，旋轉延遲時間為 601000540025.56毫秒。 一個300/600（轉/每分鐘）軟盤，平均旋轉延遲時間為 6010003002100毫秒, 60100060025

5、0毫秒。,9.1.1 磁盤性能簡述,傳輸時間Tt 數(shù)據(jù)從磁盤讀出，或向磁盤寫數(shù)據(jù)所經(jīng)歷的時間，約 為零點幾個毫秒,可以忽略不計。 Ttb/rN b讀寫的字節(jié)數(shù) r磁盤以秒計的旋轉速度 N一條磁道上的字節(jié)數(shù) 訪問時間Ta=Ts+Tr+Tt=(m*n+s)+1/2r+b/rN,9.1.1 磁盤性能簡述,移動磁頭磁道為哪個進程服務 旋轉磁盤扇區(qū)為哪個進程服務 目標各進程對磁盤的平均訪問時間（主要是平均尋 道時間，即平均移動的磁道數(shù)目）最小,9.1.2 磁盤調度算法,先來先服務FCFS（First-Come,First-Served） 最簡單的磁盤調度算法，根據(jù)進程請求訪問磁盤的先后次 序進行調度。

6、優(yōu)點 公平、簡單，每個進程的請求都能依次得到處理，不會 出現(xiàn)某個進程長時間得不到滿足的情況。 缺點 未對尋道進行優(yōu)化，平均尋道時間可能較長,9.1.2 磁盤調度算法,9.1.2 磁盤調度算法,最短尋道時間優(yōu)先 SSTF（Shortest Seek Time First） 選擇要訪問的磁道與當前磁頭所在的磁道距離最近的進程 優(yōu)點 每次的尋道時間最短 缺點 不能保障平均尋道時間最短,出現(xiàn)進程“饑餓”現(xiàn)象,9.1.2 磁盤調度算法,9.1.2 磁盤調度算法,掃描算法SCAN 進程“饑餓”現(xiàn)象 在SSTF中，若不斷有新進程到來，且其訪問的磁道與當 前磁道的距離較近，這種進程被優(yōu)先執(zhí)行，而老進程一直得

7、不到滿足。 SCAN算法 不僅考慮訪問的磁道與當前磁道的距離，更優(yōu)先考慮的 是磁頭的當前移動方向，又稱電梯調度算法。 優(yōu)點 較好的尋道性能，又能防止進程“饑餓”現(xiàn)象，被廣泛應用與大 、中、小型機及網(wǎng)絡中的磁盤調度 缺點 可能使進程的請求被嚴重推遲,9.1.2 磁盤調度算法,9.1.2 磁盤調度算法,9.1.2 磁盤調度算法,循環(huán)掃描算法CSCAN(Circular SCAN) 規(guī)定磁頭單向移動，即使最小磁道號與最大磁道號緊鄰， 形成循環(huán)。,9.1.2 磁盤調度算法,N步掃描算法N-Step-SCAN、 改進前幾種算法可能出現(xiàn)磁頭靜止在一個磁道上，導致其 它進程無法及時進行磁盤I/O。 把磁盤I

8、/O請求隊列分成長度為N的子隊列，每次使用FCFS處理子隊列，每個隊列內部，使用SCAN算法處理N個請求。 當N很大時，該算法的性能接近于SCAN算法。 當N=1時，該算法退化為FCFS算法。 雙隊列掃描算法FSCAN 對N步掃描算法的簡化，即把磁盤I/O請求分成兩個隊列， 當前請求磁盤I/O的進程放入一個隊列，新生成的磁盤I/O請求放 入另一隊列中。交替使用SCAN算法處理一個隊列。,9.2 外存分配方法,即文件物理組織方式，其目標： 有效利用外存空間 提高文件的訪問速度 9.2.1 連續(xù)分配 9.2.2 鏈接分配 9.2.3 索引分配,9.2.1 連續(xù)分配,連續(xù)分配（Continuous

9、Allocation）要求為每一 個文件分配一組相鄰的盤塊。 優(yōu)點 順序訪問容易：連續(xù)的空間 順序訪問速度快：一條或相鄰的磁道上 缺點 要求有連續(xù)的存儲空間：形成外碎片；運行時進行修改、刪除也易形成外碎片。 必須事先知道文件的長度：裝入時要求；預估計小于實際文件，需中止COPY，重新估計；若文件動態(tài)增長，應該預留空間，但會造成空間使用效率低。,9.2.1 連續(xù)分配,9.2.2 鏈接分配,引入： 與內存管理類似： 進程占有連續(xù)的內存空間（內、外零頭）離散地占有內存空間； 文件占有連續(xù)的外存空間（碎片）離散地占有外存空間； 解決方法： 在每個盤塊上設一鏈接指針，將同屬于一個文件的多個離散盤塊鏈接成

10、一個鏈表，由此所形成的物理文件鏈接文件。 消除了外碎片，可以動態(tài)增、刪、改。,9.2.2 鏈接分配,隱式鏈接 在文件目錄的每個目錄項FCB中含有指向鏈接文件第一和最后一個盤塊的指針 只適用于順序訪問，對隨機訪問效率極低，可靠性差。 改進：將幾個盤塊組成一個簇（Cluster）,在進行分配時 以簇為單位進行，鏈接文件的元素也以簇為單位，這樣可以成 倍減少查找時間，也可減少指針占用的存儲空間，但增大了內 碎片。,9.2.2 鏈接分配,9.2.2 鏈接分配,顯式鏈接 把用于鏈接文件各物理塊的指針，顯式的存放在內存的一 張鏈接表中，即文件分配表FAT（File Allocation Table）。P2

11、66 不能支持高效的直接存取 FAT占用較大的內存空間,9.2.2 鏈接分配,FCB A,FCB B,FAT,MS-DOS / Windows98 FAT表結構,MS-DOS文件系統(tǒng)的文件物理結構采用FAT表結構。該結構為了克服鏈接文件隨機讀取任一邏輯塊需要化費多次盤I/O操作的不足，將各盤塊中的鏈接指針集中存放在盤的開始部分，構成一張表，稱為FAT表。FAT表每一項存放鏈接指針（下一個簇號），每個FAT表項占12位或16位，稱為FAT12或FAT16。對于軟盤因為容量小，簇數(shù)也少，采用12位FAT表，對于硬盤則采用16位FAT表。 FAT表文件系統(tǒng)原為小硬盤的目錄結構而設計，由于簇的數(shù)目最多

12、只能用16位表示，即最多只能有64K個簇，要用FAT表管理大的磁盤分區(qū)，只能采取增大每簇所包含的扇區(qū)數(shù)，一般根據(jù)磁盤的類型和容量大小來決定簇的大小，如下表所示。當然每簇包含扇區(qū)數(shù)增加，帶來內零頭的浪費，這對小文件特別嚴重。 Windows98為了減少內另頭的浪費，可采取每簇的數(shù)目用32位表示，減少每簇包含扇區(qū)數(shù)，這稱為FAT32。 FAT16 、FAT32文件系統(tǒng)簇和扇區(qū)關系也見下表所示。,MS-DOS / Windows98 FAT表結構-1,9.2.3 索引分配,單級索引分配 為每個文件分配一個索引表，把分配給該文件的盤塊號， 記錄在該索引表中。文件目錄中，填上指向該索引表的指針。 優(yōu)點

13、支持直接訪問 不產(chǎn)生外碎片 缺點 索引表在外存空間，需為小文件也匹配索引塊。,9.2.3 索引分配,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,9.2.3 索引分配,多級索引分配 P268,第二級索引,磁盤空間,360,740,1125,主索引,9.2.3 索引分配,3.混合分配方式 由于80以上文件是小文件，為了解決能高速存取小文件和管理大文件的矛盾，UNIX將直接尋址、一級索引、二級索引和三級索引結合起來，形成了混合尋址方式，如下圖所示。,UNIX System

14、V 混合尋址方式,在UNIX S V的索引結點中設有13個地址項di_addr13,它們把所存的地址項分成兩類，其中最后三個地址項分別是一級索引、二級索引和三級索引的指針，而前面10個為直接尋址的地址項，即存放文件邏輯塊第09塊的盤塊號。 如每個盤塊大小為4KB時，當文件不大于40KB時，便可直接從索引結點中讀出該文件全部盤塊號，這樣讀小文件時速度快；如文件大于 40KB時，系統(tǒng)再逐步增加一級索引、二級索引和三級索引，這樣最大管理的文件為40KB4MB4GB4TB，達到管理大文件的目標。,五、例,一個文件系統(tǒng)中有一個20MB大文件和一個20KB小文件,當分別采用連續(xù)、鏈接、單級索引、二級索引和

15、UNIX Sytem V 分配方案時(每塊大小為4096B,每塊地址用4B表示)，問: 1.各文件系統(tǒng)管理的最大的文件是多少? 2.每種方案對大、小二文件各需要多少專用塊來記錄文件的物理地址(說明各塊的用途) ? 3如需要讀大文件前面第5.5KB和后面（16M5.5KB）信息，則每個方案各需要多少次盤I/O操作? 這個范例是幫助讀者深入比較文件物理組織的各種方案：順序文件的連續(xù)分配、鏈接文件的鏈接分配、二級索引分配、鏈接索引分配和UNIX的直接間接混合分配，明確各種分配方案的優(yōu)缺點和UNIX分配方案的設計特點。,例-解答,1.各種分配方案的文件系統(tǒng)可管理的最大文件 連續(xù)分配：不受限制，可大到整

16、個磁盤文件區(qū)。 鏈接分配：同上。 單級索引：同上。 二級索引：由于盤塊大小為4KB，每個地址用4B表示，一個盤塊可存1K個索引表目，二級索引可管理的最大文件容量為4KB1K1K4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件。 UNIX混合分配：可管理的最大文件為40KB4MB+4GB4TB。 2.每種分配方案對20MB大文件和20KB小文件各需要多少專用塊來記錄文件的物理地址? 連續(xù)分配：對大小二個文件都只需在文件控制塊FCB中設二項，一是首塊物理塊塊號，另一是文件總塊數(shù)，不需專用塊來記錄文件的物理地址。,例-解答,鏈接分配：對大小二個文件都只需在文件控制塊FCB中設二項，一是

17、首塊物理塊塊號，另一是文件總塊數(shù)；同時在每塊存文件的物理塊中設置存貯下一塊塊號的指針。 單級索引：對20KB小文件只有5個物理塊大小，所以只需一塊專用物理塊來作索引塊，用來保存文件的各塊物理塊塊號。對于20MB大文件有5K個物理塊大小，由于鏈接索引的每個索引塊只能保存（1K1）個物理塊塊號（還有一個表目作索引塊鏈接指針），所以它需要6塊專用物理塊來作鏈接索引塊，用于保存文件各塊的物理地址。 二級索引：對大小文件都固定要用二級索引，對20KB小文件，用一塊作第一級索引，用另一塊作二級索引，共用二塊專用物理塊作索引塊，對于20MB大文件，用一塊作第一級索引，用5塊作第二級索引，共用六塊專用物理塊作

18、索引塊。,范例-解答,UNIX的混合分配：對20KB小文件只需在文件控制塊FCB的i_addr13中使用前5個表目存放文件的物理塊號，不需專用物理塊。對20MB大文件，F(xiàn)CB的i_addr13中使用前10個表目存放大文件前10塊物理塊塊號，用一級索引塊一塊保存大文件接著的1K塊塊號，還要用二級索引存大文件以后的塊號，二級索引使用第一級索引1塊，第二級索引4塊?？偣惨残枰?塊專用物理塊來存放文件物理地址。 3.為讀大文件前面第5.5KB和后面（16M5.5KB）信息需要多少次盤I/O操作? 連續(xù)分配：為讀大文件前面和后面信息都需先計算信息在文件中相對塊數(shù)，前面信息相對邏輯塊號為5.5K4K=1，

19、后面信息相對邏輯塊號為（16M5.5K）/4K=4097。再計算物理塊號文件首塊號相對邏輯塊號，最后化一次盤I/O操作讀出該塊信息。,例-解答,鏈接分配：為讀大文件前面5.5.KB的信息，只需先讀一次文件頭塊得到信息所在塊的塊號，再讀一次第1號邏輯塊得到所需信息。而讀大文件后面16MB5.5KB的信息，要先把該信息所在塊前面塊順序讀出，共化費4097次盤IO操作，才能得到信息所在塊的塊號，最后化一次I/O操作讀出該塊信息。所以總共需要4098次盤IO才能讀取（16MB+5.5KB）字節(jié)信息。 單級索引：為讀大文件前面5.5KB的信息，只需先讀一次第一塊索引塊得到信息所在塊的塊號，再讀一次第1號

20、邏輯塊得到所需信息，共化費2次盤IO操作。為讀大文件后面（16MB+5.5KB）的信息，需要先化5次盤IO操作依次讀出各索引塊，才能得到信息所在塊的塊號，再化一次盤I/O操作讀出該塊信息。共化費6次盤IO操作。,例-解答,二級索引：為讀大文件前面和后面信息的操作相同，首先進行一次盤IO讀第一級索引塊，然后根據(jù)它的相對邏輯塊號計算應該讀第二級索引的那塊，第一級索引塊表目號=相對邏輯塊號1K，對文件前面信息11K0，對文件后面信息40971K4，第二次根據(jù)第一級索引塊的相應表目內容又花一次盤IO讀第二級索引塊，得到信息所在塊塊號，再花一次盤IO讀出信息所在盤塊，這樣讀取大文件前面或后面信息都只需要

21、3次盤IO操作。,例-解答,UNIX混合分配：為讀大文件前面5.5KB信息，先根據(jù)它的相對邏輯塊號，在內存文件控制塊FCB的i_addr13第二個表目中讀取信息所在塊塊號，而只化費一次盤IO操作即可讀出該塊信息。為讀大文件后在（16MB5。5KB）信息，先根據(jù)它的相對邏輯塊號判斷它是在UNIX二級索引管理范圍，先根據(jù)i_addr11內容化一次盤IO操作讀出第一級索引塊，再計算信息所在塊的索引塊號在第一級索引塊的表目號為（4097-9-1024）10243，根據(jù)第一級索引塊第3個表目內容再化費一次盤IO操作，讀出第二級索引塊，就可以得到信息所在塊塊號，最后化一次盤IO讀出信息所在盤塊，這樣總共需

22、要3次盤IO操作才能讀出文件后面的信息。,例-解答,9.3 空閑存儲空間的管理,9.3.1 空閑表法 9.3.2 空閑鏈表法 9.3.3 位示圖法 9.3.4 成組鏈接法,9.3.1 空閑表法,為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對 應一個表目，包括序號、該區(qū)的起始空閑盤塊號、空閑盤塊數(shù) 目等，按起始空閑盤塊號排序。 分配：是一種連續(xù)分配方式，順序查找空閑表，找到 第一個合適的空閑區(qū)，修改空閑表。 回收：將相應塊按序填回表中，并與前后合并成大塊。 特點：連續(xù)存放，易產(chǎn)生碎片。,9.3.2 空閑鏈表法,空閑盤塊鏈 將磁盤上所有空閑存儲空間，以盤塊為單位鏈成 一個鏈表。 分配：從鏈首開始

23、，依次摘下適當數(shù)目的空閑盤 塊進行分配。 回收：依次鏈入鏈尾。 特點：分配、回收簡單，空閑盤塊鏈可能很長。 空閑盤區(qū)鏈 將磁盤上所有空閑存儲空間，以盤區(qū)（包括若干 盤塊）為單位鏈成一個鏈表。 分配：查找合適大小的盤區(qū)進行分配 回收：與前后盤區(qū)合并 特點：分配、回收復雜，空閑盤區(qū)鏈較短。,9.3.3 位示圖法,位示圖 系統(tǒng)為文件存儲空間建立一張位示圖，如下圖。位示圖 反映了整個存儲空間的分配情況，其中每一位對應一個物理塊 ，“1”表示對應塊已被分配，“0”表示對應塊為空白。,位 號,字 號,9.3.3 位示圖法,盤塊的分配 順序掃描位示圖，找到一個或一組為“0”的二進制位 將位號、字號轉換為盤塊號，進行分配： 塊號=位數(shù)*字號+位號 修改位示圖，置“1”。 盤塊的回