作業系統 第十二章 檔案系統實作

第十二章 檔案系統實作 檔案系統架構 檔案存取 開啟檔案表 共享檔案 可用空間管理 檔案配置方法 檔案目錄實作 x 檔案系統評估 摘要

檔案系統架構 檔案系統的目的 存取效率上的考量 磁碟主要可分為磁盤與讀寫頭兩大部分 為使用者或是作業系統本身提供大量的資料儲存空間。 在主記憶體與磁碟之間的資料傳輸都是以區塊（block） 作為存取的基本單位。 大部分的檔案系統都會將數個區塊集合成一個磁簇（cluster），並以磁簇為單位進行檔案資料的存取。 磁碟主要可分為磁盤與讀寫頭兩大部分 磁盤中的磁軌是用來儲存資料。 讀寫頭是用來在磁盤上讀取或是寫入資料。

檔案存取 應用程式 邏輯檔案系統 檔案組織模組 基本檔案系統 I/O控制 裝置 行程發出讀取檔案的需求，並提供檔案路徑 測試使用者對於檔案存取要求的權限 將邏輯檔案的路徑值轉換為磁碟機的實體區塊位置 對磁碟機進行讀取實體區塊的要求 進行實際的 I/O 控制 從儲存裝置中實際讀出資料

開啟檔案表 檔案系統要進行檔案存取的動作 Linux 系列的作業系統 到目錄結構中搜尋指定的檔案 開啟並記錄在一個開啟檔案表（Open File Table）中 Linux 系列的作業系統 每個被開啟的檔案會有一個相對應的檔案描述器（file descriptor） Windows 中有類似檔案描述器的功能 檔案處理器（file handler）

開啟檔案表(續) 當資料有所更改時 開啟檔案表相關資訊 先在此開啟檔案表中進行修改，待檔案被正常關閉之後，才會將這些資訊寫入磁碟中。 檔案名稱、存取權限、存取日期以及檔案指標等 索引 檔案名稱 存取權限 存取日期 其他資訊 檔案指標 main.c RWX　R - -　 - - - 2001/12/1 … 1 mail.txt RWX　RW - R- - 2002/1/23 2 a.out RWX　RWX　RWX 2002/4/10 n

共享檔案 共享檔案 一個檔案可能會被鏈結在兩個以上的目錄。 如圖目錄 D 同時被目錄 A 及 B 所鏈結。 分割／根目錄 A B C G D E F

共享檔案(續) 任一個鏈結到此共享檔案的目錄中將此檔案刪除時，不會將此共享檔案真正地從磁碟實體區塊中刪除，而只是將此計數減 1 。 當計數等於 0，才將共享檔案刪除。 A C 擁有者: A 計　數: 1 B 計　數: 2 擁有者: B

第十二章 檔案系統實作 檔案系統架構 可用空間管理 鏈結串列 位元向量 計數 檔案配置方法 檔案目錄實作 檔案系統評估 摘要

可用空間管理 可用空間（free space）管理機制 常用方法 位元向量(bit vector) 讓應用程式在新增檔案時，可以從未被使用的空間中找到足夠的空間來存放資料。 常用方法 鏈結串列（linked list） 位元向量(bit vector) 計數（counting)

鏈結串列 將所有的可用空間利用指標串連起來。 使用一個開頭指標指向此可用空間鏈結串列的第一個區塊。 可用空間指標 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 27 25 28 29 30 31 32 33 34

鏈結串列(續) 主要缺點 常用解決方法 若以磁簇為資料存取單位 搜尋效率不佳必須循序地讀取才能得到所有可用空間的區塊資訊。 犧牲第一個區塊的磁碟空間，將其他所有可用空間的實體位置以索引的方式儲存在此區塊中，以加速可用空間的搜尋。 若以磁簇為資料存取單位 可降低額外的紀錄空間(儲存指標)。 可提高存取的速度。

位元向量 每個區塊都是一個獨立的單位，並以一個位元來記錄該區塊是否為可用空間。 若一個磁碟中的第 1、2、4、6、10、11、12、19、23、24、25 個區塊屬於可用空間，其可用空間的位元向量可表示為： 0010101110001111110111000……… 若以磁簇為基本存取單位，則可節省更多額外的紀錄空間。

計數 可用空間表中的主要紀錄只包含了磁碟位置和計數值。 如圖，從第 2 個區塊開始，有連續 6 個可用空間區塊。 索引 起始值 計數 1 2 如圖，從第 2 個區塊開始，有連續 6 個可用空間區塊。 00 01 02 03 04 索引 起始值 計數 1 2 6 12 3 17 4 27 5 30 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

計數(續) 可用空間所在的位置過於分散，也就是外部斷裂（external fragmentation）的情形較嚴重時，這種可用空間的記錄方式反而會比較浪費空間。

第十二章 檔案系統實作 檔案系統架構 可用空間管理 檔案配置方法 連續式配置 鏈結串列式配置 索引式配置 檔案目錄實作 檔案系統評估 摘要

檔案配置方法 檔案配置時，必須考慮的重點 常用的三種磁碟空間的配置方法 磁碟空間的有效利用 檔案能否被快速地存取 連續式配置 （contiguous allocation） 鏈結串列式配置（linked list allocation） 索引式配置（indexed allocation）

連續式配置 搜尋適合可用空間有下列幾種常用的方法： 最先適合（first fit） 最佳適合（best fit） 最差適合（worst fit） 01 02 00 03 04 06 07 05 08 09 11 12 10 13 14 16 17 15 18 19 21 22 20 23 24 26 27 25 28 29 31 32 30 33 34 tree address 檔案名稱 30 2 8 3 記數 list 起始值 17

連續式配置(續) 連續式配置的主要問題 搜尋可用空間的問題 磁碟空間的浪費問題 外部斷裂 內部斷裂 利用鏈結串列式配置可以解決問題

鏈結串列式配置 如下圖所示，檔案開頭在第 5 個區塊 第 5 個區塊指向第 6 個區塊 直到第 27 個區塊為止 檔案名稱 起始值 結束值 note 5 27 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

鏈結串列式配置(續) 優點 缺點 不會有外部斷裂問題 建立新檔案時並不需同時就宣告檔案的大小 檔案只能循序存取 可靠度的問題 若某個檔案的一個指標被破壞，整個檔案就無法再被存取 可利用雙向鏈結串列（double linked list）來解決

索引式配置 解決鏈結串列式配置的無法隨機存取的問題 所有的區塊指標都集中起來存儲存在一個固定的索引區塊（indexed block）中(編號24) -1 代表整個檔案結束的符號 04 06 27 32 07 -1 檔案 索引區塊 ABC 24 目錄 01 02 00 03 05 08 09 11 12 10 13 14 16 17 15 18 19 21 22 20 23 26 25 28 29 31 30 33 34

索引式配置(續) 適度地控制索引區塊的大小，有下列幾種方法 鏈結索引 多層索引 組合索引 (如圖) 資料 索引 直接存取 單層索引 雙層索引

第十二章 檔案系統實作 檔案系統架構 可用空間管理 檔案配置方法 檔案目錄實作 x 線性串列 雜湊表格 檔案系統評估 摘要

第十二章 檔案系統實作 檔案系統架構 可用空間管理 檔案配置方法 檔案目錄實作 檔案系統評估 性能 效率 可靠性 一致性 摘要

性能 增進整體檔案系統的性能 利用快取記憶體，可減少磁碟讀寫頭的移動 虛擬磁碟（virtual disk） 將一些可以快速存取的記憶體充當磁碟使用 讓部分檔案存取速度可以像在快取記憶體中存取資料一樣快 記憶體磁碟 程式執行區 … 檔案開啟表 分頁緩衝區 磁碟機 CPU 磁軌緩衝區

效率 不同的磁碟空間配置方法各有其優缺點。如： 對整個檔案與目錄的結構作深入的分析，並採用其中最適合的方法來實作。 將日期資訊直接儲存在檔案所屬目錄的鏈結表格中 效率較差 將日期資訊與檔案本身存放在一起 缺點是在搜尋同一個目錄中的所有檔案時，可能要存取多個其他區塊中的日期資訊，也會造成效率上的低落。 對整個檔案與目錄的結構作深入的分析，並採用其中最適合的方法來實作。

可靠性 備份（backup） 還原（restore） 差異備份（differential backup） 將檔案系統中的所有資料複製一份，並存放在其他的儲存媒體中 還原（restore） 將備份中資料存回原來的檔案系統中 差異備份（differential backup） 執行過第一次的完整備份之後，之後就只需要將差異的那一部分儲存起來。 缺點 任何一次的差異性備份有所損壞或是遺失時，就無法還原成完整的檔案系統。

一致性 要確認檔案系統的一致性 正確的區塊檢查結果表 檢查檔案配置以及可用空間的區塊記錄 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 使用中區塊 1 未使用區塊 1

一致性（續） 錯誤的區塊檢查結果表（重複指派與未指派） 錯誤的區塊檢查結果表（重複的區塊指派） 編號７被可用空間重複計算 使用中區塊 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 使用中區塊 1 未使用區塊 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 使用中區塊 1 2 未使用區塊 1 2

摘要（１） 檔案系統的實作 對檔案進行讀寫 實際存取流程 可用空間的管理 檔案資料的區塊配置 檔案目錄實作 檔案系統評估的介紹 從目錄結構中搜尋並開啟該檔案 每個行程都會有一個開啟檔案表來儲存這些開啟檔案的紀錄

摘要(2) 可用空間 記錄可用空間的方法有 磁碟配置方法 磁碟中沒有被用來記錄檔案資料的磁碟區塊 鏈結串列 位元向量 計數 連續式配置 鏈結串列式配置 索引式配置

摘要(3) 目錄結構較常使用的方法 線性串列 雜湊表格 評估一個檔案系統必須考慮 性能 效率 可靠性 一致性