iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 27
1
自我挑戰組

OS作業系統學習系列 第 27

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

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

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

檔案的結構是邏輯儲存unit或是相關資料的集合,而檔案系統是存放在secondary storage (硬碟)。檔案系統的組織方式是用layer的方式,會有一個file control block 儲存架構,包含檔案所有資訊。以下是檔案存取的步驟:
https://ithelp.ithome.com.tw/upload/images/20181111/20112132o6w1EY6oVp.png

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

以下是file control block 的典型結構:
https://ithelp.ithome.com.tw/upload/images/20181111/20112132VY8aiIsx9I.png
下面有兩張圖,第一張是開啟檔案時,第二張是讀取檔案時在記憶體內的作法:
https://ithelp.ithome.com.tw/upload/images/20181111/20112132oIrhsnAK0q.png
https://ithelp.ithome.com.tw/upload/images/20181111/20112132tDYKm4NTLF.png
Virtual File System(VFS,虛擬檔案系統):
VFS提供object-oriented 方法去實行檔案系統,可以讓同樣的system call介面(API)用在不同型態的檔案系統。API是VFS的介面,並不是任何特別型態的檔案系統。以下是例圖:
https://ithelp.ithome.com.tw/upload/images/20181111/20112132RbfQtXkHCw.png
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
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132KuxGO5i01O.png
    https://ithelp.ithome.com.tw/upload/images/20181111/201121329gi5f0LwKy.png
    而有一個以他為基礎改版的系統,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
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132rvdCP11KC3.png
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132ULiWHEsTrw.png
    他會有一個File-Allocation Table(檔案配置表格),用MS-DOS和OS/2分配disk空間。
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132dOchPVz8P7.png

  • Indexed allocation(索引式配置):
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132YgvOACU7Ai.png
    將所有的指標都放入index block內,所以這個方法需要一個index table,而且可以隨機存取,不會浪費空間,但卻增加了index block的空間,以下是無長度限制的file例圖:
    Q1是index table內哪個block
    Q2是index table中block位置
    R2是block內file的位置
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132xIBFMHHvKT.png
    下面這張圖是雙層式索引,他就有一個outer-index table跟一個index table:
    Q1是outer-index table放置位置
    Q2是index table中block位置
    R2是block內file的位置
    https://ithelp.ithome.com.tw/upload/images/20181111/20112132cjQSTcPsta.png
    https://ithelp.ithome.com.tw/upload/images/20181111/201121322IqidaOXU5.png


上一篇
第二十六天 File System(檔案系統)--下
下一篇
第二十八天 Implementing File-System(檔案系統實作)--下
系列文
OS作業系統學習30

尚未有邦友留言

立即登入留言