作業系統之檔案管理（下）

二、檔案操作的實作

這裡主要是以

UNIX

作業系統為例。

2.1 檔案操作的實作

• 建立檔案

  建立系統與檔案的聯系，實質是建立檔案的

  FCB

*   在目錄中為新檔案建立一個目錄項（在`UNIX`中還需要`i`節點），根據提供的參數及需要填寫相關内容      

• • 配置設定必要的存儲空間

• 打開檔案

  根據檔案名目錄中檢索，并将該檔案的目錄項讀入記憶體，建立相應的資料結構，為後續的檔案操作做好準備。打開檔案後一般會傳回一個值，這個值一般叫檔案描述符或檔案句柄，之後的操作是通過檔案描述符來進行的。

2.2 檔案操作：建立檔案

create

（檔案名，通路權限）

• 1、檢查參數的合法性

  例如：檔案名是否符合命名規則；有無重名檔案，合法則進行下一步，否則報錯傳回。

• 2、申請空閑目錄項，并填寫相關内容

• 3、為檔案申請磁盤塊
• 4、傳回

2.3 檔案操作：打開檔案

為檔案讀寫做準備：給出檔案路徑名，獲得檔案句柄（file handler）或檔案描述符（file descripter），需将該檔案的目錄項讀到記憶體fd = open（檔案路徑名，打開方式）

1、根據檔案路徑名查目錄，找到目錄項（或i節點号）

2、根據檔案号查系統打開檔案表，看檔案是否已被打開，如果是，則共享計數加一，否則，将目錄項（或i節點）等資訊填入系統打開檔案表空表項，共享計數置為一。

3、根據打開方式、共享說明和使用者身份檢查通路合法性

4、在使用者打開檔案表中擷取一空表項，填寫打開方式等，并指向系統打開檔案表對應表項，傳回資訊：fd（檔案描述符，是一個非負整數，用于以後讀寫檔案）

2.4 檔案操作：指針定位

seek

（

fd

， 新指針位置）：系統為每個程序打開的每個檔案維護一個讀寫指針，即相對于檔案開頭的偏移位址（讀寫指針指向每次檔案讀寫的開始位置 ，在每次讀寫完成後，讀寫指針按照讀寫的資料量自動後移相應的數值）

• 1、由

  fd

  查使用者打開檔案表，找到對應的表項
• 2、将使用者打開檔案表中檔案讀寫指針位置設為新指針的位置，供後繼讀寫指令存取該指針處檔案内容。

2.5 檔案操作：讀檔案

read（檔案描述符，讀指針，要讀的長度，記憶體目的位址）

1、根據打開檔案時得到的檔案描述符，找到相應的檔案控制塊（目錄項），确定讀操作的合法性，讀操作合法則進行下一步，否則出錯處理。

2、将檔案的邏輯塊号轉換為實體塊号。根據參數中的讀指針、長度與檔案控制塊中的資訊，确定塊号、塊數、塊内位移

3、申請緩沖區

4、啟動磁盤I/O操作，把磁盤塊中的資訊讀入緩沖區，再送到指定的記憶體區（多次讀盤）

5、反複執行3、4直至讀出所需數量的資料或讀至檔案尾

三、檔案系統的管理

3.1 檔案系統的可靠性

可靠性：抵禦和預防各種實體性破壞和人為性破壞的能力

• 塊壞問題

• 備份

  通過轉儲操作，形成檔案或檔案系統的多個副本。

3.2 檔案系統備份

• 全量轉儲

  定期将所有檔案拷貝到後援存儲器

• 增量轉儲

  隻轉儲修改過的檔案，即兩次備份之間的修改。減少系統開銷。

• 實體轉儲

  從磁盤第零塊開始，将所有磁盤塊按序輸出到錄音帶

• 邏輯轉儲

  從一個或幾個指定目錄開始，遞歸地轉儲子給定日期後所有更改的檔案和目錄

3.3 檔案系統一緻性

• 問題的産生：

  磁盤塊–>記憶體–>寫回磁盤塊

  若在寫回之前，系統崩潰，則檔案系統出現不一緻

• 解決方案

  設計一個使用程式，當系統再次啟動時，運作該程式，檢查磁盤塊和目錄系統

3.4 磁盤塊的一緻性檢查

**說明：：**一緻性檢查時，檢查所有的檔案和空閑塊，檢查完之後可能會出現四種結果。第一種是一個一緻性的結果，即某個磁盤塊要麼配置設定給了某個檔案，要麼在空閑塊中。第二種結果是在空閑塊中找不到，但是也沒有配置設定給某個檔案，于是我們通過在空閑塊表中将磁塊标記為一來解決。第三種結果是某個磁盤塊在空閑塊表中出現了兩次，同樣是不合理的，對這一位進行修改。最後一種結果是在兩個檔案中出現，這種情況較為複雜，我們應該在空閑塊中找一個，然後将其中一個磁盤塊内容拷貝到這個空閑塊中，然後将使用塊表中的這一位減一。

3.5 檔案系統的寫入政策

對某些檔案做出了修改，那麼什麼時候将修改後的内容寫入到檔案中。這裡需要考慮檔案系統一緻性和速度。下面有幾種寫入政策

通寫（write-through）

記憶體中的修改立即寫到磁盤。缺點是速度性能差，如FAT檔案系統。

延遲寫（lazy-write）

利用回寫（write back）緩存的方法得到高速。其缺點就是可恢複性較差，可能會導緻資訊丢失

可恢複寫（tansaction log）

采用事務日志來實作檔案系統的寫入，既考慮安全性，又考慮速度性能，如NTFS

四、檔案系統的安全性

這裡我們讨論如何確定未經授權的使用者不能存取某些檔案？

4.1 檔案保護機制

• 用于提供安全性、特定的作業系統機制
• 對擁有權限的使用者，應該讓其進行相應的操作，否則，應禁止
• 防止其他使用者冒充對檔案進行操作
• 于是在實作的時候需要考慮使用者身份驗證和通路控制。對于使用者身份我們可以采用比如密碼、密碼等方式。

4.2 檔案的通路控制

有不同的通路控制手段，比如主動控制（使用通路控制表）和能力表（使用權限表）。

• 主動控制

  每個檔案一個

  記錄使用者

  ID

  和通路權限

• 使用者可以是一組使用者

  檔案可以是一組檔案

• 能力表

  每個使用者一個

  記錄檔案名及通路權限

4.3 UNIX的檔案通路控制

采用檔案的二級存取控制，審查使用者的身份、審查操作的合法性

第一級：對通路者身份的識别

對使用者分類：

*   檔案主（`owner`）      

• • 檔案主的同組使用者（

    group

    ）
  • 其他使用者（

    other

• 第二級：對操作權限的識别

  對操作分類：

*   讀操作（`r`）      

• • 寫操作（

    w

  • 執行操作（

    x

  • 不能執行任何操作（

    -

五、檔案系統的性能

5.1 檔案系統的性能問題

• 磁盤服務：速度成為系統性能的主要瓶頸之一。是以，在設計檔案系統時應盡可能減少磁盤通路次數

• 提高檔案系統性能的方法：

  目錄項（

  FCB

  ）分解、目前目錄、磁盤碎片整理、塊高速緩存、磁盤排程、提前讀取、合理配置設定磁盤空間、資訊的優化分布、

  RAID

  技術等等

5.2 提高檔案系統性能：塊高速緩存（BLOCK CACHE）

又稱為檔案緩存、磁盤高速緩存、緩沖區高速緩存。是指在記憶體中為磁盤塊設定的一個緩沖區，儲存了磁盤中某些塊的副本。當對檔案系統進行操作的時候：

檢查所有的讀請求，看所需塊是否在塊高速緩沖中

如果在，則可直接進行讀操作；否則，先将資料塊讀入塊高速緩存，再拷貝到所需的地方。

由于通路的局部性原理，當一資料塊被讀入塊高速緩存以滿足一個I/O請求時，和可能将來還會再次通路到這一資料塊。

5.3 如何實作塊高速緩存

• 塊高速緩存的組織方式

• 

• **說明：**在塊高速緩存中有若幹個資料塊，首先将這些塊使用一個雙向連結清單組織起來，當要通路這個鍊的時候就将其從此鍊中拿出來，然後挂接到鍊尾，而我們對于某個檔案使用的塊要檢查其是否在高速緩存中，是以這裡又使用塊号進行散列以提高檢查速度。

塊高速緩存的置換問題（修改LRU）

因為此緩存的空間肯定是不會很大的，是以當其滿時我們需要對其進行置換。對于以後可能會再次使用的塊我們将其放在鍊尾，而對于使用機率很小的塊可能就需要将其剔除。

塊高速緩存的寫入政策

在檔案系統中，我們需要考慮該塊是否會影響檔案系統的一緻性。這裡如前面所講，不同的作業系統采用了不同的一緻性解決方案。

提前讀取

*   思路：每次通路磁盤，多讀入一些磁盤塊      

• • 依據：程式執行的空間局部性原理
  • 開銷：較小（隻有資料傳輸時間）
  • 具有針對性

5.4 Windows的檔案通路方式

一般有下面三種方式：

不使用檔案緩存

*   普通方式      

• • 通過

    Windows

    提供的

    FlushFileBuffer

    函數實作

• 使用檔案緩存（塊高速緩存）

*   預讀取。每次讀取的塊大小、緩沖區大小、置換方式      

• • 寫回。寫回時機選擇、一緻性問題

• 異步模式

*   不再等待磁盤操作的完成。      

• • 使處理器和

    I/O

    并發工作

使用者對磁盤的通路通過通路檔案緩存來實作：

• 由

  Windows

  的

  Cache Manager

  實作對緩存的控制

*   讀取資料的時候預取      

• • 在

    Cache

    滿時，根據

    LRU

    原則清除緩存的内容
  • 定期更新磁盤内容使其與

    Cache

    一緻（每秒）

• write-back

  機制

*   在使用者要對磁盤寫資料時，隻更改`Cache`中的内容，由`Cache Manager`決定何時将更新反映到磁盤      

5.5 提高檔案系統性能：合理配置設定磁盤空間

配置設定磁盤塊時，把有可能順序存取的塊放在一起（盡量配置設定在同一柱面上，進而減少磁盤臂的移動次數和距離）

**說明：**我們讀取檔案系統時，每次都要先找到i節點區，然後再去找到檔案位置，如果i節點區在最外道，而相關檔案在最裡道，則在讀取的時候磁臂就需要不斷的移動，這樣顯示效率低下。一種解決方案如(a)，我們将i節點區和相關檔案放在距離較近的磁道上；另一種是如(b)，首先将磁道分成了若幹組，然後将i節點區也劃分成若幹部分，每一組磁道都有一個i節點區，而每個檔案都和其i節點區在同一組，這樣磁臂也不需要很大的移動。

5.6 提高檔案系統性能：磁盤排程(重點)

當有多個訪盤請求等待時，采用一定的政策，對這些請求的服務順序調整安排，進而降低平均磁盤服務時間，達到公平、高效的目的。

• 公平
• 一個IO請求在有限時間内滿足

• 高效

  減少裝置機械運動帶來的時間開銷

一次訪盤時間 = 尋道時間 + 旋轉延遲時間 + 傳輸時間

• 減少尋道時間
• 減少延遲時間

5.7 磁盤排程算法(重點)

例子：假設磁盤通路序列：

98、183、37、122、14、124、65、67

，這些數字表示柱面号或磁道号。讀寫頭起始位置為

53

。請計算磁頭服務序列和磁頭移動總距離（道數）。下面使用幾種算法進行計算：

• 1、先來先服務（

  FCFS

• 按通路請求到達的先後次序服務

*   優點：簡單、公平      

• 缺點：效率不高，相鄰兩次請求可能會造成最内到最外的柱面尋道，使磁頭反複移動，增加了服務時間，對機械也不利。

• 

• 磁道服務序列和通路序列一緻，磁頭移動總距離為640，平均80。

2、最短尋道時間優先（Shortest Seek Time First）(重點)

用于磁盤

優先選擇距目前磁頭最近的通路請求進行服務，主要考慮尋道優先。

優點

改善了磁盤平均服務時間

缺點

造成某些通路請求長期等待而得不到服務

3、掃描算法（

SCAN

電梯算法）(重點)

當裝置無通路請求時，磁頭不動；當有通路請求時，磁頭按一個方向移動，在移動過程中遇到的通路請求進行服務，然後判斷該方向上是否有通路請求，如果有則繼續掃描；否則改變移動方向，并為經過的通路請求服務，如此反複。其實是一種對距離和方向的折中算法。

4、單向掃描算法（

C-SCAN

這是對掃描算法的一種改進。

*   總是從零号柱面開始向裡掃描      

按柱面（磁道）位置選擇通路者

移動臂到達最後一個柱面後，立即帶動讀寫磁頭快速傳回到零号柱面

傳回時不為任何的等待通路者服務

傳回後可再次進行掃描

主要的目的是減少了新請求的最大延遲。

5、N-step-SCAN政策

把磁道請求隊列分成長度為N的子隊列，每一次用SCAN處理一個子隊列

在處理某一個隊列時，新請求添加到其他子隊列中

如果最後剩下請求數小于N，則它們全部都将在下一次掃描時處理

N值比較大時，其性能接近SCAN；當N = 1時，即FIFO

主要是為了解決磁頭臂的粘性問題。

6、FSCAN政策

使用兩個子隊列

掃描開始時，所有請求都在一個隊列中，而另一個隊列為空

掃描過程中，所有新到的請求都放入另一個隊列中

對新請求的服務延遲到處理完所有老請求之後

主要是為了解決磁頭臂的粘性問題。本算法及以上都是對磁臂移動的優化算法。

7、旋轉排程算法

根據延遲時間來決定執行次序的排程。一般有三種情況：

若幹等待通路請求通路同一磁頭上的不同扇區

若幹等待通路請求通路不同磁頭上的不同扇區

若幹等待通路請求通路不同磁頭上的相同扇區

• • 解決方案：

• • • 對于前兩種情況：總是讓首先到達讀寫磁頭位置下的扇區先進行傳送操作

• • 對于第三種情況：這些扇區同時到達讀寫磁頭位置下，可任意選擇一個讀寫磁頭進行傳送操作

5.8 提高檔案系統性能：資訊優化分布

記錄在磁道上的排列方式也會影響輸入輸出操作的時間。

**說明：**如果資訊是按左邊那樣分布的，那麼如果首先讀到1号記錄，然後花5ms處理，但是此時磁盤已經轉到了4号記錄，于是如果我們要處理2号記錄，則必須将4、5、6、7、8都旋轉過去之後才能處理2号記錄；而如果資訊是按右邊那樣分布的，當處理完1号記錄，而此時磁盤也剛好旋轉到了2号記錄處，這樣就能極大的提高檔案系統的性能。

5.9 提高檔案系統性能：記錄的成組與分解

• 記錄的成組

  把若幹個邏輯記錄合成一組存放在一塊的工作

• 進行成組操作時必須使用記憶體緩沖區，緩沖區的長度等于邏輯記錄長度乘以成組的塊因子（成組的長度）。
• 成組的目的：提高了存儲空間的使用率；減少了啟動外設的次數，提高系統的工作效率。

• 記錄的分解

  從一組邏輯記錄中把一個邏輯記錄分離出來

典型的例子就是目錄檔案的存儲。

5.10 提高檔案系統性能：RAID技術

起始就是獨立磁盤備援陣列（Redundant Arrays of Independent Disks），就是将多塊磁盤按照一定要求構成一個獨立的儲存設備。目的就是提高可靠性和性能。在實作時，需要考慮存儲系統的速度、容量、容錯、資料災難發生後的資料恢複。

資料是如何組織的

*   通過把多個磁盤組織在一起，作為一個邏輯卷提供磁盤跨越功能      

• 通過把資料分成多個資料塊，并行寫入/讀出多個磁盤，以提高資料傳輸率（資料分條

  stripe

• 通過鏡像或校驗操作，提供容錯能力（備援資訊的儲存）
• 最簡單的組織方式是鏡像，最複雜的是塊交錯校驗。
• 例1：

  RAID 0

  - 條帶化

*   資料分布在陣列的所有磁盤上      

• 有資料請求時，同時多個磁盤并行操作
• 充分利用總線寬帶，資料吞吐率提高，驅動器負載均衡

• 

• 這種方式沒有備援資訊儲存，即無差錯控制，性能是最佳的。

• 例2：

  RAID 1

  -鏡像

*   最大限度保證資料安全和可恢複性      

• • 所有資料同時存在與兩塊磁盤的相同位置
  • 磁盤使用率為50%

  • 

  • 9

資料的安全性是最好的，但是磁盤使用率較低。      

• 例3：

  RAID 4

  -交錯塊奇偶校驗

*   帶奇偶校驗      

• • 以資料塊為機關

  • 

  • 資料儲存在前四塊盤上，而校驗資訊儲存在第五塊盤上。