文件系統(tǒng)基礎[王道操作系統(tǒng)知識備份]

• 文件的概念

  • 文件是以計算機硬盤為載體的存儲在計算機上的信息的集合。系統(tǒng)運行時計算機以進程為基本單位進行資源調度，用戶進行輸入輸出時，以文件為基本單位

  • 數據項：用于描述一個對象某種屬性的一個值。包括基本數據項和組合數據項

  • 記錄：記錄一組相關數據項的集合

  • 文件：由創(chuàng)建者所定義的一組相關信息的集合。包括有結構文件和無結構文件

• 文件屬性

  • 名稱、標識符、類型、位置、大小、保護、時間日期用戶標識

• 文件基本操作

  • 創(chuàng)建文件、寫文件、讀文件、文件重定位（文件尋址，按某條件搜索返回文件位置）、刪除文件、截斷文件

• 文件打開與關閉

  • 許多文件操作都涉及為給定文件搜索相關目錄條目，許多文件系統(tǒng)要求首次使用文件時，文件被顯式的打開，即使用系統(tǒng)調用open將文件的屬性復制到內存的打開文件表的一個表目中（open返回指向打開文件表表目的指針）。操作系統(tǒng)一般維護一個打開文件表，用戶需要一個文件時從打開文件表的索引指定文件，文件不在使用則將此條目從打開文件表刪除。

  • 通常，系統(tǒng)打開文件表的某一項文件時，還會打開一個文件計數器，記錄多少個進程打開了該文件。當計數為0時，刪除該條目

  • 每個打開文件都關聯(lián)一些信息：

    • 文件指針

    • 文件打開計數

    • 文件磁盤位置

    • 訪問權限

• 文件邏輯結構

  • 無結構文件

    • 流式文件，以字節(jié)為單位，將數據按順序記錄并積累保存

  • 有結構文件

    • 順序文件：文件記錄一個接一個的順序排列，記錄一般定長，可順序存儲或鏈表方式存儲

    • 索引文件：
      image

    • 索引順序文件：
      image

    • 散列文件（直接文件）：通過散列函數鍵值直接決定記錄的物理位置

• 目錄結構

  • 文件控制塊FCB
    類比PCB進程控制塊

    • 文件控制塊FCB是存放控制文件需要的各種信息的數據結構。FCB的有序集合稱為文件目錄，FCB就是文件目錄項。

    • FCB主要包含基本信息（文件名、物理位置、邏輯結構、物理結構），存取控制信息，實用信息（建立時間、修改時間）

  • 索引節(jié)點
    注意I結點存放的是文件描述信息，目錄項中存放文件名和指向I結點的指針

    • 在檢索文件過程中，只用找到文件名，然后取出對應的物理地址即可。也就是說檢索目錄時，只需要將文件名加載到內存，其他信息不需要。因此UNIX采用文件名和其他信息分開的方法，文件描述信息單獨形成一個索引節(jié)點，稱為I結點。文件目錄中的目錄項是包含文件名和指向I結點的指針。

    • 一個FCB大小64B，盤塊大小1KB，一個盤塊可存放16個FCB（FCB必須連續(xù)存放）。在UNIX中，一個目錄項只有16B，其中14B是文件名，2B是i結點指針。1KB可存放64個文件目錄項

    • UNIX系統(tǒng)的索引結點包含：文件主標識符、文件類型、文件存取權限、文件物理地址、文件長度、文件鏈接計數、文件存取時間

    • 文件被打開時，磁盤索引結點復制到內存中，在內存中索引結點加了以下內容：索引結點編號（用于標識索引結點）、狀態(tài)、訪問計數、邏輯設備號、鏈接指針

  • 目錄結構

    • 單級、
      image

    • 兩級、
      image

    • 多級、
      image

    • 無環(huán)圖
      image
      • 便于實現文件共享

• 文件共享

  • 基于索引節(jié)點的共享（硬鏈接）
    image
    • 基于索引結點的共享，在索引結點中有一個鏈接計數count，用于記錄鏈接到本索引結點的用戶目錄項數目。當count為0時才刪除該文件

  • 基于符號鏈實現的共享（軟鏈接）
    符號鏈是一個文件，這個文件內容就是被鏈接文件的路徑

    • 為使用戶B可共享A的文件F，創(chuàng)建一個LINK類文件，也取名為F，并將F寫入B的文件目錄中。這個新文件只包含被鏈接文件F的路徑名，這種方式被稱為符號鏈接。

    • 符號鏈有一個優(yōu)點是網絡共享時，只需要知道該文件主機網絡地址和主機內的絕對地址。

• 文件保護

  • 可加控制的訪問類型：讀、寫、執(zhí)行、添加、刪除、列表清單，（重命名、復制、編輯）

  • 訪問控制

    • 基于身份的訪問控制

      • 為每個文件和目錄增加一個訪問控制表，規(guī)定每個用戶名及其可被允許的訪問類型

      • 精簡的訪問列表包括擁有者（創(chuàng)建文件），組（共享文件且具有類似訪問的用戶），其他（系統(tǒng)內其他用戶）

    • 口令

      • 用戶在創(chuàng)建文件時提供一個口令，在創(chuàng)建FCB時附上相應口令。用戶請求時必須提供口令

      • 時間空間開銷少，但是口令直接存儲在系統(tǒng)內部不安全

    • 密碼

      • 對文件進行加密，被訪問時需要使用密碼

文件系統(tǒng)實現

• 文件系統(tǒng)層次結構

  • 用戶調用接口

    • 文件系統(tǒng)為用戶提供與文件及目錄有關的調用，如新建、打開、讀寫、關閉、刪除文件、建立或刪除目錄

    • 此層由若干個程序模塊組成，每個模塊對應一個系統(tǒng)調用，用戶發(fā)出系統(tǒng)調用，控制即轉入相應模塊

  • 文件目錄系統(tǒng)

    • 主要功能是管理文件目錄。（管理活躍文件目錄表、讀寫狀態(tài)信息表、管理進程的打開文件表、管理與組織存儲設備上的文件目錄結構、調用下一級存取控制模塊）

  • 存取控制驗證模塊

    • 實現文件保護，把用戶訪問要求與FCB中指示的訪問控制權限進行比較

  • 邏輯文件系統(tǒng)與文件信息緩沖區(qū)

    • 根據文件的邏輯結構將用戶讀寫的邏輯記錄轉換稱文件邏輯結構內對應的塊號

  • 物理文件系統(tǒng)

    • 把邏輯記錄轉換為實際物理地址

  • 輔助分配模塊

    • 管理輔存空間

  • 設備管理程序模塊

    • 分配設備、分配設備讀寫用緩沖區(qū)，磁盤調度、啟動設備、處理設備中斷、設法設備讀寫緩沖區(qū)、釋放設備

• 目錄實現
  目錄實現是為了查找文件，線性表對那個現象查找，哈希表對應散列查找

  • 線性列表

    • 最簡單的目錄實現方式是使用存儲文件名和數據塊指針的線性表。使用鏈表可減少刪除文件的時間，實現簡單但是比較費時

  • 哈希表

    • 根據文件名得到一個值，并返回一個指向線性列表中元素的指針。優(yōu)點查找迅速，插入刪除頁比較簡單。

• 文件實現
  文件實現其實是研究文件的物理結構，即文件數據在物理存儲設備上如何分布。包含兩方面，一是文件的分配方式，即對磁盤非空閑塊管理，二是文件存儲空間管理，即對磁盤空閑塊管理

  • 文件分配方式
    image

    指如何為文件分配磁盤塊

    • 連續(xù)分配

      • 每個文件占用磁盤上一組連續(xù)的塊，這種方式作業(yè)訪問磁盤需要尋道數和尋道時間最小

      • 支持順序訪問和直接訪問，優(yōu)點實現簡單，存取速度快，缺點文件長度無法動態(tài)增加。反復增刪文件后會出現外部碎片

    • 鏈接分配

      • 采取離散分配方式，消除了外部碎片，顯著提高磁盤利用率，可動態(tài)增加文件大小

      • 鏈接分配又可分為隱式鏈接和顯式鏈接

        • 隱式鏈接，每個文件對應一個磁盤塊鏈表，每個磁盤塊存有指向下一個塊的指針，目錄項存儲第一塊指針和最后一塊指針。創(chuàng)建文件時，目錄增加一個目錄項，指針初始化為NULL，大小為0。隱式鏈接缺點無法直接訪問盤塊，且盤塊指針也會消耗存儲空間。

        • 顯式鏈接，指的是將指向文件物理塊的指針，從每個塊末尾提取出來存放到一個鏈接表中，這個表稱為文件分配表（FAT表），每個表項存放對應塊的下一塊鏈接指針。文件分配表不僅記錄了文件各塊之間的先后順序，也可標記出空閑的磁盤塊。（空閑磁盤塊在文件存取表中對應下一塊指針為-2）

    • 索引分配

      • 索引分配將文件的所有盤塊號集中放到一起構成索引表（塊）。每個文件都有其索引塊，索引塊是一個數組，數目的條目是磁盤塊地址數組。索引塊第i個條目指向文件的第i個塊。目錄項條目存儲索引塊的地址。

      • 索引塊支持直接訪問，且沒有外部碎片，缺點是因為索引塊，增加了系統(tǒng)存儲空間開銷

      • 索引分配為了支持大文件，可使用鏈接索引塊方式、多層索引、混合索引的方式

  • 文件存儲空間管理

    • 文件存儲空間劃分與初始化

      • 一個文件存儲于文件卷中，這個卷可以是物理盤的一部分、也可以是整個物理盤。

      • 文件卷中，文件區(qū)和目錄區(qū)是分開的。

      • 邏輯卷在提供服務前需要劃分好目錄區(qū)和文件區(qū)，建立空閑分區(qū)管理表格及存放邏輯卷信息的超級塊

    • 文件存儲器空間管理
      文件存儲設備管理實際是對空閑塊的組織和管理

      • 空閑表

        • 空閑表法屬于連續(xù)分配方法，與內存的動態(tài)分區(qū)方法類似。

        • 系統(tǒng)為外存所有空閑區(qū)建立一張空閑盤塊表，每個空閑區(qū)對應一個空閑表項，包括表項序號、空閑區(qū)第一個盤塊號、盤塊數。然后將空閑區(qū)按照起始盤塊號遞增排列。

        • 空閑盤區(qū)分配，與內存動態(tài)分配類似，使用首次適應算法、循環(huán)首次適應算法等

      • 空閑鏈表

        • 空閑鏈表包括空閑盤塊鏈和空閑盤區(qū)鏈

        • 空閑盤塊鏈是將磁盤空閑的空閑空間以盤塊為單位拉成一條鏈。用戶請求分配空間時，從鏈首開始摘下適當數目盤塊。

        • 空閑盤區(qū)鏈是將空閑盤區(qū)拉成一條鏈，每個盤區(qū)上應有指明本盤區(qū)大小的信息。分配盤曲方法和空閑表類似。（首次適應、循環(huán)首次適應）

      • 位示圖

        • 位示圖利用二進制的一個位標識磁盤對應塊的使用情況。值為0時表示空閑，值為1時表示已分配。

      • 成組鏈接法
        空閑表和空閑鏈表不適用與大型文件系統(tǒng)，UNIX采用成組鏈接法

        • 把順序的n個空閑扇區(qū)地址保存到第一個空閑扇區(qū)內，其后一個空閑扇區(qū)保存另一組順序空閑扇區(qū)地址，如此繼續(xù)，直到所有空閑扇區(qū)均予以鏈接。

        • 系統(tǒng)只需要保存一個指向第一個空閑扇區(qū)的指針。

        • 表示文件存儲器空閑空間的位向量表或第一個成組鏈塊，以及卷中的目錄區(qū)、文件區(qū)劃分信息都需要放到輔存儲器中，一般放在卷頭位置，在UNIX系統(tǒng)中稱為超級塊。在對卷中文件操作時，超級塊需要預先讀入系統(tǒng)空閑的主存。

磁盤組織與管理

• 磁盤結構
  image

  • 磁盤是由表面涂有磁性物質的金屬或塑料構成的圓形盤片，通過一個成為磁頭的導體線圈讀取數據

  • 存儲數據的同心圓稱為磁道，磁道與磁頭一樣寬，一個磁道被分為幾百個扇區(qū)，每個扇區(qū)固定大小。相鄰磁道之間通過一定間隙分隔開。

  • 磁盤存儲能力受限于最內道的最大記錄密度

  • 磁盤可分為固定頭自盤，活動頭磁盤，固定盤磁盤，可換盤磁盤

• 磁盤調度算法

  • 磁盤時間

    • 尋找時間

      • 活動頭磁盤讀取信息前，將磁頭移動到指定位置，這個時間包括跨越n個磁道的時間和啟動磁臂的時間。T_n = m \times n + s

    • 延遲時間

      • 磁頭定位到某一磁道的扇區(qū)所需時間，對于轉速r的磁盤T_r = \frac {1} {2r} ，

    • 傳輸時間

      • 從磁盤讀出或向磁盤寫入數據的時間，取決于每次讀取的字節(jié)數和磁盤轉速。T_t = \frac b {rN}

    • 總平均時間 T_a = T_s + \frac 1 {2r} + \frac b {rN}

  • 磁盤調度算法
    image

    • 先來先服務（FCFS）算法
      image
      • 若有大量進程競爭使用磁盤，算法在性能上接近隨機調度（較差）

    • 最短尋找時間優(yōu)先（SSTF）算法
      image
      • 性能優(yōu)于FCFS，但是會產生饑餓現象

    • 掃描算法（SCAN，電梯調度算法）

      • 在當前移動方向上選擇與當前磁頭所在磁道最近的作為下一次服務的對象

      • SCAN對最近掃描過的區(qū)域不公平，在局部性方面不如FCFS和SSTF。

    • 循環(huán)掃描算法（C-SCAN）

      • 在掃描算法基礎上規(guī)定磁頭單向移動，回返時直接快速移動至起始端，從而避免，SCAN算法總是偏向于處理接近最里或最外的磁道的訪問請求。

      • 實際上采用SCAN（C-SCAN），磁頭總是嚴格的遵循從盤面一端到另一端，顯然這是可以改進的。如LOOC調度，磁頭只需要移動到最遠端的一個請求即可返回

  • 磁盤管理

    • 磁盤初始化

      • 低級初始化：磁盤能存儲數據前，劃分為扇區(qū)以便磁盤控制器可以讀和寫。低級初始化為磁盤每個扇區(qū)采用特別的數據結構，每個扇區(qū)由頭、數據區(qū)域（512B），尾部組成

      • 操作系統(tǒng)將自身數據結構記錄在磁盤：第一步將磁盤分為一個或多個柱面組成的分區(qū)（C盤、D盤），第二部進行邏輯格式化，也就是初始化文件系統(tǒng)

    • 引導塊

      • 計算機啟動時需要運行一個初始化程序（自舉程序），初始化CPU、寄存器等

      • 自舉程序保存在ROM中，為避免改變自舉代碼需要改變ROM硬件的問題，因此ROM中只保留很小的自舉裝入程序，完整的功能（自舉程序）保存在磁盤啟動塊中。啟動塊位于磁盤固定位置，擁有啟動分區(qū)的磁盤稱為啟動磁盤或系統(tǒng)磁盤

    • 壞塊

      • 簡單磁盤處理壞塊，壞扇區(qū)會在FAT表（文件分配表）中標明，程序不會使用

      • 復雜的磁盤，其控制器維護一個磁盤壞塊表。控制器可用備用塊來邏輯的替換壞塊，稱為扇區(qū)備用