創作模闆1
- 前言
- 推薦
- 第八章 磁盤存儲器的管理
- 8.1 外存的組織方式
- 8.1.1 連續組織方式
- 8.1.2 連結組織方式
- 8.1.3 FAT技術
- 8.1.4 NTFS的檔案組織方式
- 8.1.5 索引組織方式
- 8.2 檔案存儲空間的管理
- 8.2.1 空閑表法和空閑連結清單法
- 8.2.2 位示圖
- 8.2.3 成組連結法
- 8.3 提高磁盤I/O速度的途徑
- 8.3.1 磁盤高速緩存(Disk Cache)
- 8.3.2 提高磁盤I/O速度的其他方法
- 8.3.3 磁盤備援陣列
- 8.4 提高磁盤可靠性的技術
- 8.4.1. 第一級 磁盤容錯技術SFT-1
- 8.4.2. 第二級 磁盤容錯技術SFT-2
- 8.4.3 基于叢集技術的容器功能
- 8.4.4 後背習題
- 8.5 資料一緻性控制
- 8.5.1 事務
- 8.5.2 檢查點(Check Points)
- 8.5.3 并發控制
- 8.5.4 重複資料的一緻性問題
- 最後
前言
以下内容源自計算機作業系統（第四版）
關于作業系統，
CSDN有很多的優秀部落格。
在這裡，
本文摘取其他部落格内容，
并附上相關連結，
如有侵權，
聯系删除，
僅供學習交流使用
第八章 磁盤存儲器的管理
8.1 外存的組織方式
檔案的實體結構直接與外存的組織方式有關。對于不同的外存組織方式，将形成不同的檔案實體結構。目前常用的外存組織方式有：
1）連續組織方式。
2）連結組織方式.
3）索引組織方式。
8.1.1 連續組織方式
為每個檔案配置設定一組連續的相鄰實體塊, 形成的檔案結構稱順序檔案結構, 實體檔案稱順序檔案。這種配置設定方式保證了記錄的邏輯順序, 與占用盤塊的實體順序一緻; 在目錄項的"檔案實體位址"字段中存放該檔案的第一個記錄所在盤塊号和檔案長度(塊數)。如:
連續配置設定的優缺點
優點: 順序存取簡單容易, 也支援直接(随機)存取。
順序存取速度快, 尋道次數和尋道時間最少。
也适合随機通路, 計算出盤塊位址直接通路。
缺點: 易産生外部碎片, 降低外存空間的使用率; 可利
用緊湊法将外部碎片拼接成連續存儲空間, 但緊湊
一次需要進行大量的磁盤操作花費大量的時間。
不利于檔案的插入和删除。
必須事先知道檔案的大小, 對于動态增長的檔案效果較差。需要估算預留的連續外存空間, 預留白間不足将引起大片磁盤空間的移動, 預留白間太大将使大量的外存空間長期空閑。 8.1.2 連結組織方式
将檔案存放在多個離散的盤塊中, 同一檔案的盤塊連結成一個連結清單, 消除外部碎片, 顯著的提高了外存空間的使用率, 有利于檔案插入和删除, 有利于檔案的動态擴充。
1. 隐式連結
在檔案目錄的每個目錄項中,都含有指向連結檔案第一個盤塊和最後一個盤塊的指針,
而在每個盤塊中都含有指向下一個盤塊的指針,隻有508位元組供使用。
缺點: 隻适合順序通路, 随機通路要從頭查找極低效。
可靠性差, 盤塊的指針出現問題會導緻鍊斷開。
更多的尋道次數和尋道時間。
解決方法:
可将幾個盤塊組成一個簇, 減少查找指定塊的時間。
2. 顯式連結
将連結檔案各實體塊的指針存放在記憶體的一張連結表中, 整個磁盤僅設一張表稱為檔案配置設定表(FAT), 表項的序号是實體盤塊号, 每個表項中存放連結指針(下一盤塊号)。每個檔案的第一個盤塊号填入該檔案的檔案控制塊(FCB)的"實體位址"字段中。記錄的查找過程全部在記憶體中進行, 檢索速度快、通路磁盤磁盤次數少、可靠性高。
8.1.3 FAT技術
8.1.4 NTFS的檔案組織方式
8.1.5 索引組織方式
連結配置設定存在的問題：
要順序查找許多盤塊号, 不支援高效的直接存取。
FAT占用較大的記憶體空間。
1. 單級索引配置設定
為每個檔案配置設定一個集中存放的索引塊(表), 該表實質就是磁盤塊位址數組,其中第i項存放指向檔案的第i塊盤塊号, 該檔案的目錄項中存儲了指向該索引塊的指針;支援直接存取, 如:記錄号m 第i塊 盤塊号
2. 多級索引配置設定
對于大檔案, 當配置設定的盤塊号已裝滿一個索引塊時, 必須另配置設定索引塊, 各索引塊通過指針連結起來,檔案太大索引塊太多時, 檢索索引塊将是低效的, 此時應為這些索引塊再建立一級索引, 形成了兩級索引, 必要時還可建立更多級的索引配置設定方式。
3. 混合(增量式)索引配置設定方式
索引配置設定方式的索引塊花費較多空間,小檔案索引塊使用率更低。UNIX用混合索引模式避免此缺點。每個檔案的索引結點含13個位址項 i.addr(0)~ i.addr(12), 每項4個位元組; 前10項存放直接位址(實體塊号), 若檔案大于40kB，則用i.addr(10)指向單級索引塊進行一次間接尋址,該塊中最多可放1k個實體塊号,檔案可長達4MB; 還可用 i.addr(11) 和 i.addr(12) 作為二次和三次間接尋址, 檔案最大長度分别可達4GB和4TB。
對比三種配置設定的優缺點
連續配置設定
優點:順序存取簡單高效,尋道距離次數少,通路速度快, 也适合随機通路,算出塊位址直接通路。
缺點: 有外部碎片,外存使用率低,插入和删除不容易
連結配置設定
優點: 消除外存碎片, 外存使用率高, 有利于檔案的動态擴充, 容易插入和删除,
缺點:不适合随機通路,可靠性差,尋道次數多速度慢
顯式連結配置設定可顯著減少尋道次數,提高檢索速度, 但FAT占用了較大的記憶體空間
索引配置設定
優點: 連結配置設定的全部優點, 還适合随機通路,尋道次數少, 檢索速度快。
缺點: 索引塊費較多空間,小檔案尤甚,混合索引可避免
8.2 檔案存儲空間的管理
為了實作前面任何一種檔案組織方式，都需要為檔案配置設定盤塊，是以必須知道磁盤上哪些盤塊是可用于配置設定的。故在檔案配置設定磁盤時，除了需要檔案配置設定表外，系統還應為可配置設定存儲空間設定相應的資料結構，即設定一個磁盤配置設定表，用于記住可供配置設定的存儲空間情況。此外，還應提供對盤塊進行配置設定和回收的手段。不論哪種配置設定和回收方式，存儲空間的基本配置設定機關都是磁盤塊而非位元組。
8.2.1 空閑表法和空閑連結清單法
1. 空閑表法
1）空閑表。
空閑表法屬于連續配置設定方式，它與記憶體的動态配置設定方式雷同。
即系統也為外存上的所有空閑區建立一張空閑表，每個空閑區對應于一個空閑表項，其中包括表項序号、該空閑區的第一個盤塊号、該區的空閑盤塊數等資訊。再将所有空閑區按其起始盤塊号遞增的次序排列。
2）存儲空間的配置設定與回收。
空閑盤區的配置設定與記憶體的動态配置設定類似，同樣是采用首次适應算法、循環首次适應算法等。
系統在對使用者所釋放的存儲空間進行回收時，也采取類似于記憶體回收的方法，即要考慮回收區是否與空閑表中插入點的前區和後區相鄰接，對相鄰接者應予以合并。
應該說明，在記憶體配置設定上，雖然很少采用連續配置設定方式，然而在外存的管理中，由于這種配置設定方式具有較高的配置設定速度，可減少通路磁盤的 I/O 頻率，故它在諸多配置設定方式中仍占有一席之地。例如，在前面所介紹的對換方式中，對對換空間一般都采用連續配置設定方式。對于檔案系統，當檔案較小(1～4 個盤塊)時，仍采用連續配置設定方式，為檔案配置設定相鄰接的幾個盤塊；當檔案較大時，便采用離散配置設定方式。另外，對于多媒體檔案，為了能減少磁頭的尋道時間，也采用連續配置設定方式。
2. 空閑連結清單法
1）空閑盤塊鍊。
這是将磁盤上的所有空閑空間，以盤塊為機關拉成一條鍊。當使用者因建立檔案而請求配置設定存儲空間時，系統從鍊首開始，依次摘下适當數目的空閑盤塊配置設定給使用者。當使用者因删除檔案而釋放存儲空間時，系統将回收的盤塊依次插入空閑盤塊鍊的末
尾。
2）空閑盤區鍊。
這是将磁盤上的所有空閑盤區(每個盤區可包含若幹個盤塊)拉成一條鍊。在每個盤區上除含有用于訓示下一個空閑盤區的指針外，還應有能指明本盤區大小(盤塊數)的資訊。配置設定盤區的方法與記憶體的動态分區配置設定類似，通常采用首次适應算法。在回收盤區時，同樣也要将回收區與相鄰接的空閑盤區相合并。
位示圖法
8.2.2 位示圖
1. 位示圖
位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況。當其值為“0”時，表示對應的盤塊空閑；為“1”時，表示已配置設定。這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。通常可用 m × n 個位數來構成位示圖，并使 m × n 等于磁盤的總塊數。位示圖也可描述為一個二維數組 map[m, n]。
2. 盤塊的配置設定
根據位示圖進行盤塊配置設定時，可分三步進行：
1）順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑時)。
2）将所找到的一個或一組二進制位轉換成與之相應的盤塊号。假定找到的其值為“0”的二進制位位于位示圖的第 i 行、第 j 列，則其相應的盤塊号應按下式計算：
b = n * (i - 1) + j；
式中，n 代表每行的位數。
3）修改位示圖，令 map[i,j] = 1。
3. 盤塊的回收
盤塊的回收分兩步：
1）将回收盤塊的盤塊号轉換成位示圖中的行号 i 和列号 j 。轉換公式為：
i = (b - 1) / n + 1；
j = (b - 1) % n + 1；
2）修改位示圖。令 map[i,j] = 0。
位示圖常用于微型機和小型機中。
8.2.3 成組連結法
空閑表法和空閑連結清單法都不适用于大型檔案系統，因為這會使空閑表或空閑連結清單太長。在 UNIX 系統中采用的是成組連結法，這是将上述兩種方法相結合而形成的一種空閑盤塊管理方法，它兼備了上述兩種方法的優點而克服了兩種方法均有的表太長的缺點。
8.3 提高磁盤I/O速度的途徑
其中最主要的技術便是磁盤高速緩存。
8.3.1 磁盤高速緩存(Disk Cache)
磁盤高速緩存的形式
(1) 專用: 在記憶體中單獨開辟一塊固定的區域專用。
(2) 共享: 所有空閑記憶體為緩沖池與請求分頁系統共享
1. 資料傳遞方式
(1) 資料傳遞
(2) 指針傳遞
2. 置換算法
常用的算法有:最近最久未使用算法LRU, 最近未使用算法NRU和最少使用算法LFU。
許多系統除了考慮最近最久未使用這一原則外還要考慮：通路頻率、可預見性、資料的一緻性。
3. 周期性地寫回磁盤
根據LRU算法,經常通路的盤塊可能長期不被回寫,可能導緻丢失資料, 可采用周期性(幾十秒)地寫回磁盤。
8.3.2 提高磁盤I/O速度的其他方法
1. 提前讀
預先将下一盤塊資料一次讀入減少讀盤次數。
2. 延遲寫
考慮緩沖區的資料不久之後可能還會通路故暫時不寫入磁盤, 将它挂在空閑隊列的末尾, 當它最久未被通路，到了隊列之首要被淘汰時再寫入磁盤。
3. 優化實體塊的分布
配置設定實體塊時, 把有可能順序存取的塊放在一起, 盡量分布在同一柱面或相鄰柱面上, 進而減少磁盤臂的移動次數。但采用線性連結清單來組織空閑塊時比較困難, 此時, 将同一磁道的若幹個盤塊組織成一簇, 以簇為機關進行配置設定, 可減少磁頭的平均移動距離。
4. 虛拟盤
利用記憶體空間區仿真磁盤,又稱RAM盤; 斷電或關機後虛拟盤的資料将丢失, 是以虛拟盤僅放臨時資料。與磁盤高速緩存的差別在于：内容由使用者控制，而不是OS控制。
8.3.3 磁盤備援陣列
1. 并行交叉存取
為提高對磁盤的通路速度, 用N台磁盤驅動器組成磁盤陣列, 系統将資料分為若幹個子盤塊資料分别存儲到各個磁盤的相同位置上,并行傳輸到記憶體,由于采用了并行存取方式加快了通路速度N-1倍。
2. 廉價磁盤備援陣列(Redundant Array of Inexpensive Disk)
為提高磁盤存儲資料的可靠性,采用備援存儲; 如: N=7, 6個盤做資料盤,1個盤做奇偶校驗盤, 校驗盤存儲6個資料盤的奇偶校驗值; 當某個盤損壞時可以用其它6個盤的資料盤恢複資料; RAID 有 0-7級, 其中 0 級無備援, 1 級是鏡像存儲備援50%, 3 級使用專用校驗盤, 5 級将校驗值螺旋分布在陣列的所有磁盤上。
3. RAID的優點
可靠性高、磁盤的通路速度高、性能/價格比高。
8.4 提高磁盤可靠性的技術
容錯技術是通過在系統中設定備援部件的辦法，來提高系統可靠性的一種技術。
磁盤容錯技術往往也被人們稱為系統容錯技術 SFT。可把它分成三個級别：第一級(SFT-I)是低級磁盤容錯技術；第二級(SFT-II)是中級磁盤容錯技術；第三級是系統容錯技術，它基于叢集技術實作容錯。
8.4.1. 第一級 磁盤容錯技術SFT-1
防止因磁盤表面缺陷造成的資料破壞或丢失, 包括雙份目錄、雙份檔案配置設定表和寫後讀校驗等措施
(1)雙份目錄和雙份檔案配置設定表
(2)熱修複重定向和寫後讀校驗
熱修複重定向:将磁盤的2~3%作為熱修複重定向區
寫後讀校驗:寫盤後立即讀并與原資料校驗
8.4.2. 第二級 磁盤容錯技術SFT-2
(1) 磁盤鏡像
兩個磁盤驅動器互為備份
(2)磁盤雙工
通道、磁盤控制器和磁盤驅動都為雙份
廉價磁盤備援陣列(RAID):第5章已介紹塊
交錯校驗
8.4.3 基于叢集技術的容器功能
8.4.4 後背習題
8.5 資料一緻性控制
同一資料存放在不同的檔案中, 對它修改時應對不同的檔案都統一修改, 才能保證資料的一緻性。修改時資料的流向是, 磁盤塊記憶體寫回磁盤塊。若在寫回之前, 系統崩潰, 則檔案系統資料出現不一緻。
系統應配置保證資料一緻性的軟體和相應的硬體，硬體采取備援技術配置一個高度可靠的存儲系統, 稱為穩定存儲器; 目前廣泛采用磁盤雙工方式來實作穩定存儲器。設計保證資料一緻性的實用程式, 當系統再次啟動時, 運作該程式, 檢查磁盤塊和目錄系統。
8.5.1 事務
1. 事務的定義
事務是用于通路和修改資料的一個程式機關, 由一系列相關的讀寫操作組成; 被通路的資料可以分散在不同位置, 隻有一系列讀寫操作全部完成才能以托付操作(Commit Operation)終止操作; 而隻要有一個操作失敗就執行夭折操作(Abort Operation)。
為了保證資料的一緻性, 對于夭折事務所操作過的資料必須恢複原來的狀态, 使該事務退回(rolled back),保證一個事務對一批資料修改操作,要麼全部完成要麼 一個也不修改, 這種特性稱事務的原子性。
2. 事務記錄(Transaction Record)
為了實作事務的原子修改, 用事務記錄這種資料結構來實作, 它被存放在穩定存儲器中, 用來存儲事務運作時資料項修改的全部資訊, 故又稱為運作記錄(Log), 該記錄包括下列字段:
事務名
資料項名
舊值
新值
3. 恢複算法
如果系統發生故障,應對以前的事務進行清理, 通過查找事務記錄表做如下操作：
(1) 如果在Log表中隻有(Ti開始)記錄無(Ti托付)記錄則調用undo(Ti ) 把所有被Ti修改過的資料恢複為原值。
(2)如果在Log表中既有(Ti開始)記錄又有(Ti托付)記錄則調用redo(Ti ) 把已被Ti修改過的資料設定為新值。
8.5.2 檢查點(Check Points)
1. 檢查點的作用
引入檢查點的主要目的，是為了對事務記錄的清理工作經常化, 設定檢查點記錄; 每隔一定的時間做一次清理:
将記憶體中的目前事務記錄表的所有記錄, 和所有已修改的資料, 輸出到穩定存儲器中; 再将檢查點記錄輸出到穩定存儲器中; 每當出現一個檢查點記錄便執行恢複操作。
2. 新的恢複算法
發生故障後,恢複算法隻需對最後一個檢查點之後的事務記錄進行處理。
即從最後一個檢查點之後的第一個事務記錄開始,對所有的事務Tk , 在Log表中出現(Tk托付)記錄則執行redo(Tk ), 未出現(Tk托付)記錄則執行undo(Tk )。
8.5.3 并發控制
由于事務具有的原子性, 使得一個事務執行完後才允許另一事務執行, 即事務對資料項的修改是互斥的,事務的這種特性稱為順序性,将實作順序性的技術稱為并發控制。可以用互斥信号量來保證事務處理的順序性,但用的最廣的是“鎖”。
1. 利用互斥鎖實作順序性
設定一種用于實作互斥的鎖, 簡稱互斥鎖,為每一個共享對象設一把互斥鎖, 如果事務 Ti 需要對一批對象進行通路,則為了保證事務操作的原子性, 應先獲得這批對象的互斥鎖, 将他們全部鎖住, 如果成功便可以對這批對象執行讀寫操作,然後全部開鎖, 若某對象已被其它事務鎖住, 則Ti 要将已鎖住的對象全部開鎖。
2. 利用互斥鎖和共享鎖實作順序性
對于共享檔案,寫隻能互斥進行, 但讀操作卻允許多個事務同時去讀, 顯然用互斥鎖不能實作同時讀, 為此引入另一種鎖共享鎖。互斥鎖僅允許一個事務對相應的對象執行讀或寫, 共享鎖則允許多個事務對相應的對象執行讀操作, 同時不允許任何一個事務對相應的對象執行寫操作。類似于讀者寫者問題。
8.5.4 重複資料的一緻性問題
1.重複檔案的一緻性
以UNIX類型的檔案系統為例,通常一個檔案的目錄項由一個檔案名和一個索引結點号組成; 當有重複檔案時, 一個檔案的目錄項由一個檔案名和若幹個索引結點号組成。保證重複檔案的一緻性用兩種方法：
(1) 當一個檔案被修改後,可查目錄, 從各i結點找到各拷貝的實體位置, 對這些拷貝做同樣修改。
(2) 為新修改的檔案建立幾個新拷貝取代原來的拷貝。
2. 盤塊号一緻性的檢查
兩張表，每塊對應一個表中的計數器，初值為0
表一：記錄了每塊在空閑塊表中出現的次數