第二十七天 Implementing File-System(檔案系統實作)--上

我們先來說說File-System Structure(檔案系統結構)：

檔案的結構是邏輯儲存unit或是相關資料的集合，而檔案系統是存放在secondary storage (硬碟)。檔案系統的組織方式是用layer的方式，會有一個file control block 儲存架構，包含檔案所有資訊。以下是檔案存取的步驟：

1. 應用程式：process發出read需求並提供路徑
2. 邏輯檔案系統：檢查儲存權限
3. 檔案組織模組：將logical address轉換成physical address
4. 基本檔案系統：讀取physical address 要求
5. I/O控制：實際的I/O控制
6. 裝置：從儲存裝置讀取資料

以下是file control block 的典型結構：

下面有兩張圖，第一張是開啟檔案時，第二張是讀取檔案時在記憶體內的作法：


Virtual File System(VFS，虛擬檔案系統)：
VFS提供object-oriented 方法去實行檔案系統，可以讓同樣的system call介面(API)用在不同型態的檔案系統。API是VFS的介面，並不是任何特別型態的檔案系統。以下是例圖：

Directory Implementation(目錄實作)：
常用的方法有兩種：

• Linear List(線性串列)：
  將檔案名稱串起來，再用pointer指到data block。這個方法實作上很容易，但需要消化時間去執行。
• Hash Table(雜湊表格)：
  用hash data架構串列起來，這個方法是犧牲空間換取時間，空間大的系統可以使用。他能減少目錄搜尋時間，且有固定的大小，但可能發生碰撞問題，因為hash後可能會有相同的位置。

檔案在硬碟內block的配置方式有以下幾種：

• Contiguous allocation(連續配置)：
  在硬碟內每個檔案佔據了一組連續的block，這是一個簡單的方式，只需要起始位置(block#)跟block長度，可以隨機存取，但會浪費空間(動態存取位置問題)，而且檔案不可以增大，以下有例圖：
  Q跟R分別代表logical address/512(硬碟內最大容量)的商和餘數
  而存取block的位置為Q+起始位置
  block內的位置為R
  
  
  而有一個以他為基礎改版的系統，Extent-Based system，將單位從block變成一個範圍(一個連續的block)。

• Linked allocation(串列式配置)：
  每個file是disk block的linked list，block可能散佈在disk上任何地方。這種方式只需要起始位置，可以自由分配空間，但就沒有辦法隨機存取，以下為例圖：
  Q跟R分別代表logical address/511(硬碟內最大容量-1，因為有指定起始位置)的商和餘數
  而存取block的位置為Q
  block內的位置為R+1
  
  
  他會有一個File-Allocation Table(檔案配置表格)，用MS-DOS和OS/2分配disk空間。
  

• Indexed allocation(索引式配置)：
  
  將所有的指標都放入index block內，所以這個方法需要一個index table，而且可以隨機存取，不會浪費空間，但卻增加了index block的空間，以下是無長度限制的file例圖:
  Q1是index table內哪個block
  Q2是index table中block位置
  R2是block內file的位置
  
  下面這張圖是雙層式索引，他就有一個outer-index table跟一個index table：
  Q1是outer-index table放置位置
  Q2是index table中block位置
  R2是block內file的位置