1、外部存儲管理外部存儲管理存儲介質存儲介質（1 1）介質種類：介質種類：磁盤，磁帶，光盤。磁盤，磁帶，光盤。（2 2）物理塊：物理塊：在文件系統中，文件的存儲設備常常劃分為若干大在文件系統中，文件的存儲設備常常劃分為若干大小相等的物理塊。同時也將文件信息劃分成相同大小的邏輯小相等的物理塊。同時也將文件信息劃分成相同大小的邏輯塊，所有塊統一編號。以塊為單位進行信息的存儲、傳輸和塊，所有塊統一編號。以塊為單位進行信息的存儲、傳輸和分配。分配。（3 3）磁帶：磁帶：永久保存大容量數據的順序存取設備。前面的物理塊永久保存大容量數據的順序存取設備。前面的物理塊被存取訪問之后，才能存取后續的物理塊的內容。存

2、取速度被存取訪問之后，才能存取后續的物理塊的內容。存取速度較慢，主要用于后備存儲，或存儲不經常用的信息，或用于較慢，主要用于后備存儲，或存儲不經常用的信息，或用于傳遞數據的介質。傳遞數據的介質。Hard Disk DrivesIBM/Hitachi MicrodriveWestern Digital Drivehttp:/ HeadSide ViewProperties of a Hard Magnetic Disk Properties Independently addressable element: sector OS always transfers groups of sector

3、s together”blocks” A disk can access directly any given block of information it contains (random access). Can access any file either sequentially or randomly. A disk can be rewritten in place: it is possible to read/modify/write a block from the disk Typical numbers (depending on the disk size): 500

4、 to more than 20,000 tracks per surface 32 to 800 sectors per track A sector is the smallest unit that can be read or written Zoned bit recording Constant bit density: more sectors on outer tracks Speed varies with track locationTrackSectorPlatters磁盤：磁盤：直接（隨機）存取設備，存取磁盤上任一物理塊的時間不依直接（隨機）存取設備，存取磁盤上任一物理

5、塊的時間不依賴于該物理塊所處的位置。賴于該物理塊所處的位置。信息記錄在磁道上，多個盤片，正反兩信息記錄在磁道上，多個盤片，正反兩面都用來記錄信息，每面一個磁頭。所有盤面中處于同一磁道號上面都用來記錄信息，每面一個磁頭。所有盤面中處于同一磁道號上的所有磁道組成一個柱面。的所有磁道組成一個柱面。物理地址形式：物理地址形式：磁頭號（盤面號）、磁磁頭號（盤面號）、磁道號（柱面號）、扇區號。磁盤系統由磁盤本身和驅動控制設備組道號（柱面號）、扇區號。磁盤系統由磁盤本身和驅動控制設備組成，實際存取讀寫的動作過程是由磁盤驅動控制設備按照主機要求成，實際存取讀寫的動作過程是由磁盤驅動控制設備按照主機要求完成的。

6、完成的。第第i塊塊 間隙間隙 第第i+1塊塊柱面柱面扇區扇區磁臂磁臂磁頭磁頭（1 1）一次訪盤請求：一次訪盤請求：讀讀/ /寫，磁盤地址（設備號，柱面號，磁頭號，扇區號），寫，磁盤地址（設備號，柱面號，磁頭號，扇區號），內存地址（源內存地址（源/ /目）。目）。（2 2）完成訪盤過程的三個動作：完成訪盤過程的三個動作：1.1.尋道（時間）：尋道（時間）：磁頭移動定位到指定磁道。磁頭移動定位到指定磁道。2.2.旋轉延遲（時間）：旋轉延遲（時間）：等待指定扇區從磁頭下旋轉經過。等待指定扇區從磁頭下旋轉經過。3.3.數據傳輸（時間）：數據傳輸（時間）：數據在磁盤與內存之間的實際傳輸。數據在磁盤與內存

7、之間的實際傳輸。（3 3）很多系統允許有些磁盤是可裝卸的節省驅動設備成本，增加靈活性和便攜性）很多系統允許有些磁盤是可裝卸的節省驅動設備成本，增加靈活性和便攜性。（4 4）硬盤又分為兩種：硬盤又分為兩種：1 1. .固定頭磁盤：固定頭磁盤：每個磁道設置一個磁頭，變換磁道時不需要磁頭的機械移動每個磁道設置一個磁頭，變換磁道時不需要磁頭的機械移動，速度快但成本高。，速度快但成本高。2.2.移動頭磁盤：移動頭磁盤：一個盤面只有一個磁頭，變換磁道時需要移動磁頭，速度慢一個盤面只有一個磁頭，變換磁道時需要移動磁頭，速度慢但成本低。但成本低。Disk I/O PerformanceResponse Tim

8、e = Queue+Disk Service TimeUserThreadQueueOS PathsControllerDisk Performance of disk drive/file system Metrics: Response Time, Throughput Contributing factors to latency: Software paths (can be loosely modeled by a queue) Hardware controller Physical disk media Queuing behavior: Can lead to big incr

9、eases of latency as utilization approaches 100%100%ResponseTime (ms)Throughput (Utilization)(% total BW)01002003000%Magnetic Disk Characteristic Cylinder: all the tracks under the head at a given point on all surface Read/write data is a three-stage process: Seek time: position the head/arm over the

10、 proper track (into proper cylinder) Rotational latency: wait for the desired sectorto rotate under the read/write head Transfer time: transfer a block of bits (sector)under the read-write head Disk Latency = Queueing Time + Controller time +Seek Time + Rotation Time + Xfer Time Highest Bandwidth: T

11、ransfer large group of blocks sequentially from one trackSectorTrackCylinderHeadPlatterSoftwareQueue(Device Driver)HardwareController Media Time(Seek+Rot+Xfer)RequestResultTypical Numbers of a Magnetic Disk Average seek time as reported by the industry: Typically in the range of 8 ms to 12 ms Due to

12、 locality of disk reference may only be 25% to 33% of the advertised number Rotational Latency: Most disks rotate at 3,600 to 7200 RPM (Up to 15,000RPM or more) Approximately 16 ms to 8 ms per revolution, respectively An average latency to the desired information is halfway around the disk: 8 ms at

13、3600 RPM, 4 ms at 7200 RPM Transfer Time is a function of: Transfer size (usually a sector): 512B 1KB per sector Rotation speed: 3600 RPM to 15000 RPM Recording density: bits per inch on a track Diameter: ranges from 1 in to 5.25 in Typical values: 2 to 50 MB per second Controller time depends on co

14、ntroller hardware Cost drops by factor of two per year (since 1991)Disk Performance Assumptions: Ignoring queuing and controller times for now Avg seek time of 5ms, avg rotational delay of 4ms Transfer rate of 4MByte/s, sector size of 1 KByte Random place on disk: Seek (5ms) + Rot. Delay (4ms) + Tra

15、nsfer (0.25ms) Roughly 10ms to fetch/put data: 100 KByte/sec Random place in same cylinder: Rot. Delay (4ms) + Transfer (0.25ms) Roughly 5ms to fetch/put data: 200 KByte/sec Next sector on same track: Transfer (0.25ms): 4 MByte/sec Key to using disk effectively (esp. for filesystems) is to minimize

16、seek and rotational delaysDisk Tradeoffs How do manufacturers choose disk sector sizes? Need 100-1000 bits between each sector to allow system to measure how fast disk is spinning and to tolerate small (thermal) changes in track length What if sector was 1 byte? Space efficiency only 1% of disk has

17、useful space Time efficiency each seek takes 10 ms, transfer rate of 50 100 Bytes/sec What if sector was 1 KByte? Space efficiency only 90% of disk has useful space Time efficiency transfer rate of 100 KByte/sec What if sector was 1 MByte? Space efficiency almost all of disk has useful space Time ef

18、ficiency transfer rate of 4 MByte/sec磁盤的訪問優化磁盤的訪問優化 循環排序循環排序 按照數據的分布對輸入按照數據的分布對輸入/輸出請求進行排序，提高處理的效率輸出請求進行排序，提高處理的效率 舉例舉例 假設每個磁道上保存假設每個磁道上保存4個記錄（塊），磁盤旋轉速度是個記錄（塊），磁盤旋轉速度是20ms/轉，如果收到如下請求序列：讀記錄轉，如果收到如下請求序列：讀記錄4、讀記錄、讀記錄3、讀記錄讀記錄2、讀記錄、讀記錄1，則如何安排輸入，則如何安排輸入/輸出順序，到達理輸出順序，到達理想的處理性能。想的處理性能。 按請求次序讀取上述記錄，總的處理時間：按請

19、求次序讀取上述記錄，總的處理時間：(1/2+1/4+3*3/4) * 20 = 60 (ms) 按讀取記錄按讀取記錄1, 2, 3, 4的順序，則總的處理時間為：的順序，則總的處理時間為：(3/4 + + 3* ) * 20 = 35 (ms) 如果知道當前讀位置為記錄如果知道當前讀位置為記錄3，則按讀取記錄，則按讀取記錄4,1,2,3順序，則總的處理時間為：順序，則總的處理時間為：(4 * ) * 20 = 20 (ms) 塊1塊2塊3塊4磁盤訪問優化磁盤訪問優化 優化分布優化分布 按照數據處理的規律，合理安排其磁盤上的分布，以提高處理的效率按照數據處理的規律，合理安排其磁盤上的分布，以提高

20、處理的效率 舉例舉例 假設每個磁道上劃分為假設每個磁道上劃分為10個塊，分別存放個塊，分別存放AJ十個邏輯記十個邏輯記錄，磁盤旋轉速度是錄，磁盤旋轉速度是20ms/轉。如果處理程序讀出每個記轉。如果處理程序讀出每個記錄后花錄后花4ms進行處理，則如何安排邏輯記錄的存放位置，進行處理，則如何安排邏輯記錄的存放位置，以達到理想的處理性能？以達到理想的處理性能？1A2H3E4B2*2 = 4ms磁盤訪問優化磁盤訪問優化 交替地址交替地址 通過數據的冗余存放來提高訪問的速度通過數據的冗余存放來提高訪問的速度 缺點：缺點： 消耗較多的存儲空間消耗較多的存儲空間 數據一致性問題決定其較適合于數據記錄總是讀

21、出使用的數據一致性問題決定其較適合于數據記錄總是讀出使用的方式方式磁盤的搜索定位磁盤的搜索定位 對于移動臂磁盤設備，除了旋轉位置外，還有搜索定位的問對于移動臂磁盤設備，除了旋轉位置外，還有搜索定位的問題（尋道）題（尋道） 常見的移動臂調度算法：常見的移動臂調度算法： 先來先服務先來先服務 電梯調度算法電梯調度算法 最短查找時間優先算法最短查找時間優先算法 掃描算法掃描算法 分步掃描算法分步掃描算法 循環掃描算法循環掃描算法移動臂調度算法移動臂調度算法1.“電梯調度電梯調度”算法：算法：1.1. 選擇沿臂的移動方向最近的柱面，如果同一柱面上有多個請求，還需進行旋轉優化選擇沿臂的移動方向最近的柱面

22、，如果同一柱面上有多個請求，還需進行旋轉優化。2.2. 如果這個方向沒有訪問請求時，就改變臂的移動方向，如果這個方向沒有訪問請求時，就改變臂的移動方向， 并使移動頻率極小化，處并使移動頻率極小化，處理所迂到的最近的理所迂到的最近的I/OI/O請求，非常類似于電梯的調度規則。請求，非常類似于電梯的調度規則。2.“最短查找時間優先最短查找時間優先”算法：算法：本算法考慮了各個請求之間的區別，總是先執行查本算法考慮了各個請求之間的區別，總是先執行查找時間最短的那個磁盤請求，從而，較找時間最短的那個磁盤請求，從而，較“先來先服務先來先服務”算法有較好的尋道性能。算法有較好的尋道性能。3.“掃描掃描”算

23、法：算法：磁盤臂每次沿一個方向移動，掃過所有柱面，遇到最近的磁盤臂每次沿一個方向移動，掃過所有柱面，遇到最近的I/OI/O請求請求便進行處理，直到最后一個柱面后，再向相反方向移動回來。便進行處理，直到最后一個柱面后，再向相反方向移動回來。 4.“分步掃描分步掃描”算法：算法：將將I/OI/O請求分成組，每組不超過請求分成組，每組不超過N N個請求，每次選一個組進行個請求，每次選一個組進行掃描，處理完一組后再選下一組。掃描，處理完一組后再選下一組。 5.“循環掃描循環掃描”算法：算法：移動臂總從移動臂總從0 0號柱面至最大號柱面順序掃描，然后，直接返回號柱面至最大號柱面順序掃描，然后，直接返回0

24、 0號柱面重復進行，歸途中不再服務，構成了一個循環。號柱面重復進行，歸途中不再服務，構成了一個循環。移動臂調度算法比較移動臂調度算法比較算法比較：算法比較：1.1.1 1，2 2兩種算法，單位時間內處理的兩種算法，單位時間內處理的I/OI/O請求多即吞吐量大，但請求的等待請求多即吞吐量大，但請求的等待時間可能較長。時間可能較長。2.“掃描掃描”算法適宜于磁盤負載重的系統，它不分具體情況掃過所有柱面算法適宜于磁盤負載重的系統，它不分具體情況掃過所有柱面造成性能不夠好。造成性能不夠好。3.“分步掃描分步掃描”算法使得算法使得I/OI/O請求等待時間之間的差距最小，吞吐量適中。請求等待時間之間的差距

25、最小，吞吐量適中。4.“電梯調度電梯調度”算法杜絕饑餓，性能適中。算法杜絕饑餓，性能適中。5.“循環掃描循環掃描”算法適應不斷有大批量柱面均勻分布的算法適應不斷有大批量柱面均勻分布的I/OI/O請求，且磁道上請求，且磁道上存放記錄數量較大的情況。存放記錄數量較大的情況。獨立磁盤冗余陣列獨立磁盤冗余陣列(RAID) 基本思路：基本思路： 用一組較小容量的、獨立的、可并行工作的磁盤驅動器組成陣用一組較小容量的、獨立的、可并行工作的磁盤驅動器組成陣列來代替單一的大容量磁盤，并加入冗余技術，數據能夠以多列來代替單一的大容量磁盤，并加入冗余技術，數據能夠以多種方式組織和分布存儲。種方式組織和分布存儲。

26、優點：優點： 數據的分布存儲，提高了單個數據的分布存儲，提高了單個I/O請求的處理性能請求的處理性能 數據的冗余，提高了系統的可靠性數據的冗余，提高了系統的可靠性獨立磁盤冗余陣列獨立磁盤冗余陣列(RAID)RAIDRAID的特性：的特性：1.RAID1.RAID是一組物理磁盤驅動器，可被操作系統看作是單一邏輯磁盤驅動器是一組物理磁盤驅動器，可被操作系統看作是單一邏輯磁盤驅動器; ;2.2.數據被分布存儲在陣列橫跨的物理驅動器上數據被分布存儲在陣列橫跨的物理驅動器上; ;3.3.冗余磁盤的作用是保存奇偶校驗信息，當磁盤出現失誤時它能確保數據的冗余磁盤的作用是保存奇偶校驗信息，當磁盤出現失誤時它能

27、確保數據的恢復。恢復。RAID level 0RAID level 0：1.1.數據劃成條塊被分布存儲在橫跨陣列中的所有磁盤上；數據劃成條塊被分布存儲在橫跨陣列中的所有磁盤上；2.2.邏輯上連續的數據條塊，在物理上可被依次存儲在橫向相鄰的磁盤驅動器邏輯上連續的數據條塊，在物理上可被依次存儲在橫向相鄰的磁盤驅動器上；上；3.3.通過陣列管理軟件進行邏輯地址空間到物理地址空間的映射。通過陣列管理軟件進行邏輯地址空間到物理地址空間的映射。Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip1

28、0Strip11Strip2Strip6Strip14Strip10 RAID Level 0Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip10Strip3Strip7Strip15Strip10Strip11Strip2Strip6Strip14Strip10Data mapping for a RAID Level 0 ArrayStrip0Strip1Strip2Strip3Strip4Strip5Strip6Strip7Strip8.ArrayManagementsoftwareRAID level 1RAID level

29、 1：雙份數據，每個盤都有一個包含相同數據的鏡像盤。雙份數據，每個盤都有一個包含相同數據的鏡像盤。1.1.讀請求能通過包含相同請求數據中的任何一個磁盤提供服務，其中的一個讀請求能通過包含相同請求數據中的任何一個磁盤提供服務，其中的一個所化查找和搜索時間最少所化查找和搜索時間最少; ;2.2.寫操作時，要求改寫對應的兩個數據子塊，可采用并行操作，寫操作的性寫操作時，要求改寫對應的兩個數據子塊，可采用并行操作，寫操作的性能由并行操作中較慢的一個決定能由并行操作中較慢的一個決定; ;3.3.一個驅動器出現故障，數據可以從鏡像盤獲得。一個驅動器出現故障，數據可以從鏡像盤獲得。RAID level 2

30、RAID level 2 ：1.1.采用并行存取技術，驅動器的移動臂同步工作，每個磁盤的磁頭都在相同采用并行存取技術，驅動器的移動臂同步工作，每個磁盤的磁頭都在相同位置。糾錯碼按照橫跨的每個數據盤的相應位計算，并存儲在多只校驗盤位置。糾錯碼按照橫跨的每個數據盤的相應位計算，并存儲在多只校驗盤的相應位的位置。的相應位的位置。2.2.校驗磁盤的數量與數據盤的多少成比例。校驗磁盤的數量與數據盤的多少成比例。Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Str

31、ip10RAID Level 1 (Mirrored)Strip0Strip4Strip8Strip12Strip1Strip5Strip9Strip13Strip3Strip7Strip15Strip11Strip2Strip6Strip14Strip10b0b1b2b3f0(b)f1(b)f2(b)RAID Level 2 (Redundancy through Hamming Code)RAID level 3RAID level 3：（1 1）RAID3RAID3僅使用一只冗余盤，僅使用一只冗余盤， 出現故障時，使用奇偶校驗盤的信息校驗，數據可用出現故障時，使用奇偶校驗盤的信息校驗，數

32、據可用剩下的磁盤的信息重新構造，若剩下的磁盤的信息重新構造，若X0X0到到X3X3存放數據，存放數據，X4X4為奇偶盤，對于第為奇偶盤，對于第i i位的奇偶位的奇偶校驗位可如下計算校驗位可如下計算: : X4(i)=X3(i)X2(i)X1(i)X0(i) X4(i)=X3(i)X2(i)X1(i)X0(i) 假定驅動器假定驅動器X1X1出故障，如果把出故障，如果把X4(i)X4(i)，X1(i)X1(i)加到上面等式兩邊，得到加到上面等式兩邊，得到 X1(i)=X4(i)X3(i)X2(i)X0(i)X1(i)=X4(i)X3(i)X2(i)X0(i)RAID level 4RAID lev

33、el 4：1.RAID41.RAID4和和RAID5RAID5使用獨立存取技術，在一個獨立存取的磁盤陣列中，每個驅動器都可使用獨立存取技術，在一個獨立存取的磁盤陣列中，每個驅動器都可以獨立地工作，所以，獨立的以獨立地工作，所以，獨立的I/OI/O請求可以被并行地得到滿足。因此獨立存取陣列請求可以被并行地得到滿足。因此獨立存取陣列適合于有頻繁適合于有頻繁I/OI/O請求的應用。請求的應用。2.2.每當執行一個小數據量寫操作時，陣列管理軟件不旦要修改用戶數據，而且也要修每當執行一個小數據量寫操作時，陣列管理軟件不旦要修改用戶數據，而且也要修改對應的奇偶校驗位。改對應的奇偶校驗位。 b0b1b2b3

34、P(b) RAID Level 3 (Bit interleaved Parity)block0block4block8block12block1block5block9block13block3block7block15block11block2block6block14block10P(0-3)P(4-7)90P(8-11)P(12-15)RAID Level 4 (Block level Parity)RAID level 5RAID level 5：1.RAID51.RAID5的奇偶校驗碼是分布橫跨輪轉存放在所有的磁盤上，設有的奇偶校驗碼是分布橫跨輪轉存放在所有的磁盤上，設有n n個磁

35、盤的個磁盤的陣列，則開頭的陣列，則開頭的n n個奇偶校驗碼螺旋式地位于個奇偶校驗碼螺旋式地位于n n個磁盤上，能避免個磁盤上，能避免RAID4RAID4發發生的奇偶校驗盤瓶頸口問題。生的奇偶校驗盤瓶頸口問題。RAID level 6RAID level 6和和RAID level 7RAID level 7：1.1.增強型增強型RAIDRAID。RAID6RAID6中設置了專用快速的異步校驗磁盤，具有獨立的數據訪中設置了專用快速的異步校驗磁盤，具有獨立的數據訪問通路，比低級問通路，比低級RAIDRAID性能更好，但價格昂貴。性能更好，但價格昂貴。2.RAID72.RAID7對對RAID6RAI

36、D6作了改進，該陣列中的所有磁盤都有較高傳輸速率，性能優作了改進，該陣列中的所有磁盤都有較高傳輸速率，性能優異，但價格也很高。異，但價格也很高。RAID Level 5 (Block level Distributed parity)block0block4block8block12block1block5block9P(12-15)block3P(4-7)block14block10block2block6block13P(8-11)P(0-3)block7Block11Block15block0block4block8block12磁盤存儲性能（1 1）磁盤服務：磁盤服務：其速度和可靠性成

37、為文件系統性能和可靠性的主要瓶頸，設計文件系其速度和可靠性成為文件系統性能和可靠性的主要瓶頸，設計文件系統時應盡可能減少磁盤訪問次數。統時應盡可能減少磁盤訪問次數。（2 2）塊高速緩存：塊高速緩存：系統在內存中保存一些塊，邏輯上它們屬于磁盤，檢查所有的讀請系統在內存中保存一些塊，邏輯上它們屬于磁盤，檢查所有的讀請求，看所需的塊是否在高速緩存中。如果在，則可直接進行讀操作。否則，首先要求，看所需的塊是否在高速緩存中。如果在，則可直接進行讀操作。否則，首先要將塊讀到高速緩存，再拷貝到所需的地方，如果高速緩存已滿，則需要進行淘汰。將塊讀到高速緩存，再拷貝到所需的地方，如果高速緩存已滿，則需要進行淘汰。（3 3）合理分配磁盤空間：合理分配磁盤空間：分配塊時，把有可能順序存取的塊放在一起，最好在同一柱分配塊時，把有可能順序存取的塊放在一起，最好在同一柱面上，從而減少磁盤臂的移動次數。面上，從而減少磁盤臂的移動次數。（4 4）磁盤調度：磁盤調度：當多個訪盤請求在等待時，采用一定的策略，對這些請求的服務順序當多個訪盤請求在等待時，采用一定的策略，對這些請求的服務順序調整安排，旨在降低平均磁盤服務時間，達到公平、高效。調整安排，旨在降